2. Relacja równoliczności i moc zbioru. Przeliczalność i nieprzeliczalność.

Zbiory X i Y nazywamy równolicznymi, gdy istnieje bijekcja taka, że f : X → Y. Równoliczność zbiorów oznaczamy przez X ∼ Y.

Dla dowolnych zbiorów X, Y, Z, zachodzi:

1. X ∼ X.

2. X ∼ Y => Y ∼ X.

3. Jeżeli X ∼ Y i Y ∼ Z , to X ∼ Z.

Moc zbioru opisuje jego liczebność, mówimy że dwa zbiory mają tę samą moc wtedy i tylko wtedy gdy są równoliczne.

Mówimy, że zbiór jest przeliczalny, gdy jest skończony lub równoliczny
z N.

Zbiór A≠⌀ ; jest przeliczalny wtedy i tylko wtedy, gdy istnieje suriekcja f : N → A.

Zbiory liczb całkowitych (Z) i wymiernych (Q) są przeliczalne.

Własności zbiorów przeliczalnych:

1. Jeśli A jest zbiorem przeliczalnym oraz B ⊂ A, to B jest zbiorem przeliczalnym.

2. Jeśli A i B są zbiorami przeliczalnymi, to produkt A×B jest zbiorem przeliczalnym.

3. Jeśli {A_n : n ∈ N} jest ciągiem zbiorów przeliczalnych, to suma ⋃_n ∈ NA_n  jest zbiorem przeliczalnym.

4. N^k dla k ≥ 1 jest przeliczalny.

Zbiór nazywamy nieprzeliczalnym, gdy nie jest przeliczalny.

Przykłady zbiorów nieprzeliczalnych:

• Dowolny przedział [a ; b] (dla a < b) jest nieprzeliczalny.

• Zbiór R jest nieprzeliczalny, bo gdyby był przeliczalny, to [0; 1] byłby przeliczalny na mocy własności 1).

• Zbiór R \ Q jest nieprzeliczalny, bo gdyby był przeliczalny,

to R =Q ∪ (R \ Q) byłby przeliczalny z własności 3).

• Zbiór {0;1}^N jest nieprzeliczalny, bo jest nieskończony i nierównoliczny z N.