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.