Tællelige mængder

Tællelighed af en mængde er en slags ækvivalent til mængders størrelse, for ved uendelige mængder kan man ikke regne med antallet af elementer, fordi antallet af elementer er uventet … uendeligt. Mængdens størrelse kalder vi også kardinalitet.

Størrelsen af en uendelig mængde

At bestemme størrelsen af en endelig mængde er enkelt, vi tæller elementerne. Mængden M = {a, b, c, d, e} har altså størrelsen 5, og vi skriver |M| = 5.

Ved uendelige mængder er situationen noget mere kompliceret. Hvordan kunne vi sammenligne størrelsen af uendelige mængder? Kan man det overhovedet, eller er alle uendelige mængder »lige store«?

Lad os som eksempel tage mængden af naturlige tal og mængden af lige naturlige tal. Vi har altså mængderne ℕ = {1, 2, 3, 4, 5, 6, …} og S = {2, 4, 6, …}. Man fristes til at sige, at mængden af naturlige tal er større end mængden af lige tal, for de naturlige tal indeholder alle de lige tal og desuden nogle ekstra elementer — de ulige tal.

Vi kunne altså skrive, at S ⊂ ℕ gælder, mængden S er en ægte delmængde af mængden ℕ. Og vi kunne sige, at hvis S ⊂ ℕ, så er mængden ℕ større — den indeholder jo flere elementer end mængden S.

En af grundene til, at vi ikke kan måle mængder efter delmængderelationen, er, at mængder kan have forskellig størrelse, selv om ingen af mængderne er en delmængde af den anden. Det kan vi vise allerede med endelige mængder: A = {1, 3, 4, 9} og B = {b, u, r, z, m}. Der gælder: |A| = 4 og |B| = 5. Mængden B er større end mængden A, men alligevel gælder A ⊂ B ikke. Ved uendelige mængder kan vi se det på de lige og ulige tal. Ingen af mængderne er en delmængde af den anden.

Delmængderelationen er altså ikke nogen ideel kandidat til at afgøre, om en mængde er større end en anden.

Bijektion

Lad os prøve en anden tilgang. Vi har to mængder, A og B. Vi kan sige, at de har samme størrelse, hvis der mellem dem findes en bijektiv afbildning. Hvad betyder det? At vi tager et element fra mængden A, et element fra mængden B og danner et par (a, b). Disse elementer fjerner vi fra mængderne, og vi fortsætter. Hvis vi kan »tømme« begge mængder, har vi fundet en bijektiv afbildning.

Et eksempel med endelige mængder: A = {a, b, c} og B = {1, 2, 3}. Det første par kunne være (a, 1), det næste (b, 2) og til sidst (c, 3). Vi har opbrugt alle elementer i begge mængder, vi har fundet en bijektiv afbildning. Det er vigtigt, at dette ikke er den eneste bijektive afbildning. Også dette er en gyldig løsning: (a, 3), (b, 1), (c, 2).

Ved uendelige mængder er det allerede lidt mere interessant. Vi prøver med de ulige og lige naturlige tal. Intuitivt føler vi, at der burde være lige mange af dem. Lad os prøve. Vi tager det første ulige tal og afbilder det på det første lige tal: (1, 2). Så det andet ulige og det andet lige tal: (3, 4). Osv. Vi får dermed parrene: (1, 2), (3, 4), (5, 6), (7, 8), … Vi kunne skrive, at hvert ulige tal l afbildes på det lige tal l + 1, og hvert lige tal s er billedet af det ulige tal s − 1. For hvert ulige og for hvert lige tal har vi altså et par, som indeholder tallet. Mængderne af ulige og lige tal er dermed lige store.

Lige tal og naturlige tal

Nu prøver vi den samme fremgangsmåde og sammenligner mængden af naturlige tal og lige tal. Vi har altså mængderne ℕ = {1, 2, 3, 4, 5, 6, …} og S = {2, 4, 6, …}. Intuitivt forventer vi, at mængden af naturlige tal er større.

