Uppräkneliga mängder

Uppräknelighet hos en mängd är ungefär en motsvarighet till mängders storlek, eftersom man för oändliga mängder inte kan räkna med antalet element: antalet element är nämligen oväntat … oändligt. Storleken på en mängd kallas också kardinalitet.

Storleken på en oändlig mängd

Att bestämma storleken på en ändlig mängd är enkelt: vi räknar elementen. Mängden M = {a, b, c, d, e} har alltså storleken 5, vilket vi skriver |M| = 5.

För oändliga mängder är situationen betydligt svårare. Hur skulle vi kunna jämföra storleken på oändliga mängder? Går det alls, eller är alla oändliga mängder ”lika stora”?

Låt oss som exempel ta mängden av positiva heltal och mängden av jämna positiva heltal. Vi har alltså mängderna ℤ⁺ = {1, 2, 3, 4, 5, 6, …} och S = {2, 4, 6, …}. Man skulle kunna tro att mängden av positiva heltal är större än mängden av jämna tal, eftersom de positiva heltalen innehåller alla jämna tal och dessutom några element till, nämligen de udda talen.

Vi skulle alltså kunna skriva S ⊂ ℤ⁺, mängden S är en äkta delmängd av mängden ℤ⁺. Och vi skulle kunna säga att om S ⊂ ℤ⁺ så är mängden ℤ⁺ större, den innehåller ju fler element än mängden S.

En anledning till att vi inte kan mäta mängder med delmängdsrelationen är att mängder kan ha olika storlek även om ingen av dem är en delmängd av den andra. Det går att visa redan med ändliga mängder: A = {1, 3, 4, 9} och B = {b, u, r, z, m}. Det gäller att |A| = 4 och |B| = 5. Mängden B är större än mängden A, men ändå gäller inte A ⊂ B. För oändliga mängder ser vi det på de jämna och de udda talen. Ingen av mängderna är en delmängd av den andra.

Delmängdsrelationen är alltså inte någon bra kandidat för att avgöra om en mängd är större än en annan.

Bijektion

Vi provar en annan ansats. Vi har två mängder, A och B. Vi kan säga att de har samma storlek om det finns en bijektiv avbildning mellan dem. Vad betyder det? Att vi tar ett element ur mängden A, ett element ur mängden B och bildar paret (a, b). De här elementen tar vi bort ur mängderna och fortsätter. Om vi kan ”tömma” båda mängderna har vi hittat en bijektiv avbildning.

Exempel med ändliga mängder: A = {a, b, c} och B = {1, 2, 3}. Det första paret kan vara (a, 1), nästa (b, 2) och till sist (c, 3). Vi har använt alla element i båda mängderna och alltså hittat en bijektiv avbildning. Observera att det här inte är den enda bijektiva avbildningen. Det här är också en giltig lösning: (a, 3), (b, 1), (c, 2).

För oändliga mängder blir det lite intressantare. Vi provar udda och jämna positiva heltal. Intuitivt känns det som att det borde finnas lika många. Vi provar. Vi tar det första udda talet och avbildar det på det första jämna talet: (1, 2). Sedan det andra udda och det andra jämna: (3, 4). Och så vidare. Vi får paren (1, 2), (3, 4), (5, 6), (7, 8), … Vi kan skriva att varje udda tal l avbildas på det jämna talet l + 1 och att varje jämnt tal s är bilden av det udda talet s − 1. För varje udda och varje jämnt tal har vi alltså ett par som innehåller talet. Mängderna av udda och jämna tal är därför lika stora.

Jämna tal mot positiva heltal

Nu provar vi samma metod och jämför mängden av positiva heltal med mängden av jämna tal. Vi har mängderna ℤ⁺ = {1, 2, 3, 4, 5, 6, …} och S = {2, 4, 6, …}. Intuitivt väntar vi oss att mängden av positiva heltal är större.

