Konstruieren Sie (mithilfe von U) eine Funktion p : N → N die nicht in F enthalten ist.

Question

Sei F eine Menge von Funktionen von N nach N und g : F → N eine Bijektion. Wir definieren U : N → F, U(n)(x) := g ⁻¹(n)(x).

Konstruieren Sie (mithilfe von U) eine Funktion p : N → N die nicht in F enthalten ist.

Answer 1

Hallo,

kurz zum Hintergrund: Wenn es so eine Bijektion gibt, dann ist die Menge F abzählbar. Die Aufgabe sagt also: Wenn ich eine Menge F von Funktionen von N nach N habe, die abzählbar ist, dann kann das nicht die Menge aller Funktionen von N nach N sein.

Definiere: \(p: \mathbb{N} \to \mathbb{N}, p(n):=g^{-1}(n)(n)+1\)

Bachte dazu: \(g^{-1}(n)\) ist eine Funktion und \(g^{-1}(n)(n)\) ihr Wert für das Argument n.

p gehört nicht zu F. Denn sonst müsste es ein \(m \in \mathbb{N}\) geben mit \(p=g^{-1}(m)\), also

$$\forall k \in \mathbb{N}:\quad p(k)=g^{-1}(m)(k)$$

Aber p ist so definiert, dass süeziell für \(k=m\) gilt:  \(p(m)=g^{-1}(m)(m)+1\)

Gruß

Comments

<3<3<3<3<3<3<3<3<3<3<3<3<3<3