Nichtleere endliche Menge injektiv, wenn surjektiv

07.11.2019, 20:54

Isy13

Nichtleere endliche Menge injektiv, wenn surjektiv

Hallo Schwarmintelligenz,

habe folgende Aufgabe und komme einfach nicht weiter:

Sei X eine endliche Menge. Beweisen Sie die folgende Aussage:

a) ist X eine endliche Menge mit n Elementen, so ist eine Abbildung f: X->X genau dann injektiv, wenn sie surjektiv ist.
b) a muss nicht gelten, wenn die Menge X unendlich viele Elemente besitzt

Mein Ansatz ist folgender:

Beweis durch vollständige Induktion n=|M|

Induktionsanfang: n=1 --> ist richtig, da die Menge aus nur einem Element besteht und die einzige Abbildung somit surjektiv und injektiv ist.

Induktionsvoraussetzung: Behauptung sei für alle Mengen M mit |M| $\begin{eqnarray*} \leq \end{eqnarray*}$ n f: M->M richtig.

Induktionsschritt: z.Z. Behauptung stimmt für alle Mengen M mit |M|=n+1

sei |M|=n+1 und f: M->M eine subjektive Abbildung
z.Z. f ist injektiv

So und da hört es dann leider auf. wie muss ich einschränken, damit ich Dur Induktion weiter beweisen kann? verwirrt

Ich hoffe mit kann jemand helfen Big Laugh

Liebe Grüße

Isy

08.11.2019, 07:20

Elvis

Auf diesen Beitrag antworten »

Überlege, was die Funktion f mit dem n+1-ten Element machen kann. Viele Möglichkeiten gibt es da nicht mehr.
Ein direkter Beweis mit einfachen Worten dürfte leichter sein und zeigt, dass man die Definitionen verstanden hat.

08.11.2019, 10:05

Isy13

Auf diesen Beitrag antworten »

Zitat:

Original von Elvis
Überlege, was die Funktion f mit dem n+1-ten Element machen kann. Viele Möglichkeiten gibt es da nicht mehr.
Ein direkter Beweis mit einfachen Worten dürfte leichter sein und zeigt, dass man die Definitionen verstanden hat.

Das heißt, für eine Induktion müsste n-1 nehmen, um zu zeigen, dass es für jede endliche Menge gilt? verwirrt

Und als direkter Beweis mit Worten müsste es dann heißen:

Wenn eine endliche Menge besteht, dann gibt es für jede Abbildung M einen Wert X und damit ist es surjektiv, was bedeutet, dass es für jedes X genau eine Abbildung M gibt, woraus sich schließen lässt, dass es dadurch auch injektiv ist? geschockt

08.11.2019, 11:23

Elvis

Auf diesen Beitrag antworten »

Du hast Induktion vorgeschlagen, dann solltest du auch wissen, wie man das macht.

Induktionsvoraussetzung: Sei $\begin{eqnarray*} M \end{eqnarray*}$ eine endliche Menge mit $\begin{eqnarray*} n \end{eqnarray*}$ Elementen und $\begin{eqnarray*} f:M\to M \end{eqnarray*}$ eine Funktion. Dann gilt: $\begin{eqnarray*} f \end{eqnarray*}$ injektiv $\begin{eqnarray*} \Leftrightarrow f \end{eqnarray*}$ surjektiv.
Induktionsschritt: Sei $\begin{eqnarray*} M \end{eqnarray*}$ eine endliche Menge mit $\begin{eqnarray*} n+1 \end{eqnarray*}$ Elementen und $\begin{eqnarray*} f:M\to M \end{eqnarray*}$ eine Funktion. Zu zeigen: $\begin{eqnarray*} f \end{eqnarray*}$ injektiv $\begin{eqnarray*} \Leftrightarrow f \end{eqnarray*}$ surjektiv.

Die Aussage gilt für jede Einschränkung von $\begin{eqnarray*} f \end{eqnarray*}$ auf jede $\begin{eqnarray*} n \end{eqnarray*}$ -elementige Teilmenge $\begin{eqnarray*} M'\subset M \end{eqnarray*}$ , und das $\begin{eqnarray*} n+1 \end{eqnarray*}$ -te Element kann dann durch $\begin{eqnarray*} f(x_{n+1})=x_{n+1} \end{eqnarray*}$ nur noch auf sich abgebildet werden, weil sonst $\begin{eqnarray*} f \end{eqnarray*}$ nicht injektiv oder nicht surjektiv ist. Jetzt fängt das Problem an: Nicht jede bijektive Funktion $\begin{eqnarray*} f:M\to M \end{eqnarray*}$ lässt sich so auf eine echte Teilmenge einschränken. Zum Beispiel klappt das schon nicht bei $\begin{eqnarray*} M=\{1,2\},f(1)=2,f(2)=1 \end{eqnarray*}$ . Ich weiß nicht, wie du die Induktion retten willst.

Vorschlag zum Beweis mit einfachen Worten.

Hat M n Elemente, dann ordnet eine Selbstabbildung f jedem Element genau ein Element aus M zu. Ist f injektiv, dann sind die n Bilder paarweise verschieden, das sind also alle Elemente von M, mithin ist f surjektiv. Ist f nicht injektiv, dann haben zwei Urbilder dasselbe Bild. Dann bleiben aber nicht genug Urbilder übrig, um durch f alle Elemente von M als Bild zu erreichen, also ist f nicht surjektiv. qed.

08.11.2019, 12:35

URL

Auf diesen Beitrag antworten »

Für einen Induktionsbeweis könnte man zwei Ansätze versuchen:
1. Man beweist die Aussage allgemeiner für Abbildungen $\begin{eqnarray*} f:M\to N \end{eqnarray*}$ mit endlichen, gleichmächtigen Mengen $\begin{eqnarray*} M,N \end{eqnarray*}$
2. Man verkettet f mit einer Bijektion g, so dass $\begin{eqnarray*} g\circ f \end{eqnarray*}$ einen Fixpunkt hat.

Allerdings finde ich einen Induktionsbeweis hier auch nicht angebracht. Ist $\begin{eqnarray*} M=\{m_1,\ldots ,m_k\} \end{eqnarray*}$ , dann muss man sich nur die Menge $\begin{eqnarray*} f(M)=\{f(m_1),\ldots ,f(m_k)\} \end{eqnarray*}$ anschauen und landet bei Elvis' Argumentation

Neue Frage »

Antworten »

Nichtleere endliche Menge injektiv, wenn surjektiv

Verwandte Themen