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 $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.

[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 í $\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ð $φ(2 k) = 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 $n \in \mathbb{N}$ má rita sem $φ(2 n) = 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 $\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 á.