Wst e p do Teorii Mnogości i Logiki

,

Lista 8

Zadanie 8.1 Wykazać, że następujące zbiory są przeliczalne: (a) Q , Q ∩ [0 , 1) ,

Q ∩ [0 , ∞) ,

(b) Zbiór wszystkich możliwych (tzn. możliwych do zapisania przy użyciu skończonej liczby liter alfabetu ) słów języka polskiego.

(c) Zbiór przedziałów o końcach w punktach wymiernych.

(d) Zbiór wielomianów o współrzędnych wymiernych.

(e) Dowolna rodzina parami rozłącznych kół na płaszczyźnie.

(f) Zbiór skończonych ciągów zero-jedynkowych.

(g) Zbiór skończonych podzbiorów zbioru przeliczalnego.

(h) Dowolna rodzina parami rozłącznych przedziałów otwartych na prostej.

(i) {n ∈ N : 5 | n },

{ 7 n : n ∈ N; },

{n : n > 109 , n jest parzysta},

(j) {( n, k) ∈

2

2

N : n | k },

{( n, k) ∈ N : k = nn },

√

√

(k) {x ∈

2

R : sin( x) =

},

{n + m 2 : n, m ∈

2

N }.

(l) Zbiór punktów płaszczyzny o współrzędnych wymiernych.

(m) Zbiór wszystkich macierzy wymiaru n × k o elementach wymiernych.

(n) {( n, k, l) ∈ N × (N \ { 0 }) × Q : l = n , 5 | ( n + k) }.

k

Zadanie 8.2 Wykazać, że poniższe zbiory nie są przeliczalne: (a) R × { 0 }, [0 , 1) × N , { 1 } × R × Q .

(b) Zbiór wszystkich liczb zespolonych.

(c) [0 , 1] ,

R \ Q ,

R \ N ,

R \ [0 , ∞) .

(d) Zbiór wszystkich nieskończonych podzbiorów zbioru przeliczalnego.

(e) Zbiór wszystkich funkcji ze zbioru A, który jest co najmniej przeliczalny w zbiór B mocy większej niż 1.

Zadanie 8.3 Wykazać, że jeżeli X, Y, A, B są nieskończone oraz X ∼ Y (tzn. X jest równoliczny z Y) i A ∼ B to P ( X) ∼ P ( Y )

( X ∪ A) ∼ ( Y ∪ B)

( X × A) ∼ ( Y × B)

X A ∼Y B.

Zadanie 8.4 Zakładamy, że X jest zbiorem nieskończonym, a ∈ X oraz b 6∈ X. Pokazać, że card X = card( X \ {a}) = card( X ∪ {b}) .

Zadanie 8.5 Zakładamy, że f : X → Y jest surjekcją. Definiujemy relację równoważności na X warunkiem xRy ↔

f ( x) = f ( y) . Wykazać, że zbiór Y jest równoliczny ze zbiorem klas abstrakcji relacji R.

Zadanie 8.6 Sprawdzić, definiując odpowiednią bijekcję, że następujące pary zbiorów są równoliczne: (0 , 1)

oraz

[0 , 1] ,

R

oraz

[0 , ∞) ,

{( n, k) : n, k ∈ N , ( ∃ m ∈ N) nm = k} oraz N ,

{( x, y) ∈

2

R : x 2 + y 2 ¬ 1 }

oraz

R .

R

oraz

(0 , 1) ,

(0 , ∞)

oraz

R ,

{( k, l) : k, l ∈ N , k | l} oraz N ,

{( n, n 2) : n ∈ N } oraz

N ,

{x ∈ R : sin( x) = 0 } oraz

N .

Zadanie 8.7 Wykazać, żę dla zbiorów X, Y isnienie funkcji różnowartościowej f : X → Y jest równoważne istnieniu surjekcji g : Y → X.