Rachunek zbiorów

\(\def\RR{\mathbb{R}}
\def\pot#1{{\sf P}(#1)}
\def\<{\langle}
\def\>{\rangle}
\def\incl{\subseteq}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\tz{\;\;|\;\;}
\)

Zadanie 1

Zaznacz na rysunku zbiory:

1. \(\{\< x, y\> \in \RR^2 \tz (x^2+y^2 > 1) \Rightarrow (y+x > 0)\}\),
2. \(\{x \in \RR \tz (x^2<0) \Rightarrow (x^2 >0)\}\),
3. \(\{x \in \RR \tz \forall x \; (x^2 > 0)\}\),
4. \(\{x \in \RR \tz \exists z \forall y \;(y > (x-z)^2)\}\),
5. \(\{\< x, y\> \in \RR^2 \tz (x^2+y^2 > 1) \Rightarrow \exists z (x^2 + (y-z)^2 < \frac{1}{4})\}\).

Zadanie 2

Udowodnij, że dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzi równość:

1. \(A = (A \cap B) \cup (A - B) \),
2. \(A \cap (B \cup C)= (A \cap B) \cup (A \cap C) \),
3. \(A - (B \cup C)= (A - B) \cap (A - C) \),
4. \((A \cup B) - C = (A - C) \cup (B - C) \).

Zadanie 3

Sprawdź czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzi następująca implikacja:

1. jeśli \(A \cup B = A \cup C\) to \(B = C\),
2. jeśli \(A - B = A - C\) to \(B = C\),
3. jeśli \(A - B = B - A\) to \(A = B\).

Zadanie 4

Sprawdź czy dla dowolnych zbiorów \(A\), \(B\), \(C\), \(D\) zachodzi następująca implikacja:

1. jeśli \(A \incl B\) to \(A \cap B = A\),
2. jeśli \(A \incl B\) i \(C \incl D\) to \(A \cap C \incl B \cap D\),
3. jeśli \(A \incl B\) to \(C- B \incl C - A\),
4. jeśli \(A \incl B\) to \( -A \supseteq -B\).

Zadanie 5

Sprawdź czy dla dowolnych zbiorów \(A\) i \(B\) zachodzi:

1. \(\pot{A \cup B} = \pot{A} \cup \pot{B}\),
2. \(\pot{A \cap B} = \pot{A} \cap \pot{B}\).

Zadanie 6

Udowodnij, że dla dowolnych zbiorów \(A\) i \(B\), zawieranie \(A \incl B\) zachodzi wtedy i tylko wtedy gdy \(\pot{A} \incl \pot{B}\).

Zadanie 7 (przykład z wykładu)

Udowodnij, że dla dowolnego zbioru \(A\) zachodzi \(\bigcup\pot{A} = A\).

Zadanie 8

Niech \(\A \incl \pot{\RR}\) będzie rodziną zbiorów spełniających warunek \(\forall B \in \A \;\forall C \incl \RR (C \incl B \Rightarrow C \in A)\). Udowodnij, że \(\bigcup \A = \{z \in \RR \tz \{z\} \in \A\}\).

Zadanie 9

Sprawdź czy dla dowolnych rodzin zbiorów \(\A\) i \(\B\) zachodzi implikacja:

1. jeśli \(\A \incl \B\) to \(\bigcup \A \incl \bigcup \B\),
2. jeśli \(\A \incl \B\) to \(\bigcap \A \supseteq \bigcap \B\).

Zadanie 10

Udowodnij, że dla dowolnych rodzin zbiorów \(\A\) i \(\B\) zachodzi \(\bigcup (\A \cup \B) = (\bigcup \A) \cup (\bigcup \B)\). Czy zachodzi równość \(\bigcup (\A \cap \B) = (\bigcup \A) \cap (\bigcup \B)\)?

Zadanie 11

Rodzina zbiorów \(\A\) jest łańcuchem jeśli dla każdych \(X,Y \in \A\) zachodzi \(X \incl Y\) lub \(Y \incl X\). Udowodnij, że:

1. iloczyn dowolnej niepustej rodziny łańcuchów jest łańcuchem,
2. suma łańcucha łańcuchów jest łańcuchem.

Funkcje

\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\pot#1{{\sf P}(#1)}
\def\<{\langle}
\def\>{\rangle}
\def\incl{\subseteq}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\tz{\;\;|\;\;}
\def\to{\rightarrow}
\def\poz{\vphantom{f}}
\def\pusty{\varnothing}
\)

Zadanie 0

Dla podanych poniżej \(A\) i \(B\) odpowiedz ile jest funkcji z \(A\) w \(B\), funkcji częściowych z \(A\) w \(B\), funkcji różnowartościowych z \(A\) w \(B\), funkcji z \(A\) na \(B\).

1. \(A=\pusty\), \(B=\pusty\)
2. \(A=\pusty\), \(B=\{b\}\)
3. \(A=\{a\}\), \(B=\pusty\)
4. \(A=\{a\}\), \(B=\{b\}\)
5. \(A=\{a\}\), \(B=\{b_1,b_2\}\)
6. \(A=\{a_1,a_2\}\), \(B=\{b_1,b_2\}\)

