Enumerierung

Enumerierung, in Mathematik und Logik, bezeichnet das systematische Auflisten aller Elemente einer Menge in einer bestimmten Reihenfolge. Für endliche Mengen bedeutet eine Enumerierung eine Bijektion zwischen der Menge und einem Anfangssegment der natürlichen Zahlen, typischerweise {1,...,n}. Bei unendlichen Mengen dient eine Enumerierung dazu, eine Sequenz zu erzeugen, deren Bild die Menge ist.

Formalisiert wird eine Enumerierung einer Menge S oft durch eine Funktion e: N -> S mit der Eigenschaft, dass jedes Element von S irgendwann als e(n) erscheint; bei endlichen S ist dies eine Bijektion. Eine solche Sequenz a1, a2, a3, ... heißt eine Enumeration von S.

Eine solche Sequenz a1, a2, a3, ... heißt eine Enumeration von S.

Im Begriff der Zählbarkeit spielt Enumerierung eine zentrale Rolle. Eine endliche Menge ist zählbar. Eine unendliche Menge ist zählbar (auflzählbar), wenn es eine Bijektion mit N gibt oder äquivalenterweise eine surjektive Abbildung von N auf S existiert.

Bekannte Beispiele: Die natürlichen Zahlen sind abzählbar. Die rationalen Zahlen lassen sich ebenfalls aufzählen.

Anwendungen finden sich in der Kombinatorik, der Mengentheorie, der algorithmischen Generierung von Objekten und der Datenorganisation. In der Informatik bezeichnet man Programme, die Elemente einer Menge nacheinander ausgeben, als Enumeratoren; rekursiv aufzählbare Mengen lassen sich von Turingmaschinen erzeugen.

---