Men lad os nu prøve at finde den pågældende bijektive afbildning. Vi kan sige, at hvert naturligt tal n afbildes på sit dobbelte, på 2n. Dermed får vi parrene (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … For hvert naturligt tal n har vi altså parret (n, 2n), og for hvert lige tal s har vi parret (s/2, s). Vi har fundet en bijektiv afbildning, mængden af lige tal og mængden af naturlige tal er altså lige store, de har samme kardinalitet.

Det kan virke forvirrende, for de naturlige tal indeholder jo flere elementer end de lige tal. De naturlige tal indeholder alle de lige tal og desuden alle de ulige tal. Men vi kan finde en bijektion, så de to mængder er lige store.

Sammenligning med de naturlige tal

De naturlige tal angiver i virkeligheden den mindste størrelse af en uendelig mængde. Om en anden mængde har samme størrelse som mængden af naturlige tal, kan ofte afgøres forholdsvis let — det er nok at finde en bijektion til de naturlige tal, og i praksis betyder det, at det er nok, hvis vi kan nummerere, ordne elementerne i vores mængde M.

Altså hvis vi kan stille mængdens elementer op, så vi kan afgøre, hvilket element der er det første, hvilket der er det andet, tredje, fjerde, tiende osv., så er mængden lige så stor som ℕ. Om en sådan mængde siger vi, at den er tællelig.

Det er let at se, at de lige og ulige naturlige tal er tællelige, for vi kan angive det første, andet, tredje osv. lige/ulige tal. Hvad med de lige hele tal? Altså mængden S = {…, −4, −2, 0, 2, 4, …}. Kan vi ordne dem? Det kan vi, vi tager bare den samme ordning som før og skriver lige efter hvert positivt lige tal også dets negative udgave: S = {0, 2, −2, 4, −4, 6, −6, …}. På samme måde for eksempel for de hele tal.

Størrelsen af de rationale tal

Et mere interessant eksempel er de rationale tal, brøkerne. Kan vi ordne dem? Det kan vi, men det bliver lidt mere kompliceret. Vi konstruerer en tabel, der har uendeligt mange rækker og kolonner. I hver celle står en brøk. I den n'te kolonne og den m'te række har vi brøken n/m. Altså i 1. kolonne og 2. række har vi $\frac{1}{2}$, og i tredje kolonne og fjerde række har vi 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Hvordan ordner og nummererer vi nu disse tal? Vi kan ikke nummerere dem række for række eller kolonne for kolonne, for så ville vi med det samme drukne i den pågældende række/kolonne. I stedet tager vi tallene langs diagonaler: (første diagonal:) 1/1, (anden diagonal:) 2/1, 1/2, (tredje diagonal:) 3/1, 2/2, 1/3, (fjerde diagonal:) 4/1, 3/2, 2/3, 1/4, … Der er stadig en masse dubletter blandt brøkerne, men det gør ikke noget. Det, der er værre, er, at der ikke er nogen negative tal. Det kan løses enkelt: hver gang vi skriver en brøk, sætter vi dens negative udgave lige efter den. Og så mangler vi bare nul helt i begyndelsen. Og det er det hele, vi har alle de rationale tal i en talfølge.

Samlet får vi talfølgen: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Størrelsen af de reelle tal

Er de reelle tal lige så mange som de naturlige tal? Afgørelsen bliver endnu mere kompliceret end for de rationale tal. Vi laver et modstridsbevis. Antag, at de reelle tal er tællelige, og at der findes en bijektiv afbildning på de naturlige tal. Antag altså, at de kan ordnes. Og lad os sige, at følgende afbildning er den ordning:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

I tabellen er de første syv reelle tal i vores ordning. Denne ordning kan naturligvis være vilkårlig, tallene behøver ikke at være sorteret efter størrelse.

Ifølge antagelsen er alle de reelle tal ordnet i denne uendelige tabel. (Tabellen er igen uendelig, her er kun de første syv indgange.) Vi vil nu forsøge at finde/konstruere et tal, som er reelt, men ikke står i denne tabel. Hvis vi finder et sådant tal, er det i modstrid med, at alle de reelle tal står i tabellen, og heraf kan vi så slutte, at mængden af reelle tal ikke er tællelig.

Det tal, der ikke står i tabellen, konstruerer vi sådan her:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Vi begynder med at skrive 0,… Sådan kommer vores nye reelle tal til at se ud i begyndelsen. På første decimalplads står så et ciffer, som ikke står på første plads i det første reelle tal i vores ordning (i tabellen er det fremhævet med en ramme). Der er cifferet 3, så vi vælger for eksempel 1, og vi får tallet 0,1…

Vi fortsætter. På anden plads kommer et ciffer, som ikke står på anden plads i det andet reelle tal. Der er 9, så for eksempel 2. Vi får tallet 0,12… På tredje plads kommer et ciffer, som er forskelligt fra det tredje ciffer i det tredje reelle tal. Der er 3, så vi vælger for eksempel 7. Vi får 0, 127…

Og så videre og så videre. På den n'te plads i det nye tal står altid et ciffer, som er forskelligt fra cifferet på den n'te plads i det n'te tal i vores ordning.

Hvad får vi ud af det? Vi får et tal, der adskiller sig fra alle tallene i vores ordning i mindst ét ciffer. Lad os tage det sidste foreløbige resultat: 0,127… Dette tal adskiller sig helt sikkert fra det første tal i vores ordning i mindst det første ciffer — fordi vi har konstrueret det sådan. Fra det andet tal adskiller det sig i mindst det andet ciffer. Fra det tredje i det tredje ciffer. Generelt adskiller det nye tal sig fra det tal i ordningen, som står på den n'te plads, i mindst cifferet på den n'te plads.

Dette nykonstruerede tal finder vi altså ikke i tabellen, som skulle symbolisere bijektionen mellem de naturlige tal og de reelle tal. De reelle tal er derfor flere end de naturlige tal. De reelle tal er ikke tællelige, de er overtællelige.

Yderligere kilder

• Are there more odd or even numbers?