Teljanlegt mengi

Teljanlegt mengi er mengi $A$ , sem er þannig búið að mögulegt er að setja fram gagntæka vörpun frá því á hlutmengi $B\subseteq \mathbb {N}$ náttúrulegu talnanna. Ef $B$ inniheldur óendanlega mörg stök (t.d. ef $B$ er mengi frumtalnanna eða sléttu talnanna) er $A$ ennfremur teljanlega óendanlegt. Sé mengi ekki teljanlegt er það kallað óteljanlegt.

Óformleg útskýring

Vissulega er ógjörningur að telja að fullu upp óendanleg mengi, teljanleg eða óteljanleg, í raunveruleikanum. Hvortveggja innihalda jú óendanlega mörg stök og gætu því í fljótu bragði virst jafn"óteljanleg" fyrir vikið. En það sem greinir að óendanleg mengi sem eru teljanleg og þau sem eru óteljanleg er að ef S er teljanlegt mengi er alltaf til upptalning á S (þ.e. runa af stökum úr S) sem kemur að hvaða staki a ∈ S sem er fyrr eða síðar ef haldið er áfram nógu lengi.

Ef S er óteljanlegt er ekki svo, þ.e. sama hvernig reynt er að telja S upp er alltaf til stak a ∈ S sem aldrei verður talið upp, sama hversu lengi er talið.

Dæmi

Sérhvert endanlegt mengi er teljanlegt þar sem unnt er að ganga á röðina af stökunum (röðin skiptir ekki máli) og úthluta hverju staki næstu náttúrulegu tölu, þar sem við byrjum á 1. Þessi aðgerð tekur enda því mengið er endanlegt, svo vörpunin er einfaldlega milli mengisins og fyrstu n náttúrulegu talnanna (sem er hlutmengi í $\mathbb {N}$ ) og er augljóslega gagntæk.
Mengi sléttra talna S er teljanlega óendanlegt. Þetta fæst beint út úr skilgreiningunni, þar sem S er jú hlutmengi í $\mathbb {N}$ . Hins vegar getum við sýnt að hægt sé að varpa S beint á mengi náttúrulegra talna. Smíðum vörpun $\phi :S\rightarrow \mathbb {N}$ þannig að $\phi (2k)=k$ fyrir sérhvert náttúrulegt k. Með öðrum orðum deilir $\phi$ sléttri tölu með tveimur til að finna samsvarandi náttúrulega tölu. Þessi vörpun er eintækt fall: ef $\phi (i)=\phi (j)$ fyrir einhver i,j í S þá er $i/2=j/2$ og því $i=j$ . Hún er ennfremur átæk: töluna $n\in \mathbb {N}$ má rita sem $\phi (2n)=n$ , svo $\phi$ er gagntæk. Því er S teljanlegt. Við höfum í raun sýnt hvernig beri að sanna jafngildi skilgreiningunnar við þá sem krefst þess að gagntæka vörpunin sé yfir á allt $\mathbb {N}$ (svo fremi sem mengið sé ekki endanlegt).
Mengi ræðra talna er teljanlegt (sjá hlekk), eins og Georg Cantor sýndi fram á með dúfustélsaðferð sinni. Þetta hefur þá afleiðingu að tvívíð hnit, og almennara $\mathbb {N} ^{k}$ í hærri víddum, eru teljanleg mengi þar sem hægt er að ímynda sér að ræða talan ${\frac {x}{y}}$ sé nákvæmlega talnatvenndin $(x,y)$ .
Mengi óræðra talna er hins vegar óteljanlegt, eins og Cantor sýndi einnig fram á.
Látum S vera mengi allra endanlegra strengja á endanlegu stafrófi Σ. S inniheldur þannig tóma strenginn, alla 1-stafs strengi, alla 2-stafa strengi o.s.frv. Almennt inniheldur S alla k-stafa strengi þar sem $k\in \mathbb {N}$ og er því óendanlegt þar sem ekkert þak er á því hversu stórt k getur orðið. S er ennfremur teljanlegt einfaldlega með því að telja fyrst upp tóma strenginn, því næst alla 1-stafs strengi, þá alla 2-stafa strengi, alla 3-stafa strengi o.s.frv. út í hið óendanlega. Þetta er alltaf hægt þar sem strengir af lengd k á endanlegu stafrófi eru endanlega margir ( $N^{k}$ ef N er fjöldi stafa í Σ). Sérhver endanlegur strengur á Σ, og þar með í S, kemur fyrr eða síðar upp í þessari upptalningu.
Látum nú S vera mengi allra óendanlegra strengja á endanlegu stafrófi Σ. Með því að nota skálínuaðferð Cantors má sýna að S er óteljanlegt, þ.e. sama hvernig talið er upp, alltaf má finna óendanlegan streng á Σ, og þar með í S, sem er ekki með í þeirri upptalningu.

Þessi stærðfræðigrein er stubbur. Þú getur hjálpað til með því að bæta við greinina.