02.10.2019: Rachunek Zdań - I

1. Pojęcie zdania rachunku zdań
2. Pojęcie waluacji i rozszerzenie waluacji $\pi$ na dowolne zdania ($val(\phi,\pi)$)
3. Pojęcie tautologii: $\models \phi$ jeśli dla dowolnej waluacji $\pi$ mamy $val(\phi,\pi) = \mathbb{1}$
4. Skróty: $\phi \equiv \eta$ oznacza, że $\models (\phi \IFF \eta)$
5. Najważniejsze tautologie:
   1. prawa przemienności: $(p\lor q) \equiv (q\lor p)$, $(p\land q) \equiv (q\land p)$
   2. prawa łączności: $(p\lor q)\lor r \equiv p \lor (q \lor r)$, $(p\land q)\land r \equiv p \land (q \land r)$
   3. prawo podwójnej negacji: $\neg\neg p \equiv p$
   4. prawa de Morgana: $\neg (p\lor q) \equiv (\neg p \land \neg q)$, $\neg (p\land q) \equiv (\neg p \lor \neg q)$
   5. prawo eliminacji implikacji: $(p \to q) \equiv (\neg p \lor q)$
   6. prawo eliminacji równoważności: $(p\IFF q) \equiv ((p\to q) \land (q\to p))$

Zadania domowe

1. Zadanie: naucz się alfabetu greckiego.
2. Zadanie: 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) $$

03.10.2019: Rachunek Zdań - II

1. Przykład: (sprzeczność implikuje wszystko) $(p\land \neg p) \to q$
2. Własności $\equiv$: zwrotnośc, przemienność, przechodniość
3. Przyklad: $\neg (p \to q) \equiv (p \land \neg q)$
4. Def. Literał: zmienna zdaniowa lub jej negacja
5. Def. Formuła jest w postaci konjunkcyjno normalnej (CNF) jeśli jest alternatywą formuł które są koniunkcjami literałów
6. Def. Formuła jest w postaci dyzjunkcujno normalnej (DNF) jeśli jest koniunkcją formuł które są klauzulami (czli alternatywami literałów; inna nazwa: dyzjunktów).
7. Tw. Dla każdej formuły $\phi$ istnieją formuły $\psi$ i $\eta$ takie, że $\phi \equiv \psi \equiv \eta$ oraz $\psi$ jest w postaci DNF zaś $\eta$ jest w postaci CNF.
8. Formuła $\psi$ jest spełnialna jeśli istnieje waluacje $\pi$ taka, że $\pi(\psi) = 1$
9. Rozmiar formuły: $len(\phi)$ = długość fromuły interpretowanej jako napis
10. Problem P=NP: czy istnieje algorytm $\mathbb{A}$ oraz wielomian $w(x)$ taki, że dla dowolnej formuły $\phi$ w postaci DNF mamy
    1. $\mathbb{A}(\phi)=1$ wtedy i tylko wtedy, gdy $\phi$ jest spełnialna
    2. algorytm $\mathbb{A}$ na formula $\phi$ działa w czasie $w(len(\phi))$

09.10.2019: Rachunek Zdań - III

1. Przykłady tautologii i ich zastosowanie do upraszczania kodów programów
2. Spójnik Pierce'a: $p\downarrow q \equiv (\neg p) \land (\neg q)$ (NOR)
3. Spójnik Shefera: $p|q \equiv (\neg p) \lor (\neg q)$ (NAND)
4. Operacja XOR: $p \oplus q \equiv ((\neg p \land q) \lor (p \land \neg q))$:
   1. $p\oplus p \equiv \bot$
   2. $p\oplus q \equiv q \oplus p$
   3. $p \oplus (q \oplus r) \equiv (p \oplus q)\oplus r$
5. Zastosowanie operacji $\oplus$ do kodowania informacji: $code(x) = x \oplus a$; $decode(x) = x \oplus a$; $$ decode(code(a)) = (x\oplus a)\oplus a) = x \oplus (a \oplus a) = x \oplus \bot = x $$

