Eine injektive Abbildung für Σ∗ × Σ∗ = {(u,v) | u,v ∈ Σ∗} → Σ∗ finden?

Question

So lautet die Aufgabe:

Sei Σ = {0,1}.

Geben Sie eine injektive Abbildung fb : Σ∗ ×Σ∗ = {(u,v) | u,v ∈ Σ∗} → Σ∗ an.

Problem/Ansatz:

Man muss Tupeln von u und v auf etwas abbilden, was in Form von einem Wort sein muss, um Element von  Σ∗ zu sein. Damit die Abbildung Injektiv ist, dürfen keine 2 Tupeln auf das gleiche Element aus  Σ∗ zeigen.

Unser Ansatz wäre zum Beispiel: (u,v) → u01v

Dies ist dennoch nicht injektiv, da zum Beispiel die Tupeln (0,011) und (001,1) zeigen auf das gleiche Wort 001011.

Vielen Dank im Voraus

Comments

Benutze, dass sich jede natürliche Zahl eindeutig als Produkt einer geraden und einer ungeraden Zahl schreiben lässt.

---

6 = 3·2 = 1·6

---

Stimmt. Gemeint war :  Eindeutiges Produkt aus Zweierpotenz und ungerader Zahl.

Answer 1

s(x) sei die Länge des Wortes x.

n(x) sei die natürliche Zahl, dessen Binärdarstellung x ist.

(v,w) ↦ n^-1(2^s(v)·3^n(v)·5^s(w)·7^n(w)) ist injektiv