M abzählbar - mit rekursiv definierter Abbildung

Question

Aufgabe:

Sei \( M \) eine unendliche Menge und sei \( \sigma: \mathbb{N} \rightarrow M \) eine surjektive Abbildung. Zeigen Sie, dass die Menge \( M \) abzählbar ist.

Hinweis: Betrachten Sie die rekursiv definierte Abbildung

\( \varphi: \mathbb{N} \rightarrow M \) mit
\( \varphi(1)=\sigma(1) \quad \text { und } \quad \varphi(n+1)=\sigma\left(m_{n}\right) \quad \text { für alle } n \in \mathbb{N}, \)

wobei
\(m_{n}:=\min \{k \in \mathbb{N} \mid \sigma(k) \notin\{\varphi(1), \ldots, \varphi(n)\}\} . \)

Zeigen Sie zunächst, dass die Abbildung wohldefiniert ist. Dazu ist zu zeigen, dass für jedes \( n \in \mathbb{N} \) das Minimum in \( (1) \) angenommen wird und dass tatsächlich \( \varphi(n) \in M \) gilt.

Problem/Ansatz:

Leider habe ich keinen wirklich brauchbaren Ansatz gefunden. Wenn jemand eine Lösung oder eine Idee vorstellen könnte, wäre ich sehr dankbar.

Beste weihnachtliche Grüße,

Verwirrung

Answer 1

Für die Wohldefiniertheit, sei \( n \in \mathbb{N} \) beliebig. Die Menge \( P=\{\varphi(1), \ldots, \varphi(n)\} \) ist endlich, und somit gibt es noch irgendein \( x_{1} \in M \) mit \( x_{1} \notin P \). Dementsprechend gibt es auch ein \( k_{1} \in \mathbb{N} \) mit \( \sigma\left(k_{1}\right)=x_{1} \), da \( \sigma \) surjektiv ist. Auch ist \( m_{n} \) von unten beschränkt, da \( m_{n} \geq 1 . \) Wenn \( k_{1} \neq m_{n} \), so gibt es also ein \( k_{2} \in \mathbb{N} \) und \( x_{2} \in M \) mit \( \sigma\left(k_{2}\right)=x_{2} \) und \( x_{2} \notin P \) und \( k_{2}<k_{1} \). Dadurch können wir eine streng monoton fallende Folge \( \left(k_{n}\right) \) definieren, welche von unten beschränkt (durch \(1\)) ist und somit nach endlich vielen Schritten "terminiert". Somit exisitert also das Minimum.

Die Injektivität der Funktion folgt direkt aus ihrer Konstruktion. Ist \( a, b \in \mathbb{N} \) und \( \varphi(a)= \) \( \varphi(b) \). Man nehme zu einem Widerspruch führend an, \( a \neq b \) und o.V.d.A. \( a<b \). Es ist per Definition \( \varphi(b)=\sigma\left(m_{b-1}\right) \) und \( \sigma\left(m_{b-1}\right) \notin\{\varphi(1), \ldots, \varphi(b-1)\} \). Nun ist aber \( a=k \) für \( k \in\{1,2, \ldots, b-1\} \) und somit \( \varphi(b)=\sigma\left(m_{b-1}\right) \neq \varphi(a) \), ein Widerspruch.