Gud kan räkna upp de oändligt många rationella talen på en sekund

Gud kan räkna upp de oändligt många rationella talen på en sekund

…men han kan aldrig räkna upp de reella talen. Det har Georg Cantor bevisat.

Jag visade i förra posten ett sätt att klämma in de oändligt många rationella talen i var sitt rum på David Hilberts hotell.

Men hur kan Gud räkna upp de oändligt många rationella talen under en ändlig tidsperiod?

Man tycker att det borde vara omöjligt men Gud är väldigt fiffig. Så här kan han gå till väga för att räkna upp alla oändligt många tal på en enda sekund:

Han ägnar den första halvsekunden åt att räkna upp det första rationella talet.

Han ägnar nästa fjärdedels sekund åt att räkna upp det andra talet

Han ägnar nästa åttondels sekund att räkna upp det tredje talet.

Han ägnar nästa sextondels sekund att räkna upp det fjärde talet, o.s.v.

Gud räknar alltså snabbare och snabbare. Han använder hela tiden hälften så lång tid till att räkna upp nästa tal i jämförelse med den tid han använde till det föregående.

Tidsåtgången kan skisseras på följande sätt:

1/2+1/4+1/8+1/16+1/32+ …

Denna summa av allt kortare tidsperioder kommer närma sig en sekund allt mer i all oändlighet men kan omöjligen överskrida den gränsen. Detta innebär att, när en sekund har gått så finns det inget rationellt tal som inte Gud har räknat upp. Alla tal är uppräknade.

*

Än ännu större utmaning i uppräkningsbarhet än de rationella talen är mängden av alla ändliga listor med positiva heltal.

Vad beträffar de rationella talen så betraktade vi dem i princip som mängden av alla listor med två heltal – täljare och nämnare.

Mängden av alla ändliga listor med positiva heltal innehåller bland annat:

1) Det oändliga antalet listor med bara ett positivt heltal. Te.x listan med talet sexhundratolv: (612)
2) Det oändliga antalet listor med 2 positiva heltal.T.ex. listan (16245, 3429849)
3) Det oändliga antalet listor med 3 positiva heltal. T.ex. listan (1, 2, 187287387)
4) Det oändliga antalet listor med 4 positiva heltal. T.ex. listan (182, 4459, 1, 29898)

1 000 000 000) Det oändliga antalet listor med en miljard positiva heltal…
o.s.v…

Kan alla medlemmar i denna mängd verkligen få ett rum i Hilberts Hotell?

Enklaste sättet att ge dessa heltalslistor unika rum är helt enkelt att koda dem i någon talbas mindre än 10 och sedan låta t.ex. siffran 9 beteckna avdelningen mellan två heltal i listan.

Låt oss testa och se hur några olika tal skulle kunna kodas med basen nio:

Följer man denna princip skulle alltså rummet med nummer: 278539532876975198138 innehålla heltalslistan (18921, 317103, 613, 5948)

På detta sätt skulle varje tänkbar (icke oändlig) lista med heltal få sitt eget rum på Hilberts hotell.

Värt att notera är dock att inte alla rum kommer att behöva användas. Det gäller t.ex. de rum vars rumsnummer innehåller flera nior bredvid varandra. Dessa rumsnummer har ingen bestämd tolkning och kan sägas vara odefinierade.

*

Men hur är det med de reella talen? Kan Gud räkna upp även dessa? Här måste Gud tyvärr kasta in handduken. Georg Cantor bevisade att en sån bedrift är omöjlig.

Mängden av alla reella tal skulle kunna liknas vid mängden av alla oändliga listor av siffror, (d.v.s. siffrorna 0,1,2,3,4,5,6,7,8,9).

Varje reellt tal skulle kunna betraktas som en oändlig decimalutveckling – en oändlig följd av siffror.

Konstanterna Pi och e t.ex. är ju ett reella tal med oändliga rader av decimaler.

Men, kanske man kan invända, inte alla reella tal har ju oändliga rader med decimaler. Jovisst är det så, men syftet i just detta fall är att påvisa de reella talens ”o-uppräkningsbarhet” och då räcker det om vi tar i, så att säga i underkant. Det är lätt att konstatera att de reella talen, bland annat, har oändliga antal tal, med oändliga decimalutvecklingar. Sen, att det dessutom existerar reella tal som inte har oändliga decimalutvecklingar, det kommer inte att utgöra ett problem för vårt bevis.

