Słownik teorio-mnogościowy

Tutaj jest lista podstawowych pojęć z Teorii Mnogości. Każdy student kierunku Informatyka na WPPT po pierwszym semestrze studiów pierwszego stopnia powinien znać wszystkie pojęcia i fakty które się tutaj znajdują.

Aksjomat Ekstensjonalności: Dwa zbiory są równe jeśli mają te same elementy.
Aksjomat Wyboru (AC): Każda rozbicie ma selektor, czyli taki zbiór, który z każdym elementem rozbicia ma dokładnie jeden element wspólny.
AC jest zdaniem niezależnym od pozostałych aksjomatów teorii mnogości. Równoważnymi postaciami AC są LKZ oraz WO.
Alef zero: Moc zbioru liczb naturalnych. Oznaczenie: $\aleph_0$
Antytautologia: Zdanie rachunku zdań fałszywe dla dowolnej waluacji. Inna nazwa - zdanie sprzeczne.
Zdanie jest sprzeczne wtedy i tylko wtedy, gdy jego negacja jest tautologią.
Arytmetyka kardynalna: $|A|+|B|$ = $|(A \times \{0\})$ + $(B \times \{1\})|$

$|A|\cdot |B| = |A \times B|$

$|A|^{|B|} = |A^B|$

$\aleph_0+\aleph_0 = 2 \cdot \aleph_0 = 3 \cdot \aleph_0 = \ldots = \aleph_0 \cdot \aleph_0 = \aleph_0^2= \aleph_0^3 = \ldots = \aleph_0$

$2^{\aleph_0}$ = $\mathfrak{c}^{\aleph_0}$ = $\mathfrak{c}$,

$\mathfrak{c}+\mathfrak{c} = 2 \cdot \mathfrak{c} = 3 \cdot \mathfrak{c} = \ldots = \aleph_0 \cdot \mathfrak{c} = \mathfrak{c} \cdot \mathfrak{c}$

$\mathfrak{c}^2 = \mathfrak{c}^3 = \ldots = \mathfrak{c}^{\aleph_0} = \mathfrak{c}$

