Unterschied zwischen ab- und aufzählbaren Mengen

Question

Ich wüsste gerne den Unterschied zwischen ab- und aufzählbaren Mengen. Mir ist bei beidem nicht ganz klar um was es sich handelt!

Answer 1

Abzählbare Mengen lassen sich injektiv auf die natürlichen Zahlen abbilden.

Für (rekursiv) aufzählbare Mengen M kann man eine surjektive berechenbare Funktion f aus den natürlichen Zahlen in die Menge angeben. Anders gesagt, kann man die Menge dadurch angeben, dass man nacheinander durch einen Algorithmus f(1), f(2), ... berechnet. Es gilt also:

$ M=\bigcup_{i\in\mathbb{N}} f(i) $

 

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen