nicht endliche Menge, Beweis

27.10.2006, 17:33

nicht endliche Menge, Beweis

Hallo zusammen. Also folgender Beweis steht an:

Sei $\begin{eqnarray*} M \end{eqnarray*}$ eine Menge. Dann sind folgende Aussagen äquivalent:

a) $\begin{eqnarray*} M \end{eqnarray*}$ ist nicht endlich

b) Es gibt ein $\begin{eqnarray*} y\in M \end{eqnarray*}$ und eine injektive Abbildung $\begin{eqnarray*} f: M->M \end{eqnarray*}$ mit $\begin{eqnarray*} f(x)\neq y \end{eqnarray*}$ für alle $\begin{eqnarray*} y\in M \end{eqnarray*}$

Ich habe zusammen mit den Tipps aus den Übungsgruppen folgendes zusammengebastelt für a=>b

Nach Voraussetzung ist M nicht endlich. Sei $\begin{eqnarray*} A\subseteq M \end{eqnarray*}$ sodass eine bijektive Abbildung existiert $\begin{eqnarray*} f: A->\mathbb N \end{eqnarray*}$ .

Definiere nun folgende Abbildungen:

$\begin{eqnarray*} f(m_i)=m_{i+1} \end{eqnarray*}$ mit $\begin{eqnarray*} m_i\in A,i\in \mathbb N \end{eqnarray*}$

$\begin{eqnarray*} f(n)=n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in M\setminus A \end{eqnarray*}$

Damit ist die Injektivität gezeigt.

Dann folgt doch, dass das gesuchte y einfach das erste Element der Menge sein muss, das nicht Nachfolger ist (Verweis auf die Peano Axiome)

Ich wäre dankbar für Kritik/Bestätigung und insbesondere auf die Schreibweise

27.10.2006, 18:17

Dual Space

Auf diesen Beitrag antworten »

RE: nicht endliche Menge, Beweis
Irgendwie verstehe ich die Aufgabe nicht so ganz.

Also ich wähle $\begin{eqnarray*} M=\mathbb{R} \end{eqnarray*}$ und $\begin{eqnarray*} f=I \end{eqnarray*}$ , d.h. $\begin{eqnarray*} f(x)=x~\forall x\in M \end{eqnarray*}$ .

Nun habe ich eine nichtendliche Menge M, aber b) wird nicht erfüllt. verwirrt

Edit (18:19): Ok, Ok ... b) soll ja auch nicht für alle injektiven Funktionen gelten ... verstanden! smile

27.10.2006, 18:22

Auf diesen Beitrag antworten »

Es soll Am Ende natürlich $\begin{eqnarray*} x\in M \end{eqnarray*}$ heißen.

Ist denn der Beweis richtig?

27.10.2006, 20:20

irre.flexiv

Auf diesen Beitrag antworten »

So ungefähr soll es aussehen. Ich sage ungefähr weil ein paar Unsauberheiten drin sind. Du benutzt zum Beispiel zwei mal das Symbol $\begin{eqnarray*} f \end{eqnarray*}$ für verschiedene Funktionen. Du hast auch nicht die Existenz von A explizit gesichert. Man sollte meiner Meinung nach schon hinschreiben das jede unendliche Menge eine abzählbare Teilmenge enthält. Die indizierten m's finde ich auch ungünstig, nachvollziehbarer wäre es mit der Nachfolgerfunktion zu arbeiten und einer bijektiven Funktion von A auf N.

Zitat:

Damit ist die Injektivität gezeigt.

Hm, das ist nicht zu zeigen, du konstruierst die Funktion ja gerade so. dass sie injektiv aber nicht bijektiv ist. Also anders formulieren.

27.10.2006, 20:37

Auf diesen Beitrag antworten »

Zitat:

Du benutzt zum Beispiel zwei mal das Symbol f für verschiedene Funktionen

stimmt, das ist in der Tat ungünstig. Ich bennene letztere einfach g.

Zitat:

Du hast auch nicht die Existenz von A explizit gesichert.Man sollte meiner Meinung nach schon hinschreiben das jede unendliche Menge eine abzählbare Teilmenge enthält

