Katedra Podstaw Informatyki
Politechnika Wrocławska

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
    1. $|A|+|B|$ = $|(A \times \{0\})$ + $(B \times \{1\})|$
    2. $|A|\cdot |B| = |A \times B|$
    3. $|A|^{|B|} = |A^B|$
    1. $\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. $2^{\aleph_0}$ = $\mathfrak{c}^{\aleph_0}$ = $\mathfrak{c}$,
    3. $\mathfrak{c}+\mathfrak{c} = 2 \cdot \mathfrak{c} = 3 \cdot \mathfrak{c} = \ldots = \aleph_0 \cdot \mathfrak{c} = \mathfrak{c} \cdot \mathfrak{c}$
    4. $\mathfrak{c}^2 = \mathfrak{c}^3 = \ldots = \mathfrak{c}^{\aleph_0} = \mathfrak{c}$
    5. $\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:
  1. $A \subseteq B$
  2. $A \cup B = B$
  3. $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:
  1. $\neg(p \lor q) \equiv (\neg p \land \neg q)$, $\neg(p \land q) \equiv (\neg p \lor \neg q)$
  2. $(A \cup B)^c = A^c \cap B^c$, $(A\cap B)^c = A^c \cup B^c$
  3. $\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
  1. jej suma jest równa zbiorowi X;
  2. składa się ze zbiorów niepustych;
  3. 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:
  1. ${n \choose k} = \frac{n!}{k! \cdot (n-k)!}$;
  2. ${n \choose k} = {n \choose n-k}$; ${n \choose 0}={n \choose n}=1$;
  3. ${n+1\choose k+1} = {n \choose k+1} + {n\choose k}$;
  4. ${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:
  1. $(\mathbf{N},\le)$ jest dobrym porządkiem
  2. 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, RN, 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.