10.10.2019: Rachunek Zdań - IV

1. Def. $\{\phi_1,\ldots,\phi_n\}\models \psi$ jeśli dla dowolnej waluacji $\pi$ takiej, że $\pi(\phi_1)=\ldots=\pi(\phi_n) = 1$ mamy również $\pi(\psi)=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. Przykład (Modus Ponens): $\{\phi,\phi\to\psi\}\models \psi$
4. Przykład (Rezolucja): $\{\phi \lor \alpha, \neg\phi\lor\beta\}\models \alpha \lor \beta$
5. Odwrotna notacja polska. Przykład: $x * (y+z)$ $\to$ yz+x*
6. Przykłady rozumowań

16.10.2019: Zbiory - I

1. Pojęcia pierwotne: zbiór, należenie ($\in$)
2. 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)~.$$
3. Tw. Istnieje dokładnie jeden zbiór pusty.
   Zbiór pusty oznaczamy symbolem $\emptyset$.
4. Def: $(x\in A \cup B) \leftrightarrow ((x\in A) \lor (x\in B)) \text{ dla dowolnego } x$
5. Def: $(x\in A \cap B) \leftrightarrow ((x\in A) \land (x\in B))\text{ dla dowolnego } x$
6. Tw. $A \cup B = B \cup A$
7. Tw. $A \cup (B \cup C) = A\cup (B\cup C)$
8. Def: Funktor zdaniowy na zbiorze $A$: przyporządkowanie $\phi$ elementom zbioru $A$ wartości logicznych $\phi(a)$
9. Def. Operacja wyróżniania: $$ x \in\{a\in A: \phi(a)\} \IFF (x\in A \land \phi(a)) $$
10. Twierdzenie (Russell) Nie istnieje zbiór wszystkich zbiorów.

17.10.2019: Zbiory - II

1. Inkluzja: $A\subseteq B$ jeśli dla dowolnego $x$ mamy $x\in A \to x\in B$
2. Tw. Następujące zdania są równoważne:
   1. $A \subseteq B$
   2. $A \cap B = A$
   3. $A \cup B = B$
3. Def. Dopełnienie zbioru $A\subseteq\Omega$ do zbioru $\Omega$: $A^c = \Omega\setminus A$
4. Przykład: (prawa de Morgana): $(A\cup B)^c = A^c \cap B^c$; $(A\cap B)^c = A^c \cup B^c$;
5. Zbiór potęgowy $P(X)$ = zbiór wszystkich podzbiorów zbioru $X$.
6. Przykład: $X \in P(X)$, $\emptyset \in P(X)$
7. Różnica symetryczna: $A\triangle B = (A\cap B^c) \cup (A^c \cap B)$
8. Def. Para nieuporządkowana: $x\in\{a,b\} \IFF (x=a \lor x=b)$
9. Def: $\{a\} = \{a,a\}$
10. Przykład: Zbiory $\emptyset$, $\{\emptyset\}$, $\{\{\emptyset\}\}$, $\{\{\{\emptyset\}\}\}$, $\{\{\{\{\emptyset\}\}\}\}$,$\ldots$ są parami różne.
11. Def (para uporządkowana) $(a,b) = \{\{a\},\{a,b\}\}$ (definicja Kuratowskiego)
12. Tw. $(a,b) = (c,d)$ wtedy i tylko wtedy, gdy $(a=c) \land (b=d)$
13. 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$

23.10.2019: Zbiory i kwantyfikatory

1. Def. (iloczyn kartezjański): $A\times B = \{(a,b): a\in A \land b \in B\}$
2. Przykład: $(A \cup B)\times C = (A\times C) \cup (B \times C)$
3. Przykład: $(A \cap B)\times C = (A\times C) \cap (B \times C)$
4. Def. Jeśli $\phi:\Omega\to\{0,1\}$ to
   1. $(\forall x)\phi(x) \equiv \{x\in\Omega: \phi(x)\} = \Omega$
   2. $(\exists x)\phi(x) \equiv \{x\in\Omega: \phi(x)\} \neq \emptyset$
