08.10.2021: Tautologie

1. Oznaczenie: $\phi \equiv \eta$ oznacza, że $\models (\phi \IFF \eta)$
2. Najważniejsze tautologie:
   1. prawo podwójnej negacji: $\neg\neg p \IFF p$
   2. prawa przemienności: $(p\lor q) \IFF (q\lor p)$, $(p\land q) \IFF (q\land p)$
   3. prawa łączności: $(p\lor q)\lor r \IFF p \lor (q \lor r)$, $(p\land q)\land r \IFF p \land (q \land r)$
   4. prawa de Morgana: $\neg (p\lor q) \IFF (\neg p \land \neg q)$, $\neg (p\land q) \IFF (\neg p \lor \neg q)$
   5. prawo eliminacji implikacji: $(p \to q) \IFF (\neg p \lor q)$
   6. prawo eliminacji równoważności: $(p\IFF q) \IFF ((p\to q) \land (q\to p))$
   7. Spójnik Pierce'a: $p | q \equiv \neg p \land \neg q$ i kreska Sheffera $p\uparrow q \equiv \neg p \lor \neg q$ - są to spójniki uniwersalne (za pomocą każdego z nich można zdefiniować dowolny inny spójnik logiczny).
   8. Spójnik XOR: $p \oplus q \equiv (p\land \neg q) \lor (\neg p \lor q)$.
      • $p \oplus \bot \equiv p$
      • $p \oplus \top \equiv \neg p$
      • $p \oplus p \equiv \bot$
      • $p \oplus (q \oplus r) \equiv (p\oplus q) \oplus r$ (łączność)
      • Wniosek: $(p \oplus k)\oplus k \equiv p$
        Tę własność można fajnie wykorzystać do kodowania informacji.

11.10.2021: Tautologie i reguły dowodzenia

1. Przykłady ważnych tautologii
   1. Sprzeczność implikuje wszystko: $\models (p\land \neg p) \to q$
   2. $\models (p\to q) \IFF (\neg q \to \neg p)$.
      Przykład zastosowania: jeśli $(x+y)/2>1$ to $x>1$ lub $y>1$
   3. $\models ((p\to q)\land (\neg p \to q))\to q$
      Przykład zastosowania: dowód tego, że $x\leq |x|$ dla dowolnego $x\in\RR$.
2. (Synteza formuł) Pokazaliśmy, że mając ustaloną tabelkę 0-1 możemy dobrać do niej formułę zbudowaną ze spójników $\land, \lor$ i $\neg$ o tej tabelce.
3. Odwrotna notacja polska
4. Reguły dowodzenia
   1. Def (Wnioskowanie) $\{\phi_1,\ldots,\phi_n\}\models \psi$ jeśli dla dowolnej waluacji $\pi$ takiej, że $val(\phi_1,\pi) = \ldots = val(\phi_n,\pi) = \mathbf{1}$ mamy również $\pi(\psi)=\mathbf{1}$.
   2. Twierdzenie. Następujące zdania są równoważne:
      1. $\{\phi_1,\ldots,\phi_n\}\models \psi$
      2. $\models (\phi_1\land\ldots\land\phi_n) \to \psi$
   3. Modus Ponens: $\{\phi, \phi\to\eta\}\models \eta$
   4. Rezolucja: $\{\phi\lor\alpha, \neg\phi\lor\beta\}\models \alpha \lor \beta$

15.10.2021: Zbiory - I

1. Aksjomat Ekstensjonalności (AE): zbiory A, B są równe wtedy i tylko wtedy, gdy dla dowolnego $x$ mamy $$(x \in A) \leftrightarrow (x \in B)~.$$
2. Tw. Istnieje dokładnie jeden zbiór pusty.
   Zbiór pusty oznaczamy symbolem $\emptyset$.
