Tellbart beløp

I mengdelære , er et sett kalt tellbar uendelig hvis den har samme effekt som settet av naturlige tall . Dette betyr at det er en sammenheng mellom og settet med naturlige tall, slik at elementene i settet kan "nummereres". ${\ displaystyle A}$ ${\ displaystyle \ mathbb {N}}$${\ displaystyle A}$${\ displaystyle A}$

I tillegg til de utallige uendelige settene, teller de endelige settene også til de høyest tellbare settene . Bruken av begrepet tellbart er ikke enhetlig. Avhengig av definisjonen, kan det bety enten uendelig eller høyst tellbar .

Et ikke-tomt sett som verken er endelig eller uendelig, kalles utellelig .

Tykkelsen på et utallig uendelig sett er for eksempel betegnet som et hovednummer med (talt: alef null) . For denne betegnelsen se også aleph-funksjonen . ${\ displaystyle \ aleph _ {0}}$${\ displaystyle \ left | \ mathbb {N} \ right | = \ aleph _ {0}}$

Eksempler på utallige uendelige sett

Naturlige tall

Settet med naturlige tall er uendelig per definisjon , siden det har samme kraft som seg selv. ${\ displaystyle \ mathbb {N}}$

primtall

Settet med primtall er også uendelig , siden det er en delmengde av de naturlige tallene, og ifølge Euklids teorem også uendelig. ${\ displaystyle \ mathbb {P}}$

${\ displaystyle n}$	1	2	3	4. plass	5	Sjette	7.	8. plass	...
${\ displaystyle f (n)}$	2	3	5	7.	11	13	17.	19.	...

Hele tall

Sett med heltall er uendelig, en telling er for eksempel gitt ${\ displaystyle \ mathbb {Z}}$

${\ displaystyle n}$	1	2	3	4. plass	5	Sjette	7.	8. plass	...
${\ displaystyle f (n)}$	0	1	−1	2	−2	3	−3	4. plass	...

Eksemplene på primtall og heltall viser at både reelle delsett og supersett kan ha samme kardinalitet som basissettet, i motsetning til forholdene for endelige sett .

Par av naturlige tall

Settet med alle par med to naturlige tall er også uendelig uendelig. ${\ displaystyle (i, j) \ in \ mathbb {N} \ times \ mathbb {N}}$

Igjen er uendelig tydelig. Spørsmålet om tellbarhet er vanskeligere. For dette bruker man parringsfunksjonen Cantor , som tilordner hvert nummer med et naturlig tall . Dette betyr at alle tallpar kan tydelig nummereres og dermed telles. ${\ displaystyle (i, j)}$${\ displaystyle k}$

${\ displaystyle n}$	1	2	3	4. plass	5	Sjette	7.	8. plass	9	10	...
${\ displaystyle f (n)}$	1.1	1.2	2.1	1.3	2.2	3.1	1.4	2.3	3.2	4.1	...

n -Tupler av naturlige tall

Settet med alle tupler med naturlige tall er også uendelig uendelig. Dette vises i sin tur ved å bruke Cantor paringsfunksjonen flere ganger . ${\ displaystyle n}$${\ displaystyle (i_ {1}, i_ {2}, \ ldots, i_ {n})}$${\ displaystyle \ mathbb {N} ^ {n}}$${\ displaystyle (n-1)}$

Rasjonelle tall

Georg Cantor viste med det såkalte første diagonale argumentet at settet med rasjonelle tall kan telles, i likhet med ethvert sett med form ( tupler av hele tall ). ${\ displaystyle \ mathbb {Z} ^ {n}}$

Figuren , er surjektiv , så kardinaliteten til er at de fleste så stor som det av . Siden det på den ene siden er uendelig mange brøker, og på den andre siden er settet uendelig, er det også uendelig. ${\ displaystyle \ mathbb {N} _ {0} ^ {3} \ rightarrow \ mathbb {Q}}$${\ displaystyle (i, j, k) \ mapsto {\ frac {ij} {1 + k}}}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle \ mathbb {N} _ {0} ^ {3}}$${\ displaystyle \ mathbb {N} _ {0} ^ {3}}$${\ displaystyle \ mathbb {Q}}$

Algebraiske tall

Et algebraisk tall er roten av et polynom med heltallige koeffisienter . Høyden på er definert som . ${\ displaystyle P (x) = a_ {0} + \ prikker + a_ {n} x ^ {n}}$${\ displaystyle P}$${\ displaystyle h (P) = | a_ {0} | + \ prikker + | a_ {n} | + n}$

For en gitt høyde er det bare endelig mange polynomer, som igjen bare har endelig mange nuller; for hver av disse k har polynomet null . Hvis alle disse nullene er satt som settet, er settet med algebraiske tall unionen . ${\ displaystyle k> 0}$${\ displaystyle a_ {0} = k-1}$${\ displaystyle P (x) = - a_ {0} + x ^ {1}}$${\ displaystyle x = a_ {0} \ in \ mathbb {N}}$${\ displaystyle Q (k)}$${\ displaystyle \ mathbb {A}}$${\ displaystyle \ bigcup _ {k \ in \ mathbb {N} \ setminus \ {0 \}} {Q (k)}}$

Som en tellbar forening av endelige sett er den derfor tellbar. På den annen side , siden inneholder er uendelig. ${\ displaystyle \ mathbb {A}}$${\ displaystyle \ mathbb {A}}$${\ displaystyle \ mathbb {N}}$${\ displaystyle \ mathbb {A}}$

Ord over et alfabet

Ved å bruke den såkalte standardnummereringen via alfabetet , kan man også telle ordene til et språk i betydningen matematikk. ${\ displaystyle \ Sigma}$

Beregnbare tallfunksjoner

Settet av alle beregne nummer funksjoner er countably uendelig. Man kan spesifisere en standard nummerering av alle tenkelige båndprogrammer . Siden antall båndprogrammer er større enn antall beregningsfunksjoner (det kan være to forskjellige programmer som beregner den samme funksjonen), er tallfunksjonene uendelige.

Eksempel på et utallig uendelig sett

Settet med reelle tall er derimot utallige . Dette betyr at det ikke er noen kartlegging som viser hvert reelle tall til et naturlig tall, se Cantors andre diagonale argument .

eiendommer

• Hvert delsett av et (høyst) tellbart sett er (høyst) tellbart.
• Den forening av to (høyst) Tellbar er (høyst) tellbar.
• Mer generelt er hver forening av et tellbart antall (høyst) tellbare sett igjen (på det meste) tellbart.
• Det kartesiske produktet av to (høyst) tellbare sett er (på det meste) tellbart.
• Hvis det er en overføring av settet med naturlige tall på settet , er det høyest tellbart.${\ displaystyle \ mathbb {N}}$${\ displaystyle A}$${\ displaystyle A}$
• Hvert utallige sett er maksimalt opptellingen.

Se også

• I topologi oppfyller "små" topologiske rom et aksiom av tellbarhet .
• Hovednummer (matematikk)