5. Tw. $(\forall x)(\phi(x)\land\psi(x)) \equiv (\forall x)(\phi(x)) \land (\forall x)(\psi(x))$
6. Tw. $(\exists x)(\phi(x)\lor\psi(x)) \equiv (\exists x)(\phi(x)) \lor (\exists)(\psi(x))$
7. Tw. $\left((\forall x)\phi(x) \lor (\forall x)\psi(x)\right) \to (\forall x)(\phi(x)\lor\psi(x)) $
8. Tw. $(\exists x)(\phi(x)\land\psi(x)) \to \left((\exists x)\phi(x) \land (\exists x)\psi(x)\right)$
9. Tw $\neg (\exists x) \phi(x) \equiv (\forall x)(\neg \phi(x))$ (prawo de Morgana)
10. Tw $\neg (\forall x) \phi(x) \equiv (\exists x)(\neg \phi(x))$ (prawo de Morgana)
11. 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)$.

24.10.2019: Zbiory i 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$

   i nie ma żadnych innych uniwersalnych zależności.
3. Def. $(\exists a\in A)\phi(x) \equiv (\exists x)(x\in A \land \phi(x))$
4. Def. $(\forall a\in A)\phi(x) \equiv (\forall x)(x\in A \to \phi(x))$
5. Tw. $\neg (\exists a\in A)\phi(x) \equiv (\forall x \in A)(\neg \phi(x))$
6. Tw. $\neg (\forall a\in A)\phi(x) \equiv (\exists x \in A)(\neg \phi(x))$
7. Przykład: $A\times B = \{u\in P(P(A\cup B)): (\exists a \in A)(\exists b \in B)(u = (a,b))\}$
8. Przykład: $\Omega = \RR$: Zdanie $(\forall x)(\exists q\in\QQ)(|x-q| \lt 1)$ jest prawdziwe (gęstość liczb wymiernych), lecz zdanie $(\exists q\in\QQ)(\forall x)(|x-q|\lt 1)$ jest fałszywe.
9. 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

30.10.2019: Relacje

