Processing math: 41%

poniedziałek, 27 stycznia 2014

Ć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) 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,+,0 i {a,b},,ϵ.
  4. Jakiej mocy jest zbiór wszystkich ciągłych w R?

poniedziałek, 20 stycznia 2014

Ćwiczenia 12: dobre ufundowanie

Zadania

  1. Niech BR+. Udowodnić, że istnieje zbiór CR+ taki, że
    • x,yC(xy|xy|B,
    • x(xCyC|xy|B.
  2. Czy zbiór N,lex jest dobrze ufundowany?
  3. Czy zbiór N2,lex jest dobrze ufundowany?
  4. Podaj trzy przykłady zbiorów dobrze uporządkowanych mocy 0 tak, aby żadne dwa nie były ze sobą izomorficzne.
  5. 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.

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={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. Rozważmy częściowy porządek A, 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.