Bijektive Abbildung von N auf {0, 1}*?
Wie sieht eine Bijektive Abbildung von den Natürlichen Zahlen N mit 0 auf eine endliche Folge von {0, 1} aus, und wie Beweise ich das diese Bijektiv ist?
2 Antworten
Du kann n\in N_0 eindeutig darstellen als \sum_i=0^n a_i * 2^i mit a_i\in{0,1}.
Warum lasse ich die Summe bis n laufen? Weil damit der Vektor der (a_i) endlich ist (wie in der Aufgabenstellung gefordert) und ich mich um die ganze Geschichte mit log2(n) drücken kann. ;-)
Dass diese Abbildung eine Bijektion ist, kann man recht einfach beweisen.
Das sollte eigentlich mit einem indirekten Beweis gehen. Angenommen, es gibt zwei Zahlen x1 und x2\in N0, x1 ungleich x2, die auf denselben Vektor (a_i) abgebildet werden...
Du kannst quasi N auf die Dualzahlen abbilden. Also jede Dezimalzahl N auf die entsprechende Dualzahl. Allerdings wird das wohl nicht surjektiv weil dir alles mögliche mit führenden Nullen fehlt. Geht das überhaupt bijektiv? Oder was meinst du mit {0, 1}*?
Ich denke mal führende 0en lässt man dann weg, dann ist ja eigentlich nur logisch das sie bijektiv sein muss, weil für jedes n nur eine Dualzahl existiert die diese wiedergibt. Aber 1. wie ich das Formel schreibe weiß ich nicht und 2. wird meinem Tutor die Begründung "ist nur logisch" wohl kaum akzeptieren.^^
Also die Surjektivität daraus zuziehen bekomme ich hin, aber wie Beweise ich die Injektivität. Durch ein Gegenbeispiel vllt. aber bekomme nicht wirklich ein Ergebnis...