poniedziałek, 27 stycznia 2014

Ćwiczenia 13: logika

Zadania

  1. 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 b przez c.
    c) Liczba a jest pierwsza.
    d) 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) \(\langle \mathbb{Q}, +, \cdot, 0, 1\rangle\) i \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\),
    b) \(\langle \mathbb{N}, +, 0\rangle\) i \(\langle \mathbb{R}, +, 0 \rangle\),
    c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\mathbb{R}^2\),
    d) \(\langle P_2, \bot\rangle\) i \(\langle P_3, \bot \rangle\), gdzie \(P_n\) to zbiór prostych w \(\mathbb{R}^n\)
    e) \(\langle \mathbb{R}, +, \cdot, 0, 1\rangle\) i \(\langle P(\mathbb{N}), \cup, \cap, \emptyset, \mathbb{N}\rangle\),
    f) \(\langle \mathbb{N}, \leq, 0\rangle\) i \(\langle \mathbb{R}, \leq, 0\rangle\),
    g) \(\langle \mathbb{N}, +,  0\rangle\) i \(\langle\{a,b\}^*, \cdot, \epsilon\rangle\).
  4. Jakiej mocy jest zbiór wszystkich ciągłych w \(\mathbb{R}\)?

poniedziałek, 20 stycznia 2014

Ćwiczenia 12: dobre ufundowanie

Zadania

  1. Niech \(B \subseteq \mathbb{R}_{+}\). Udowodnić, że istnieje zbiór \(C \subseteq \mathbb{R}_{+}\) taki, że
    • \(\forall_{x,y \in C}(x\neq y \to | x - y | \in B\),
    • \(\forall_x (x\not \in C \to \exists y \in C | x - y | \not\in B\).
  2. Czy zbiór \(\langle \mathbb{N}^*, \leq_{lex}\rangle\) jest dobrze ufundowany?
  3. Czy zbiór \(\langle \mathbb{N}^2, \leq_{lex}\rangle\) jest dobrze ufundowany?
  4. Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy \(\aleph_0\) tak, aby żadne dwa nie były ze sobą izomorficzne.
  5. Niech  \(\langle A, \leq \rangle\) będzie zbiorem dobrze uporządkowanym, w którym wszystkie antyłańcuchy są skończone. Niech \(\{a_i\}_{i\in \mathbb{N}}\) będzie dowolnym ciągiem elementów. Udowodnić, że istnieją i, j takie, że i<j i \(a_i \leq a_j\).

Praca domowa

Ostatnia praca domowa zostanie ogłoszona w poniedziałek po południu. Termin oddania: czwartek 23 stycznia 2014 r. Praca domowa zostanie zebrana na wykładzie.

poniedziałek, 13 stycznia 2014

Ćwiczenia 11: porządki cz. 2

Przypominam, że jutro o 16 w sali 4420 jest klasówka poprawkowa.

Zadania

  1. Niech
    \(A = \{ 3 - \frac{1}{2n} \mid n \in \mathbb{N} - \{0\}\}\),
    \(B = \{ \pi - \frac{2}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{4\}\),
    \(C = \{0\} \cup \{ \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\} \cup \{ 2 - \frac{1}{n} \mid n \in \mathbb{N} - \{0\}\}\).
    Rozpatrzmy zbiory A, B, C, \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{Q}\), \(\mathbb{Q} - \{0\}\), \(\mathbb{R}\), \(\mathbb{R} - \{0\}\). Które z nich są izomorficzne?
  2. 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ą?
  3. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
  4. Niech A będzie dowolnym zbiorem i niech \(B \subseteq A \times A\). Udowodnić, że istnieje maksymalny zbiór \(C \subseteq A\) taki, że \(C \times C \subseteq B\).

Praca domowa

Kolejna praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 20 stycznia 2014 r.

Ciekawe zadanie dodatkowe - dla chętnych

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

poniedziałek, 16 grudnia 2013

Ćwiczenia 10: porządki (niekoniecznie świąteczne)

Zadania

  1. Które z następujących zbiorów są równoliczne:
    \[\mathbb{Q}\times\mathbb{Z},\mathbb{R}\times\mathbb{Q}, \mathbb{R}-\mathbb{Q}, 2^{\mathbb{N}}, 2^{\mathbb{R}}, P(\mathbb{Q}\times\mathbb{Z}), \bigcup_{n\in \mathbb{N}}\mathbb{N}^n ? \]
  2. W zbiorze \(\{1,2,3,5,12,18,120,300\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy? Wskaż kres dolny zbioru \(\{5,12\}\) oraz kres górny zbioru \(\{3,12\}\).
  3. Podać przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi, 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.
  4. Rozpatrzmy częściowe uporządkowanie zbioru \(\{0,1\}^{\mathbb{N}}\):
    \[ f \leq g \hbox{ wtw. } \forall_x f(x) \leq g(x)\]
    a) Czy ten porządek jest liniowy?
    b) Czy istnieje w nim łańcuch nieskończony?
    c) Czy istnieje antyłańcuch nieskończony?
    d) Czy ma element największy, najmniejszy, minimalny, maksymalny?
  5. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
  6. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
  7. Czy relacja równoważności może być częściowym porządkiem?
  8. Znaleźć moc zbioru wszystkich porządków częściowych w \(\mathbb{N}\).