3. Def: Funkcja zdaniowa na zbiorze $A$: przyporządkowanie $\phi$ elementom zbioru $a \in A$ wartości logicznych $\phi(a)$.
4. Def. Operacja wyróżniania: $$ x \in\{a\in A: \phi(a)\} \IFF (x\in A \land \phi(x)) $$
5. Przykład: Jeśli $X=\NN$, $\phi(x) = "2|x"$, to $\{x\in\NN: \phi(x)\}$ jest zbiorem wszystkich liczb naturalnych parzystych.
6. Twierdzenie (Russell) Nie istnieje zbiór wszystkich zbiorów.
7. Def. Para nieuporządkowana: $x\in\{a,b\} \IFF (x=a \lor x=b)$
8. Def: (singleton elementu $a$) $\{a\} = \{a,a\}$
9. Przykład: Zbiory $\emptyset$, $\{\emptyset\}$, $\{\{\emptyset\}\}$, $\{\{\{\emptyset\}\}\}$, $\{\{\{\{\emptyset\}\}\}\}$,$\ldots$ są parami różne.
10. Def (suma): $(x\in A \cup B) \leftrightarrow ((x\in A) \lor (x\in B))$
11. Def (przekrój): $(x\in A \cap B) \leftrightarrow ((x\in A) \land (x\in B))$
12. Def (różnica): $(x\in A \setminus B) \leftrightarrow ((x\in A) \land (x\notin B))$
13. Def. $A\subseteq B$ jeśli dla dowolnego x mamy $(a\in A) \to (x \in B)$
14. Wniosek: AE $\equiv$ $((A=B) \IFF (A\subseteq B) \land (B\subseteq A))$
15. Def (zbiór potęgowy) $P(X)$ = zbiór wszystkich podzbiorów zbioru $X$
16. Przykład: $P(\emptyset) = \{\emptyset\}$
17. Obserwacja: $\{\emptyset,X\} \subseteq P(X)$

15.10.2021: Zbiory - I

1. Tw. $A \cup B = B \cup A$
2. Tw. $A \cap (B \cap C) = (A \cap B) \cap C$
3. Odpowiedniość między własnościami zbiorów a tautologiami
4. Tw. $(A\setminus B)\setminus C = A \setminus (B\cup C)$
5. Tw. Następujące zdania są równoważne:
   1. $A \subseteq B$
   2. $A \cap B = A$
   3. $A \cup B = B$
6. Def. Dopełnienie zbioru $A \subseteq \Omega$ do zbioru $\Omega$: $A^c = \Omega \setminus A$
7. Tw. (prawa de Morgana Rachunku Zbiorów) Dla dowolnych $A,B\subseteq\Omega$:
   1. $(A\cup B)^c = A^c \cap B^c$
   2. $(A\cap B)^c = A^c \cup B^c$
8. Składowe rodziny zbiorów

22.10.2021: Zbiory i kwantyfikatory

25.10.2021: Kwantyfikatory - I

1. Fakt: $(\forall x)(\phi(x)\land\psi(x)) \equiv ((\forall x)\phi(x))\land ((\forall x)\psi(x))$
2. Fakt: ($(\forall x)\phi(x)) \lor (\forall x)\psi(x)) \to ((\forall x)\phi(x)\lor \psi(x))$
3. Diagram funkcji zdaniowej $\phi:\Omega\times\Omega\to\{0,1\}$: $D_\phi=\{(x,y)\in\Omega:\phi(x,x)\}$
4. Def. $(\exists a\in A)\phi(x) \equiv (\exists x)(x\in A \land \phi(x))$
5. Def. $(\forall a\in A)\phi(x) \equiv (\forall x)(x\in A \to \phi(x))$
6. Tw. $\neg (\exists a\in A)\phi(x) \equiv (\forall x \in A)(\neg \phi(x))$
7. Tw. $\neg (\forall a\in A)\phi(x) \equiv (\exists x \in A)(\neg \phi(x))$
8. Def. Dla $\phi:\Omega\times\Omega \to \{0,1\}$ definiujemy
   1. $(\forall x)(\forall y)\phi(x,y) \equiv (\forall x)\left((\forall y)\phi_x(y)\right)$
   2. $(\exists x)(\exists y)\phi(x,y) \equiv (\exists x)\left((\exists y)\phi_x(y)\right)$
   3. $(\forall x)(\exists y)\phi(x,y) \equiv (\forall x)\left((\exists y)\phi_x(y)\right)$
   4. $(\exists x)(\forall y)\phi(x,y) \equiv (\exists x)\left((\exists y)\phi_x(y)\right)$
   gdzie $\phi_x(y) = \phi(x,y)$.

29.10.2021: Kwantyfikatory - II

