Prebrojivost skupova

[Bistabil]

Pozdrav ekipa!
Uskoro imam rok iz diskretne i nikako mi ne ide ova "prebrojivost" skupova. Ako može netko da mi objasni ova dva zadatka. Hvala

1) Neka je S = {[a,b] je podskup od R : a,b je element od N, a < b}. Je li skup S prebrojiv? Obrazložite.

2) Zadan je skup S = {(x, y) je element Q^2 : postoji n je element iz N, x^2 + y^2 = n^2 }. Je li skup S konačan? Je li prebrojiv? Obrazložite

[ivstojic]

1) Vrijedi:[dtex][a, b] \in S \iff (a, b) \in \{(m, n) \in \mathbb{N}^2 : m < n\},[/dtex]to jest postoji bijekcija između S i skupa parova prirodnih brojeva u kojima je prvi element para manji od drugog. Ovaj skup je očito beskonačan a podskup je prebrojivog skupa [tex]\mathbb{N}^2[/tex], pa je prebrojiv. Zaključujemo da je i [tex]S[/tex] prebrojiv skup (jer postoji bijekcija između [tex]S[/tex] i gore spomenutog prebrojivog skupa).

2) [tex]S[/tex] je beskonačan jer je primjerice za svaki [tex]k \in \mathbb{N}[/tex], par [tex](3 k, 4 k)[/tex] element od [tex]S[/tex]. Naime, [tex](3 k)^2 + (4 k)^2 = (3^2 + 4^2) k^2 = 5^2 k^2 = (5 k)^2[/tex] pa vidimo da je za [tex](3 k, 4 k) \in \mathbb{Q}^2[/tex], prirodni broj [tex]5 k \in \mathbb{N}[/tex] takav da vrijedi [tex](3 k)^2 + (4 k)^2 = (5 k)^2[/tex]. Kako je [tex]S[/tex] beskonačni podskup prebrojivog skupa [tex]\mathbb{Q}^2[/tex], zaključujemo da je [tex]S[/tex] prebrojiv.

[Bistabil]