This flashcard is just one of a free flashcard set. See all flashcards!
29
Abzählbare Mengen
Eine Menge M heißt abzählbar, wenn es eine surjektive Funktion 
gibt. Nicht abzählbare Mengen heißen überabzählbar.
Bsp.:
- alle endlichen Mengen sind abzählbar
- Potenzmenge der natürlichen Zahlen ist überabzählbar
- Menge der Sprachen über dem Alphabt {0,1} ist überabzählbar
=> Menge der TMn ist abzählbar (weil durch GN kodierbar und Menge der GN Teilmenge von
und Menge der Sprachen ist überabzählbar => es gibt mehr Sprachen als TMn
gibt. Nicht abzählbare Mengen heißen überabzählbar.Bsp.:
- alle endlichen Mengen sind abzählbar
- Potenzmenge der natürlichen Zahlen ist überabzählbar
- Menge der Sprachen über dem Alphabt {0,1} ist überabzählbar
=> Menge der TMn ist abzählbar (weil durch GN kodierbar und Menge der GN Teilmenge von
und Menge der Sprachen ist überabzählbar => es gibt mehr Sprachen als TMn