Zadanie 1

Udowodnij, że jeśli \(f:A \to B\) i \(g:B \to C\) są funkcjami różnowartościowymi to \(g \circ f: A \to C\) też jest funkcją różnowartościową.

Zadanie 2

Niech \(f : A \to B\). Udowodnij, że \(f\) jest na \(B\) wtedy i tylko wtedy gdy dla dowolnego \(C\) i dowolnych \(g,h : B\to C\) zachodzi implikacja \(g\circ f = h \circ f \to g = h\).

Zadanie 3

Podaj przykład \(A\), \(B\), \(f:A\to B\), \(X \subseteq A\) i \(Y \subseteq B\), takich że:

1. \(f\poz^{-1}(f(X)) \not = X\)
2. \(f( f\poz^{-1}(Y))\not= Y\)

Zadanie 4 (przykład z wykładu - pierwsza część)

Niech \(f : \pot{\NN} \times \pot{\NN} \to \pot{\NN}\) będzie taka, że \(f(\< C,D \> ) = C \cap D\) dla dowolnych \(C, D \subseteq \NN\). Czy \(f\) jest różnowartościowa i czy jest na \(\pot{\NN}\)?
Dla \(B \subseteq \NN\) znaleźć \(f(\pot{B} \times \pot{B})\) i \( f\poz^{-1}(\{\NN\})\).

Zadanie 5

Niech \(f : A^{A} \to \pot{A}\) będzie taka, że \(f(\varphi) =\varphi(A)\). Dla jakich zbiorów \(A\) ta funkcja jest różnowartościowa, a dla jakich zbiorów \(A\) jest na \(\pot{A}\)?

Zadanie 6

Niech \(F : \NN^{\NN}\to \pot{\NN}\) będzie taka, że \(F(f) = f\poz^{-1}(\{1\})\). Czy \(F\) jest różnowartościowa i czy jest na \(\pot{\NN}\)? Znajdź obraz zbioru funkcji stałych i przeciwobraz zbioru \(\{\{10\}\}\).

Zadanie 7 (przykład z wykładu)

Pokaż, że funkcja \(\varphi : \pot{A\times B} \to \pot{A}^B\) taka, że dla dowolnych \(\Delta\in \pot{A\times B},\ b\in B\),

\( \varphi(\Delta)(b) = \{a\in A : \< a, b\> \in\Delta\}\)
jest różnowartościowa i na \(\pot{A}^B\).

Zadanie 8

Znajdź przykład \(f:\NN\to\NN\), takiej że przeciwobraz każdego zbioru jednoelementowego jest:

1. jednoelementowy
2. dwuelementowy
3. nieskończony.

Zadanie 9

Które z poniższych zdań są prawdziwe, a które fałszywe?

1. \(\forall f \in\NN^{\NN}\, \exists B\subseteq\NN
   ( f\poz^{-1}(B)\not=\pusty \wedge B\not=\NN)\)
2. \(\exists B\subseteq\NN\, \forall f\in\NN^{\NN}
   ( f\poz^{-1}(B)\not=\pusty \wedge B\not=\NN)\)
3. \(\exists f \in\NN^{\NN}\, \forall B\subseteq\NN
   ( f\poz^{-1}(B)\not=\pusty \to B=\NN)\)
4. \(\forall B\subseteq\NN\, \exists f \in\NN^{\NN}
   ( f\poz^{-1}(B)\not=\pusty \to B=\NN)\)

Zadanie 10 (równoliczność)

Udowodnij, że \(\NN \times \NN\) i \(\NN\) są równoliczne używając funkcji \(f(\< m,n \>) = 2^m*(2*n+1)-1\).

Zadanie 11 (równoliczność)

Udowodnij, że jeśli \(A \sim B\) to \(\pot{A} \sim \pot{B} \).

Zadanie 12 (równoliczność)

Udowodnij, że \((A^B)^C \sim A^{C\times B}\).

Moce

\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\r{\,r\,}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\poz{\vphantom{f}}
\def\alz{\aleph_0}
\def\C{{\mathfrak C}}
\def\card#1{\overline{\overline{#1}}}
\)

Zadanie 1

Jaka jest moc zbioru wszystkich odcinków o końcach wymiernych na prostej rzeczywistej?

Zadanie 2

Jaka jest moc zbioru wszystkich skończonych podzbiorów \(\NN\)?

Zadanie 3

Jaka jest moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca?

Zadanie 4

Jakiej mocy jest podzbiór płaszczyzny ograniczony krzywymi o równaniach \(y = x^2\) i \(y = 1 - x^2\)?

Zadanie 5

Niech \(A\) i \(B\) będą zbiorami mocy \(\C\). Jakie są moce zbiorów \(A \cup B\) i \(A \times B\)?

Zadanie 6

Udowodnij, że jeśli moc każdego ze zbiorów \(A_t\), dla \(t \in \RR\), wynosi \(\C\) to zbiór \(\bigcup_{t \in \RR} A_t\) jest również mocy \(\C\).

Zadanie 7

Jaka jest moc zbioru funkcji z \(\NN\) do \(\NN\) (a) nierosnących? (b) niemalejących?

