Mängdlära: kardinalitet av mängden av autobijektioner på N (Matematik/Universitet)

Frågan gäller alltså kardinaliteten av mängden $\mathrm{Sym}(\mathbb{N})$ av alla bijektioner $\mathbb{N}\to\mathbb{N}$ (sådana bijektioner kallas även för permutationer eller symmetrier på $\mathbb{N}$ ).

Mest pedagogiskt vore kanske att börja med en enklare uppgift, och sedan successivt göra den svårare:

Visa att $\mathrm{Sym}(\mathbb{N})$ är en oändlig mängd (dvs. att $|\mathbb{N}|\leqslant |\mathrm{Sym}(\mathbb{N})|$ ).
Visa att $\mathrm{Sym}(\mathbb{N})$ är överuppräknelig (dvs. $|\mathbb{N}|<|\mathrm{Sym}(\mathbb{N})|$ ).
Visa att $\mathrm{Sym}(\mathbb{N})$ har samma kardinalitet som $\mathbb{R}$ (dvs. $|\mathrm{Sym}(\mathbb{N})|=\mathfrak{c}$ ).

Klarar du den första, eller rent av den andra? (Om du skulle lyckas lösa någon av de svårare först, så kan det vara värt att gå tillbaka och se om du kan hitta ett mer elementärt argument som räcker för att lösa någon av de enklare varianterna.)

Observera: Beroende på vilken metod man väljer har man inte nödvändigtvis så stor nytta av att ha löst (1) och (2) innan man löser (3) - så det är ingen klassisk "hjälp genom deluppgifter" jag ger nu - men det kan nog ändå vara en bra uppvärmning för att komma in i "kardinalitetstänket".

Ledtråd för (1)

Det enda du behöver göra är räkna upp oändligt många (mer eller mindre specifikt beskrivna) permutationer.

(Eventuellt hjälper det till med att få en konkret känsla för de här sakerna, om man inser att det finns ett 1-till-1-förhållande mellan å ena sidan bijektioner $f:\mathbb{N}\to\mathbb{N}$ och å andra sidan följder $(a_0,a_1,a_2,\ldots)$ av naturliga tal där varje naturligt tal förekommer precis en gång, som ges av mappningen $f\mapsto (f(0),f(1),f(2),\ldots)$ .)

Ledtråd för (2)

Kommer du ihåg hur man brukar visa att $\mathbb{R}$ är en överuppräknelig mängd?

Kanske kan du använda samma (eller en liknande) teknik här på något vis?

Ledtråd för (3)

Du har säkert märkt att när man vill visa en likhet $a=b$ så kan det ibland vara smidigt att göra det genom att först visa $a\leqslant b$ och sedan $b\leqslant a$ .

Ungefär samma sak gäller för kardinaltal!

