Matematik

a) Der er et generelt argument for dette: For alle mængder A gælder der, at |A|<|P(A)|. Bevis: Først indser vi, at funktionen g:A→P(A) givet ved g(x)={x} er injektiv, så |A|≤|P(A)|. Vi vil nu vise, at de to mængder aldrig kan have samme størrelse, så antag for modstrid, at funktionen f:A→P(A) er surjektiv og betragt mængden . Da B er en delmængde af A må B∈P(A). Da f er surjektiv findes et y i A så f(y)=B. Bemærk, at y∈B hvis og kun hvis y∉f(y), men dette er jo modstrid, thi f(y)=B. Dette viser, at |A|<|P(A)|. Så bare lad A=N og du får dit svar.

b) Da du kan totalordne delmængderne af N så definerer vi funktionen φ_k(A)=(n₁(A),...,n_k(A)) hvor n_i(A) er det i'te element arrangeret efter størrelse (f.eks. er n₁({2,4,5})=2, n₂({2,4,5})=4, n₃({2,4,5})=5 så φ₃({2,4,5})=(2,4,5). Det er let at se, at denne funktion er injektiv og du får dermed, at |P_k(N)|<=|N^k| for alle k.

c) Da |N^k|=|N| for alle positive heltal k ser vi, at P_k(N) er tællelig for alle positive heltal k. Bemærk nu, at

,

thi hvis A er en endelig delmængde af N, så er |A|=k for et k i N, i.e. A ligger i P_k(N). Omvendt hvis A ligger i den store foreningsmængde på den højre side, så ligger A i en af P_k'erne for et k i N, men det betyder jo bare, at A er en endelig delmængde af N med k elementer, så A ligger i mængden på den venstre side. Da foreningsmængden af tælleligt mange tællelige mængder er tællelig følger det så, at P_fin(N) er tællelig.