1. Def. $x\in\bigcup\mathcal{A} \IFF (\exists X\in\mathcal{A})(x\in X)$
2. Def. $x\in\bigcap\mathcal{A} \IFF (\forall X\in\mathcal{A})(x\in X)$
3. Przykład: $\bigcup\{A,B,C\} = A\cup B\cup C$, $\bigcap\{A,B,C\} = A\cap B\cap C$,
4. Uwaga: $\bigcap \emptyset$ nie jest zbiorem
5. Def. $R$ jest relacją jeśli istnieje $X$ taki, że $R\subseteq X\times X$.
6. Przykłady: $R = \{(a,b),(a,c), (b,c)\}$, $LT = \{(x,y)\in\RR^2: x \le y\}$
7. Def. $dom(R) = \{x: (\exists y)((x,y) \in R\}$
8. Def. $rng(R) = \{y: (\exists x)((x,y) \in R\}$
9. Def. $R\circ S = \{(x,z):(\exists y)((x,y)\in S \land (y,z)\in R\}$
10. Tw. $R\circ(S\circ T) = (R\circ S)\circ T$
11. Def. $R^{-1} = \{(y,x):(x,y)\in R\}$
12. Tw. $(R\circ S)^{-1} = S^{-1}\circ R^{-1}$
13. Uwaga: Jeśli $(G,\star)$ jest grupą, to $(x\star y)^{-1} = y^{-1}\star x^{-1}$

06.11.2019: Relacje i funkcje

1. Def. $R[A] = \{y:(\exists a\in A)((a,y)\in R\}$
2. Tw. $R[A\cup B] = R[A] \cup R[B]$
3. Tw. $R[A\cap B] \subseteq R[A] \cap R[B]$
4. 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)$$

07.11.2019: Relacje

1. Tw. Złożenie funkcji jest funkcją.
2. Fakt. Jeśli $f$ jest funkcją, to $f^{-1}[A] = \{x\in dom(f): f(x) \in A\}$
3. Wniosek. Jeśli $f$ jest funkcją to $f^{-1}[A\cap B] = f^{-1}[A] \cap f^{-1}[B]$.
4. Def. Funkcja $f$ jest injekcją, jeśli $(\forall x_1,x_2)(f(x_1)=df(x_2) \to x_1=x_2)$
5. Def. Funkcja $f:A\to B$ jest surjekcją, jeśli $(\forall b\in B)(\exists a\in A)(f(a)=b)$
6. Tw. Złożenie injekcji jest injekcją
7. Wniosek. Jeśli $f$ jest funkcją, to $f^{-1}$ jest funkcją wtedy i tylko wtedy, gdy $f$ jest injekcją.
8. Tw. Złożenie surjekcji jest surjekcją
9. Def $f$ jest bijekcją, jeśli $f$ jest jednocześnie injekcją i surjekcją
10. Wniosek. Złożenie bijekcji jest bijekcją
11. 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)$
12. Def. Relacja $\sim \subseteq X\times X$ jest relacją równoważności na $X$ jeśli jest zwrotna na $X$, symetryczna i przechodnia
13. Przykład: Na zbiorze liczb całkowitych $\ZZ$ określamy relację $$ x \sim y \IFF 2|(x-y) $$ To jest relacja równoważności na $\ZZ$.
14. 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\}~. $$
15. 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)(\neg(a\sim b) \to [a]_\sim \cap [b]_\sim = \emptyset)$
16. Def. Jeśli $\sim$ jest relacją równoważności na $X$, to $$ X/_\sim = \{[a]:a\in X\} $$
17. Wniosek. Jeśli $\sim$ jest relacją równoważności na $X$, to $$ \bigcup (X/_\sim) = X~. $$

14.11.2018: Relacje równoważności

1. Przykład: Rozważamy relację równoważności na $\ZZ$ określną wzorem $x\sim y \IFF 5|(x-y)$: $[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\}$.
   Mamy: $\ZZ/\sim = \{[0]_\sim,[1]_\sim,[2]_\sim,[3]_\sim,[4]_\sim\}$
2. 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$.
3. Przykład: $\Omega$ = zbiór zwierząt; definiujemy $$ f(x) = (\text{ile nóg ma x},||\text{x ma pióra}||) $$
4. Pobawiliśmy się trochę wstęgą Möbiusa
5. Tw. Niech $\equiv$ będzie relacją równoważności na $\Omega$. Niech $f(x) = [x]_{\equiv}$. Wtedy $f:\Omega \to \Omega/\equiv$ oraz $$ \sim_f \quad = \quad \equiv $$
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. Wniosek: Jeśli $\sim$ jest relacją równoważności na $X$, to $X/_\sim$ jest rozbiciem zbioru $X$
8. Tw. Niech $\mathcal{P}$ będzie partycją zbioru $X$. Wtedy relacja $$ x \sim y \IFF (\exists P\in\mathcal{P})(\{x,y\}\subseteq P) $$ jest relacją równoważności na $X$ oraz $X/\sim = \mathcal{P}$
9. Definicja: Relacja $R$ jest częściowym porządkiem na zbiorzez $X$ jeśli $R$ jest zwrotna na $X$, jest przechodnia i jest słabo-antysymetryczna.
10. Przykłady: standardowa słaba nierówność $\leq$ na $\RR$; podzielność na $\NN$; inkluzja ograniczona do $P(\Omega)$
Zadanie: Wyznacz wszystkie rozbicia zbioru pustego.

20.11.2018: Częściowe porządki

