Teljanlegt mengi
Úr Wikipediu, frjálsa alfræðiritinu
Teljanlegt mengi er mengi A, sem er þannig búið að mögulegt er að setja fram gagntæka vörpun frá því á hlutmengi
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.
[breyta] 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 í
) 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 í
. Hins vegar getum við sýnt að hægt sé að varpa S beint á mengi náttúrulegra talna. Smíðum vörpun
þannig að φ(2k) = k fyrir sérhvert náttúrulegt k. Með öðrum orðum deilir φ sléttri tölu með tveimur til að finna samsvarandi náttúrulega tölu. Þessi vörpun er eintækt fall: ef φ(i) = φ(j) fyrir einhver i,j í S þá er i / 2 = j / 2 og því i = j. Hún er ennfremur átæk: töluna
má rita sem φ(2n) = n, svo φ 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
(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
í hærri víddum, eru teljanleg mengi þar sem hægt er að ímynda sér að ræða talan
sé nákvæmlega talnatvenndin (x,y). - Mengi óræðra talna er hins vegar óteljanlegt, eins og Cantor sýndi einnig fram á.