Zadanie 8

Udowodnij, że jeśli \(A\) jest zbiorem nieskończonym, a \(B\) przeliczalnym to \(A \cup B \sim A\). Wywnioskuj, że moc zbioru liczb niewymiernych jest \(\C\).
Wskazówka: Każdy zbiór nieskończony ma podzbiór mocy \(\alz\).

Zadanie 9

Niech \(A \subseteq \pot{\NN}\) będzie taką rodziną zbiorów, że dwa dowolne elementy tej rodziny są rozłączne. Jaka co najwyżej jest moc zbioru \(A\) ?

Zadanie 10

Niech \(A \subseteq \pot{\NN}\) będzie taką rodziną zbiorów, że dwa dowolne elementy tej rodziny mają co najwyżej jeden element wspólny. Jaka co najwyżej jest moc \(A\) ?

Zadanie 11

Niech \(A\) będzie taką rodziną przedziałów na prostej rzeczywistej, że dowolne dwa przedziały z tej rodziny są rozłączne. Udowodnij, że \(A\) jest przeliczalna.

Zadanie 12

Punkt \(x\) jest właściwym maksimum lokalnym funkcji \(f:\RR \to \RR\) jeśli

\(\exists \epsilon\! >\! 0\, \forall y \not = x \quad (|y-x|<\epsilon \Rightarrow f(y) < f(x))\)
Czy zbiór ekstremów lokalnych funkcji ciągłej z \(\RR\) w \(\RR\) może być nieprzeliczalny?

Zadanie 13

Niech \(f : \RR^3 \to \RR\). Udowodnij, że istnieje takie \(x\in \RR\), że zbiór \(f\poz^{-1}(\{x\})\) nie zawiera żadnej kuli.

Zadanie 14

Jaka jest moc zbioru wszystkich funkcji ciągłych z \(\RR\) w \(\RR\)?

Zadanie 15

Jaka jest maksymalna moc zbioru punktów nieciągłości funkcji niemalejącej z \(\RR\) w \(\RR\)?

Relacje

\(\def\RR{\mathbb{R}}
\def\NN{\mathbb{N}}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\incl{\subseteq}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\R{{\cal R}}
\def\tz{\;\;|\;\;}
\)

Zadanie 1 (iloczyn kartezjański)

Znajdź iloczyn kartezjański \(A \times B\), gdzie

1. \(A = \{a\}\), \(B = \{b\}\),
2. \(A = \emptyset\), \(B = \emptyset\),
3. \(A = \emptyset\), \(B = \{b\}\),
4. \(A = \{a\}\), \(B = \{b,c\}\),

Zadanie 2 (zbiór wszystkich relacji)

Dla przykładów \(A\) i \(B\) z poprzedniego zadania podaj zbiór wszystkich relacji w \(A \times B\).

Zadanie 3

Niech \(R, S \subseteq A \times A\). Czy z tego, że \(R \cdot S = S \cdot R\) wynika, że \(R=S\) lub \(R =1_A\) lub \(S =1_A\) ?

Zadanie 4

Znajdź przykład 5-elementowej relacji symetrycznej w zbiorze \(\NN\). Czy istnieje 5-elementowa relacja zwrotna w \(\NN\)? A 5-elementowa relacja przechodnia?

Zadanie 5

Niech \(R\) będzie relacją dwuargumentową w zbiorze \(A\). Czy możliwe jest, że

1. \(R^{-1}\subseteq R\) i \(R \not = R^{-1}\)?
2. \(R^{-1} = A\times A - R\)?

Zadanie 6

Niech \(\R\) będzie niepustą rodziną relacji w \(B\times C\) i niech \(s \subseteq A \times B\). Udowodnij, że:

1. \(s \cdot (\bigcup \R) = \bigcup \{s \cdot r \tz r \in \R\}\),
2. \(s \cdot (\bigcap \R) \subseteq \bigcap \{s \cdot r \tz r \in \R\}\). Czy \(\subseteq\) można zastąpić przez \(=\)?
3. \( (\bigcup \R)^{-1} = \bigcup \{ r^{-1} \tz r \in \R\}\),
4. \( (\bigcap \R)^{-1} = \bigcap \{ r^{-1} \tz r \in \R\}\),

Zadanie 7

Czy suma, iloczyn i złożenie dwóch relacji symetrycznych jest relacją symetryczną ? To samo pytanie może być też postawione dla relacji zwrotnych, przechodnich, antysymetrycznych i spójnych.

Zadanie 8

Udowodnij, że suma łańcucha relacji przechodnich jest relacją przechodnią.

Zadanie 9

Niech \(r\) będzie relacją dwuargumentową w zbiorze \(\NN^\NN\) określoną następująco:

\(\la f, g \ra \in r \quad \Leftrightarrow \quad \forall n:\NN\, (f(n) \,|\, g(n) \lor g(n) \,|\, f(n))\)
Czy relacja \(r\) jest zwrotna, symetryczna, przechodnia, antysymetryczna? Czym jest \(r \cdot r\) ?

Zadanie 10 (najczęściej robione na wykładzie)

