13.10.2018: Rachunek Zdań

1. Pojęcie zdania rachunku zdań
2. Pojęcie waluacji i rozszerzenie waluacji $\pi$ na dowolne zdania ($val(\phi,\pi)$)
3. Pojęcie tautologii: $\phi$ jest waluacją ($\models \phi$) jeśli dla dowolnej waluacji $\pi$ mamy $\pi(\phi) = \mathbb{1}$
4. Przykłady:
   • $\models(p \lor \neg p)$
   • $\models (p\lor q) \IFF (q \lor p)$

15.10.2018: Tautologie

1. Skróty:
   • $\pi\models \phi$ oznacza, że $val(\phi,\pi)=\mathbf{1}$
   • $\phi \equiv \eta$ oznacza, że $\models (\phi \IFF \eta)$
2. Najważniejsze tautologie:
   1. prawa przemienności: $(p\lor q) \IFF (q\lor p)$, $(p\land q) \IFF (q\land p)$
   2. 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)$
   3. prawo podwójnej negacji: $\neg\neg p \IFF p$
   4. sprzeczność implikuje wszystko: $(p\land \neg p) \to q$
   5. prawa de Morgana: $\neg (p\lor q) \IFF (\neg p \land \neg q)$, $\neg (p\land q) \IFF (\neg p \lor \neg q)$
   6. prawo eliminacji implikacji: $(p \to q) \IFF (\neg p \lor q)$
   7. prawo eliminacji równoważności: $(p\IFF q) \IFF ((p\to q) \land (q\to p))$
   8. Spójnik Pierce'a: $p\cdot 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).
   9. 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.

Notatki z wykładu: LiSF02.pdf
Zadanie domowe: wyznacz tabelkę zero-jedynkową dla zdania $$ \phi = (p\land q \land \neg r) \lor (p \land \neg q \land r) \lor (\neg p \land \neg q \land r) $$

Notatki:

20.10.2020: Synteza formuł

1. Przykłady ważnych tautologii
   1. $\models ((p\to q)\land (q\to r))\to (p\to r)$ [prawo przechodności implikacji]
   2. $(p\to q) \IFF (\neg q \to \neg p)$ Przykład zastosowań: dowód nie wprost faktu $\sqrt{2}\notin\QQ$
   3. $\models ((p\to q)\land (\neg p \to q))\to q$ Przykład zastosowań: dowód tego, że $x\leq |x|$ dla dowolnego $x\in\RR$