$\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \ldots$
Bijekcja: Funkcja, która jest jednocześnie injekcją i surjekcją.
Złożenie bijekcji jest bijekcją. Fukcja odwrotna do bijekcji jest bijekcją.
Continuum: Moc zbioru liczb rzeczywistych. Oznaczenie: $\mathfrak{c}$.
$\mathfrak{c} = 2^{\aleph_0}$
Częściowy porządek: Para $(X,R)$ taka, że $R$ jest relacją zwrotną na $X$, przechodnią i słabo antysymnetryczną.
Obcięcie częściowego porządku do podzbioru jest również częściowym porządkiem. Relacja odwrotna do częściowego porządku jest częściowym porządkiem.
Dobry porządek: Taki liniowy porządek, że każdy jego niepusty podzbiór ma element najmniejszy.
Element maksymalny: Jeśli $(X,R)$ jest częściowym porządkiem, to element $a\in X$ jest $R$-maksymalny, jeśli $(\forall x\in X)(a R x \to x=a)$.
Dualne pojęcie: "element minimalny".
Element minimalny: Jeśli $(X,R)$ jest częściowym porządkiem, to element $a\in X$ jest $R$-minimalny, jeśli $(\forall x \in X)(x R a \to x=a)$.
Dualne pojęcie: "element maksymalny".
Element najmniejszy: Jeśli $(X,R)$ jest częściowym porządkiem, to element $a\in X$ jest $R$-najmniejszy, jeśli $(\forall x \in X)(a R x)$.
Dualne pojęcie: "element najwiekszy".
Element najwiekszy: Jeśli $(X,R)$ jest częściowym porządkiem, to element $a\in X$ jest $R$-najwiekszy, jeśli $(\forall x \in X)(x R a)$.
Dualne pojęcie: "element najmniejszy".
Funkcja: Zbiór $f$ jest funkcją, jeśli jest taką relacją, że $(\forall x,a,b)((x,a)\in f \land (x,b) \in f) \to a=b)$.
Hipoteza Continuum (CH): Zdanie: "jeśli $A \subseteq \mathbf{R}$ to $|A| =|\mathbf{R}|$ lub $|A| \le |\mathbf{N}|$"
Hipoteza Continuum jest niezależna od pozostałych aksjomatów teorii mnogości.
Iloczyn kartezjański: Iloczynem kartezjańskim zbiorów $A$ i $B$ nazywamy zbiór $A\times B$ złożony ze wszystkich par uporządkowanych $(a,b)$ takich, że $a \in A$ oraz $b \in B$.
Injekcja: Funkcja $f: X \to Y$ jest injekcją jeśli $f(x)=f(y) \to x=y$ dla dowolnych $x,y$.
Złożenie injekcji jest injekcją. Relacja odwrotna do funkcji f jest funkcją wtedy i tylko wtedy, gdy f jest injekcją.
Inkluzja: Zbiór A zawiera się w zbiorze B jeśli każdy element zbioru A należy do zbioru B.
Następujące zdania są równoważne:
$A \subseteq B$
$A \cup B = B$
$A \cap B = A$
Izomorfizm: Dwa częściowe porządki $(X,R)$ i $(Y,Q)$ są izomorficzne, jeśli istnieje bijekcja $f:X \to Y$ taka, że $$(\forall x,y \in X)((x R y) \equiv (f(x) Q f(y))~.$$
Klasa abstrakcji: Klasą abstrakcji elementu $a$ względem relacji równoważności $R$ nazywamy zbiór $[a]_R = \{x : a R x\}$.
Krata: Częściowy porządek $(X,R)$ w którym każdy niepusty skończony podzbiór ma kres górny oraz kres dolny.
Ważne przykłady krat: $P(X)$ z inkluzją; dodatnie liczby naturalne z podzielnością
Krata zupełna: Częściowy porządek (X,R) w którym każdy niepusty podzbiór ma kres górny oraz kres dolny.
Ważne przykłady krat: P(X) z inkluzją;
Lemat Kuratowskiego-Zorna (LKZ): Zdanie: w każdym częściowym porządku, który spełnia warunek "każdy łańcuch ma ograniczenie górne", istnieje element maksymalny.
LKZ jest równoważny Aksjomatowi Wyboru. LKZ jest naturalnym narzędziem do dowodzenia twierdzeń typu: każda przestrzeń liniowa ma bazę, w każdym pierścieniu z jednością istnieje ideał maksymalny.
Liczba algebraiczna: Liczba, która jest pierwiastkiem jakiegoś niezerowego wielomianu o współczynnikach wymiernych.
Zbiór liczb algebraicznych jest przeliczalny. Przykłady: $\sqrt{2}$, $\sqrt{2}+\sqrt{3}$.
Liczba przestępna: Liczba rzeczywista, która nie jest liczbą algebraiczną.
Liczby $e$ oraz $\pi$ są liczbami przestępnymi.
Liniowy porządek: Taki częściowy porządek $(X,R)$, że $(\forall x,y \in X)( (x R y) \lor (x=y) \lor (y R x))$.
Podstawowe przykłady: liczby naturalne, liczby całkowite, liczby rzeczywiste, liczby wymierne (z naturalnym porządkiem)
Modus ponens: Następująca reguła wnioskowania: $\{p, p \to q\} \models q$
Obraz zbioru przez relację: Obrazem zbioru $A$ przez relację $R$ nazywamy zbiór $R[A]$ złożony z wszystkich takich elementow $y$, że $(\exists x \in A)(xRy)$.
Para elementów: Parą elementów $x$ i $y$ jest zbiór $\{x,y\}$, którego jedynymi elementami są $x$ i $y$.
Zbiór $\{x\}$, równy $\{x,x\}$, nazywamy singletonem elementu $x$.
Para uporządkowana: Definicja Kuratowskiego: $(x,y) = \{\{x\},\{x,y\}\}$.
Jej podstawowa własność: $(a,b)=(c,d)$ wtedy i tylko wtedy, gdy $(a=c) \land (b=d)$
Prawa de Morgana: Kilka praw rachunku zdań, rachunku zbiorów, rachunku predykatów łączących własności spójników/operatorów dualnych:
$\neg(p \lor q) \equiv (\neg p \land \neg q)$, $\neg(p \land q) \equiv (\neg p \lor \neg q)$
$(A \cup B)^c = A^c \cap B^c$, $(A\cap B)^c = A^c \cup B^c$
$\neg (\exists x)\phi(x) \equiv (\forall x)(\neg \phi(x))$, $\neg (\forall x)\phi(x) \equiv (\exists x)(\neg \phi(x))$
Przechodniość: Relacja R jest przechodnia, jeśli $(\forall x,y,z)((x R y) \land (y R z) \to x R z)$.
Relacja R jest przechodnia wtedy i tylko wtedy, gdy $R\circ R \subseteq R$.
Punkt stały odwzorowania: Punktem stałym odwzorowania $f:X \to X$ nazywamy taki element $a \in X$, że $f(a) = a$.
Każda funkcja ciągła $f:[0,1] \to [0,1]$ ma punkt stały (łatwe). Każda funkcja ciągła $f:[0,1]^n \to [0,1]^n$ ma punkt stały (tw. Brouwera).
Relacja: Zbiór par uporządkowanych.
Relacja odwrotna: Relacją odwrotną do relacji $R$ nazywamy zbiór $R^{-1} = \{(x,y): (y,x) \in R\}$.
$(R^{-1})^{-1} = R$; $(R \circ S)^{-1} = S^{-1}\circ R^{-1}$
Relacja równoważności: Relacja zwrotna, symetryczna oraz przechodnia.
Relacja równoważności rozbija swoją dziedzinę na rozłączne klasy abstrakcji.
Rezolucja: Następująca reguła wnioskowania: $\{p \lor Q, \neg p \lor R\} \models Q \lor R$
Rodzina zbiorów: Zbiór, którego elementami są zbiory. W aksjomatycznych teoriach mnogości każdy zbiór jest rodziną zbiorów.
Rozbicie zbioru: Rozbiciem zbioru X nazywamy taką rodzinę podzbiorów zbioru X, że
jej suma jest równa zbiorowi X;

składa się ze zbiorów niepustych;

jej elementy są parami rozłączne.
Każda relacja równowazności generuje rozbicie swojej dziedziny. Każdemu rozbiciu odpowiada relacja równoważności, która ją generuje.
Równoliczność: Zbiory $A$ i $B$ są równoliczne ($|A|=|B|$), jeśli istnieje bijekcja między A i B.
Dla dowolnych zbiorów $A$, $B$ i $C$ mamy: $|A|=|A|$, $|A|=|B| \to |B|=|A|$, $|A|=|B| \land |B|=|C| \to |A|=|C|$.
Różnica symetryczna: Binarne działanie mnogościowe zdefinowane wzorem $(A\setminus B) \cup (B\setminus A)$.
Różnica symetryczna jest przemienna, łączna. Zbiór pusty jest elementem neutralnym. Elementem odwrotnym do A jest A.
Supremum: Najmniejsze ograniczenie górne zbioru.
W częściowym porządku $(\mathbf{N},|)$ mamy $\sup\{a,b\} = NWW(a,b)$.
Surjekcja: Funkcja $f: X \to Y$ jest surjekcją jeśli $rng(f) = Y$.
Złożenie surjekcji jest surjekcją.
Symbol Newtona: ${n \choose k}$ = liczba $k$-elementowych podzbiorów zbioru $\{1,\ldots,n\}$
Podstawowe własności:
${n \choose k} = \frac{n!}{k! \cdot (n-k)!}$;
${n \choose k} = {n \choose n-k}$; ${n \choose 0}={n \choose n}=1$;
${n+1\choose k+1} = {n \choose k+1} + {n\choose k}$;
${n+1\choose k+1} = \frac{n+1}{k+1} \cdot {n \choose k}$.
Symetria: Relacja R jest symetryczna, jeśli $(\forall x,y)(x R y \to y R x)$.
Relacja R jest symetryczna wtedy i tylko wtedy, gdy $R^{-1} = R$.
Słaba antysymetria: Relacja R jest słabo antysymetryczna, jeśli $(\forall x,y\in X)((x R y \land y R x) \to x=y)$.
Tautologia: Zdanie rachunku zdań prawdziwe dla każdej waluacji.
Dokładniej: zdanie $\varphi$ jest tautologią, jeśli dla dowolnej waluacji $\pi$ mamy $\pi(\varphi)$ = TRUE.
Twierdzenie Cantora: $|A| \lt |P(A)|$.
Twierdzenie Cantora-Bernsteina: $(|A| \le |B| \land |B| \le |A|) \to |A|=|B|$.
Twierdzenie Kuratowskiego-Tarskiego: Jeśli $L$ jest kratą zupełną oraz $f:L \to L$ jest monotoniczne (czyli $x \le y \to f(x) \le f(y)$), to $f$ ma punkt stały.
Twierdzenie Russell'a: Nie istnieje zbiór wszystkich zbiorów.
Waluacja: Dowolne przyporządkowanie zmiennym zdaniowym wartości logicznych.
Wartości logiczne: W klasyczym rachunku zdań jest to zbiór {FALSE,TRUE}.
Zasada Dirichletta: Jeśli m, n są liczbami naturalnymi, $n < m$ oraz $f:\{1,...,m\} \to \{1,...,n\}$ to $f$ nie jest injekcją.
Jest to jedna z form Indukcji Matematycznej.
Zasada Indukcji Matematycznej: Następująca własność liczb naturalnych:
"jeśli A jest podzbiorem zbioru liczb naturalnych $\mathbf{N}$ takim, że $$0\in A \land (\forall n \in \mathbf{N})(n \in A \to n+1 \in A)~,$$ to $A = \mathbf{N}$"
Zasadę Indukcji Matematycznej łatwo można wyprowadzić z nastepujących dwóch własności liczb naturalnych:
$(\mathbf{N},\le)$ jest dobrym porządkiem

dla każdej liczby naturalnej $n$ różnej od $0$ istnieje liczba naturalna $m$ taka, że $n = m+1$.
Zasada dobrego uporządkowania (WO): Zdanie: "każdy zbiór można dobrze uporządkować".
Jest to jedna z form Aksjomatu Wyboru.
Zbiór mocy continuum: Zbiór równoliczny ze zbiorem liczb rzeczywistych.
Przykłady zbiorów mocy continnum: R, RxR, P(N), {0,1}^N, R^N, C(R,R)
Zbiór potęgowy: Zbiorem potęgowym zbioru $X$ nazywamy zbiór $P(X)$ wszystkich podzbiorów zbioru $X$.
$P(0) = \{0\}$; $P(P(0)) = \{0,\{0\}\}$; $|P(A)| = 2^{|A|}$
Zbiór przeliczalny: Zbiór $A$ jest przeliczalny jeśli jest pusty lub istnieje surjekcja z liczb naturalnych na zbiór $A$.
Przykłady zbiorów przeliczalnych: zbiory skończone, liczby naturalne, liczby wymierne, liczby algebraiczne, $\mathbf{N}\times\mathbf{N}$,
zbiór wszystkich ciągów skończonych elementów z ustalonego skończonego zbioru, zbiór wszystkich algorytmów, zbiór wszystkich funkcji obliczalnych.
Zbiór pusty: Zbiór, który nie ma żadnego elementu.
Z Aksjomatu Ekstensjonalności wynika, że istnieje dokładnie jeden zbiór pusty.
Zbiór skończony: Zbiór równoliczny ze zbiorem $\{0,...,n-1\}$ dla pewnej liczby naturalnej $n$.
Zwrotność: Relacja $R$ jest zwrotna na zbiorze $X$ jeśli $(\forall x \in X)((x,x)\in R)$.
Złożenie relacji: Złożeniem relacji $R$ i $S$ nazywamy relację $R \circ S$ taką, że dla wszystkich par $(x,z)$ mamy $$(x,z)\in R \circ S \equiv (\exists y)((x,y)\in S) \land (y,z)\in R))$$
Złożenie relacji jest łączne. Nie jest przemienne.