Praca domowa

Praca domowa pojawi się w poniedziałek po południu na stronie wykładu. Termin oddania: 13.01.2014 r.

Życzę Państwu odpoczynku w czasie przerwy świątecznej. Nie zapomnijcie, że łańcuch to nie tylko ozdoba choinkowa :)

Wesołych Świąt! 
Szczęśliwego Nowego Roku 2014!



poniedziałek, 9 grudnia 2013

Ćwiczenia 9: moce cz. 2

Zadania

  1. Jaka jest moc zbioru ciągów liczb wymiernych stałych od pewnego miejsca?
  2. Znaleźć moc zbioru \(\mathbb{R}^{\mathbb{Q}}\).
  3. Pokazać, że \((A^{B})^C \sim A^{B \times C}\).
  4. Znaleźć moc zbioru wszystkich bijekcji z \(\mathbb{N}\) do \(\mathbb{N}\).
  5. Niech r będzie taką relacją w zbiorze  \(\mathbb{Q}^{\mathbb{N}}\), że \(\langle f,g \rangle \in r\) wtedy i tylko wtedy, gdy różnica f - g jest zbieżna do zera. Znaleźć moc zbioru ilorazowego i moce klas abstrakcji relacji r.

Praca domowa

Kolejna praca domowa zostanie opublikowana w poniedziałek po południu na stronie wykładu. Termin oddania: 16 grudnia 2013 r.

poniedziałek, 2 grudnia 2013

Ćwiczenia 8: moce

Przypominam, że w tym tygodniu, w czwartek na wykładzie, jest klasówka.

Twierdzenie Cantora-Bernsteina

Jeśli \(\overline{\overline{A}} \leq \overline{\overline{B}}\) i \(\overline{\overline{B}} \leq \overline{\overline{A}}\), to \(\overline{\overline{A}} = \overline{\overline{B}}\).

W praktyce: szukamy mocy zbioru C.
  1. Znajdujemy dwa (być może różne) zbiory A, B takie, że \(\overline{\overline{A}} = \overline{\overline{B}}\). 
  2. Znajdujemy dwie funkcje różnowartościowe \(f : A \to C\) i \(g: C \to B\).
  3. Twierdzenie Cantora-Bernsteina mówi, że \(\overline{\overline{C}} = \overline{\overline{A}}= \overline{\overline{B}}\).
Wskazówka: dobrze jest zacząć od znalezienia typu zbioru C. Typ zbioru C daje nam zawsze ograniczenie górne na moc zbioru C.
Przykład: Znaleźć moc zbioru C wszystkich relacji w \(\mathbb{N}\), które ...
Rozwiązanie: Zbiór wszystkich relacji w \(\mathbb{N}\) to \(P(\mathbb{N}\times\mathbb{N})\). Zatem \(C \subseteq P(\mathbb{N}\times\mathbb{N})\), a stąd dostajemy:
\[\overline{\overline{C}} \leq \overline{\overline{P(\mathbb{N}\times\mathbb{N})}} = \mathfrak{C}\]
I już wiemy, że moc zbioru C nie może być równa np. \(2^{\mathbb{\mathfrak{C}}}\).

Zadania

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

Zadanie do przemyślenia

Zadanie dla osób, które po przygotowaniu do klasówki będą się nudzić:
  1. Znaleźć moc zbioru wszystkich funkcji ciągłych z \(\mathbb{R}\) do \(\mathbb{R}\).
W tym tygodniu nie ma pracy domowej.

poniedziałek, 25 listopada 2013

Klasówka

Przypominam, że 5 grudnia na wykładzie będzie klasówka. Materiał obowiązujący na klasówce:
  • rachunek zbiorów,
  • funkcje,
  • relacje,
  • relacje równoważności,
  • równoliczność,
  • zbiory przeliczalne.

Jeśli są jakieś zadania (z ćwiczeń, ze zbioru zadań lub inne) albo zagadnienia, które chcielibyście powtórzyć przed klasówką, proszę napisać w komentarzu.