Georg Cantors argument, det så kallade diagonalargumentet, påvisade att ingen oändlig uppräkning av reella tal skulle kunna vara komplett eftersom man, enligt ”diagonalmetoden”, alltid kan definiera att tal som inte finns med i listan. I en oändlig uppräkning av reella tal saknas alltid det tal…

…vars första siffra skiljer sig från den första siffran i den oändliga uppräkningens första siffra och
vars andra siffra skiljer sig från den den andra siffran i den oändliga uppräkningens andra siffra och
vars tredje siffra skiljer sig från den den tredje siffran i den oändliga uppräkningens tredje siffra…
o.s.v

Det saknade talet skiljer sig alltså per definition från varje tal i den oändliga uppräkningen. Skulle man lägga till det saknade talet till listan så skulle man alltid kunna konstruera ett nytt tal som skiljer sig från varje tal i den kompletterade listan.

För mig känns ändå Cantors diagonalbevis lite onödigt. Är det inte ganska uppenbart att man inte kan ”lagra” alla pi:s decimaler i ett rumsnummer med ett ändligt antal siffor. Vi har ju tidigare sett att varje ändlig mängd information kan kodas så att den kan lagras i rumsnumret på Hotellet. Hotellet har visserligen ett oändligt antal rum vilket innebär att det inte finns någon gräns för hur många siffror rumsnumren kan ha, men det betyder inte att det existerar något specifikt rumsnummer vars antal siffror saknar gräns. Pi kan alltså inte lagras i något specifikt rum. De reella talen är ouppräkningsbara. Gud går bet. Även om Gud är grym på att räkna oändligt snabbt.

Not: Originalbilden på Gud, Adam och Eva är ett träsnitt av Julius Schnorr von Carolsfeld från omkring 1860. Den heter ”Der sechste Schöpfungstag” (”Den sjätte skapelsedagen”)

How to Give Every Rational Number a Room at Hilbert’s Hotel

For example. Let’s take the rational number  -3/4 .

In what room in Hilbert’s Hotell will we find that number?

Just insert the values -3 (=a) and 4 (=b) into the formula and we get…

so in room 1408 we’ll find -3/4.

Note that the comparison operators like ”<” or ”≥” evaluates to 1 if true or 0 if false.

This shows that the set of rational numbers is enumerable.

PS:
To represent every possible rational number it may seem unnecessary to allow for negative integers in both nominator and denominator… Yes, that’s true. It’ not necessary. I just wanted to keep the symmetry.

Hilberts oändliga hotell

Är mängden positiva rationella tal

där tal ingår som exempelvis

lika stor som mängden heltal?

Eller annorlunda uttryckt:  Skulle alla positiva rationella tal kunna få var sitt rum på Hilberts hotell?

Svaret är ja.

För att förklara hur det är möjligt kan vi utgå från ett liknande problem.

Hur kan ett hotell med ett oändligt antal rum varje dag ta emot en ny buss med ett oändligt antal gäster?

Den enklaste principen som hotellet kan utnyttja är att varje dag endast fylla vartannat av de rum som fortafarande står tomma.

Om vi t.ex. utgår från att hotellet från början är tomt så ger vi busspassagerarna dag ett vartannat rum. D.v.s. rum 1,3,5,7,9,11,13 o.s.v De jämna rummen står fortfarande tomma.

De oändligt många busspassagerarna dag två ger vi vartannat av de kvarvarande jämna rummen: D.v.s rum 2,6,10,14,18,22,26,30 o.s.v

De oändligt många busspassagerarna dag tre ger vi vartannat av de kvarvarande rummen: D.v.s. rum 4,12,20,28,36,44 o.s.v

Och så kan vi fortsätta hur länge som helst.

Vi kan formulera en enkel formel för vilket rum en given busspassagerar får.

Om vi betecknar numret på busspassageraren med a och numret på ankomstdagen med b så kan vi tilldela alla ett rumsnummer, r,  med hjälp av formeln:

För att formeln ska bli snyggare så börjar vi räkna från noll istället för ett. Den första passageraren som kliver av bussen betecknar vi passagerare noll (a = 0). Den första dagen betecknar vi dag noll (b = 0).

Vi ser då t.ex. att den första passageraren, den första dagen får rum nummer 1.

Eller att passagerare nummer nittiotre på dag nummer sjutton får rumsnummer…

…tjugofyra miljoner femhundratio tusen fyrahundrasextiofyra.

Varje passagerare, varje dag, tilldelas alltså ett unikt rumsnummer som är ledigt och som ingen annan kommer göra anspråk på.

En trevlig egenskap i detta system är att hotellpersonalen inte behöver skriva upp passagerarnummer och ankomstdag i nåt register. Endast utifrån numret på hotellrummet så kan de lista ut detta.