1. Diagramy Hassego
2. 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)$
3. Jeśli $(X,R)$ jest częściowym porządkiem, to $(X,R^{-1})$ jest również częściowym porządkiem.
   (dualność) Jeśli $a$ jest $R$-minimalny to $a$ jest $R^{-1}$-maksymalny, ....
4. Produkt dwóch częściowyc porządków
5. Pojęcie izomorfizmu dwóch częściowych porządków
6. Pojęcie liniowego porządku
7. Def. Liniowy porządek $(L,\leq)$ jest dobrym porządkiem jeśli $$ (\forall A\subseteq L)(A \neq \emptyset \to (\exists a\in A)(\forall x\in A)(x \leq a)) $$
8. Tw. Następujęce zdania są równoważne:
   1. $(\NN,\leq)$ jest dobrym porządkiem
   2. [Indukcja matematyczna] Dla dowolnego $A\subseteq \NN$ jeśli $0\in A$ oraz $$(\forall n)(n \in A) \to n+1\in A)$$ to $A = \NN$.
   3. Nie istnieje ciąg liczb naturalnych $(x_n)_{n\in\NN}$ taki, że $$x_0 \gt x_1 \gt x_2 \gt \ldots.$$

21.11.2018: Indukcja Matematyczna

1. Przykład: $1+2+\ldots+n = \frac{n(n+1)}{2}$
2. Przykład: $1^2+2^2+\ldots+n^2 = \frac16 n(n+1)(2n+1)$
3. Przykład: $1^3+2^3+\ldots+n^3 = \left(\frac{n(n+1)}{2}\right)^2$
4. Przykład: dla dowolnej liczby naturalnej $n$ istnieje ciąg $(p_k)_{k=1\ldots m}$ liczb pierwszych taki, że $$n = p_1\cdot p_2\cdots p_m$$
5. Def. [Równoliczność] $|A| = |B|$ jeśli istnieje bijekcja $f:A\to B$.
6. Podstawowe własności równoliczności:
   1. $|A| = |A|$
   2. Jeśli $|A| = |B|$, to $|B|=|A|$
   3. Jeśli $|A| = |B|$ i $|B|= |C|$ to $|A|=|C|$
7. Def. (zbiory skończone) $|A|=n$ jeśli $|A| = |\{1,2,\ldots,n\}|$
8. Def. (zbiory mocy "alef zero") $|A|=\aleph_0$ jeśli $|A| = |\NN|$
9. Trochę rozmawialiśmy o hotelach Elona Muska na księżycu.
10. Lemat. Jeśli $|A| = n$ i $a\in n$, to $|A\setminus \{a\}| = n-1$
11. Tw. W każdym niepustym skończonym częściowym porządku istnieje element minimalny.

27.11.2019: Indukcja Matematyczna - II

1. Tw. (Zasada Dirichletta; zasada gołębnika). Jeśli $X$, $Y$ są zbiorami skończonymi, $|X|\lt |Y|$ oraz $f:Y\to X$ to $f$ nie jest injekcją.
2. Przykład: W każdym zbiorze pięciu punktów z trójkąta równobocznego istnieją dwa rożne punkty takie $P$ i $Q$ , że $odl(P,Q)\leq \frac12$
3. Zastosowanie: metoda szukania elementów minimalnych w zbiorze skończonym.
4. Tw. Niech $(X,\leq)$ będzie (skończonym) częściowym porządkiem. Istnieje wtedy liniowy porządek $\preceq$ na zbiorze $X$ taki, że $\leq \subseteq \preceq$.
   Uwaga: Twierdzenie to jest prawdziwe bez założenia skończoności zbioru $X$, ale na razie nie mamy środkow do udowodnienia tego w pełnej ogólności.

28.11.2019: Indukcja Matematyczna - III

1. Tw. Niech $X$ będzie zbiorem skończonym. Wtedy następujące zdania są równoważne:
   1. $f$ jest injekcją
   2. $f$ jest surjekcją
