”Wst¸ep do Teorii Mnogości”, przykÃladowe zadania egzaminacyjne Zadanie 1 (5p. + 5p.)

W zbiorze NN określamy relacj¸e R nast¸epuj¸aco:

{an} R {bn} ⇐⇒ a 0 = b 0

dla {an}, {bn} ∈ NN.

(a) Czy relacja R jest relacj¸a równoważności ? Odpowiedź uzasadnić.

(b)

Jeżeli R jest relacj¸a równoważności, to wyznaczyć jej klasy abstrakcji. Odpowiedź

uzasadnić.

Zadanie 2 (5p. + 5p.)

Niech f : X → Y b¸edzie funkcj¸a. Określamy g: P( Y ) → P( X) wzorem g( B) = f − 1( B) dla B ⊆ Y . Udowodnić, że funkcja f jest surjekcj¸a wtedy i tylko wtedy, gdy funkcja g jest injekcj¸a.

Zadanie 3 (10p.)

Dla jakich liczb naturalnych n = 0 , 1 , 2 , . . . zachodzi nast¸epuj¸aca nierówność: n( n − 1) ≤ log

2

2( n !) .

Odpowiedź uzasadnić.

Zadanie 4 (10p.)

Udowodnić, że dla dowolnych zbiorów zachodzi implikacja A ∼ B ∧ C ∼ D ⇒ AC ∼ BD.

Zadanie 5 (4p. + 3p. + 3p.)

W zbiorze { 0 , 1 } N, gdzie N = { 0 , 1 , 2 , . . .} określamy relacj¸e S wzorem f S g ⇐⇒ ∀ n ∈ N f ( n) ≤ g( n) dla f , g ∈ { 0 , 1 } N.

(a) Czy ( { 0 , 1 } N , S) jest liniowym porz¸adkiem?

(b) Czy istnieje w tym porz¸adku Ãlańcuch nieskończony?

(c) Czy istnieje w tym porz¸adku antyÃlańcuch nieskończony?

Odpowiedzi uzasadnić.