13 svar
267 visningar
Qetsiyah är nöjd med hjälpen

En äkta delmängd kan ha samma kardinalitet som mängden?

På wikipedia: 

It is possible for a proper subset of an infinite set to have the same cardinality as the original set, something that cannot happen with proper subsets of finite sets.

Men det finns inget exempel på det, jag vill se ett

parveln 729
Postad: 23 apr 2020 19:48 Redigerad: 23 apr 2020 19:49

N och Z+ är väl det enklaste exemplet. Du hittar nog bijektionen själv. Faktum är att varje oändlig mängd har en äkta delmängd med samma kardinalitet som mängden själv.

Edit: Det sista påståendet gäller i ZFC.

Arktos 1089
Postad: 23 apr 2020 19:51

Mängden positiva heltal är (uppräkneligt) oändlig.
Mängden positiva jämna tal är en äkta delmängd till den.
Ändå har de lika många element.

Visst?

oggih 872 – F.d. Moderator
Postad: 25 apr 2020 14:22 Redigerad: 25 apr 2020 14:58

Kom ihåg att två mängder XX och YY sägs ha samma kardinalitet om det finns en bijektion f:ABf:A\to B.


Vardagligt exempel: Om du av någon anledning skulle glömma hur man räknar med naturliga tal, så kan du alltid kontrollera huruvida du har lika många fingrar på din högerhand som på din vänsterhand genom att försöka para ihop fingrarna på respektive hand med varandra!

Mr. Burns i The Simpsons kan t.ex. nöjt konstatera att han har lika många fingrar på båda händerna! ^_^


Ett annat exempel: Mängden av alla heltal \mathbb{Z} har samma kardinalitet som mängden av jämna heltal 22\mathbb{Z}. Som bijektion ("ihopparning") kan vi välja dubbleringsfunktion f:2f:\mathbb{Z}\to 2\mathbb{Z} med f(n)=2nf(n)=2n. Det är enkelt att kontrollera att den är både injektiv och surjektiv, dvs. en bijektion.

Om vi vill kan vi skriva ut den lite mer explicit så här:

\vdots

(-2)(-4)(-2)\mapsto (-4)

(-1)(-2)(-1)\mapsto (-2)

000\mapsto 0

121\mapsto 2

242\mapsto 4

363\mapsto 6

\vdots

oggih 872 – F.d. Moderator
Postad: 25 apr 2020 14:43 Redigerad: 25 apr 2020 15:12

Ett till exempel: Mängden av de naturliga talen \mathbb{N} har har samma kardinalitet som mängden av alla heltal \mathbb{Z}. Ett sätt att visa detta är att göra följande ihopparning \mathbb{N}\to\mathbb{Z}:

000\mapsto 0

1-11\mapsto -1

212\mapsto 1

3-23\mapsto -2

424\mapsto 2

5-35\mapsto -3

\vdots

Är du med på vad regeln är? Vilket heltal skulle den här bijektionen mappa det naturliga talet 129129 till?


Coolare exempel: Mängden av alla heltal \mathbb{Z}  har samma kardinalitet som mängden av alla rationella tal \mathbb{Q}.

Idén förklaras i den här youtubevideon:

https://www.youtube.com/watch?v=WQWkG9cQ8NQ

Notera dock att detta bara ger dig en bijektion mellan positiva heltal och positiva rationella tal, men det är enkelt att utvidga detta till en bijektion \mathbb{Z}\to\mathbb{Q} (hur?).

oggih 872 – F.d. Moderator
Postad: 25 apr 2020 14:51 Redigerad: 25 apr 2020 15:01

Ett sista exempel (som du lärde dig redan på gymnasiet, även om det kanske inte var någon som påpekade det då):

Intervallet (-π/2,π/2)(-\pi/2,\pi/2) har samma kardinalitet som hela den reella tallinjen!

Som bijektion kan vi välja... ja, vaddå? Ledtråd: tänk trigonometriskt!

Visa spoiler

Tangens! Funktionen tan:(-π2,π2)\tan: (-\frac{\pi}{2},\frac{\pi}{2})\to \mathbb{R} är både injektiv och surjektiv.

