z.z. Funktion ist Bijektion

27.10.2012, 12:00

Nilradikal

z.z. Funktion ist Bijektion

Hallo,

folgende Aufgabe:

http://s14.directupload.net/file/d/3056/rhvt7hc7_png.htm

Also zunächst einmal wie ich die Funktion f verstanden habe. Sie bildet die Teilmengen von X ab auf eine Tupel von Nullen und Einsen. Dieses Tupel hat so viele Einträge wie X Elemente hat. Also wenn X n Elemente hat, dann haben wir n-Tupel. Das Tupel gibt an welches Element in A enthalten ist (der entsprechende Eintrag ist 1) und welche nicht(0).
Habe ich das richtig verstanden?
Nun muss Ich also die Injektivität sowie Surjektivität zeigen. Allerdings stoße ich schon an der Formulierung "Zeige" auf. Heißt das jetzt beweisen oder plausibel erklären?
Ich habe mir dann folgendes gedacht, aber ich schätze als Beweis würde das nicht reichen, jedoch vielleicht als plausible Erklärung (??):
Zunächst einmal setze ich voraus, dass die Elemente der Mengen alle geordnet sind also $\begin{eqnarray*} \{ x_1, x_2, ... , x_n \}\Rightarrow x_1 < x_2 < ... < x_n \end{eqnarray*}$
zur Injektivität: Annahme die Funktion ist nicht injektiv. Dann existieren also $\begin{eqnarray*} A_1, A_2 \subset X \end{eqnarray*}$ mit $\begin{eqnarray*} A_1 \neq A_2 \end{eqnarray*}$ und $\begin{eqnarray*} f(A_1) = f(A_2) \end{eqnarray*}$ .
Da A1 und A2 sich in ihren Elementen unterscheiden müssen, betrachte ich der Reihe nach alle Elemente von A1 und A2.
Wenn x1 nicht in A1 ist so beginnt das Tupel mit einer Null (t1 = 0). Da A2 auf das selbe Tupel abbildet, muss dieses auch mit einer Null beginnen, folglich ist x1 auch nicht A2 enthalten. Analog wenn x1 in A1(t1 = 1) ist. Fahre so fort für alle n Elemente aus X . Es folgt, dass A1 und A2 die selben Elemente haben müssen, da die Tupel gleich sind, und somit A1 = A2. Die Funktion ist also injektiv.

Zur Surjektivität ......
Bevor ich das aufschreibe, wollte ich fragen ob der "Beweis" für die Injektivität so in Ordnung ist.

27.10.2012, 12:15

DP1996

Auf diesen Beitrag antworten »

Zeigen heißt tatsächlich, einen Beweis hinschreiben.

Die Argumentation passt meines Erachtens soweit, allerdings setzt du durch deine Notation voraus, das X endlich ist, und die Argumentation an sich ist etwas überkompliziert.

Tatsächlich brauchst du keine Ordnung auf X, da du weißt, dass $\begin{eqnarray*} f(A_1)=f(A_2)\Leftrightarrow \forall x\in X:\chi_{A_1}(x)=\chi_{A_2}(x) \end{eqnarray*}$ . Wenn nun tatsächlich $\begin{eqnarray*} f(A_1)=f(A_2) \end{eqnarray*}$ gilt, was bedeutet das für die Elemente von $\begin{eqnarray*} A_1 \end{eqnarray*}$ und $\begin{eqnarray*} A_2 \end{eqnarray*}$ ? Was also für die beiden Mengen?

27.10.2012, 14:53

Nilradikal

Auf diesen Beitrag antworten »

Hallo,
Naja, das bedeutet, dass sie das gleiche Bild haben, insbesondere haben sie die gleichen Elemente. Das heißt $\begin{eqnarray*} A_1 = A_2 \end{eqnarray*}$

27.10.2012, 21:26

DP1996

Auf diesen Beitrag antworten »

genau.

Hast du schon eine Idee für die Surjektivität?

27.10.2012, 21:55

Nilradikal

Auf diesen Beitrag antworten »

Zur Surjektivität:
Nun, ich muss von einem beliebigen y ausgehen, welches ein Tupel von Nullen und Einsen ist. Jetzt gehe ich wieder davon aus das X endlich ist unglücklich

: Seien also n Elemente in X enthalten. Dann ist y ein n-Tupel und es gibt $\begin{eqnarray*} 2^n - 1 \end{eqnarray*}$ Mögichkeiten die Nullen und Einsen anzuordnen. (Das Tupel, das nur Nullen hat wird nicht betrachtet, da es das Bild der leeren Menge ist, welche nicht berücksichtigtt wird) . Ferner weiß ich, dass es $\begin{eqnarray*} 2^n - 1 \end{eqnarray*}$ Teilmengen von X gibt (also wieder ohne leere Menge). Bei der Injektivität hatten wir gezeigt, dass es für jeden Funktionswert f(x) genau ein x gibt, woraus sofort die Surjektivität folgt...
Was meinst du dazu?

28.10.2012, 13:20

DP1996

Auf diesen Beitrag antworten »

Naja, die Einschränkung auf endliche Mengen ist nicht wirklich aufwändig, denn wenn eine Funktion f eine endliche Menge M auf eine andere, zu M gleichmächtige Menge N abbildet, dann ist f injektiv genau dann, wenn f surjektiv ist (das Schubfachprinzip bzw. das Taubenschlagprinzip).

Du hast ja bereits richtig erkannt, dass

Zitat:

ich muss von einem beliebigen y ausgehen, welches ein Tupel von Nullen und Einsen ist.

Du kannst aber dieses Tupel auch als Tupel aller Bildlemente einer Funktion $\begin{eqnarray*} \chi_A \end{eqnarray*}$ betrachten.

Neue Frage »

Antworten »

z.z. Funktion ist Bijektion

Verwandte Themen