Overtellbarhet
(I videoen over rundt 01:05 sier Andreas at det «[...] alltid eksisterer en surjektiv funksjon [...]», men han mener «aldri».)
Test deg selv
Hvilke av disse mengdene er tellbare? (Resten er overtellbare.)
$\{1,a,3,c\}$ er en endelig mengde med $4$ elementer, så den er tellbar (for alle endelige mengder er tellbare).
$\mathbb{N}$ er tellbar, for det finnes en en-til-en korrsepondanse mellom $\mathbb{N}$ og $\mathbb{N}$.
Potensmengden til mengden av naturlige tall er overtellbar. Som nevnt i videoen kan mengden av alle delmengder av $\mathbb{N}$ representeres som mengden av alle uendelige bitsekvenser, og mengden av alle uendelige bitsekvenser er som vist i videoen overtellbar.
$\mathbb{Z}$ er tellbar, for det finnes en en-til-en korrsepondanse mellom $\mathbb{N}$ og $\mathbb{Z}$.
Mengden av uendelige bitsekvenser er som vist i videoen overtellbar, og er altså ikke tellbar.
Mengden av naturlige partall er tellbar, for det finnes det en en-til-en korrsepondanse mellom $\mathbb{N}$ og mengden av naturlige partall.
Mengden av alle studenter ved Universitetet i Oslo er en endelig mengde, så den er tellbar.
$\mathbb{Q}$ er tellbar, for det finnes som demonstrert en en-til-en korrsepondanse mellom $\mathbb{N}$ og $\mathbb{Q}$.
$\mathbb{R}$, mengden av reelle tall, er overtellbar. Dette kan vises med den samme diagonaliseringsmetoden som ble brukt for å vise at mengden av uendelige bitsekvenser er overtellbar. For enhver tellbar liste med reelle tall kan vi konstruere et reelt tall som ikke er med i listen.