Niech \(r\) będzie relacją dwuargumentową w zbiorze \(A\) i niech \(r^+\) (najmniejsza relacja przechodnia zawierająca \(r\)) będzie zdefiniowana wzorem \(r^+=\bigcap \{s \tz r \subseteq s \land s\) jest relacją przechodnią w \(A\}\). Udowodnij, że \(r^+ = \bigcup \{r^n \tz n \in \NN-\{0\}\}\), gdzie \(r^1 = r\) i \(r^{n+1} = r \cdot r^n\).

Zadanie 11

Dla relacji \(r \subseteq A \times A\), niech \(f_r : N \to N\) będzie funkcją daną wzorem \(f_r(n) = r^n\), gdzie \(r^n = r \cdot \ldots \cdot r\) oznacza \(n\)-krotne złożenie relacji \(r\) (przy czym \(r^0 = id_A\)). Dla jakich \(r\) ciąg \(\{f_r(i)\}_{i\in\NN}\) jest wstępujący (tj. dla każdego \(i \in \NN\) zachodzi \(f_r(i) \subseteq f_r(i+1)\)) ?

Porządki częściowe

\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\QQ{\mathbb{Q}}
\def\r{\,r\,}
\def\R{\cal R}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\fczesc{\mathrel{{-}\mskip-2.7mu{\circ}\mskip-2.7mu{\rightarrow}}}
\def\poz{\vphantom{f}}\)

Zadanie 1

Podaj przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi i jednym minimalnym, bez elementu najmniejszego i z takim czteroelementowym antyłańcuchem, który jest ograniczony z góry ale nie ma kresu górnego.

Zadanie 2

W zbiorze \(\{2,3,4,5,6,8,9,12,24\}\), uporządkowanym częściowo przez relację podzielności (\(m \preceq n\) wtedy i tylko wtedy gdy \(n = m\cdot k\), dla pewnego \(k \in \NN\)) wskaż wszystkie elementy minimalne, maksymalne, największe i najmniejsze. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy?

Zadanie 3

Niech \(r \subseteq \NN^\NN\times \NN^\NN\) będzie relacją określoną następująco: \(f\r g \Leftrightarrow \forall_{n \in \NN} \; f(n) \leq g(n)\). Udowodnij, że \(\la\NN^\NN, r\ra\) to częściowy porządek. Wskaż elementy minimalne, najmniejsze, maksymalne, największe, nieskończony łańcuch, nieskończony antyłańcuch. Czy jest to porządek liniowy? Czy jest gęsty?

Zadanie 4

Rozpatrzmy zbiór \(\{0,1\}^*\) z porządkiem leksykograficznym \(\preceq_{lex}\). Znajdź kres górny i dolny (jeśli istnieją) dla następujących zbiorów:

1. \(A=\{01^n \; | \; n \in \NN\}\)
2. \(B=\{0^n1 \; | \; n \in \NN\}\)
3. \(C=\{w \in \{0,1\}^* \; | \; \textrm{liczba zer i jedynek w słowie}\; w\; \textrm{jest taka sama}\}\)
4. \(D=C-\{\epsilon\}\)
5. \(E=\{0,1\}^* - C\)

Zadanie 6

Jak zmienią sie odpowiedzi gdy kresy powyższych zbiorów będą szukane w częściowym porządku \(\la\{0,1\}^\NN \cup \{0,1\}^*, \preceq_{lex}\ra\), gdzie \(\{0,1\}^\NN \cup \{0,1\}^*\) jest zbiorem słów skończonych lub nieskończonych nad alfabetem \(\{0,1\}\), a \(w \preceq_{lex} v\) zachodzi wtedy i tylko wtedy gdy \(w\) jest prefiksem \(v\) lub gdy istnieje pozycja \(i\) taka, że \(w_i=0\) i \(v_i=1\)?

Zadanie 7

Które z następujacych stwierdzeń są prawdziwe dla dowolnego porządku \(\la X,\leq\ra\) i dowolnych \(A,B\subseteq X\):

1. Jeśli istnieje \(\sup(A\cup B)\), to istnieją \(\sup A\) i \(\sup B\)?
2. Jeśli istnieją \(\sup A\) i \(\sup B\), to istnieje \(\sup(A\cup B)\)?
3. Jeśli istnieją \(\sup A\), \(\sup B\) i \(\sup(A\cup B)\), to \(\sup(A\cup B)=\sup\{\sup A,\sup B\}\)?

Zadanie 8

Niech \(A\) i \(B\) będą zbiorami częściowo uporządkowanymi i niech funkcje \(f:A\to B\) oraz \(g:B\to A\) będą monotoniczne. Udowodnić, że następujące warunki są równoważne:

1. \(\forall a{\in}A\;\forall b{\in}B\;(a\leq g(b) \Leftrightarrow f(a)\leq b)\);
2. \(\forall a{\in}A\;(a\leq g(f(a)))\) oraz \(\forall b{\in}B\;(f(g(b))\leq b)\).

Zadanie 9

Niech \(A\) będzie dowolnym zbiorem i niech \(B \subseteq A \times A\). Udowodnij, że istnieje maksymalny zbiór \(C \subseteq A\) taki, że \(C\times C \subseteq B\).

