15 svar
230 visningar
Qetsiyah är nöjd med hjälpen!
Qetsiyah 4709 – Volontär digitala räknestugor
Postad: 1 sep 2020 Redigerad: 1 sep 2020

Mängdlära: kardinalitet av mängden av autobijektioner på N

En fortsättning på https://www.pluggakuten.se/trad/linjar-algebra-etymologi-kvot-rum/

Beviset gäller att visa att kardinaliteten är samma som R. 

Men jag behöver nog fler ledtrådar oggih.

oggih 790 – F.d. Moderator
Postad: 1 sep 2020 Redigerad: 1 sep 2020

Frågan gäller alltså kardinaliteten av mängden Sym()\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:

  1. Visa att Sym()\mathrm{Sym}(\mathbb{N}) är en oändlig mängd (dvs. att |||Sym()||\mathbb{N}|\leqslant |\mathrm{Sym}(\mathbb{N})|).
  2. Visa att Sym()\mathrm{Sym}(\mathbb{N}) är överuppräknelig (dvs. ||<|Sym()||\mathbb{N}|<|\mathrm{Sym}(\mathbb{N})|).
  3. Visa att Sym()\mathrm{Sym}(\mathbb{N}) har samma kardinalitet som \mathbb{R} (dvs. |Sym()|=c|\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".

oggih 790 – F.d. Moderator
Postad: 2 sep 2020 Redigerad: 2 sep 2020
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:f:\mathbb{N}\to\mathbb{N} och å andra sidan följder (a0,a1,a2,)(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(f(0),f(1),f(2),)f\mapsto (f(0),f(1),f(2),\ldots).)

oggih 790 – F.d. Moderator
Postad: 2 sep 2020 Redigerad: 2 sep 2020
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?

oggih 790 – F.d. Moderator
Postad: 2 sep 2020 Redigerad: 2 sep 2020
Ledtråd för (3)

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

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

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

Det går då att dra slutsatsen att det måste finnas en bijektion h:Sym()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 Sym()\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 Sym()\mathrm{Sym}(\mathbb{N})\to\mathbb{R} är det nog smidigast att jobba stegvis. Kanske kan man blanda in P()\mathcal{P}(\mathbb{N}) på något sätt? 

Qetsiyah 4709 – Volontär digitala räknestugor
Postad: 4 sep 2020 Redigerad: 4 sep 2020

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.

oggih 790 – F.d. Moderator
Postad: 4 sep 2020 Redigerad: 4 sep 2020

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 i=0ai\sum_{i=0}^\infty a_i vara en betingat konvergent serie [detta betyder att den är konvergent, men att i=0|ai|\sum_{i=0}^\infty |a_i| inte är konvergent]. Då kan vi för varje reellt tal xx\in\mathbb{R} hitta minst en permutation f:f:\mathbb{N}\to\mathbb{N} sådan att i=0af(i)=x\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 xx\in\mathbb{R} väljer en permutation fx:f_x:\mathbb{N}\to\mathbb{N} som får serien att konvergera mot xx så får vi en injektiv avbildning Sym()\mathbb{R}\to\mathrm{Sym}(\mathbb{N}) med xfxx\mapsto f_x, vilket ger att |||Sym()||\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 i=0nai\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 Sym()\mathrm{Sym}(\mathbb{N})\to\mathbb{R} (vilket i så fall, helt korrekt, skulle visa att att |||Sym()||\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:f:\mathbb{N}\to\mathbb{N} till värdet av den "permuterade serien" i=0naf(i)\sum_{i=0}^n a_{f(i)}. Enligt satsen skulle vi då "träffa" varje xx\in\mathbb{R} minst en gång. Perfekt! Men, problemet är att det även kommer finnas permutationer ff 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 2\sqrt{2}) och mappa alla sådana problematiska permutationer dit. Då får vi en väldefinierad surjektiv mappning Sym()\mathbb{R}\to \mathrm{Sym}(\mathbb{N}), och allt är frid och fröjd.

Qetsiyah 4709 – Volontär digitala räknestugor
Postad: 5 sep 2020 Redigerad: 5 sep 2020

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

oggih 790 – F.d. Moderator
Postad: 28 okt 2020 Redigerad: 28 okt 2020

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

   k=0(-1)kk+1.\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.

oggih 790 – F.d. Moderator
Postad: 28 okt 2020 Redigerad: 28 okt 2020

Ö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 ?

Qetsiyah 4709 – Volontär digitala räknestugor
Postad: 28 okt 2020 Redigerad: 28 okt 2020

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?

oggih 790 – F.d. Moderator
Postad: 29 okt 2020 Redigerad: 29 okt 2020

Liknelsen förklarar hur man, givet en godtycklig betingat konvergent serie i=0ai\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. 12+14+18+=1\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?

oggih 790 – F.d. Moderator
Postad: 29 okt 2020 Redigerad: 29 okt 2020

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 p1<p2<p3<p_1<p_2<p_3<\cdots och de negativa termernas index för n1<n2<n3<n_1<n_2<n_3<\cdots, så att termerna splittas i två separata listor: (api)i=1(a_{p_i})_{i=1}^\infty med positiva termer och (ani)i=1(a_{n_i})_{i=1}^\infty med negativa termer.
  • Notera att i=1api\sum_{i=1}^\infty a_{p_i} divergerar mot ++\infty, och att i=1ani\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 an1a_{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 |an1|+1|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 b1b_1. Den "omsorterade" serien kommer nu vara (ap1+ap2++ab1+an1)(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 an2a_{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).

Svara Avbryt
Close