1. Dla dowolnej formuły $\phi = \phi(x,y)$ zachodzą następujące zależności:
   

   $(\forall x)(\forall y)\phi$	$\to$	$(\exists x)(\forall y)\phi$	$\to$	$(\forall y)(\exists x)\phi$	$\to$	$(\exists x)(\exists y)\phi$
   $\updownarrow$						$\updownarrow$
   $(\forall y)(\forall x)\phi$	$\to$	$(\exists y)(\forall x)\phi$	$\to$	$(\forall y)(\exists x)\phi$	$\to$	$(\exists y)(\exists x)\phi$

2. Gra w zapałki (możemy brać 1 lub 2 zapałki):
   1. Istnieje strategia zwycięzka dla gracza I lub dla gracza II
   2. strategia zwycięzka - trzymaj się liczb podzielnych przez 3

5.11.2021: Kwantyfikatory i Relacje

1. Tw. Każda skończona dwuosobowa gra jest zdeterminowana
2. Suma uogólniona: $x\in \bigcup \mathcal{A} \equiv (\exists A\in\mathcal{A})(x\in A)$
3. Przekrój uogólniony: $x\in \bigcap \mathcal{A} \equiv (\forall A\in\mathcal{A})(x\in A)$
4. Przykład: $\bigcup\{A,B,C\} = A\cup B\cup C$, $\bigcap\{A,B,C\} = A\cap B\cap C$,
5. Def. Zbiór $X$ jest relacją, jeśli istnieje zbiór $X$ taki, że $R\subseteq X\times X$
6. Def (relacja odwrotna) $R^{-1} = \{(y,x): (x,y) \in R\}$
7. Def. (złożenie relacji) $(x,z)\in R\circ S \IFF (\exists y)((x,y)\in S \land (y,z)\in R)$
8. Tw. $(R\circ S)^{-1} = S^{-1} \circ R^{-1}$
9. Tw. $R\circ (S\circ T) = (R\circ S)\circ T$ (łączność złożenia relacji)
10. Def. $dom(R) = \{x: (\exists y)((x,y) \in R\}$
11. Def. $rng(R) = \{y: (\exists x)((x,y) \in R\}$
12. Def. $R$ jest symetryczna jeśli $(\forall x,y)((x,y)\in R \to (y,x)\in R)$
13. Def. $R$ jest zwrotna na $X$ jeśli $R\subseteq X\times X$ oraz $(\forall x \in X)((x,x)\in R)$
14. Def. $R$ jest przechodnia, jeśli $(\forall x,y,z)((x,y)\in R\land (y,z)\in R \to (x,z)\in R)$

8.11.2021: Relacje i Funkcje

1. Fakt: $R$ jest przechodnia IFF $R\circ R \subseteq R$
2. $R$ jest słabo-antysymetryczna IFF $(\forall x,y)((x,y)\in R \land (y,x)\in R \to x=y)$
3. Def. $f$ jest funkcją jeśli jest relacją taką, że
   $$(\forall x)(\forall y_1)(\forall y_2)(((x,y_1)\in f \land (x,y_2)\in f) \to y_1 = y_2)$$
4. Tw. Złożenie funkcji jest funkcją.
5. WNiosek: Złożenie funkcji jest łączne
6. Def. $R[A] = \{y:(\exists a\in A)((a,y)\in R\}$
7. Def. $R^{-1}[A] = \{x:(\exists a\in A)((x,a)\in R\}$
8. Tw. $R[A\cup B] = R[A] \cup R[B]$
9. Tw. $R[A\cap B] \subseteq R[A] \cap R[B]$
10. Uwaga: złożenie relacji na ogół nie jest przemienne:
    • Wykres funkcji $y=sin(x^2)$: Wolfram Alpha
    • Wykres funkcji $y=sin^2(x)$: Wolfram Alpha

19.11.2021: Relacje i Funkcje: II

1. Tw.. Jeśli $f$ jest funkcją to $f^{-1}[A\cap B] = f^{-1}[A] \cap f^{-1}[B]$
2. Def. Funkcja $f$ jest injekcją, jeśli $(\forall x_1,x_2)(f(x_1)=df(x_2) \to x_1=x_2)$
3. Def. Funkcja $f:A\to B$ jest surjekcją, jeśli $(\forall b\in B)(\exists a\in A)(f(a)=b)$
4. Tw. Złożenie injekcji jest injekcją
5. Wniosek. Jeśli $f$ jest funkcją, to $f^{-1}$ jest funkcją wtedy i tylko wtedy, gdy $f$ jest injekcją.
6. Tw. Złożenie surjekcji jest surjekcją
7. Def. $f$ jest bijekcją, jeśli $f$ jest jednocześnie injekcją i surjekcją
8. Wniosek. Złożenie bijekcji jest bijekcją
9. Def. (równoliczność) $|A|=|B| \IFF$ istnieje bijekcja $f:A\to B$.
10. Własności pojęcia równoliczności:
    1. $|A|=|A|$
       ($id_A=\{(x,x):x\in A\}$ jest bijekcją między $A$ i $A$)
    2. $|A|=|B| \to |B|=|A|$
       (funcja odwrotna do bijekcji jest bijekcją)
    3. $(|A|=|B|\land |B|=|C|) \to |A|=|C|$
       (złożenie bijekcji jest bijekcją)
11. Def. $|A|=n \IFF |A| = |\{1,2,\ldots,n\}|$
12. Prawa de Morgana dla indeksowanych rodzin zbiorów:
    • $\left(\bigcup_{i\in I} A_i\right)^c=\bigcap_{i\in I} A_i^c$
    • $\left(\bigcap_{i\in I} A_i\right)^c=\bigcup_{i\in I} A_i^c$
13. Granica dolna i granica górna: $\limsup_n A_n = \bigcap_n\bigcup_{m\geq n}A_m$, $\liminf_n A_n = \bigcup_n\bigcap_{m\geq n}A_m$: $$ \bigcup_n A_n \subseteq \liminf_n A_n \subseteq \limsup_n A_n \subseteq \bigcup_n A_n $$

22.11.2021: Relacje równoważności

1. Def. Relacja $\sim \subseteq X\times X$ jest relacją równoważności na $X$ jeśli jest zwrotna na $X$, symetryczna i przechodnia
2. Przykład: Ustalmy liczbę naturalną $n\gt 0$. Na zbiorze $\ZZ$ określamy relację $$ x \sim y \IFF n|(x-y) $$ To jest relacja równoważności na $\ZZ$.
3. Niech $\sim$ będzie relacją równoważności na $X$. Klasą abstrakcji elementu $a\in X$ (względem relacji $\sim$) nazywamy zbiór $$ [a]_\sim = \{x\in X: a \sim x\}~. $$
4. Niech $\sim$ będzie relacją równoważności na $X$. Wtedy
   1. $(\forall a \in X)(a\in[a]_\sim)$
   2. $(\forall a,b \in X)(a\sim b \to [a]_\sim = [b]_\sim)$
   3. $(\forall a,b \in X)(([a]_\sim \cap [b]_\sim \neq \emptyset) \to (a\sim b))$
5. Przykład: dla relacji zedefiniowanej na początku wykładu dla $n=5$ mamy: $[0]_\sim = \{5k: k\in\ZZ\}$, $[1]_\sim = \{5k+1: k\in\ZZ\}$, $[2]_\sim = \{5k+2: k\in\ZZ\}$, $[3]_\sim = \{5k+3: k\in\ZZ\}$, $[4]_\sim = \{5k+4: k\in\ZZ\}$.
6. Def. Partycją (rozbiciem) zbioru $X$ nazywamy taką rodzinę zbiorów $\mathcal{A}$, że
   1. $(\forall A\in\mathcal{A})(\emptyset \neq A \subseteq X)$
   2. $(\forall A,B\in\mathcal{A})(A\neq B \to A\cap B = \emptyset)$
   3. $\bigcup\mathcal{A} = X$
7. Def. Jeśli $\sim$ jest relacją równoważności na $X$, to $$ X/_\sim = \{[a]:a\in X\} $$
8. Wniosek: Jeśli $\sim$ jest relacją równoważności na $X$, to $X/_\sim$ jest rozbiciem zbioru $X$
9. Tw. $f:X\to Y$. Na zbiorze $X$ definiujemy relację $$ x\sim_f y \IFF (f(x)=f(y)) $$ Relacja $\sim_f$ jest relacją równoważności na $X$.
10. Tw. Niech $\mathcal{P}$ będzie rozbiciem zbioru $X$. Dla $x,y\in X$ definiujemy $$ (x \sim y) \IFF (\exists A\in\mathcal{P})(\{x,y\}\subseteq A)~. $$ Wtedy $\sim$ jest relacją równoważności na zbiorze $X$.

27.11.2021: Relacje równoważności

1. Pobawiliśmy się torusami, wstępą Mobiusa i butelką Kleina
2. GRUPA ILORAZOWA.
   Ustalamy grupę abelowa $\mathcal{G} = (G,+)$. Ustalamy podgrupę $H$ grupy $\mathcal{G}$, czyli taki niepusty podzbiór zbioru $G$, że $(\forall x,y\in H)(x-y\in H)$.
   • Na zbiorze $G$ definiujemy relację $(x\sim_H y) \IFF x-y \in H$
   • Fakt. $\sim_H$ jest relacją równoważności na zbiorze $G$
   • Fakt: $[a]_\sim = a + H ( = \{a+h: h\in H\})$
   • Fakt: $(x\sim_H x')\land (y\sim_H y') \to ((x+y) \sim_H (x'+y'))$
   • Definiujemy: $[a]\mathbf{+}[b] = [a+b]$.
     Z poprzedniego faktu wynika, że definicja ta jest poprawna.
   • Fakt: $(G/\sim_H,\mathbf{+})$ jest grupą.
     Grupę tę oznaczamy przez $G/H$.
   • PRZYKŁAD: $(\ZZ,+)/(n\ZZ) \cong \CC_n$

29.11.2021: Częściowe porządki - I

1. Selektory rozbić
2. Def: Para $(X,\leq)$ jest częściowym porządkiem na zbiorze $X$ jeśli $\leq$ jest relacją zwrotną na $X$, przechodnią oraz słabo-antysymetryczną.
3. Przykłady: $(\RR,\leq)$, $(\QQ,\leq)$, $(\NN\setminus\{0\},|)$
4. Przykład: $\mathcal{P}(X)= (P(X),\subseteq)$
5. Def. Niech $(X,\leq)$ będzie częściowym porządkiem i $a\in X$.
   1. $a$ jest największy w $(X,\leq)$ jeśli $(\forall x\in X)(x\leq a)$
   2. $a$ jest najmniejszy w $(X,\leq)$ jeśli $(\forall x\in X)(a\leq x)$
   3. $a$ jest maksymalny w $(X,\leq)$ jeśli $(\forall x\in X)(a\leq x \to x=a)$
   4. $a$ jest minimalny w $(X,\leq)$ jeśli $(\forall x\in X)(x\leq a \to x=a)$
6. Tw. Element największy jest maksymalny.
7. Tw. Jeśli $(X,\leq)$ jest częściowym porządkiem, to $(X,\leq^{-1})$ też jest częściowym porządkiem
8. Fakt: Jeśli $a$ je $\leq$-największy ($\leq$-maksymalny) to $a$ jest $\leq^{-1}$-najmniejszy ($\leq^{-1}$-minimalny.
9. Wniosek. Element najmniejszy jest minimalny
.
10. Fakt: Jeśli $(X,\leq)$ jest częściowym porządkiem i $Y\subseteq X$ to $(Y,\leq \restriction Y)$ też jest częściowym porządkiem.
    Uwaga: skrót $\leq \restriction Y$ oznacza $\leq \cap (Y\times Y)$.

03.12.2021: Częściowe porządki - II

1. Produkt częściowych porządków: dla częściowych porządków $(X,\leq_1)$ i $(Y,\leq_2)$ na zbiorze $X\times Y$ określamy $$ (x,y) \leq (x',y') \IFF (x\leq_1 x') \land (y\leq_2 y') $$ Fakt: $(X\times Y,\leq)$ jest częściowym porządkiem.
2. Tw [O uniwersalności częściowego porządku $\mathcal{P}(X)$] Jeśli $(X,\leq)$ jest częściowym porządkiem, to istnieje podzbiór $Y\subseteq P(X)$ taki, że $(X,\leq)$ jest izomorficzny z $\mathcal{P}(X)\restriction Y$.
3. Def: Para $(X,\leq)$ jest liniowym porządkiem na zbiorze $X$ jeśli $(X,\leq)$ jest częściowym porządkiem takim, że $(\forall x,y \in X)(x\leq y \lor y \leq x)$.
4. Przykłady: $(\RR,\leq)$, $(\QQ,\leq)$, $(\NN, \leq)$
5. Obserwacja: w linowych porządkach pojęcia elementu najmniejszego i elementu minimalnego pokrywają się
6. Produkt leksykograficzny porządków $(L_1,\leq_1)$ i $(L_2,\leq_2)$: relacja na $L_1\times L_2$ zdefiniowana wzorem $$(x,y)\leq(x',y') \equiv (x \lt_1 x') \lor ((x=x') \land (y\leq y'))$$ Tw. To jest liniowy porządek.
7. Def. Liniowy porządek $(X,\leq)$ jest dobrym porządkiem jeśli $$ (\forall A\subseteq X)(A\neq \emptyset \to (\exists a\in A)(\forall x \in A)(a\leq x)) $$

06.12.2021: Indukcja matematyczna

1. Uwaga: w liniowych porządkach każdy element minimalny (maksymalny) jest najmniejszy (największy)
2. Def. y jest następnikiem x jeśli $y \gt x$ oraz $(\forall z)(z\gt x \to z\geq y)$. Podobnie: y jest poprzednikiem x jeśli $y \lt x$ oraz $(\forall z)(z\lt x \to z\leq y)$
3. Własności liczb naturalnych:
   1. $(\NN,\leq)$ jest dobrym porządkiem
   2. każdy element ma następnika
   3. każdy element różny od 0 ma poprzednika
4. Tw. Jeśli $(L,\preceq)$ jest dobrym porządkiem w którym element ma następnik oraz każdy element różny od elementu najmniejszego ma poprzednik, to $(L,\preceq)$ jest izomorficzny z $(N\leq)$
5. ....
6. Tw. W każdym skończonym, niepustym cześciowym porządku istnieje element minimalny

10.12.2021: Indukcja matematyczna - II

1. Tw. Jeśli $(L_1,\leq_1)$ i $(L_2,\leq_2)$ są skończonymi liniowymi porządkami i $|L_1|=|L_2|$, to są izomorficzne.
2. Tw. (O sortowaniu topologicznym) Niech $(X,R)$ będzie skończonym częściowym porządkiem. Istnieje wtedy liniowy porządek $L$ na zbiorze $X$ taki, że $R\subseteq L$.
3. Tw. Jeśli $A$ i $B$ są skończone i $A\cap B = \emptyset$ to $|A\cup B| = |A|+|B|$.
4. Tw. Jeśli $A$ i $B$ są skończone, to $|A\times B| = |A|\cdot|B|$.
5. Tw. Jeśli $A$ i $B$ są skończone, to $|A^B| = |A|^{|B|}$.
6. Tw. Jeśli $A$ jest skończony, to $|P(A)| = 2^{|A|}$.

10.12.2021: Indukcja matematyczna - II

1. Tw. $|X|=|Y|=n \to |Bij(X,Y)| = n!$
2. Tw. Jeśli $|\{1,\ldots,n\}| = |\{1,\ldots,m\}|$, to $n=m$
3. Tw. Jeśli $|X|=|Y| = n$, to dla dowolnej funkcji f:X\to Y$ następujące własności są równoważne:
   1. f jest injekcją
   2. f jest bijekcją
4. Zasada Dirichletta
5. Przykład: jeśli mamy pięć punktów w trójkącie równobocznym o boku długości 2, to dwa z nich są w odległości nie więszej niż $1$
6. Przykład: Jeśli $x_1,\ldots,x_n$ są dowolnymi liczbami naturalnymi, to istnieje niepusty zbiór $T\subseteq\{1,\ldots,n\}$ taki, że liczba $\sum_{t\in T} x_t$ jest podzielna przez $n$.
7. Tw. Jeśli $(X,\preceq)$ jest dobrym porządkiem, to nie istnieje funkcja $f:\NN\to X$ taka, że $(\forall n\in\NN)(f(n+1) \prec f(n))$

10.12.2021: Indukcja matematyczna - II

1. Funkcja

     int ndw(int a, int b){
       while (a != b){
         if (a < b) { b = b - a;}
         else (a = a - b;}
       }
       return (a);
       }
   

   kończy swoje działanie po skończonej liczbie kroków jeśli wywołamy go z parametrami dodatnimi $a$ i $b$.
2. Otoczka Kleene'ego zbioru $X$: zbió $X^*$ wszystkich skończonych ciągów elementów zbioru $X$. Ciąg pusty zaliczamy do zbioru $X^*$ i oznaczamy go symbolem $\epsilon$.
3. Na zbiorze $X^*$ mamy określone dzialanie konkatenacji $\star$. Struktura $(X^*,\star,\epsilon)$ jest monoidem.
4. Na $X^*$ określamy relację $x \sqsubseteq y \IFF (\exists z \in X^*)(y = x \star z)$. Struktura $(X^*,\sqsubseteq)$ jest częściowym porządkiem. Dlugość ciągu $x\in X^*$ oznaczamy prze $l(x)$.
5. Porządek leksykograficzny. Niech $(L,\preceq)$ będzie liniowym porządkiem. Na zbiorze $L^*$ określamy relację
   $$ (x\preceq_{lex}y) \IFF {\color{LimeGreen}(}x\sqsubseteq y \lor (\exists k){\color{red}(}(1\leq k \leq \min(l(x),l(y))) \land (x_k\prec x_k) \land(\forall i)(1\leq i\lt k \to x_i=y_i){\color{red})}{\color{LimeGreen})} $$
6. Tw. Jeśli $(L,\preceq)$ jest liniowym porządkiem to również $(L^*,\preceq_{lex})$ jest liniowym porządkiem.

10.12.2021: Teoria mocy - I

1. Def. $|X| = |Y| \IFF $ istnieje bijekcja $f|X\to Y$
2. Def. $|X|\leq|Y| \IFF $ istnieje injekcja $f:X\to Y$
3. Def. $|X|\lt |Y| \IFF ((|X|\leq |Y|) \land (|X| \neq |Y|))$
4. Twierdzenie Cantora. Dla dowolnego zbioru $X$ mamy
   $$|X| \lt |P(X)|$$
5. Twierdzenie Cantora - Bernsteina. Dla dowolnych zbiorów $X$ i $Y$ mamy
   $$(|X|\leq|Y| \land |Y|\leq |X|) \to |X|=|Y|$$

15.12.2021: Teoria mocy - I

1. Oznaczenie: $(|A|=\aleph_0) \IFF (|A|=|\NN|)$
2. Oznaczenie: $(|A|=\mathfrak{c}) \IFF (|A|=|\RR|)$
3. Przykład: $|(-1,1)| = \mathfrak{c}$
4. Przykład: Jeśli $A\subseteq \RR$ oraz dla pewnych $a\lt b$ mamy $(a,b)\subseteq A$ to $|A| = \mathfrak{c}$
5. Def. Zbiór $A$ jest przeliczalny jeśli $A=\emptyset$ lub istnieje surjekcja $f:\NN\to A$
6. Tw. Zbiór $A$ jest przeliczany wtedy i tylko wtedy, gdy $|A|\in\NN$ lub $|A| = \aleph_0$
7. Tw. $|\NN\times\NN| = \aleph_0$
8. Wniosek. $|\QQ| = \aleph_0$

03.01.2022: Teoria mocy - II

1. Tw. Suma przeliczalnej rodziny zbiorów przeliczalnych jest przeliczalna
2. Tw. Jeśli $|A|=|B|$ to $|P(A)| = |P(B)|$
3. Tw. $|P(A)| = |\{0,1\}^A|$
4. Tw. $|\RR| = |P(\NN)|$
5. Wniosek: $|\NN| \lt |\RR|$
6. Def: Jeśli $|A| = \kappa$ i $|B| = \lambda$ to
   1. $\kappa + \lambda = |(A\times \{0\}) \cup (B\times\{1\}|$
   2. $\kappa \cdot \lambda = |A\times B|$
7. Fakt: powyższe definicje są poprawne
8. Przykłady: $n + \aleph_0 = \aleph_0$, $\aleph_0 + \aleph_0 = \aleph_0$, $3\cdot \aleph_0 = \aleph_0$, $\aleph_0 \cdot \aleph_0 = \aleph_0$, $\ldots$

05.01.2022: Teoria mocy - III

1. Def. Jeśli $\kappa = |A|$ oraz $\lambda = |B|$ to $\kappa^\lambda = |A^B|$
2. Fakt: Powyższa definicja jest poprawna.
3. Tw. $\kappa^{\lambda + \mu} = \kappa^\lambda \cdot \kappa^\mu$
4. Wniosek: $\mathfrak{c} \cdot \mathfrak{c} = \mathfrak{c}$
   Czyli $|\RR\times \RR| = |\RR|$.
5. Tw: $\kappa^{\lambda \cdot \mu} = \left(\kappa^\lambda\right)^\mu$
6. Wniosek: $|\RR^\NN| = \mathfrak{c}$
7. Tw. $|C(\RR,\RR)| = \mathfrak{c}$, gdzie $C(\RR,\RR)$ oznacza rodzinę wszystkich funkcji ciągłych z $\RR$ w $\RR$
8. Currying: zamiana funkcji ze zbioru $A^{B\times C}$ w funkcję ze zbioru $\left(A^B\right)^C$

10.01.2022: Ciągi liczb naturalnych

1. Tw. Jeśli $0 \lt |\Sigma| \leq \aleph_0$ to $|\Sigma^*| = \aleph_0$
2. Obserwacja: $|\NN^{\NN}| = \mathfrak{c}$
3. Niezbyt dokładne pojęcie funkcji obliczanych (OBL) z $\NN$ do $\NN$
4. Obserwacja: $\aleph_0 = |OBL| \lt |\NN^{\NN}|$

14.01.2022: Aksjomat Wyboru

1. AC: każda partycja ma selektor.
2. Def. $\prod_{t\in T}A_t = \{f \in (\bigcup_{t\in T}A_t)^T: (\forall t\in T)(f(t)\in A_t)\}$
3. Tw. AC jest równoważny zdaniu: jeśli $(T_t)_{t\in T}$ jest rodziną zbiorów niepustych, to $\prod_{t\in T}A_t \neq\emptyset$.
4. WOP: każdy zbior można dobrze uporządkować
5. Tw. WOP implikuje AC
6. Pojęcia łańcucha i antyłańcucha w częściowym porządku oraz ograniczenia górnego zbioru.
7. LKZ: Każdy częściowy porządek w którym każdy łańcuch ma ograniczenie górne ma element maksymalny.
8. Tw. LKZ implikuje AC
9. Tw (LKZ) Każda przestrzeń wektorowa ma bazę

17.01.2022: Konstrukcje matematyczne

1. Pojęcie liczb algebraicznych
2. Konstrukcja liczb całkowitych z liczb naturalnych
3. Konstrukcja liczb wymiernych z liczb całkowitych

21.01.2022: Aksjomaty teorii mnogości - I

1. A1 [aksjomat ekstensjonalności] $(\forall x,y)((\forall z)(z\in x \IFF z \in y) \to x=y)$
2. A2 [aksjomat zbioru pustego] $(\exists x)(\forall y)(\neg (y \in x))$
3. A3 [aksjomat pary] $(\forall x,y)(\exists z)(\forall t)(t\in z \IFF (t = x \lor t = y))$
4. A4 [aksjomat sumy] $(\forall x)(\exists y)(\forall t)(t\in y \IFF (\exists z \in x)(t \in z))$
5. A5 [aksjomat zbioru potęgowego] $(\forall x)(\exists y)(\forall z)(z \in y \IFF z \subseteq x)$
6. A6 [aksjomat wyróżniania] Dla dowolnej formuły $\phi(t,\vec{z})$ $$ (\forall \vec{z})(\forall x)(\exists y)(\forall t)(t\in y \IFF (t\in x \land \phi(t,\vec{z}))) $$

24.01.2022: Aksjomaty teorii mnogości - II

1. A7 [Aksjomat nieskończoności] $(\exists x)(\emptyset\in x \land (\forall y)(y \in x \to y \cup \{y\} \in x))$
2. Definicja $\omega$ (zbioru liczb naturalnych): najmniejszy w sensie inkluzji zbiór przechodni
3. A8 [Aksjomat zastępowania] Dla dowolnej formuły $\phi(x,y,\vec{z})$: $$ (\forall \vec{z})[(\forall x)(\exists !y)\phi(x,y,\vec{z}) \to (\forall a)(\exists b)(\forall t)(t\in b \IFF (\exists s\in a)\phi(s,t,\vec{z})) ] $$
4. A9 [Aksjomat regularności] $(\forall x)(x\neq\emptyset \to (\exists y\in x)(x\cap y = \emptyset))$
5. ZF = A1 + A2 + ... + A9
6. AC [Aksjomat wyboru] $$(\forall x)[((\forall t \in x)(t\neq\emptyset) \land (\forall s,t \in x)(s\neq t \to s\cap t = \emptyset)) \to (\exists s)(\forall t\in x)(|s\cap t| = 1)) $$
7. ZFC = ZF + AC

28.01.2022: Zbiory tranzytywne i liczby porządkowe