Zadanie 10

Udowodnij, że każdy częściowy porządek można rozszerzyć do liniowego.

Zadanie 11

Niech \(A\) będzie dowolnym zbiorem do którego należą \(0\) i \(1\) i niech \(f: \pot{A^*} \to \pot{A^*}\) będzie określona następująco

\(f(X)=\{\epsilon\} \cup X \cup \{0w \; | \; w \in X\} \cup \{1w \; | \; w \in X\}\)

Udowodnij, że \(f\) jest monotoniczna, zbadaj jakie są jej punkty stałe i udowodnij, że \(\{0,1\}^*\) jest jej najmniejszym punktem stałym.

Zadanie 12 (omawiane na wykładzie)

Rozważmy częściowy porządek \(\la A \fczesc B, \subseteq\ra\), gdzie \(A \fczesc B)\) to zbiór funkcji częściowych z \(A\) do \(B\) i \(f \, \subseteq\, g\) wtedy i tylko wtedy gdy dla każdego \(a \in A\) albo \(f(a)\) jest nieokreślone, albo obie funkcje \(f\) i \(g\) są określone w \(a\) i \(f(a)=g(a)\). Czy \(\la A \fczesc B, \subseteq\ra\) jest kratą zupełną?

Zadanie 13 (omawiane na wykładzie)

Udowodnij, że porządek \(\la A \fczesc B, \subseteq\ra\) zdefiniowany powyżej jest zupełny.

Zadanie 14

Niech \(A = \{3 - {1\over 2n} \;|\; n \in \NN - \{0\}\}\), \(B = \{\pi - {2\over n} \;|\; n \in \NN - \{0\}\}\cup \{4\}\), \(C = \{0\} \cup \{{1\over n} \;|\; n \in \NN - \{0\}\}\cup \{2 - {1\over n} \;|\; n \in \NN - \{0\}\}\). Rozpatrzmy zbiory \(A\), \(B\), \(A \cup B\), \(C\), \(\NN\), \(\ZZ\), \(\QQ\), \(\QQ - \{0\}\), \(\RR\), \(\RR - \{0\}\) uporządkowane liniowo przez zwykłą relację ,,\(\leq\)''. Które z nich są izomorficzne?

Relacje równoważności

\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\ZZ{\mathbb{Z}}
\def\r{\,r\,}
\def\R{\cal R}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\poz{\vphantom{f}}
\def\alz{\aleph_0}
\def\C{{\mathfrak C}}
\def\card#1{\overline{\overline{#1}}}
\)

Zadania wstępne

Zadanie A

Dla podanych poniżej \(A\) i \(r\), sprawdź czy \(r\) jest relacją równoważności na \(A\).

1. \(A=\RR\;, x \r y \Leftrightarrow x^2 = y^2\),
2. \(A=\RR\;, x \r y \Leftrightarrow x^2 \not = y^2\),
3. \(A=\ZZ\;, x \r y \Leftrightarrow x \leq y\),
4. \(A=\pot{\NN}\;, x \r y \Leftrightarrow x \cap \textrm{Parz}= y \cap \textrm{Parz}\), gdzie \(\textrm{Parz}\) to zbiór wszystkich liczb parzystych.

Zadanie B

Czy częściowy porządek może być relacją równoważności?

Zadanie C

Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w danym zbiorze?

Zadanie D

Które z następujących relacji to relacje równoważności w \(\RR\)?

1. \(\{\la x,y\ra \;|\; xy \geq 0\}\),
2. \(\{\la x,y\ra \;|\; xy > 0\}\),
3. \(\{\la x,y\ra \;|\; x^2-5y+1=y^2-5x+1\}\),
4. \(\{\la x,y\ra \;|\; (x \leq 1 \land y \leq 1) \lor (x > 1 \land y > 1) \}\),
5. \(\{\la x,y\ra \;|\; (x\leq 1 \land y \leq 1) \lor (x\geq 1 \land y \geq 1) \}\).

Zadanie E

Które z następujących relacji to relacje równoważności w zbiorze \(A=\{2,3,4,5\}\)?
A które w zbiorze \(A=\{2,3,4,5,6\}\)?

1. \(\{ \la a,b\ra \;|\; a=b \lor a+b \in A \}\),
2. \(\{ \la a,b\ra \;|\; a=b \lor ab \leq 7 \}\),
3. \(\{ \la a,b\ra \;|\; a|b \lor b|a \}\).

Zadanie F

Czy istnieje relacja równoważności na \(\NN\) która ma:

1. 22 klasy abstrakcji a w każdej klasie po 37 elementów? (było na wykładzie)
2. 2 klasy abstrakcji po 17 elementów, 5 klas po 33 elementy i jedną nieskończoną?
3. nieskończenie wiele nieskończonych klas abstrakcji?

Zadania

Zadanie 1

Niech \(r\) będzie relacją binarną w \(\NN^\NN\) taką, że \(f \r g\) wtedy i tylko wtedy gdy dla każdego \(n \in \NN\) różnica \(f(n) - g(n)\) jest parzysta. Udowodnij, że \(r\) jest relacją równoważności. Jaka jest moc klasy abstrakcji funkcji identycznościowej? Jaka jest moc zbioru wszystkich klas abstrakcji?