2. Def. Literał: zmienna zdaniowa lub jej negacja
3. Def. Zdanie jest w postaci dyzjunkcyjno normalnej (DNF) jeśli jest alternatywą zdań które są koniunkcjami literałów
4. KONSTRUKCJA: mamy ustaloną tabelkę 0-1, czyli funkcję $F$ taką że $F((i_1,i_2,\ldots,i_n)) \in \{0,1\}$ dla dowolnego ciągu $(i_1,i_2,\ldots,i_n)$ elementów o wartościach $0$ lub $1$. Pokazaliśmy, że istnieje zdanie $\phi$ w postaci DNF zbudowana ze zmiennych $p_1,\ldots,p_n$ taka, że dla dowolnej waluacji $\pi$ zmiennych $p_1,\ldots,p_n$ mamy $val(\phi,\pi) = F((\pi(p_1),\ldots,\pi(p_n))$.
   
   Wygląda to na dosyć skomplikowane, ale chodzi o prostą rzecz: mając daną tabelkę 0-1 można do niej dopasować zdanie
5. Def. Zdanie jest w postaci koniunkcyjno normalnej (CNF) jeśli jest koniunkcją formuł które są klauzulami (czli alternatywami literałów).
6. Tw. Dla każdego zdania $\phi$ istnieją zdania $\psi$ i $\eta$ takie, że $\phi \equiv \psi \equiv \eta$ oraz $\psi$ jest w postaci DNF zaś $\eta$ jest w postaci CNF.
7. Zdanie $\psi$ jest spełnialne jeśli istnieje waluacje $\pi$ taka, że $\pi(\psi) = 1$
8. Rozmiar zdania: $\|\phi\|$: $\|p_i\|=1$, $\|\neg\phi\| = \|\phi\|+1$, $\|\phi \lor\psi\| = \|\phi \land\psi \| = \|\phi\| +\|\psi\|+1 $
9. Problem P=NP: czy istnieje algorytm $\mathbb{A}$ oraz wielomian $w(x)$ taki, że dla dowolnego zdania $\phi$ w postaci CNF mamy
   1. $\mathbb{A}(\phi)=1$ wtedy i tylko wtedy, gdy $\phi$ jest spełnialne
   2. algorytm $\mathbb{A}$ na zdaniu $\phi$ działa w czasie $w(\|\phi\|)$

22.10.2020: Reguły wnioskowania

1. Rozdzielność koniunkcji względem alternatywy: $\models ((p\lor q)\land r) \IFF ((p\land r)\lor (q\land r))$
2. Rozdzielność alternatywy względem koniunkcji: $\models ((p\land q)\lor r) \IFF ((p\lor r)\land (q\lor r))$
3. 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}$.
4. 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$
5. Twierdzenie. Załóżmy, że $\{\phi_1,\ldots,\phi_n\}\models \alpha$. Wtedy dla dowolnych zdań $\psi_1,\ldots, \psi_k$ mamy również $\{\phi_1,\ldots,\phi_n,\psi_1,\ldots, \psi_k\}\models \alpha$.
6. Twierdzenie. Załóżmy, że $\{\phi_1,\ldots,\phi_n\}\models \alpha$. Wtedy dla dowolnego zdania $\psi$ mamy
   1. $\{\phi_1,\ldots,\phi_n\}\models \psi$
   2. $\{\phi_1,\ldots,\phi_n,\alpha\}\models \psi$
7. Reguła wnioskowania Modus Ponens: $\{\alpha,\alpha\to\beta\}\models\beta$. Regułę tę zapisujemy w następującej postaci: $$ \frac{\alpha,\quad \alpha\to\beta}{\beta} $$
8. Reguła rezolucji: $\{\phi\lor\alpha, \neg \phi \lor \beta\}\models(\alpha \lor \beta)$. Oto jej standardowa forma zapisu: $$ \frac{\phi\lor\alpha, \neg \phi \lor \beta}{\alpha \lor \beta} $$
9. Przykład rozumowania: $\{p,p\to q,q\to r\}\models r$: $$ \frac{\frac{p \quad p\to q}{q}\quad\quad q\to r}{r} $$
10. A na koniec wykładu opowiedzieliśmy sobie jak wróżkę umiejącą rozstrzygać czy dane zdanie jest tautologią wykorzystać do wskazania spełniającej waluacji.

27.10.2020: Zbiory - I