So einen Satz hatten wir leider noch nicht

Zitat:

Hm, das ist nicht zu zeigen, du konstruierst die Funktion ja gerade so. dass sie injektiv aber nicht bijektiv ist. Also anders formulieren.

stimmt, das muss besser formuliert werden

Und die Funktionsbezeichnungen habe ich einfach so von dem Übungsleiter übernommen.

Aber ansonsten dürfte das stimmen, oder nicht? Also vor allem die Überlegung zu dem einen gesuchten y

Und bei der umgekehrten Richtung plane ich einen Widerspruchsbeweis

27.10.2006, 21:38

irre.flexiv

Auf diesen Beitrag antworten »

Joa das schon. Ist genau dasjenige Element, dass keinen "Vorgänger" besitzt.

28.10.2006, 10:55

Auf diesen Beitrag antworten »

Also ich habe mir das nochmals überlegt und an den besagten Stellen versucht besser zu formulieren. Am Ende des Beweises stellt sich dann nochmals eine Frage. Aber erstmal der Beweis von a)=>b) nochmal

Nach Voraussetzung ist M nicht endlich. Sei $\begin{eqnarray*} A\subseteq M \end{eqnarray*}$ sodass eine bijektive Abbildung existiert $\begin{eqnarray*} f: A->\mathbb N \end{eqnarray*}$ .

Definiere nun folgende Abbildungen:

$\begin{eqnarray*} f(m_i)=m_{i+1} \end{eqnarray*}$ mit $\begin{eqnarray*} m_i\in A,i\in \mathbb N \end{eqnarray*}$

$\begin{eqnarray*} g(n)=n \end{eqnarray*}$ mit $\begin{eqnarray*} n\in M\setminus A \end{eqnarray*}$

Nach Konstruktion ist f injektiv.

So und jetzt zu der Formulierung, dass das gesuchte Element y genau dasjenige ist, welches keinen Vorgänger hat. Es gibt den Satz, dass jede nichtleere Teilmenge von natürlichen Zahlen ein kleinstes Element hat. Kann ich dann sagen, dass y das Minimum von A ist?

29.10.2006, 14:33

irre.flexiv

Auf diesen Beitrag antworten »

Zitat:

Kann ich dann sagen, dass y das Minimum von A ist?

Nicht ohne weiteres, denn A ist nicht notwendig geordnet.

Zitat:

$\begin{eqnarray*} f: A->\mathbb N \end{eqnarray*}$

Du benutzt schonwieder zwei mal das Symbol $\begin{eqnarray*} f \end{eqnarray*}$ . Eigentlich sollte $\begin{eqnarray*} f \end{eqnarray*}$ laut Aufgabenstellung doch eine Abbildung $\begin{eqnarray*} f : M \rightarrow M \end{eqnarray*}$ sein.

Ich schreibe dir mal wie ich es machen würde.

Wegen $\begin{eqnarray*} |M| = \infty \end{eqnarray*}$ gibt es eine abzählbare Menge $\begin{eqnarray*} A \subseteq M \end{eqnarray*}$ . Sei $\begin{eqnarray*} g : A \rightarrow \mathbb N \end{eqnarray*}$ bijektiv und $\begin{eqnarray*} s : \mathbb N \rightarrow \mathbb N \end{eqnarray*}$ die Nachfolgerfunktion.

Durch

$\begin{eqnarray*} f(m) = \left\{\begin{array}{c} m \quad, m \in M\setminus A \\ (g^{-1}\circ s \circ g)(m) \quad , m \in A \end{array}\right. \end{eqnarray*}$

wird eine injektive Abb. definiert, die wegen

$\begin{eqnarray*} g^{-1}(1) \not \in f(M) \end{eqnarray*}$

nicht bijektiv ist.

29.10.2006, 15:08

Auf diesen Beitrag antworten »

gut, da die Menge nicht angordnet ist, wäre das gesuchte y ja bei mir einfach y=f(1)

Neue Frage »

Antworten »

nicht endliche Menge, Beweis

Verwandte Themen