Zadanie 2

Niech \(A\) będzie niepustym zbiorem i niech \(f : A \to A\).

1. Udowodnij, że jeśli \(f\) jest różnowartościowa to relacja \(r\subseteq A\times A\), dana warunkiem
   \(x \r y \quad \Leftrightarrow \quad \exists n\in\NN (f^n(x) = y \vee f^n(y) = x)\)
   jest relacją równoważności.
2. Czy prawdziwe jest twierdzenie odwrotne, tj. czy jeśli \(r\) jest relacją równoważności to \(f\) musi być różnowartościowa?
3. Podaj przykład takich \(A\) i \(f\), że \(r\) ma nieskończenie wiele skończonych klas abstrakcji, każda o innej liczbie elementów. (Można zrobić rysunek.)

Zadanie 3

Czy suma, przecięcie i złożenie dwóch relacji równoważności jest zawsze relacją równoważności?

Zadanie 4

Udowodnij, że dla każdego \(A\) i dowolnej relacji binarnej \(r\) na \(A\) istnieje najmniejsza relacja równoważności zawierająca \(r\).

Zadanie 5

Niech \(r\) będzie relacją równoważności w zbiorze \(\NN\), i niech \(f : \NN \times\NN \to \pot{\NN}\) będzie taka, że \(f(\la x, y\ra) = [x]_r \cup [y]_r\), dla dowolnych \(x, y \in \NN\). Czy funkcja \(f\) jest różnowartościowa? Czy jest na \(\pot{\NN}\)? Znajdź \(f\poz^{-1}(\{[3]_r\})\) oraz \(f(r)\).

Zadanie 6

Niech \(\R\) będzie zbiorem wszystkich relacji równoważności w \(\NN\) i niech \(f : \R \to \pot{\NN}\) będzie taka, że \(f(r) = [1]_r\), dla dowolnego \(r \in \R\). Znajdź \(\bigcup_{r\in\R}f(r)\) i \(\bigcap_{r\in\R}f(r)\).

Zadanie 7

Jaka jest moc zbioru wszystkich relacji równoważności w \(\NN\)?

Zadanie 8

Czy istnieje taka relacja równoważności \(r\) w zbiorze \(\RR\), w której:
(a) każda klasa abstrakcji jest mocy \(\alz\) oraz \(\card{\RR/r} = \alz\) ?
(b) każda klasa abstrakcji jest mocy \(\alz\) oraz \(\card{\RR/r} = \C\) ?
(c) każda klasa abstrakcji jest mocy \(\C\) oraz \(\card{\RR/r} = \alz\) ?
(d) każda klasa abstrakcji jest mocy \(\C\) oraz \(\card{\RR/r} = \C\) ?

Dobre ufundowanie

\(\def\NN{\mathbb{N}}
\def\RR{\mathbb{R}}
\def\r{\,r\,}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\poz{\vphantom{f}}
\def\alz{\aleph_0}
\def\C{{\mathfrak C}}
\def\card#1{\overline{\overline{#1}}}
\)

Zadanie 1

Czy zbiór \(\NN^*\) uporządkowany leksykograficznie jest dobrze ufundowany? A zbiór \(\NN^2\)?

Zadanie 2

Udowodnij, że jeśli \(\la A, \leq_A\ra\) oraz \(\la B, \leq_B\ra\) są dobrze ufundowane i \(A \cap B = \emptyset\) to porządek \(\la A \cup B, \leq\ra\) zdefiniowany następująco

\(x \leq y\; \Leftrightarrow \;\;x \leq_A y \; \vee \;x \leq_B y \;\vee \; (x \in A \wedge y \in B)\)
jest dobrze ufundowany.

Zadanie 3

Udowodnij, że jeśli zbiór \(X\) jest co najmniej trzyelementowy i \(\la X, \leq\ra\) jest dobrze uporządkowany (liniowy i dobrze ufundowany) to nie jest gęsty.

Zadanie 4

Udowodnij, ze jeśli \(f: A \to B\) jest monotoniczną bijekcją pomiedzy dobrymi porządkami \(\la A, \leq_A\ra\) i \(\la B, \leq_B\ra\) to funkcja odwrotna \(f^{-1}\) też jest monotoniczna. Czy założenie, że \(\la A, \leq_A\ra\) i \(\la B, \leq_B\ra\) są dobrymi porządkami jest istotne?

Zadanie 5

Podaj trzy przykłady dobrych porządków mocy \(\alz\), tak aby żadne dwa nie były ze sobą izomorficzne.

Zadanie 6

Niech \(A\subseteq\RR\) będzie dobrze uporządkowany przez zwykłą relację nierówności dla liczb rzeczywistych. Udowodnić, że \(A\) jest zbiorem przeliczalnym.

Zadanie 7

