[MENGENLEERE] Wie Abzählbarkeit zeigen?

... komplette Frage anzeigen

3 Antworten

A wird auf 1 abgebildet

B wird auf 2 abgebildet

...

Z wird auf 26 abgebildet

AA wird auf 27 abgebildet

AB wird auf 28 abgebildet

und so weiter.

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von J0T4T4
03.10.2016, 12:08

Ja, daran habe ich auch schon gedacht. Mein Problem dabei war jedoch, dass ich die Idee wieder verworfen habe, da ja theoretisch niemals ein B am Anfang stehen wird, da das Wort vorher unendlich lang sein müsste, und ich mir nicht sicher bin, ob die Unendlichkeit der Länge der Zeichenkette und der Natürlichen Zahlen deckungsgleich sind.

0

Hallo,

Du könntest eindeutige natürliche Zahlen über Produkte von Primzahlen erzeugen.

Fängst die Zeichenkette mit einem A an, ordnest Du ihr die erste Primzahl, nämlich 2, zu. AA ist 2², AAA ist 2³ usw. taucht ein B auf, hast Du 2^n*3 AC bekäme 2*5, AAC 2²*5 usw. Taucht nun ein B auf, bekommt es die nächste Primzahl nach der 5 zugewiesen, weil die 3 schon woanders vorkommen könnte. 

Beginnt die Kette mit B, bekommt das B die 3, BB bekommt 3², während BA 3*5 ergibt, BC 3*7. Du mußt also dafür sorgen, daß die Primfaktoren in jeder Kette immer höher werden.

So ist gewährleistet, daß Du - egal, wie viele Buchstabenkombinationen schon vergeben sind - immer neue, unverwechselbare gefunden werden.

Denn egal, welche Buchstaben nach dem A noch kommen, Du wirst immer eine gerade Zählnummer erhalten. Keine andere Zahlenkombination wird gerade sein, weil die 2 als Primfaktor nur dann auftaucht, wenn A der erste Buchstabe der Kombination ist.

Ebenso geht es mit dem B als erstem Buchstaben. Nur B ist durch 3, aber nicht durch 2 teilbar, weil bei keiner Kombination, die nicht mit B beginnt, ist die 3 ohne die 2 als Primfaktor erhalten.

Bei C als erstem Buchstaben ist es die 5. Alle Kombinationen, die mit C beginnen, sind durch 5 teilbar, aber nicht durch 2 oder 3, weil diese Faktoren hier nicht vorkommen.

So sollte die Abzählbarkeit gewährleistet sein.

Herzliche Grüße,

Willy

Antwort bewerten Vielen Dank für Deine Bewertung

Falls es dich interessiert, steht ein vollständiger formaler Beweis auf der auf meinem Profil verlinkten Seite:


Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von kreisfoermig
03.10.2016, 13:47

Der Beweis im Dokument zeigt die Existenz einer Bijektion. Hier aber noch kompakter, wenn du NUR beweisen willst, dass |ℕ|≥|A|.

Jeder Zahl x ist eine eindeutige Primzahlzerlegung zugeordnet x=2^e[0]·3^e[1]·5^e[2]·7^e[3]·11^e[4]·… . Die Primzahlzerlegung gibt durch die Exponenten eine Kette von Zahlen an (man muss geschickt das Ende wählen), die man als Code betrachten kann. Wenn die Kette von Zahlen nur Zahlen zwischen 0 und 26–1 enthalten, so kann man die als Code für ein Wort aus A verwenden. Man sieht sofort, dass jedes Wort einen Code hat. Damit enkodiert ℕ jedes Element aus A (vielleicht mehrfach und mehr als bloße Elemente aus A). Darum gilt |ℕ|≥|A|.

Diese Idee ist in der zweiten Behauptung im Dokument enthalten.

2
Kommentar von kreisfoermig
04.10.2016, 09:01

Mir ist aufgefallen, dass der Link zu meinem Profil oben nicht funktioniert. Man klicke stattdessen einfach auf mein Bild ; )

0

Was möchtest Du wissen?