Ćwiczenia 12: relacje równoważności

Zadania

1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze A?
2. Ile jest relacji równoważności w zbiorze liczb naturalnych, które są jednocześnie częściowymi porządkami?
3.  Czy istnieje relacja równoważności w \(\NN\), która ma:
   a) dokładnie dwie klasy abstrakcji po 37 elementów,
   b) dwie klasy abstrakcji po 37 elementów, trzy klasy abstrakcji po 33 elementy i jedną nieskończoną klasę abstrakcji,
   c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
4. Niech \(R \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } \forall n(f(n) - g(n) \hbox{ jest liczbą parzystą. })\]
   a) Pokazać, że R jest relacją równoważności.
   b) Opisać klasę abstrakcji funkcji identycznościowej.
   c) Czy zbiór \((\NN\to\NN)/_R\) jest nieskończony?
   d) Czy zbiór \(\{f: \NN\to \NN \mid f(0) = 2\}\) jest klasa abstrakcji tej relacji?
5. Niech \(r\) będzie relacją równoważności w \(\NN\) i niech \(f : \NN \times \NN \to P(\NN)\) będzie taka, że:
   \[f(\langle x,y \rangle) = [x]_r \cup [y]_r\]
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(P(\NN)\)?
   c) Znaleźć \(f^{-1}(\{ [3]_r \})\).
   d) Znaleźć \(f(r)\).
6. Niech \(r \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } f(\NN) = g(\NN).\]
   a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
   b) Znaleźć \([\lambda x.1]_r\) i \([id_{\NN}]_r\).
   c) Czy istnieje dwuelementowa klasa abstrakcji?

Praca domowa - dla chętnych

Zadania 193 i 206. Ta praca domowa nie jest obowiązkowa.

Ćwiczenia 11: logika

Zadania

1. W strukturze \(\mathcal{A} =\langle \NN, P^{\mathcal{A}},Q^{\mathcal{A}}\rangle\), gdzie:
   \( \langle a,b \rangle \in P^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(a+b \geq 6\),
   \( \langle a,b \rangle \in Q^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(b = a + 2\),
   wyznaczyć wartość
   a) formuły \(\forall x P(x,y) \to \exists xQ(x,y)\),
   b) formuły \(\forall x P(x,y) \to \exists xQ(x,z)\),
   przy wartościowwaniu \(v(y) = 7, v(z)=1\).
   
2. Podać 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) niespełniona.
3. 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):
   a) \(\langle \QQ, +, \cdot, 0, 1\rangle\) i \(\langle \RR, +, \cdot, 0, 1\rangle\),
   b) \(\langle \NN, +, 0 \rangle\) i \(\langle \NN, \cdot, 1\rangle\),
   c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\RR^2\),
   d) \(\langle \NN, \leq \rangle\) i \(\langle \ZZ, \leq\rangle\).
4. Zapisać następujące stwierdzenia w języku arytmetyki  liczb naturalnych (\(+, \cdot, 0, 1, =\)) używając symboli logicznych i kwantyfikatorów.
   a) Liczba a jest mniejsza lub równa liczbie b.
   b) Liczba a jest resztą z dzielenia liczby b przez c.
   c) Liczba jest pierwsza.
5. Sygnatura \(\Sigma\) składa się z symbolu równości i dwóch jednoargumentowych symboli relacyjnych R, S i jednego jednoragumentowego symbolu funkcyjnego f.
   a) Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}, f^{\mathcal{A}}\rangle\), w których obraz zbioru \(R^{\mathcal {A}}\) przy funkcji \(f^{\mathcal {A}}\) zawiera się w zbiorze \(S^{\mathcal {A}}\).

Praca domowa

Zadania 563 d,e i 569 e,g.

Ćwiczenia 10: powtórzenie przed klasówką

Zadania

1. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
2. Udowodnić, że nie istnieje słowo w takie, że \(a \cdot w = w \cdot b\).
3. Zdefiniować na listach operację dopisania liczby n na końcu listy.
4. Funkcję \(F : (\NN \to P(\NN)) \to P(\NN)\) jest określona warunkiem
   \[ F(x) = \bigcup \{x(i) \mid i \in \NN\}.\]
   a) Czy F jest różnowartościowa?
   b) Czy F jest na \(P(\NN)\)?
   c) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest jednoelementowy?
   d) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest czteroelementowy?
5. Podać przykład funkcji \(f : \NN \to \NN\) i zbioru \(X \subseteq \NN\), aby funkcja \(g:\NN\to P(\NN)\) określona wzorem:
   \[ g(i) = (f^i)^{-1}(X)\]
   była różnowartościowa.

Ze względu na klasówkę w tym tygodniu nie ma pracy domowej.