Processing math: 48%
Zadania
- Zapisać następujące stwierdzenia w języku arytmetyki liczb
naturalnych (+,⋅,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 b przez c.
c) Liczba a jest pierwsza.
d) Liczba a jest największym wspólnym dzielnikiem liczb b i c chyba, że jest parzysta.
e) Liczby x i y mają te same dzielniki pierwsze.
- Sformułować poprawne zaprzeczenia stwierdzeń:
a) Liczby m i n są pierwsze.
b) Liczby m in są względnie pierwsze.
- Dla każdej z następujących par struktur wskazać formułę prawdziwą w jednej, a w drugiej nie.
a) ⟨Q,+,⋅,0,1⟩ i ⟨R,+,⋅,0,1⟩,
b) ⟨N,+,0⟩ i ⟨R,+,0⟩,
c) ⟨P2,∥⟩ i ⟨P2,⊥⟩, gdzie P2 to zbiór prostych w R2,
d) ⟨P2,⊥⟩ i ⟨P3,⊥⟩, gdzie Pn to zbiór prostych w Rn
e) ⟨R,+,⋅,0,1⟩ i ⟨P(N),∪,∩,∅,N⟩,
f) ⟨N,≤,0⟩ i ⟨R,≤,0⟩,
g) ⟨N,≤⟩ i ⟨R,≤⟩,
h) ⟨N,+,0⟩ i ⟨{a,b}∗,⋅,ϵ⟩.
- Czy następujące formuły są tautologiami? Czy są spełnialne?
a) ∀x(p(x)→q(x))∨∀x(q(x)→p(x)),
b) ∃x(P(x)→∀yP(y)),
c) (∃x∃yP(x,y)→∀yR(y))→∀x(P(x,x)→R(x)),
d) ∀x∃y∀u∃vP(x,y,u,v)→∀u∃v∀x∃yP(x,y,u,v).
Zadania
- Niech A będzie dowolnym zbiorem i niech B⊆A×A.
Udowodnić, że istnieje maksymalny zbiór C⊆A taki,
że C×C⊆B.
- Niech B⊆R+. Udowodnić, że istnieje zbiór C⊆R taki, że
- ∀x,y∈C(x≠y→|x−y|∈B),
- ∀x∉C(∃y∈C|x−y|∉B).
- Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.
Praca domowa (nieobowiązkowa)
- Dowolny podzbiór Z nazwiemy zeznaniem. Zbiór zeznań R jest sprzeczny, jeśli istnieje w nim takie i∈Z, że i,−i∈⋃R. Udowodnić, że jeśli R jest dowolną rodziną zeznań, to istnieje maksymalna niesprzeczna podrodzina R⊆R.
Zadania
- Niech A={3−12n∣n∈N−{0}},
B={π−2n∣n∈N−{0}}∪{4},
C={0}∪{1n∣n∈N−{0}}∪{2−1n∣n∈N−{0}}.
Rozpatrzmy
zbiory A, B, C, N, Z, Q,
Q−{0}, R, R−{0}. Które z
nich są izomorficzne?
- Czy zbiory Q×(0,1] i (0,1]×Q uporządkowane leksykograficznie są izomorficzne?
- Czy zbiór ⟨N∗,≤lex⟩ jest dobrze ufundowany?
- Czy zbiór ⟨N2,≤lex⟩ jest dobrze ufundowany?
- Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy ℵ0 tak, aby żadne dwa nie były ze sobą izomorficzne.
- Niech ⟨A,≤⟩ będzie zbiorem dobrze
uporządkowanym, w którym wszystkie antyłańcuchy są skończone. Niech
{ai}i∈N będzie dowolnym ciągiem elementów.
Udowodnić, że istnieją i, j takie, że i<j i ai≤aj.
- Udowodnić, że jeśli f:A→B jest monotoniczną bijekcją między liniowymi porządkami ⟨A,≤⟩ i ⟨B,≤⟩ to funkcja odwrotna też jest monotoniczna.
- Podać przykład dobrego porządku D=⟨D,≤⟩ i rosnącej funkcji f:D→D, która spełnia jednocześnie następujące warunki:
a) ∀a∈D∃b∈D(a<b∧f(b)=b),
b) ∀a∈D∃b∈D(a<b∧f(b)>b).
- Niech ⟨A,≤⟩ będzie nieskończonym zbiorem dobrze uporządkowanym. Pokazać, że nie istnieje taka różnowartościowa funkcja f:A→A, że dla dowolnych a,b∈A jeśli a≤b, to f(b)≤f(a).
Praca domowa
-
Relacja r częściowo porządkująca zbiór N jest przyjemna, jeżeli ma nieskończony łańcuch i jest dobrym ufundowaniem, ale nie jest dobry porządkiem. Jakiej mocy jest rodzina wszystkich relacji przyjemnych?
- Niech Pfin(N) to zbiór skończonych podzbiorów zbioru N. Zdefiniować dobry porządek ≼ w zbiorze P_{fin}(\NN), żeby
\forall A, B \in P_{fin}(\NN) (A \subseteq B \to A \preccurlyeq B).
Zadania
- Znaleźć moc zbioru funkcji nierosnących z \mathbb{N} do \mathbb{N}.
- Znaleźć moc zbioru wszystkich relacji równoważności w \mathbb{N}.
- Znaleźć moc zbioru Cantora. Zbiór Cantora to przecięcie ciągu zbiorów:
C_0 = (0,1),
C_1 = (0,\frac{1}{3}) \cup (\frac{2}{3},1),
C_2= (0,\frac{1}{9}) \cup (\frac{2}{9},\frac{1}{3}) \cup (\frac{2}{3},\frac{8}{9}) \cup (\frac{8}{9},1),
...
C = \bigcap_{n\in \mathbb{N}}C_n.
- Funkcję f : \mathbb{N} \to \mathbb{N} nazywamy zygzakiem wtedy i tylko wtedy, gdy spełnia warunek
\begin{multline*}\forall_{x>0} ((f(x)>f(x-1) \to f(x) > f(x+1)) \\ \wedge (f(x)<f(x-1) \to f(x) < f(x+1))).\end{multline*}
Jakiej mocy jest zbiór wszystkich zygzaków?
- a) Jaka jest moc zbioru A = \{ f :\mathbb{N} \to \mathbb{N} \mid \forall_x( f(x) \leq x)\}?
b) Jaka jest moc zbioru B = \{ f \in A \mid f \hbox{ jest na }\mathbb{N}\}?
c) Jaka jest moc zbioru C = \{ f \in A \mid f \hbox{ jest różnowartościowa}\}?
- Jaka jest moc zbioru \mathbb{R}^\mathbb{N}?
- Jaka jest moc zbioru F tych funkcji f : P(\mathbb{N}) \to P(\mathbb{N}) takich, że dla każdego skończonego Z \subseteq \mathbb{N} wartość f(Z) jest skończona?
Praca domowa
- Jaka jest moc rodziny tych relacji równoważności w \mathbb{N}, które mają skończenie wiele klas abstrakcji?
- Ile jest takich funkcji f: \mathbb{N} \to \mathbb{N}, że każdy zbiór f^{-1}(\{n\}) jest skończony?
Wesołych Świąt!
Zadania
- Pokazać, że P(A) \sim \{0,1\}^{A}.
- Pokazać, że jeśli A \sim B, to P(A) \sim P(B).
- Znaleźć moc zbioru skończonych podzbiorów \mathbb{N}.
- Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
- Znaleźć moc zbioru funkcji z \mathbb{N} do \mathbb{N}.
- Znaleźć moc zbioru funkcji niemalejących z \mathbb{N} do \mathbb{N}.
Praca domowa
- Niech s będzie relacją w \mathbb{Q}^{\mathbb{N}} taką, że \langle f, g \rangle \in s wtedy i tylko wtedy, gdy różnica f - g jest zbieżna do zera. Pokazać, że s jest relacją równoważności. Wskazać trzy różne klasy abstrakcji.
- Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.
Zadania
- Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze A?
- Czy relacja równoważności może być częściowym porządkiem?
- Czy istnieje relacja równoważności na \mathbb{N}, która ma:
a) dokładnie 2 klasy abstrakcji po 37 elementów,
b) 2 klasy abstrakcji po 17 elementów, 3 klasy po 33 elementy i jedną nieskończoną,
c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
- Niech r \subseteq P(\mathbb{N}) \times P(\mathbb{N}) będzie taka, że
\langle X, Y \rangle \in r \hbox{ wtw istnieje skończony }Z\hbox{ taki, że } X \cup Z =Y \cup Z.
a) Udowodnić, że r jest relacją równoważności.
b) Znaleźć [\emptyset]_r.
- Niech r \subseteq (\mathbb{N} \to \mathbb{N}) \times (\mathbb{N} \to \mathbb{N} ) będzie określona w następujący sposób:
\langle f, g\rangle \in r \hbox{ wtw } f(\mathbb{N}) = g(\mathbb{N}).
a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
b) Znaleźć klasy [\lambda x.1]_r i [id_{\mathbb{N}}]_r.
c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?
d) Czy istnieje dwuelementowa klasa abstrakcji?
- Niech A będzie niepustym zbiorem i niech f : A \to A.
a) Udowodnić, że jeśli f jest różnowartościowa, to relacja r \subseteq A \times A dana warunkiem
x r y \Leftrightarrow \exists n\in \mathbb{N} (f^n(x) = y \wedge f^n(y) = x)
jest relacją równoważności.
b)
Podać przykład takich A, f, że r ma nieskończenie wiele skończonych
klas abstrakcji, każdą o innej liczbie elementów. (Można zrobić
rysunek.)
Dziś nie ma pracy domowej.
Zadania
- Rozważmy częściowy porządek \langle A \leadsto B, \leq \rangle,
gdzie A \leadsto B to zbiór funkcji częściowych z A do B i f \leq
g, wtedy i tylko wtedy, gdy dla każdego a \in A albo f(a)
jest nieokreślone, albo obie funkcje są określone i f(a) = g(a). Czy
\langle A \leadsto B, \leq \rangle jest kratą zupełną?
- Udowodnij, że \langle A \leadsto B, \leq \rangle jest częściowym porządkiem zupełnym.
- Niech A i B będą zbiorami częściowo uporządkowanymi i niech funkcje f : A \to B i g : B \to A będą monotoniczne. Udowodnić, że następujące warunki są równoważne:
a) \forall a \in A \forall b \in B (a \leq g(b) \leftrightarrow f(a) \leq b )
b) \forall a \in A (a \leq g(f(a))) \wedge \forall b \in B (f(g(b)) \leq b).
- Podaj przykład takiego przekształcenia monotonicznego f w kracie \langle P(\mathbb{N}), \subseteq \rangle, że kres górny zbioru \{ f^n(\emptyset) \mid n \in \mathbb{N}\} nie jest najmniejszym punktem stałym.
- Niech A będzie częściowym porządkiem zupełnym i niech f : A \to A będzie ciągła. Udowodnić, że jeśli a \leq f(a), to istnieje taki punkt stały b funkcji f, że a \leq b.
Praca domowa
- Które z następujących stwierdzeń jest prawdziwe dla dowolnego zbioru częściowo uporządkowanego \langle X, \leq \rangle i dowolnych A, B \subseteq X:
a) Jeśli w X istnieje \sup A i \sup B, to istnieje \sup (A \cup B).
b) Jeśli w X istnieje \sup (A \cup B), to istnieją.\sup A i \sup B.
- Niech X będzie zbiorem częściowo uporządkowanym i niech A \subseteq X nie ma elementu największego. Niech B = \{b \in X \mid \forall a \in A (b > a) \}. Pokazać, że jeśli istnieje \inf B, to istnieje \sup A oraz \sup A = \inf B \in B.
- Dla chętnych: skończyć zadanie 4 z zajęć.