Processing math: 48%

poniedziałek, 26 stycznia 2015

Ćwiczenia 13: logika

Zadania

  1. 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.
  2. Sformułować poprawne zaprzeczenia stwierdzeń:
    a) Liczby m i n są pierwsze.
    b) Liczby m in są względnie pierwsze.
  3. 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},,ϵ.
  4.  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) (xyP(x,y)yR(y))x(P(x,x)R(x)),
    d) xyuvP(x,y,u,v)uvxyP(x,y,u,v).

poniedziałek, 19 stycznia 2015

Ćwiczenia 12: lemat Kuratowskiego-Zorna

Zadania

  1. Niech A będzie dowolnym zbiorem i niech BA×A. Udowodnić, że istnieje maksymalny zbiór CA taki, że C×CB.
  2. Niech BR+. Udowodnić, że istnieje zbiór CR taki, że
    • x,yC(xy|xy|B),
    • xC(yC|xy|B).
  3. Udowodnić, że każdy porządek częściowy można rozszerzyć do porządku liniowego.

Praca domowa (nieobowiązkowa)

  1. Dowolny podzbiór Z nazwiemy zeznaniem. Zbiór zeznań R jest sprzeczny, jeśli istnieje w nim takie iZ, że i,iR. Udowodnić, że jeśli R jest dowolną rodziną zeznań, to istnieje maksymalna niesprzeczna podrodzina RR.

poniedziałek, 12 stycznia 2015

Ćwiczenia 11: izomorfizm porządków, dobre ufundowanie

Zadania

  1. Niech A={312nnN{0}},
    B={π2nnN{0}}{4},
    C={0}{1nnN{0}}{21nnN{0}}.
    Rozpatrzmy zbiory A, B, C, N, Z, Q, Q{0}, R, R{0}. Które z nich są izomorficzne?
  2. Czy zbiory Q×(0,1] i (0,1]×Q uporządkowane leksykograficznie są izomorficzne?
  3. Czy zbiór N,lex jest dobrze ufundowany?
  4. Czy zbiór N2,lex jest dobrze ufundowany?
  5. Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy 0 tak, aby żadne dwa nie były ze sobą izomorficzne.
  6. Niech  A, będzie zbiorem dobrze uporządkowanym, w którym wszystkie antyłańcuchy są skończone. Niech {ai}iN będzie dowolnym ciągiem elementów. Udowodnić, że istnieją i, j takie, że i<j i aiaj.
  7. Udowodnić, że jeśli f:AB jest monotoniczną bijekcją między liniowymi porządkami A,B, to funkcja odwrotna też jest monotoniczna.
  8. Podać przykład dobrego porządku D=D, i rosnącej funkcji f:DD, która spełnia jednocześnie następujące warunki:
    a) aDbD(a<bf(b)=b),
    b) aDbD(a<bf(b)>b).
  9. Niech A, będzie nieskończonym zbiorem dobrze uporządkowanym. Pokazać, że nie istnieje taka różnowartościowa funkcja f:AA, że dla dowolnych a,bA jeśli ab, to f(b)f(a).

Praca domowa

  1. 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?
  2. 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).

poniedziałek, 15 grudnia 2014

Ćwiczenia 10: moce cz. 2

Zadania

  1. Znaleźć moc zbioru funkcji nierosnących z \mathbb{N} do \mathbb{N}.
  2. Znaleźć moc zbioru wszystkich relacji równoważności w \mathbb{N}.
  3. 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.
  4.  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?
  5. 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}\}?
  6. Jaka jest moc zbioru \mathbb{R}^\mathbb{N}?
  7. 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

  1. Jaka jest moc rodziny tych relacji równoważności w \mathbb{N}, które mają skończenie wiele klas abstrakcji?
  2. 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!


poniedziałek, 8 grudnia 2014

Ćwiczenia 9: równoliczność, moce

Zadania

  1. Pokazać, że P(A) \sim \{0,1\}^{A}.
  2. Pokazać, że jeśli A \sim B, to P(A) \sim P(B).
  3. Znaleźć moc zbioru skończonych podzbiorów \mathbb{N}.
  4. Znaleźć moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca.
  5. Znaleźć moc zbioru funkcji z \mathbb{N} do \mathbb{N}.
  6. Znaleźć moc zbioru funkcji niemalejących z \mathbb{N} do \mathbb{N}.

Praca domowa

  1. 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.
  2. Znaleźć moc zbioru wszystkich ciągów liczb wymiernych, które są zbieżne do zera.

poniedziałek, 1 grudnia 2014

Ćwiczenia 8: 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. Czy relacja równoważności może być częściowym porządkiem?
  3. 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.
  4. 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.
  5. 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?
  6. 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.

poniedziałek, 24 listopada 2014

Ćwiczenia 7: porządki cz. 2

Zadania

  1. 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ą?
  2. Udowodnij, że \langle A \leadsto B, \leq \rangle jest częściowym porządkiem zupełnym.
  3. 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).
  4. 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.
  5. 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

  1. 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.
  2. 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.
  3. Dla chętnych: skończyć zadanie 4 z zajęć.