1 (23)

ić, że A i B przecinają

,& E₂ z liczb 2, 3, 4, tdasięz2,3. i, że O < x < 1. Dla łych y spełniających

lego y > 0 zachodzi

ości do dodawania erwszym znaczeni u

>Q.

ńednio przez £i F. nocześnie do B i do

txeAi xeB)jj£L

Zbiory skończone, przeliczalne i nieprzeliczalne    29

t 2.12. TWIERDZENIE. Niech {£„} (n = 1, 2, 3,...) będzie rodziną zbiorów przeliczalnych; frzypwjmy

Ls,    [) e_h.

. Ił śa.l '

■Rnczos zbiór S jest przeliczalny.

f Dowód. Ubawmy każdy ze zbiorów E_n w ciąg {*,*} (k = 1,2,3,...) i rozpatrzmy tablicę Brnkończoną:

^J fS    Xi2    *i3    *14    ”5

_.    \V    .    'Xu    x₂3    X24

_    "X₃i    X₃2'    *34    )*» ' ■.,

X41 . X4.J,    ' *44 _

Br której elementy zbioru £„ tworzą n-ty wiersz. Powyższa tablica zawiera wszystkie elementy Hhioni 5. Te elementy można ustawić w ciąg tak, jak pokazują to strzałki:

• X₃ i; X2f_,    X₃1, X2'j; Xj₃; X41, X32, X23, Xj45 ...

Jesii jakiekolwiek dwa zbiory £„ mają wspólny element, to wystąpi on w (17) więcej niż raz. kftąd istnieje podzbiór T zbioru wszystkich liczb naturalnych taki, żsS ~ T, a więc zbiór Sjest Kóe więcej niż przeliczalny (twierdzenie 2.8). Ponieważ £_x c Si E_t jest nieskończony, więc i S cusi być nieskończony i dlatego przeliczalny.

I Wniosek. Przypuśćmy, że A jest nie więcej niż przeliczalny i dla każdego ocbA zbiór B„ jest kr więcej niż przeliczalny. Przyjmijmy

T= U B_v

‘    cteA

I Wedy T jest nie więcej niż przeliczalny.

Rzeczywiście T jest równoliczny z pewnym podzbiorem zbioru (15).

2.13, Twierdzenie. Niech A będzie zbiorem przeliczalnym i niech B„ będzie zbiorem \ wszystkich ciągów (a₁₍... ,a„) składających się z n wyrazów, gdzie a_keA (fc = 1,..., n); elementy nie muszą być różne. Zbiór B„jest przeliczalny.

Dowód. To, że zbiór B_t jest przeliczalny, jest oczywiste, ponieważ    = A, Przypuśćmy,

że £,.2 jest przeliczalny (« = 2,3,...). Elementy B_n mają postać:

'<18)    < (b,p) (ieĄ.pfl.s.Ą .

Przy każdym ustalonym b zbiór wszystkich par (b, a) jest równoliczny ze zbiorem A, a więc jest przeliczalny. W ten sposób B„ jest sumą zbiorów przeliczalnych. Z twierdzenia 2.12 wynika, że B„ jest przeliczalny. Twierdzenie jest prawdziwe na mocy indukcji.

WNIOSEK. Zbiór wszystkich liczb wymiernych jest przeliczalny.

Dowód. Zastosujemy twierdzenie 113, wziąwszy n =* 2 i zauważywszy, że każda liczba wymierna r ma postać b/a, gdzie a i b są liczbami całkowitymi. Zbiór par (a, b), a stąd zbiór ułamków bja, jest przeliczalny.