Men låt oss försöka hitta en bijektiv avbildning. Vi kan säga att varje positivt heltal n avbildas på sitt dubbla värde, 2n. Då får vi paren (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … För varje positivt heltal n har vi alltså paret (n, 2n), och för varje jämnt tal s har vi paret (s/2, s). Vi har hittat en bijektiv avbildning, så mängden av jämna tal och mängden av positiva heltal är lika stora, de har samma kardinalitet.

Det kan verka förvirrande, eftersom de positiva heltalen ju innehåller fler element än de jämna talen. De positiva heltalen innehåller alla jämna tal och dessutom alla udda tal. Men eftersom vi kan hitta en bijektion är de båda mängderna lika stora.

Jämförelse med de positiva heltalen

De positiva heltalen (och lika väl de naturliga talen ℕ) anger i själva verket den minsta storleken på en oändlig mängd. Om en annan mängd har samma storlek som mängden av positiva heltal är det ofta ganska lätt att ta reda på: det räcker att hitta en bijektion till de positiva heltalen, vilket i praktiken betyder att det räcker att vi kan numrera, ordna elementen i vår mängd M.

Om vi alltså kan ordna elementen i en mängd så att vi kan avgöra vilket element som är det första, vilket som är det andra, tredje, fjärde, tionde och så vidare, så är mängden lika stor som ℤ⁺. En sådan mängd kallar vi uppräknelig.

Vi ser lätt att de jämna och de udda positiva heltalen är uppräkneliga, eftersom vi kan ange det första, andra, tredje osv. jämna/udda talet. Hur är det med de jämna heltalen? Alltså mängden S = {…, −4, −2, 0, 2, 4, …}. Kan vi ordna dem? Ja, vi tar samma ordning som förut och skriver direkt efter varje positivt jämnt tal även dess negativa motsvarighet: S = {0, 2, −2, 4, −4, 6, −6, …}. På liknande sätt går det till exempel för heltalen.

Storleken på de rationella talen

Ett intressantare exempel är de rationella talen, bråken. Kan vi ordna dem? Ja, men det blir lite svårare. Vi konstruerar en tabell med oändligt många rader och kolumner. I varje ruta står ett bråk. I kolumn n och rad m har vi bråket n/m. Alltså har vi i kolumn 1 och rad 2 bråket $\frac{1}{2}$, och i kolumn 3 och rad 4 bråket 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}$$

Hur ska vi nu ordna och numrera de här talen? Vi kan inte numrera dem rad för rad eller kolumn för kolumn, eftersom vi då skulle drunkna i den första raden/kolumnen. I stället tar vi talen längs diagonalerna: (första diagonalen:) 1/1, (andra diagonalen:) 2/1, 1/2, (tredje diagonalen:) 3/1, 2/2, 1/3, (fjärde diagonalen:) 4/1, 3/2, 2/3, 1/4, … Det finns fortfarande många upprepade bråk, men det gör ingenting. Det som stör mer är att de negativa talen saknas. Det löser vi enkelt: varje gång vi skriver ett bråk sätter vi direkt efter det dess negativa motsvarighet. Sedan saknas bara noll allra först. Och det var allt, nu har vi alla rationella tal i en följd.

Sammanlagt får vi alltså följden: 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, …

Storleken på de reella talen

Är de reella talen lika många som de positiva heltalen? Avgörandet blir ännu svårare än för de rationella talen. Vi gör ett motsägelsebevis. Antag att de reella talen är uppräkneliga och att det finns en bijektiv avbildning på de positiva heltalen. Vi antar alltså att de går att ordna. Och låt oss säga att följande avbildning är den ordningen:

$$\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 finns de sju första reella talen i vår ordning. Ordningen kan förstås vara godtycklig, talen behöver inte vara sorterade efter storlek.

Enligt antagandet är alla reella tal ordnade i den här oändliga tabellen. (Tabellen är återigen oändlig, här syns bara de sju första posterna.) Nu ska vi försöka hitta/konstruera ett tal som är reellt men inte finns i tabellen. Om vi hittar ett sådant tal är det en motsägelse mot att alla reella tal finns i tabellen, och av det kan vi sluta oss till att mängden av reella tal inte är uppräknelig.

Talet som inte finns i tabellen konstruerar vi så här:

$$\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 börjar med att skriva 0,… Så kommer vårt nya reella tal att se ut i början. På den första decimalplatsen sätter vi en siffra som inte står på första platsen i det första reella talet i vår ordning (i tabellen är den markerad med en ruta). Där står siffran 3, så vi väljer till exempel 1 och får talet 0,1…

Vi fortsätter. På andra platsen sätter vi en siffra som inte står på andra platsen i det andra reella talet. Där står 9, så till exempel 2. Vi får talet 0,12… På tredje platsen sätter vi en siffra som skiljer sig från tredje siffran i det tredje reella talet. Där står 3, så vi väljer till exempel 7. Vi får 0,127…

Och så vidare och så vidare. På plats n i det nya talet står alltid en siffra som skiljer sig från siffran på plats n i tal nummer n i vår ordning.

Vad får vi ut av det? Vi får ett tal som skiljer sig från alla tal i vår ordning i minst en siffra. Ta det senaste preliminära resultatet: 0,127… Det här talet skiljer sig säkert från det första talet i vår ordning i minst den första siffran, eftersom vi byggde det så. Från det andra talet skiljer det sig i minst den andra siffran. Från det tredje i den tredje siffran. I allmänhet skiljer sig det nya talet från talet på plats n i ordningen i minst siffran på plats n.

Det nykonstruerade talet finns alltså inte i tabellen, som skulle symbolisera en bijektion mellan de positiva heltalen och de reella talen. De reella talen är därför fler än de positiva heltalen. De reella talen är inte uppräkneliga, de är överuppräkneliga.

Fler källor

• Are there more odd or even numbers? (på engelska)