Załóżmy, że \(\la A, \leq_1\ra\) i \(\la A, \leq_2\ra\) są dobrze ufundowane i takie, że \(\leq_1 \cup \leq_2\) jest częściowym porządkiem. Udowodnij, że \(\la A, (\leq_1 \cup \leq_2)\ra\) jest porządkiem dobrze ufundowanym.
Wskazówka: wykorzystaj fakt, że \(\leq_1 \cup \leq_2\) jest przechodnia.

Zadanie 8

Niech \(\la A, \leq\ra\) będzie zbiorem dobrze ufundowanym, w którym wszystkie antyłańcuchy są skończone. Niech \(\{a_i\}_{i\in\NN}\) będzie dowolnym ciągiem elementów \(A\). Udowodnij, że istnieją takie liczby \(i,j\), że \(i < j\) oraz \(a_i\leq a_j\).

Zadanie 9

Mówimy, że relacja częściowego porządku \(\leq\) w zbiorze \(A\) jest bardzo dobrym ufundowaniem, jeżeli w każdym ciągu nieskończonym \(\{a_n\}_{n\in\NN}\) można wskazać takie \(i < j\), że \(a_i\leq a_j\). Udowodnij, że jeśli \(A\) jest bardzo dobrze ufundowany przez relację \(\leq\), to każdy ciąg nieskończony w \(A\) ma nieskończony podciąg wstępujący \(a_{i_1}\leq a_{i_2}\leq a_{i_3}\leq \cdots\)

Logika

\(\def\NN{\mathbb N}
\def\QQ{\mathbb Q}
\def\RR{\mathbb R}
\def\ZZ{\mathbb Z}
\def\A{{\cal A}}
\def\[{\langle}
\def\]{\rangle}
\def\oto{\leftrightarrow}\)

Logika zdaniowa

Zadanie 1

Zbadać, czy następujące formuły są tautologiami rachunku zdań i czy są spełnialne:

1. \((p\to r)\wedge(q\to s)\wedge(\neg p\vee \neg s)\to (\neg p\vee \neg q)\);
2. \(((p\to q)\vee r)\wedge(\neg p\to r)\);
3. \((p\to q)\vee(q\to r)\vee(r\to p)\);
4. \(((p\vee q)\to r)\to (p\to r)\vee(q\to r)\);
5. \((p\to q)\wedge(\neg p\to r)\to (r\to\neg q)\);
6. \(((\neg p\to q)\to r)\to \neg(p\to q)\);
7. \((((p\to q)\to r)\to \neg p)\to \neg q\);
8. \(((p\to q)\to p)\to q\);
9. \(p\vee(\neg p\wedge q)\vee(\neg p\wedge\neg q)\);
10. \((p\to q)\vee (p\to \neg q)\);
11. \((p\wedge q\to r)\to (p\wedge \neg r)\to \neg q\);
12. \(q\vee r\to (p\vee q\to p\vee r)\);
13. \((p\vee q\vee r)\wedge(q\vee(\neg p\wedge s))\wedge (\neg s\vee q\vee r)
    \to q\).

Zadanie 2

Znaleźć (o ile istnieje) taką formułę zdaniową \(\alpha\), aby następująca formuła była tautologią rachunku zdań:

1. \(((r\to (\neg q\wedge p))\to\alpha)\to (\alpha\wedge(p\to q)\wedge r)\);
2. \((\alpha\to p)\to(p\to q)\);
3. \(((p\to\alpha)\to q)\to(q\to(\neg p\to\neg\alpha))\);
4. \((\alpha\to p)\wedge(\neg\alpha\to q)\);
5. \(((\alpha\wedge q)\to\neg p)\to((\alpha\to p)\to\neg q)\);
6. \(((\neg\alpha\to p)\to q)\to(\alpha\wedge q\to \neg p)\);
7. \(((\alpha\to p)\wedge q)\to(\alpha\vee q\to p)\);
8. \(((\alpha\to p)\wedge q)\to(\alpha\vee q\to \neg p)\).

Zadanie 3

Udowodnić, że dla dowolnej funkcji \(f:\{0,1\}^k\to\{0,1\}\) istnieje formuła \(\alpha\), w której występują tylko zmienne zdaniowe ze zbioru \(\{p_1,\ldots, p_k\}\), o tej własności, że dla dowolnego wartościowania zdaniowego \(v\) zachodzi równość \(v(\alpha) = f(v(p_1),\ldots, v(p_k))\). (Inaczej mówiąc, formuła \(\alpha\) definiuje funkcję zerojedynkową \(f\).)

Logika I rzędu

Zadanie 4

W strukturze \(\A =\[\NN, P^\A, Q^\A\]\), gdzie:
\(\[a,b\]\in P^\A\) wtedy i tylko wtedy, gdy \(a+b\geq 6\);
\(\[a,b\]\in Q^\A\) wtedy i tylko wtedy, gdy \(b=a+2\),
wyznaczyć wartość formuł:

1. \(\forall x P(x,y) \to \exists x Q(x,y)\);
2. \(\forall x P(x,y) \to \forall x Q(x,y)\);
3. \(\forall x P(x,y) \to \exists x Q(x,z)\);

przy wartościowaniach \(v(y) = 7\), \(v(z) = 1\) oraz \(u(y)= 3, u(z) = 2\).

