Tampereen yliopisto Joukko-oppi Harjoitus 12 (20. 11.) Syksy 2023

1. Merkitään ℵ_{0} = card(ω). Osoita seuraavat väittämät todeksi:

a) ℵ_{0} ⊕ 5 = ℵ_{0}.

b) ℵ_{0} ⊕ ℵ_{0} = ℵ_{0}.

c) ℵ_{0} ⊗ ℵ_{0} = ℵ_{0}.

2. Olkoot κ, λ ja μ kardinaaleja. Osoita, että ehdosta κ < λ ei seuraa, että

a) κ ⊕ μ < λ ⊕ μ

b) κ ⊗ μ < λ ⊗ μ.

3. Kun A on joukko, kutsutaan mitä tahansa kuvausta f: n → A, missä n ∈ ω, jonoksi joukon A alkioita. Merkitään Sq(A):lla joukon A kaikkien jonojen joukkoa. Osoita, että Sq(ω) ≈ ω.

4. Osoita edellisen tehtävän avulla, että algebrallisten lukujen joukko A on numeroituva. Miten tästä päätellään, että transkendenttilukujen joukko T on ylinumeroituva? (Reaaliluku a on algebrallinen, eli a ∈ A, jos se on jonkin kokonaislukukertoimisen polynomin nollakohta. Reaaliluku on puolestaan transkendenttinen, jos se ei ole algebrallinen. Oletetaan tunnetuksi, että ℝ ≈ P(ω).)

5. Olkoon A joukko, jolla card(A) ≥ 2. Osoita, että Sq(A) ⪯ ^{ω}A.

6. [Cantorin parinkoodauskuvaus, osa 3] Tehtävissä 8.5 ja 9.5 muodostettiin Peanon systeemi (ω × ω, S, (0, 0)) ja isomorfismi h: (ω, σ, 0) ≅ (ω × ω, S, (0, 0)). Cantorin parinkoodauskuvaus määriteltiin kuvaukseksi J = h^{−1}. Osoita, että kaikilla m, n ∈ ω pätee

J(m, n) = \frac{1}{2} ((m + n)^{2} + 3m + n) .

[Vihje: Induktiota voi Peanon systeemin määritelmän mukaan tehdä kummassa tahansa Peanon systeemissä.]