sirabien
Aus ProgrammingWiki
Archivierte Version vom 2012-03-27T11:35:21+00:00. Aktuelle Version
Woche 2
Aufgabe 4
Beweisen Sie den folgenden Satz: Wenn M_{1}, M_{2}, M_{3} ... abzählbare Mengen sind, dann ist auch die Menge \bigcup_{n=1}^\infty {M_{n}} abzählbar.
m_{1}(i), m_{2}(i), m_{3}(i) …; i ∈ ℕ seien Indexfunktionen für M_{1}, M_{2}, M_{3} …
n(i); i ∈ ℕ sei Indexfunktion für \bigcup_{n=1}^\infty {M_{n}} (gesucht)
Cantorsches Diagonalisierungsverfahren 1. Art:
| |m_{1}(0) = n(0) | m_{1}(1) = n(1) | m_{1}(2) = n(5) | m_{1}(3) = n(6) | … |
| |m_{2}(0) = n(2) | m_{2}(1) = n(4) | m_{2}(2) = n(7) | m_{2}(3) = n(13) | … |
| |m_{3}(0) = n(3) | m_{3}(1) = n(8) | m_{3}(2) = n(12) | m_{3}(3) = n(17) | … |
| |m_{4}(0) = n(9) | m_{4}(1) = n(11) | m_{4}(2) = n(18) | m_{4}(3) = n(24) | … |
| |… | … | … | … | … |
\square
Alternativ:
| |m_{0}(0) = n(0) | m_{0}(1) = n(2) | m_{0}(2) = n(5) | m_{0}(3) = n(9) | … |
| |m_{1}(0) = n(1) | m_{1}(1) = n(4) | m_{1}(2) = n(8) | m_{1}(3) = n(13) | … |
| |m_{2}(0) = n(3) | m_{2}(1) = n(7) | m_{2}(2) = n(12) | m_{2}(3) = n(18) | … |
| |m_{3}(0) = n(6) | m_{3}(1) = n(11) | m_{3}(2) = n(17) | m_{3}(3) = n(24) | … |
| |… | … | … | … | … |