Zadanie 5

Podaj przykład modelu i wartościowania, przy którym formuła
\(P(x,f(x)) \to \forall x\exists y P(f(y),x)\)
jest: a) spełniona; b) nie spełniona.

Zadanie 6

Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):

1. \(\[\QQ,+,\cdot,0,1\]\) i \(\[\RR,+,\cdot,0,1\]\);
2. \(\[\NN,+,0\]\) i \(\[\NN, \cdot, 1\]\);
3. \(\[P_2, \parallel\]\) i \(\[P_2, \bot\]\), gdzie \(P_2\) oznacza zbiór wszystkich prostych w \(\RR^2\);
4. \(\[P_2, \bot\]\) i \(\[P_3, \bot\]\), gdzie \(P_2\) i \(P_3\) to odpowiednio zbiory wszystkich prostych w \(\RR^2\);
5. \(\[\RR, +, \cdot, 0,1\]\) i \(\[P(\NN), \cup, \cap, \emptyset, \NN\]\);
6. \(\[\NN,\leq,0\]\) i \(\[\ZZ, \leq, 0\]\);
7. \(\[\NN,+,0\]\) i \(\[\{a,b\}^*,\cdot,\varepsilon\]\),
8. \(\[\NN,+,0\]\) i \(\[\NN^2, \#, \[0,0\]\]\), gdzie operacja \(\#\) jest określona tak: \(\[a,b\]\#\[c,d\] = \[a+c, b+d\]\).

Zadanie 7

Sygnatura \(\Sigma\) składa się z symbolu równości, jednoargumentowych symboli relacyjnych \(R, S\) i jednego jednoargumentowego symbolu funkcyjnego \(f\). Napisać takie zdania \(\varphi\) i \(\psi\), że:

1. zdanie \(\varphi\) jest prawdziwe dokładnie w tych modelach, \(\A = \[A, R^{\A}, S^{\A}, f^{\A}\]\), w których obraz zbioru \(R^{\A}\) przy funkcji \(f^\A\) zawiera się w zbiorze \(S^{\A}\).
2. zdanie \(\psi\) jest prawdziwe dokładnie w tych modelach \(\A = \[A, R^{\A}, S^{\A}, f^{\A}\]\), w których zbiór \(S^{\A}\) jest przeciwobrazem zbioru \(R^{\A}\) przy przekształceniu \(f\).

Zadanie 8

Sygnatura \(\Sigma\) składa się z dwóch symbolu równości i dwuargumentowych symboli relacyjnych \(R\) i \(S\). Napisać takie zdania \(\varphi_1\), \(\varphi_2\) i \(\varphi_3\), że

1. zdanie \(\varphi_1\) jest prawdziwe dokładnie w tych modelach, \(\A = \[A, R^\A, S^\A\]\), w których \(R^\A\) jest relacją równoważności o dokładnie trzech klasach abstrakcji.
2. zdanie \(\varphi_2\) jest prawdziwe dokładnie w tych modelach, \(\A = \[A, R^\A, S^\A\]\), w których złożenie relacji \(R^\A\) z relacją \(S^\A\) jest identyczne ze złożeniem relacji \(S^\A\) z relacją \(R^\A\).
3. zdanie \(\varphi_3\) jest prawdziwe dokładnie w tych modelach \(\A = \[A, R^\A, S^\A\]\), w których relacja \(S^\A\) jest najmniejszą relacją symetryczną zawierajacą \(R^\A\).

Zadanie 9

Wskazać (o ile istnieje) model i wartościowanie spełniające daną formułę i nie spełniające tej formuły:

1. \(\forall y(r(x)\to r(y))\);
2. \(\forall y(r(x)\wedge r(y) \to r(f(x,y))\);
3. \(\forall x(q(x,y)\to q(f(x),y)\);
4. \(\forall x\forall y(r(x)\wedge r(y) \to r(f(x,y))\);
5. \(\forall x(r(x)\vee p(x))\to (\forall x r(x)\vee \forall x p(x))\);
6. \(\forall x\exists y(q(x,y)\vee \forall y\neg q(x,y))\);
7. \(\exists x\forall y\exists z(q(x,z)\wedge\neg q(x,y))\);
8. \(\forall x\forall y(\neg(x=y)\to \exists z(P(x,z)\wedge P(y,z))\);
9. \(\forall x\exists y\exists z(\neg(y=z)\wedge P(x,y)\wedge P(x,z))\);
10. \((\forall x P(x) \to Q(y)) \oto \exists x (P(x) \to Q(y))\);
11. \((\forall x P(x) \to Q(x)) \oto \exists x (P(x) \to Q(x))\).

Zadanie 10

Udowodnij w systemie naturalnej dedukcji:

1. \(\vdash (p\to \neg q)\to\neg(p\wedge q)\);
2. \(\vdash (p\to q\vee r)\to((p\to q)\vee(p\to r))\);
3. \(\vdash \forall x(P(x)\to Q(y))\to(\exists x P(x)\to Q(y))\);
4. \(\forall x(P(x) \to P(f(x)))\vdash \exists x P(x) \to \exists x P(f(f(x)))\).