Övning: Modifiera det här exemplet för att skapa en bijektion från (0,1)(0,1) till \mathbb{R}.


Eller okej, detta är det sista exemplet: Man kan visa att det inte går att hitta en bijektion mellan \mathbb{Z} och \mathbb{R}, så i någon mening har \mathbb{R} en "större oändligt stor" kardinalitet än \mathbb{N}, \mathbb{Z} och \mathbb{Q}. Googla på "Cantor's diagonal argument" och försök förstå hur det fungerar!

PATENTERAMERA 2354
Postad: 25 apr 2020 18:56

Intressant är ju att  och 2 har samma kardinalitet. Vilket känns lite överraskande, tycker i alla fall jag.

PATENTERAMERA skrev:

Intressant är ju att  och 2 har samma kardinalitet. Vilket känns lite överraskande, tycker i alla fall jag.

Men Rn har också samma? Är det inte ännu mer överraskande?

Qetsiyah 5222 – Volontär digitala räknestugor
Postad: 25 apr 2020 19:28 Redigerad: 25 apr 2020 19:43

Oj *****, jag kom på en sak. Kan ett stängt intervall ha samma kardinalitet som R?

Edit: ja säkert, men frågan är om bijektionen kan definieras av en kontinuerlig funktion

Edit2: är denna garret credi lite beng? https://www.quora.com/Does-the-closed-interval-0-to-1-have-the-same-cardinality-as-the-set-of-Real-numbers

Edit3: oj det var ju svaret på din fråga också oggih, hehe

Laguna 14313
Postad: 25 apr 2020 21:31

Jag tror det heter "slutet" på svenska.

Ojdå, slutet, vilken ful anglicism

oggih 872 – F.d. Moderator
Postad: 26 apr 2020 01:02 Redigerad: 26 apr 2020 01:16
Qetsiyah skrev:

Kan ett stängt intervall ha samma kardinalitet som R?

Det är en bra fråga, och faktiskt lite lättare sagt än gjort.

Har du lyckats modifera vår bijektion (-π/2,π/2)(-\pi/2,\pi/2)\to\mathbb{R} till en bijektion f:(a,b)2f:(a,b)\to\mathbb{R}^2 för ett generellt öppet intervall (a,b)(a,b)\subsetneq\mathbb{R}? (Idén finns i länken du postade innan.) Bra i så fall! 

Det vi kan göra nu är att hitta en bijektion g:[a,b](a,b)g:[a,b]\to (a,b). Om vi lyckas med det, så kan vi koppla ihop bijektionerna till sammansättningen fgf\circ g och voilà: vi har en bijektion [a,b][a,b]\to \mathbb{R}. (Stanna gärna upp och övertyga dig om att sammansättningen av två bijektioner alltid är en bijektion!)