1. Aksjomat Ekstensjonalności: 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$ 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. Twierdzenie (Russell) Nie istnieje zbiór wszystkich zbiorów.
6. Def. Para nieuporządkowana: $x\in\{a,b\} \IFF (x=a \lor x=b)$
7. Def: $\{a\} = \{a,a\}$
8. Przykład: Zbiory $\emptyset$, $\{\emptyset\}$, $\{\{\emptyset\}\}$, $\{\{\{\emptyset\}\}\}$, $\{\{\{(\{\emptyset\}\}\}\}$,$\ldots$ są parami różne.
9. Def (suma): $(x\in A \cup B) \leftrightarrow ((x\in A) \lor (x\in B))$
10. Def (przekrój): $(x\in A \cap B) \leftrightarrow ((x\in A) \land (x\in B))$
11. Twierdzenie. Dla dowolnych zbiorów $A,B,C$ mamy
    • $A \cup B = B \cup A$ (konsekwencja tautologii $p\lor q \equiv q\lor p$)
    • $A \cap B = B \cap A$ (konsekwencja tautologii $p\land q \equiv q\land p$)
    • $A\cup (B\cup C) = (A\cup B)\cup C$ (konsekwencja łączności alternatywy)
    • ....
12. Def. Inkluzja: $A\subseteq B$ jeśli dla dowolnego $x$ mamy $x\in A \to x\in B$
13. Tw. Następujące zdania są równoważne:
    1. $A \subseteq B$
    2. $A \cap B = A$
    3. $A \cup B = B$
    Od dowódu tego twierdzenia rozpoczniemy następny wykład.
Notatki z wykładu: LiSF05.pdf

Notatki:

11.10.2018: Zbiory - II

1. Fakt: Dla dowolnych zbiorów $A$, $B$, $C$, $D$:
   1. $A\subseteq A\cup B$
   2. $A\cap B \subseteq A$
   3. [monotoniczność] Jeśli $A\subseteq B$ i $C\subseteq D$, to $A\cup C \subseteq B\cup D$ oraz $A\cap C \subseteq B\cap D$
2. Def (różnica) $x\in A\setminus B \equiv (x\in A \land x\notin B$
3. Def. Dopełnienie zbioru $A\subseteq\Omega$ do zbioru $\Omega$: $A^c = \Omega\setminus A$
4. Uwaga: $A\setminus B = A \cap B^c$
5. Przykład: (prawa de Morgana): $(A\cup B)^c = A^c \cap B^c$; $(A\cap B)^c = A^c \cup B^c$;
6. Przykład: $(A\setminus B)\setminus C = \ldots = A \setminus (B\cup C)$
7. Diagramy Venna
8. Składowe rodziny $\{A_1,\ldots, A_n\}$: zbiory postaci $A_1^{\epsilon_1} \cap \ldots A_n^{\epsilon_n}$, gdzie $\epsilon_1, \ldots, \epsilon_n \in \{0,1\}$ oraz $A^0=A$ i $A^1 = A^c$
9. Fakt: Jest bezpośredni związek między zbiorami które można wygenerować ze zbiorów z rodziny $\{A_1,\ldots, A_n\}$ za pomocą operacji $\cup$, $\cap$ i $^c$ a zdaniami w postaci DNF dla zmiennych zdaniowych $p_1 = (x\in A_1)$, ... , $p_n = (x\in A_n)$.
10. Fakt: Jeśli wszystkie składowe rodziny $\mathcal{S}=\{A_1,\ldots, A_n\}$ są niepuste, to z rodziny $\mathcal{S}$ można za pomocą operacji $\cup$, $\cap$ i $^c$ wygenerować dokładnie $2^{(2^n)}$ różnych zbiorów.

03.11.2020: Zbiory - III

05.11.2020: Kwantyfikatory - I

10.11.2020: Kwantyfikatory

1. Diagram funktora $\phi:\Omega^2\to\Omega$: $D_\phi = \{(x,y)\in\Omega^2: \phi(x,y)\}$
2. 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$

3. Przykład: ciągłość jednostajna implikuje ciągłość
4. Przykład: Zdanie $\lim_{n\to\infty} \frac1n \neq 1$ jest równoważne $\neg (\forall \epsilon \gt 0)(\exists N)(\forall n\gt N)(|\frac1n-1|\lt \epsilon)$, czyli $(\exists \epsilon \gt 0)(\forall N)(\exists n \gt N)(|\frac1n-1|\geq \epsilon)$.
5. Gra w zapałki (możemy brać 1, 2 lub 3 zapałki):
   1. Istnieje strategia zwycięzka dla gracza I lub dla gracza II
   2. strategia zwycięzka - trzymaj się liczb podzielnych przez 4
   3. Każda dwuoosobowa skończona gra jest zdeterminowana
6. Def. $x\in\bigcup\mathcal{A} \IFF (\exists X\in\mathcal{A})(x\in X)$
7. Def. $x\in\bigcap\mathcal{A} \IFF (\forall X\in\mathcal{A})(x\in X)$
8. Przykład: $\bigcup\{A,B,C\} = A\cup B\cup C$, $\bigcap\{A,B,C\} = A\cap B\cap C$,

12.11.2020: Relacje

1. Def. $R$ jest relacją jeśli istnieje $X$ taki, że $R\subseteq X\times X$.
2. Def. $dom(R) = \{x: (\exists y)((x,y) \in R\}$
3. Def. $rng(R) = \{y: (\exists x)((x,y) \in R\}$
4. Def. $R\circ S = \{(x,z):(\exists y)((x,y)\in S \land (y,z)\in R\}$
5. Tw. $R\circ(S\circ T) = (R\circ S)\circ T$
6. Def. $R^{-1} = \{(y,x):(x,y)\in R\}$
7. Tw. $(R\circ S)^{-1} = S^{-1}\circ R^{-1}$
8. 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)$$

17.11.2020: Relacje i funkcje

1. Tw. Złożenie funkcji jest funkcją.
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. $|A|=|B| \IFF$ istnieje bijekcja między A i 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.2020: Relacje i funkcje

1. 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ą)
2. Def. $|A|=n \IFF |A| = |\{1,2,\ldots,n\}|$
3. Def. $|A|=\aleph_0 \IFF |A| = |\NN|$ (alef zero)
4. Def. $|A|={\frak{c}} \IFF |A| = |\RR|$ (continuum)
5. Def. $R[A] = \{y:(\exists a\in A)((a,y)\in R\}$
6. Tw. $R[A\cup B] = R[A] \cup R[B]$
7. Tw. $R[A\cap B] \subseteq R[A] \cap R[B]$
8. Def. $R^{-1}[A] = (R^{-1})[A]$
9. Wniosek. $R^{-1}[A] = \{x:(\exists a\in A)((x,a)\in R\}$
10. 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$
11. 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 $$

24.11.2020: Relacje

1. Fakt. Jeśli $f$ jest funkcją, to $f^{-1}[A] = \{x\in dom(f): f(x) \in A\}$
2. Wniosek. Jeśli $f$ jest funkcją to $f^{-1}[A\cap B] = f^{-1}[A] \cap f^{-1}[B]$.
3. Def. Niech $R$ będzie relacją na zbiorze $X$.
   1. $R$ jest zwrotna na $X$, jeśli $(\forall x\in X)((x,x)\in R)$
   2. $R$ jest symetryczna, jeśli $(\forall x, y\in X)((x,y)\in R \to (y,x) \in R)$
   3. $R$ jest przechodnia, jeśli $(\forall x,y,z\in X)(((x,y)\in R \land (y,z)\in R)) \to (x,z)\in R)$
   4. $R$ jest słabo antysymetryczna, jeśli $(\forall x,y\in X)(((x,y)\in R\land (y,x)\in R)\to x=y)$
4. Fakt. Niech $Id_X = \{(x,x):x\in X\}$. Relacja $R\subseteq X\times X$ jest zwrotna na $X$ wtedy i tylko wtedy, gdy $Id_X\subseteq R$.
5. Fakt. $R$ jest symetryczna wtedy i tylko wtedy, gdy $R=R^{-1}$

27.11.2020: 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: Na zbiorze liczb całkowitych $\ZZ$ określamy relację $$ x \sim y \IFF 5|(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 przykładu z podzielnością przez 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$

01.12.2020: Relacje równoważności

1. 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$.
2. 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$.
3. 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: $(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$
4. Pobawiliśmy się trochę wstęgą Möbiusa

08.12.2020: Częściowe porządki

1. Pojęcie selektora i przykłady
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: $(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. 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.

10.12.2020: Liniowe porządki i dobre porządki

1. Def. Częściowe porządki $(X,\leq)$, $(Y,\preceq)$ są izomorficzne jeśli istnieje bijekcja $f:X\to Y$ taka, że $$ (\forall x,y\in X)((x\leq y) \IFF (f(x)\preceq f(y)))~. $$
2. 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)$.
3. Przykłady: $(\RR,\leq)$, $(\QQ,\leq)$, $(\NN, \leq)$
4. Obserwacja: w linowych porządkach pojęcia elementu najmniejszego i elementu minimalnego pokrywają się
5. 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)) $$
6. Twierdzenie: Następujące zdania są równoważne:
   1. Zbiór liczb naturalnych jest dobrze uporządkowany
   2. Niech $\phi:\NN\to\{0,1\}$ będzie funkcją zdaniową, $a\in\NN$. Jeśli $$ \phi(a) \land (\forall n\in\NN)(\phi(n) \to \phi(n+1)) $$ to $$ (\forall n\in\NN)(a \leq n \to \phi(n))~. $$
   3. Nie istnieje ostro malejący, nieskończony ciąg liczb naturalnych.
7. Przykład: algorytm

     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$.

15.12.2020: Indukcja matematyczna

1. Tw. Dla dowolnego $n\geq 1$ mamy $\sum_{k=1}^{n} k = \frac{n(n+1)}{2}$.
2. Z1. Dla dowolnego $n\geq 1$ mamy $\sum_{k=1}^{n} k^2 = \frac16 n(n+1)(2n+1)$.
3. Z2. Dla dowolnego $n\geq 1$ mamy $\sum_{k=1}^{n} k^3 = \left(\frac{n(n+1)}{2}\right)^2$.
4. Tw. Suma kątów wewnętrznych w $n$-kącie wypukłym ($n\geq 3$) jest równa $(n-2)\cdot 180^{\circ}$.
5. Tw. (nierówność Bernoulliego). Dla dowolnego naturalnego $n$ oraz $x\geq -1$ mamy $(1+x)^n \geq 1 + n x$.
6. Tw. W każdym skończonym częściowym porządku istnieje element maksymalny
7. Tw. Każdy częściowy porządek na zbiorze skończonym można rozszerzyć do porządku liniowego

17.12.2020: Indukcja, Aksjomat Wyboru

1. Tw. Jeśli $|X|=|Y|=n\in\NN$ i $f:X\to Y$ to następujące zdania są równoważne:
   1. $f$ jest injekcją
   2. $f$ jest surjekcją
2. Zasada Dirichletta
3. Przykład: jeśli mamy pięć punktów w trójkącie równobocznym o boku 1, to dwa z nich są w odległości nie więszej niż $\frac12$
4. Aksjomat Wyboru (AC): każda partycja ma selektor
5. Def. $A^B =\{f:f \text{ jest funkcją } \land dom(f)=B \land rng(f)\subseteq A\}$
6. 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)\}$
7. 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$.

07.01.2021: Aksjomat Wyboru - II

1. Tw (AC): Definicje Heinego i Cauchy'ego ciagłości funkcji w punkcie są równoważne
2. Zasada Dobrego Uporządkowania (WOP): Każdy zbiór można dobrze uporządkować
3. Lemat Kuratowskiego- Zorna:
   1. Łańcuch w częściowym porządku: podzbiór liniowo uporządkowany
   2. Ograniczenie górne zbioru $B$: takie $a \in X$, że $(\forall x\in B)(x \preceq a)$
   3. LKZ: w każdym częściowym porządku o własności "każdy łańcuch ma ograniczenie górne" istnieje element maksymalny
4. Twierdzenie: Następujące zdania są równoważne:
   1. AC
   2. WOP
   3. LKZ
5. Tw. W każej przestrzeni wektorowej istnieje baza

14.01.2021: Zbiory przeliczalne

1. Oznaczenie: $|A| = \mathfrak{c}$ ("continuum") jeśli $|A| = |\RR|$
2. Oznaczenie: $|A| = \aleph_0$ ("alef zero") jeśli $|A| = |\NN|$
3. Def. Zbiór $A$ jest przeliczalny jeśli $A=\emptyset$ lub istnieje surjekcja z $\NN$ na $A$
4. Tw 1. Zbiór jest przeliczalny wtedy i tylko wtedy, gdy jest skończony lub jest mocy $\aleph_0$
5. Przykłady: $|\NN| = |\NN^+| = |2 \NN| = |\ZZ|$
6. Fakt 1: Jeśli $|A_1|=|A_2|$ oraz $|B_1|=|B_2|$ to $|A_1\times B_1| = |A_2\times B_2|$
7. Tw 2. $|\NN\times\NN| = \aleph_0$
   Dowód: rozważamy funkcję $f(n,m) = 2^n(2m+1)-1$
8. Tw 3. $|\QQ| = \aleph_0$
   Dowód: Z Faktu 1 Twierdzenia 2 wynika, że $|\ZZ\times\NN| = |\NN\times\NN|= \aleph_0$. Następnie zauważamy, że funkcja $f:\ZZ\times\NN \to \QQ$ zadana wzorem $f((k,n)) = \frac{k}{n+1}$ jest surjekcją. Zatem $\QQ$ jest zbiorem przeliczalnym. Z Twierdzenia 1 wynika, że $\QQ$ jest zbiorem mocy $\aleph_0$.
9. Tw. Jeśli $(A_n)_{n\in\NN}$ jest rodziną zbiorów przeliczalnych, to $\bigcup_n A_n$ też jest zbiorem przeliczalnym.

19.01.2021: Arytmetyka kardynalna i zbiory mocy continuum

1. Def. Niech $|X|=\kappa$ i $|Y|=\lambda$.
   1. $\kappa+\lambda = |(X\times\{0\}) \cup (Y\times\{1\})|$
   2. $\kappa\cdot\lambda = |X\times Y|$
   3. $\kappa^\lambda = |X^Y|$
2. soon...
3. Tw. $|P(X)| = |\{0,1\}^X|$
4. Twierdzenie
   $$2^{\aleph_0} = \frak{c}$$
   Dowód (szkic) (1) Dla $x\in\RR$ definiujemy $\phi(x) = \{q\in\QQ:q \lt x\}$ i pokazujemy, że $\phi:\RR\to \QQ$ jest injekcją (korzystamy z gęstości $\QQ$ w $\RR$).
   (2) Dla $x\in \{0,1\}^\NN$ definiujemy $$\psi(x) = \sum_{i=0}^{\infty} \frac{x_i}{3^i}$$ i pokazujemy, że $\psi:\{0,1\}^\NN \to \RR$ jest injekcją.
5. Tw. Jeśli $B\cap C = \emptyset$ to $|A^{B\cup C}| = |A^B \times A^C|$
6. Wniosek: $|\RR\times\RR| = |\RR|$
   Dowód. $2^{\aleph_0} \cdot 2^{\aleph_0}$ = $|\{0,1\}^{\{\ldots,-3,-2,-1\}} \times \{0,1\}^\NN|$ = $|\{0,1\}^{\ZZ}| = 2^{\aleph_0} = |\RR|$.

21.01.2021: Liczby kardynalne

1. Tw. $|\left(A^B\right)^C| = |A^{B\times C}|$
2. Przykład: $|\RR^\RR| = 2^{\frak{c}} \gt \frak{c}$
3. Przykład: $|\RR^\QQ| = \frak{c}$
4. Tw. $|C(\RR,\RR)| = \frak{c}$
   gdzie $C(\RR,\RR)$ oznacza zbiór wszystkich funkcji ciągłych z $\RR$ w $\RR$.
5. Currying: przykład w JavaScript

   function Adder(x){
     return function (y) { 
       return x+y  
     }
   }
   
   var add3 = Adder(3)
   
   console.log(add3(5))
   console.log(add3(10))
   

6. Otoczka Kleene'go zbioru $X$: $X^* = \bigcup_{n\geq 0} X^n$
7. Wniosek Jeśli $X$ jest zbiorem przeliczalnym, to $X^*$ jest też zbiorem przeliczalnym
8. Wniosek. Zbiór funkcji "obliczalnych" z $\NN^\NN$ jest przeliczalny. Wiemy, że $|\NN^\NN|=\frak{c} \gt \aleph_0$, zatem większość funkcji z $\NN$ w $\NN$ nie jest obliczalna.

26.01.2021: Aksjomaty Teorii Mnogości

1. Tw. Jeśli $\mathcal{A}$ jest rodziną otwartych parami rozłącznych odcinków to $|\mathcal{A}|\leq\aleph_0$.
2. Tw. Jeśli $\mathcal{A}$ jest rodziną otwartych parami rozłącznych kul na płaszczyźnie to $|\mathcal{A}|\leq\aleph_0$.
3. Tw. Jeśli $F:\RR\to\RR$ jest funkcją niemalejącą, to zbiór jej punktów nieciągłości jest przeliczalny.

Aksjomaty Teorii Mnogości ZF

1. A1 (Aksjomat Ekstensjonalności) $$(\forall x)(\forall y)((\forall z)(z\in x \IFF z \in y) \to x=y)$$
   Uwaga: wprowadzamy oznaczenie $x\subseteq y \equiv (\forall t)(t\in x \to t \in y)$. A1 możemy równoważnie zapisać $(\forall x,y)(x=y \IFF ((x\subseteq y)\land (y\subseteq x)))$.
2. A2 (Aksjomat Zbioru Pustego) $$(\exists x)(\forall y)(\neg (y\in x))$$
   Uwaga: z A1 wynika jednoznaczność takie obiektu; wprowadzamy na niego oznaczenie $\emptyset$.
3. A3 (Aksjomat Pary) $$ (\forall x)(\forall y)(\exists z)(\forall t)(t\in z \IFF (t=x \lor t = y))$$
   Uwaga: z A1 mamy jednoznaczność; wprowadzamy oznaczenie $\{x,y\}$. Definiujemy $\{x\} = \{x,x\}$. Mamy więc istnienie zbiorów $\emptyset$, $\{\emptyset\}$, $\{\{\emptyset\}\}$, ...; są to parami różne zbiory; urodziło się więc nam nieskończenie wiele zbiorów; Defiujemy $(x,y) = \{\{x\},\{x,y\}\}$; mamy więc parę uporządkowaną.
4. A4 (Aksjomat Sumy) $$(\forall x)(\exists y)(\forall z)(z\in y \IFF (\exists t)(t\in x \land z\in t))$$
   Uwaga: ten jednoznacznie wyznaczony obiekt oznaczemy przez $\bigcup x$; z A4 wynika, że każdy zbiór mogę wysumować; w szczególności mamy $\bigcup\{x,y\} = x \cup y$.
5. A5 (Aksjomat Zbioru Potęgowego) $$(\forall x)(\exists y)(\forall z)(z\in y \IFF z \subseteq x)$$
   Uwaga: ten jednoznacznie wyznaczony obiekt oznaczemy, oczywiście, przez $P(x)$; zauważamy, że jeśli $a\in x$ i $b\in y$ to $(a,b) \in P(P(x\cup y))$.
6. A6 (Aksjomat Wyróżniania) Dla dowolnej formuły $\phi(t,y_1,\ldots,y_n)$ języka teorii ZF $$(\forall x)(\forall y_1)\ldots(\forall y_n)(\exists z)(\forall t)(t\in z \IFF (t\in x \land \phi(t,y_1,\ldots,y_n))) $$
   Uwaga: ten jednoznacznie wyznaczony obiekt oznaczemy, oczywiście, przez $\{t\in x: \phi(t,y_1,\ldots,y_n)\}$; Kilka obserwacji: $x\cap y = \{t\in x: t\in y\}$, $x\setminus y = \{t\in x: \neg(t\in y)\}$, $x\times y = \{u\in P(P(x\cup y)):(\exists a\in x)(\exists b\in y)(u = (a,b))\}$. Możemy więc zdefiniować pojęcie relacji (np. $rel(x) \equiv (\exists y)(y \subseteq x\times x)$), funkcji, dziedziny, injekcji, furjakcji, obrazu itp.

Ostatnie cztery wykłady: Aksjomatczna Teoria Mnogości

1. Notatki z wykładu: LiSF25.pdf
2. Notatki z wykładu: LiSF26.pdf
3. Notatki z wykładu: LiSF27.pdf
4. Notatki z wykładu: LiSF28.pdf

19.02.2021: Wykład dodatkowy: Wprowadzenie do Teorii Kategorii

1. Notatki z wykładu: LiSF29.pdf
2. Wprowadzenie do Teorii Kategorii: A_Gentle_Introduction_to_Category_Theory.pdf