Tag hotellrum 24 510 464 ovan t.ex. När anlände gästen och vilket passagerarnummer hade hon? Det enda hotellpersonalen behöver göra är att se hur många gånger som rumsnumret är delbart med två. Svaret är sjutton gånger. (17 är alltså ankomstdagen) När man delat rumsnumret med 2 sjutton gånger så har vi fått 187 vilket är udda och inte längre delbart. 187 motsvarar 2a+1 i vår formel. Om vi sålunda drar av 1 och delar med 2 så får vi passagerarnumret:

Tillbaka nu till problemet med om varje rationellt tal kan få ett eget rum på Hilberts hotell.

Alla rationella tal kan skrivas på formen  a/b

och vi kan tänka oss att det varje dag kommer en oändlig busslast passagerare som representerar en unik ny nämnare.

Första dan kommer den oändliga busslasten med bråktal där nämnaren är 1:

Andra dan kommer den oändliga busslasten med bråktal där nämnaren är 2:

och så vidare.

Man noterar här snabbt att det rationella talet 1 som kliver av bussen allra först dag ett även kliver av bussen som nummer 2 dag två. Talet 1 kommer därmed att bo i mer än ett rum. Detta har emellertid ingen betydelse för tankeexperimentet. Det enda vi ville kontrollera var om alla rationella tal fick egna rum på Hilberts hotell. Att tal kan få mer än ett rum är inget som försvagar argumentet.

Dessa busslaster med rationella tal skulle kunna inhysas i rum enligt samma formel som vi undersökte tidigare. Vi inför följande lilla modifikation:

Vi betecknar varje tänkbart positivt rationellt tal som bråket:

där a och b betecknar godtyckliga heltal  0, 1, 2, 3, 4, 5, 6, 7 …

För ett godtyckligt rationellt tal t.ex. 17/5 = 3,4  gäller alltså att a=16 och b=4

Då kan vi använda samma formel för rumsnumret r:

Det rationella talet  17/5  får rummet

Ett alternativt system för att ta emot oändliga busslatser gäster på Hilberts hotell varje dag och som gör rumsnumret lite lättare att tolka är följande:

Princip för inhysning: Utnyttja varje dag alla kvarvarande lediga rum utom vart tionde.

Första dagen flyttar alltså gästerna in i rummen 1,2,3,4,5,6,7,8,9 … 11,12,13,14,15,16,17,18,19 … 21,22 o.s.v.

Det innebär i så fall första dagen att alla rum utom rum 10,20,30,40 o.s.v. utnyttjas.

Andra dagen används återigen samma princip: alla kvarvarande lediga rum utom vart tionde utnyttjas. Gästerna flyttar in i rummen 10,20,30,40,50,60,70,80,90 … 110,120,130,140 o.s.v

Rummen som lämnas lediga efter dag två är då 100,200,300,400,500 o.s.v.

Och så här fortsätter det, dag efter dag. Fördelen med den här principen är att hotellpersonalen enkelt kan läsa av antalet nollor på dörren till rummen för att veta ankomstdag.

Formeln som ger oss rumsnumret r utifrån passagerarnummret a och dagnumret b blir dock lite mer komplicerad.

Denna princip funkar naturligtvis också för att hysa alla positiva rationella tal

Meditation on Destruction

I put together a film this morning: Meditation on Destruction – The Machine that Destroys Everything.

The sound is essential. The crunching and tearing of metal is mesmerizing.

The sound of the bicycle saddle getting eaten at 0:33 is almost too good.

The film is put together from parts of video clips from the so called SSI’s Shred of the month series.

Ksenia Ovsyanick i Eldfågeln


Ksenia Ovsyanick i Eldfågeln

Oj vad snyggt. Jag är ledsen att jag missade den här uppsättningen av Eldfågeln som English National Ballet satte upp tidigare i år på London Coliseum.


Ksenia Ovsyanick i Eldfågeln

Dark, turbulent ‘Harry Potter’ clouds roll ominously across the back cloth as the mysterious opening music tells of pending doom. The light lifts, but only slightly (the whole ballet is done in gloom), to show his new-look Firebird, now a sleek avian encased in a bodysuit skin of glistening gold with a helmet of feathers, designed by David Bamber. She and the woman ‘Purity’ soon get tainted with the ways of the material world… (from review by Margaret Willis)

These characters look more like video-game avatars – today’s world of magic – and their moves have the faintly surreal slink of Russian “artistic gymnastics”. (from review by )


Ksenia Ovsyanick i Eldfågeln