I stället för att ge en explicit bijektion $\mathrm{Sym}(\mathbb{N})\to\mathbb{R}$ så räcker det att hitta en injektion $f:\mathrm{Sym}(\mathbb{N})\to\mathbb{R}$ (vilket vi tolkar som $|\mathrm{Sym}(\mathbb{N})|\leqslant|\mathbb{R}|$ och en injektion $g:\mathbb{R}\to\mathrm{Sym}(\mathbb{N})$ (vilket vi tolkar som att $|\mathbb{R}|\leqslant|\mathrm{Sym}(\mathbb{N})|$ ).

Det går då att dra slutsatsen att det måste finnas en bijektion $h:\mathrm{Sym}(\mathbb{N})\to\mathbb{R}$ mellan mängderna enligt vad som brukar kallas för Schröder-Bernsteins sats (kolla gärna upp på Wikipedia; även om det kan kännas som ett väldigt intuitivt resultat, så är beviset inte på något sätt trivialt).

För att få en injektion $\mathbb{R}\to\mathrm{Sym}(\mathbb{N})$ så kan du kanske fundera på om begreppet betingat konvergent serie ringer några klockor (eller sök runt lite på internet för att se om det finns någon koppling till permutationer - det finns det, och den är väldigt kul! ^_^).

För att få en injektion $\mathrm{Sym}(\mathbb{N})\to\mathbb{R}$ är det nog smidigast att jobba stegvis. Kanske kan man blanda in $\mathcal{P}(\mathbb{N})$ på något sätt?

Angående betingat konvergent serie tänker jag på något kul jag läste i en fourieranalysbok. Det fanns något som kallades svit, och uttömmande svit. Det var första gången jag såg skrivsättet i∈I under summatecknet. Det betyder att man kan arrangera en följd av (alla) heltal för att få vilket reellt tal som helst (vet inte om det bara var ett intervall, men det spelar ingen roll när vi talar om kardinalitet. Se valet av I som en bijektion från N till sig själv, mappa I till det summan konvergerar till. Vi har fått en surjektion fråm Sym(N) till R.

Men jag vet inte om vi behöver använda alla möjliga I för att "spänna" R.

Snyggt! Tänkte väl att du hade stött på Riemanns seriesats under något av dina analysäventyr! ^_^

Den säger kort och gott följande:

Sats. Låt $\sum_{i=0}^\infty a_i$ vara en betingat konvergent serie [detta betyder att den är konvergent, men att $\sum_{i=0}^\infty |a_i|$ inte är konvergent]. Då kan vi för varje reellt tal $x\in\mathbb{R}$ hitta minst en permutation $f:\mathbb{N}\to\mathbb{N}$ sådan att $\sum_{i=0}^\infty a_{f(i)}=x$ . (Vi kan dessutom hitta permutationer som får serien att divergera mot plus respektive minus oändligheten!)

Om för varje $x\in\mathbb{R}$ väljer en permutation $f_x:\mathbb{N}\to\mathbb{N}$ som får serien att konvergera mot $x$ så får vi en injektiv avbildning $\mathbb{R}\to\mathrm{Sym}(\mathbb{N})$ med $x\mapsto f_x$ , vilket ger att $|\mathbb{R}|\leqslant|\mathrm{Sym}(\mathbb{N})|$ , precis som vi ville visa!

Det enda som saknas nu är ett exempel på en betingat konvergent serie $\sum_{i=0}^n a_i$ (det måste existera betingat konvergenta serier för att vi ska kunna använda satsen!). Har du någon sådan serie i bakfickan? Kan du motivera varför den är betingat konvergent?

Men - det här var ju inte riktigt det du sa. Du sa i stället att vi kan använda satsen för att få en surjektion $\mathrm{Sym}(\mathbb{N})\to\mathbb{R}$ (vilket i så fall, helt korrekt, skulle visa att att $|\mathbb{R}|\leqslant |\mathrm{Sym}(\mathbb{N})|$ ).

Och mjae... det är rätt tänkt, men det finns en liten subtilitet som måste addresseras.

Jag antar att du menar att vi skulle mappa varje permutation $f:\mathbb{N}\to\mathbb{N}$ till värdet av den "permuterade serien" $\sum_{i=0}^n a_{f(i)}$ . Enligt satsen skulle vi då "träffa" varje $x\in\mathbb{R}$ minst en gång. Perfekt! Men, problemet är att det även kommer finnas permutationer $f$ som gör serien divergent. Till vilket reellt tal ska vi mappa de permutationerna? Well, vi kan ju faktiskt bara välja vårt favorittal (till exempel $\sqrt{2}$ ) och mappa alla sådana problematiska permutationer dit. Då får vi en väldefinierad surjektiv mappning $\mathbb{R}\to \mathrm{Sym}(\mathbb{N})$ , och allt är frid och fröjd.

Nääee, ingen i bakfickan nej. Men jag tänkte på en kul liknelse, men som jag inte riktigt förstår, kan du förklara?

bump

Ett av de mest klassiska exemplen på en betingat konvergent serie är

$\displaystyle\sum_{k=0}^\infty \frac{(-1)^k}{k+1}\,.$

När det gäller anmärkningen om Riemanns seriesats så får du gärna precisera mer vad det är du inte hänger med på, så försöker jag (eller någon annan) gärna att förklara bättre. Jag tycker det var en ganska bra och kul förklaring av bevisstrategin!

Den där liknelsen förstår jag nu faktiskt. Men det gjorde jag inte när jag frågade, tänk att det går att förstå nåt genom att bara vänta.

Övning/följdfråga i så fall: Kan du ge ett "recept" på hur man ska ordna termerna för att få en serie som divergerar mot $+\infty$ ?

Av det klassiska exemplet du visade?

Para ihop en negativ term och en positiv term så att varje par är positiv? Den där liknelsen gav väl mer specifikt ett recept för hur man får serien att konvergera till sitt önskade (ändliga) värde?

Liknelsen förklarar hur man, givet en godtycklig betingat konvergent serie $\sum_{i=0}^\infty a_i$ , ska sortera termerna för att få serien att konvergera till vilket ändligt tal som helst. Min fråga är om du på liknande vis kan förklara hur man ska sortera termerna för att få serien att divergera till $+\infty$ .

Att para ihop varje positiv term med en negativ term med mindre belopp räcker inte! Tänk om vi efter dessa "ihopparningar" får något som konvergerar (t.ex. $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots=1$ )?

Ja just det, men då konstruerar jag väl ihoppparningarna så att det divergerar?

Det blir väldigt mycket svenska och väldigt lite matte här i resonemangen (som Russel previs skrev i min andra tråd haha). Eller vill du antyda att det inte går?

Det går att sortera termerna så att serien divergerar. Övningen ligger att beskriva mer i detalj hur man ska göra!

Visa spoiler

Tricket är, precis som i liknelsen, att hålla reda på "inkomster" (positiva termer) och "räkningar" (negativa termer). För att vara helt exakta kan vi kalla de positiva termernas index för $p_1<p_2<p_3<\cdots$ och de negativa termernas index för $n_1<n_2<n_3<\cdots$ , så att termerna splittas i två separata listor: $(a_{p_i})_{i=1}^\infty$ med positiva termer och $(a_{n_i})_{i=1}^\infty$ med negativa termer.
Notera att $\sum_{i=1}^\infty a_{p_i}$ divergerar mot $+\infty$ , och att $\sum_{i=1}^\infty a_{n_i}$ divergerar mot $-\infty$ .
(Annars skulle vi får en motsägelse - varför?)
Kolla hur stor den första negativa termen $a_{n_1}$ är.
Vi kommer nu "skjuta upp" den "räkningen" tills vi klarar av att "betala" den med "minst 1 kronas marginal på kontot".
Mer precist börjar vi vår nya "omsorterade" serie med att lägga ihop så pass många positiva termer att summan blir större än eller lika med $|a_{n_1}|+1$ . (Varför är detta möjligt?)
Anta att detta kräver att vi tar med alla positiva termer till och med indexet $b_1$ . Den "omsorterade" serien kommer nu vara $(a_{p_1}+a_{p_2}+\cdots+a_{b_1}+a_{n_1})$ , och alltså vara större än eller lika med 1.
Kolla nu hur stor nästa negativa term $a_{n_2}$ är.
...

Hur ska du fortsätta nu? Varför kommer slutresultatet att vara en divergent serie (enligt definitionen av vad det innebär för en serie att divergera mot $+\infty$ )?

Kolla Wikipedia vid behov (notationen jag använder är kompatibel med beviset där).