2. Oznaczenie: $Sym(X)$ = zbiór wszystkich bijekcji z $X$ w $X$.
3. Tw. Jeśli $|X|=n \in \NN$ to $|Sym(X)| = n!$
4. Załóżmy, że $A$ i $B$ są zbiorami skończonymi. Wtedy
   1. Jeśli $A\cap B=\emptyset$ to $|A\cup B| = |A|+|B|$
   2. $|A\times B| = |A|\cdot|B|$
   3. $\left|B^A\right| = |B|^{|A|}$
   4. $|P(A)| = |\{0,1\}^A| = 2^{|A|}$
5. Oznaczenie: $[n] = \{1,2,\ldots,n\}$
6. Oznaczenie: $[n]^k = \{A\subseteq [n]: |A|=k\}$
7. Definicja: $\binom{n}{k} = \left|[n]^k\right|$
8. Tw. $\binom{n}{k} = \frac{n!}{k!\cdot(n-k)!}$
   Dowód: $$ n! = |Sym([n])| = \sum_{A\in[n]^k}|\{\pi\in Sym([n]):\pi[\{1,\ldots,k\}]=A\}| = ... $$
9. Wniosek: $2^n = \sum_{k=0}^n \binom{n}{k}$

04.12.2019: Aksjomat Wyboru

1. Def. AC = "każda rodzina niepustych i parami rozłącznych zbiorów ma selektor"
2. Def. $\prod_{i\in I}A_i = \{f \in (\bigcup_i A_i)^I: (\forall i\in I)(f(i)\in A_i)\}$
3. Tw. AC jest równoważny następującemu zdaniu: "jeśli $(\forall i\in I)(A_i \neq \emptyset)$ to $\prod_{i\in I} A_i \neq\emptyset$.
4. Def. WOP = "każdy zbiór można dobrze uporządkować".
5. TW. WOP $\Rightarrow$ AC
6. Def. Łańcuch w częściowym porządku: liniowo uporządkowany podzbiór częściowego porządku.
7. Def. (LKZ) W każdym częściowym porządku o następującej własności: "każdy łańcuch ma ograniczenie górne" istnieje element maksymalny.
8. Tw. LKZ $\Rightarrow$ AC
9. UWAGA: Prawdziwe jest twierdzenie: AC $\equiv$ WOP $\equiv$ LKZ, ale na razie nie mamy środków do jego udowodnienia.

05.12.2019: Teoria mocy - I`

1. Tw (AC) w każdej przestrzeni liniowej istnieje baza.
2. Def. $(|X| \leq |Y|) \IFF (\exists f)(f:X \stackrel{1-1}{\rightarrow} Y)$
3. Def. $(|X| \lt |Y|) \IFF ((|X| \leq |Y|) \land \neg (|X|=|Y|))$
4. Tw. [Cantor] $(\forall X)(|X| \lt |P(X)|)$
5. Przykład: $|\NN| \lt |P(\NN)| \lt |P(P(\NN))| \lt |P(P(P(\NN)))| \lt \ldots$.

11.12.2019: Teoria mocy - II

1. Tw [Cantor-Berstein] Jeśli $|X|\leq|Y|$ i $|Y|\leq|X|$ to $|X|=|Y|$.
2. Def. Zbiór $A$ jest przeliczalny jeśli $A=\emptyset$ lub istnieje surjekcja z $\NN$ na $A$.
3. Tw. Zbiór jest przeliczalny wtedy i tylko wtedy, gdy jest skończony lub jest mocy $\aleph_0$.
4. Tw. $|\NN\times\NN| = \aleph_0$
   Dowód: rozważamy funkcję $f((n,m)) = 2^n(2m+1)-1$.
5. Tw. Jeśli $|A_1|=|A_2|$ i $|B_1|=|B_2|$, to $|A_1\times B_1|=|A_2\times B_2|$.
6. Tw. $|\QQ| = \aleph_0$.