Precis som innan börjar vi med det enklaste/renaste fallet, vilket i det här fallet är a=0a=0 och b=1b=1. Jag hävdar att g:[0,1](0,1)g:[0,1]\to (0,1), definierad av 

   g(x)=12om x = 012n+1om x = 12nn>013om x = 113n+1om x = 13nn>0xannarsg{(x)}= \left\{\begin{array}{l l}\frac{1}{2} & \text{om $x = 0$}\\ \frac{1}{2^{n+1}} & \text{om $x = \frac{1}{2^n}$, $n>0$}\\ \frac{1}{3}& \text{om $x = 1$}\\ \frac{1}{3^{n+1}} & \text{om $x = \frac{1}{3^n}$, $n>0$}\\ x & \text{annars}\end{array}\right.

gör jobbet. Notera att de allra flesta punkter i [0,1][0,1] mappas till sig själva, men att vi "knör in" (finns det hjärterum så finns det stjärterum!) intervallets ändpunkter i (0,1)(0,1) genom att mappa 0120\mapsto \frac{1}{2} och 1131\mapsto \frac{1}{3}. Problemet är att vi då inte får lov att mappa 1212\frac{1}{2}\mapsto \frac{1}{2} eller 1313\frac{1}{3}\mapsto \frac{1}{3}, för då skulle vi sabba injektiviteten. I stället tar vi till följande trick: vi liksom "förskjuter" alla multiplar av en halv och en tredjedel med ett steg, på följande vis:

1214\frac{1}{2}\mapsto \frac{1}{4},    1418\frac{1}{4}\mapsto \frac{1}{8},    18116\frac{1}{8}\mapsto \frac{1}{16} osv.

1319\frac{1}{3}\mapsto \frac{1}{9},    19127\frac{1}{9}\mapsto \frac{1}{27},    127181\frac{1}{27}\mapsto \frac{1}{81} osv.

Notera att detta gör att funktionen g:[0,1](0,1)g:[0,1]\to (0,1) blir både injektiv och surjektiv - alltså en bijektion!

Jämför förresten hemskt gärna det där tricket på slutet med Hilberts hotell (googla!). Precis som det alltid finns plats för en gäst till i Hilberts hotell, så finns det tydligtvis utan några som helst problem plats för 0:an och 1:an i det öppna intervallet (0,1)(0,1)!

Övning (lite kladdigt, men inte jättesvårt): Modifiera funktionen funktionen så att du får en bijektion [a,b](a,b)[a,b]\to (a,b) för generella a<ba<b.

En till övning (rätt enkelt): Utgå från tankexperimentet "Hilberts hotell" för att hitta en bijektion från ={0,1,2,3,}\mathbb{N}=\{0,1,2,3,\ldots\} till +={1,2,3,}\mathbb{Z}^+=\{1,2,3,\ldots\}.

oggih skrev:

Det vi kan göra nu är att hitta en bijektion g:[a,b](a,b)g:[a,b]\to (a,b). Om vi lyckas med det, så kan vi koppla ihop bijektionerna till sammansättningen fgf\circ g och voilà: vi har en bijektion [a,b][a,b]\to \mathbb{R}. (Stanna gärna upp och övertyga dig om att sammansättningen av två bijektioner alltid är en bijektion!)

Det gjorde jag förra sommaren medan jag åt en kladdkaka med en jordgubbe minns jag (inte ironisk).

Precis som innan börjar vi med det enklaste/renaste fallet, vilket i det här fallet är a=0a=0 och b=1b=1. Jag hävdar att g:[0,1](0,1)g:[0,1]\to (0,1), definierad av 

   g(x)=12om x = 012n+1om x = 12nn>013om x = 113n+1om x = 13nn>0xannarsg{(x)}= \left\{\begin{array}{l l}\frac{1}{2} & \text{om $x = 0$}\\ \frac{1}{2^{n+1}} & \text{om $x = \frac{1}{2^n}$, $n>0$}\\ \frac{1}{3}& \text{om $x = 1$}\\ \frac{1}{3^{n+1}} & \text{om $x = \frac{1}{3^n}$, $n>0$}\\ x & \text{annars}\end{array}\right.

Den här måste jag smälta lite...

finns det hjärterum så finns det stjärterum!

Extra kul när "rum" har betydelse i matte hahaha

Notera att detta gör att funktionen g:[0,1](0,1)g:[0,1]\to (0,1) blir både injektiv och surjektiv - alltså en bijektion!

Jämför förresten hemskt gärna det där tricket på slutet med Hilberts hotell (googla!). Precis som det alltid finns plats för en gäst till i Hilberts hotell, så finns det tydligtvis utan några som helst problem plats för 0:an och 1:an i det öppna intervallet (0,1)(0,1)!

Ja, det vet jag om såklart! Det är populärmatematik!

Övning (lite kladdigt, men inte jättesvårt): Modifiera funktionen funktionen så att du får en bijektion [a,b](a,b)[a,b]\to (a,b) för generella a<ba<b.

Oj...

En till övning (rätt enkelt): Utgå från tankexperimentet "Hilberts hotell" för att hitta en bijektion från ={0,1,2,3,}\mathbb{N}=\{0,1,2,3,\ldots\} till +={1,2,3,}\mathbb{Z}^+=\{1,2,3,\ldots\}.

Haha. f: +, f(n)=n+1

Nu tänker jag på min gamla tråd: https://www.pluggakuten.se/trad/analys-trigfunktioner-och-godtyckligt-liten-period/?#post-19001eae-62bd-41b9-b50c-ab3e017dc397

Svara Avbryt
Close