Abzählbarkeit (Injektive Abbildung)

15.04.2010, 20:55

Risuku

Abzählbarkeit (Injektive Abbildung)

Hi,
ich lese mir gerade ein Skript durch und komme nicht weiter. Es ist folgender Satz:

Zitat:

Satz: Seien $\begin{eqnarray*} n,m \in N_0 \end{eqnarray*}$ mit $\begin{eqnarray*} n > m \end{eqnarray*}$ : Dann gibt es keine injektive Abbildung $\begin{eqnarray*} f : A_n \to A_m \end{eqnarray*}$ .

Beweis:

Siehe folgendes Bild:

BEWEIS!

Also $\begin{eqnarray*} A_n \end{eqnarray*}$ war wie folgt definiert:

$\begin{eqnarray*} A_n = \left\{ k | k \in \mathbb N , k < n \right\} \end{eqnarray*}$

Also bei mir hackt es nun bei diesen "3 Fällen". Rein Mengentechnisch kann ich mir das schon vorstellen das quasi in f n-1 Elemente auf n-2 Elemente abgebildet werden. Oder ist das einfach ein Schreibfehler im Skript das f auf $\begin{eqnarray*} A_{k-1} \end{eqnarray*}$ und $\begin{eqnarray*} A_{k-2} \end{eqnarray*}$ beschränkt wird. Dachte man ändert nur den Definitionsbereich bei dieser Schreibweise.

Hoffe jemand kann mir das etwas genauer erklären.

Vielen Dank

Gruß

15.04.2010, 21:57

Simooon

Auf diesen Beitrag antworten »

Injektiv heißt ja, dass jedes element aus dem Bildraum höchtens ein Urbild hat.

Die Vorschrift f bildet ja jedes Element von $\begin{eqnarray*} A_{n} \end{eqnarray*}$ auf $\begin{eqnarray*} A_{m} \end{eqnarray*}$
Wie du ja selbst schon gesagt hast, ist $\begin{eqnarray*} |A_{n}|>|A_{m}| \end{eqnarray*}$

WEnn man beispielsweise {1,2,3} auf {1,2} abbildet, wäre ja z.b
f(1)=1
f(2)=2
und f(3) kann ja dann nur 1 oder 2 sein und somit ist die Abbildung nicht injektiv

Ich hoffe das hilft

15.04.2010, 22:10

Risuku

Auf diesen Beitrag antworten »

Ja das ist mir klar.
Mir gehts es hauptsächlich um diese Fälle 1-3. Kann mir die jemand im einzelnen erklären?

Wäre es nicht in deinem Fall auch möglich das zB 3 kein Bild hat? Oder wäre dies keine Abbildung mehr?

Gruß

15.04.2010, 22:17

gonnabphd

Auf diesen Beitrag antworten »

Eine Funktion weist jedem Element der Urmenge ein Element der Bildmenge zu.

Was verstehst du denn im Einzelnen beim Beweis nicht?

16.04.2010, 01:10

Risuku

Auf diesen Beitrag antworten »

Ich versteh halt die 3 Schritte nicht. Das fängt dann an mit "Wenn 1 oder 2 gelten, so ist $\begin{eqnarray*} f|_{A_{k-1}} : A_{k-1} \to A_{k-2} \end{eqnarray*}$ injektiv."

Erstmal heißt für mich dieses $\begin{eqnarray*} f|_{A_{k-1}} \end{eqnarray*}$ das ich nur den Definitionsbereich einschränke. Aber hier wird direkt auch der Wertebereich miteingeschränkt.

Was heißt genau "Die Zahl k-2 tritt nicht als Bild auf bei der Abbildung f."?

Heißt das k-2 kein Urbild in $\begin{eqnarray*} A_k \end{eqnarray*}$ hat?

16.04.2010, 01:27

gonnabphd

Auf diesen Beitrag antworten »

$\begin{eqnarray*} f|_{A_{k-1}} : A_{k-1} \to A_{k-2} \end{eqnarray*}$

Ja, diese Schreibweise ist wirklich ein bisschen schwammig... Denn zu f gehört eigentlich sowohl Definitions- als auch Wertebereich. Das siehst du richtig. Aber anstatt eine neue Funktion f' mit eingeschränktem Wertebereich zu definieren, machts der Author hier halt so...

Ist aber auch nicht sooo schlimm, denn der Bildbereich ist in diesem Falle einigermassen uninteressant (es geht ja um die Injektivität).

Dass die Zahl k-2 nicht als Bild auftritt, heisst, dass es nicht im Bild von f liegt. Auch das siehst du richtig.

16.04.2010, 01:30

gonnabphd

Auf diesen Beitrag antworten »

Nochmal in Kürze und formal korrekt:

Da in den ersten beiden Fällen k-2 nicht als Bildpunkt von $\begin{eqnarray*} f|_{A_{k-1}} \end{eqnarray*}$ auftritt, kann man eine Funktion $\begin{eqnarray*} f': A_{k-1} \rightarrow A_{k-2} \end{eqnarray*}$ definieren, welche auf $\begin{eqnarray*} A_{k-1} \end{eqnarray*}$ mit $\begin{eqnarray*} f \end{eqnarray*}$ übereinstimmt und deshalb injektiv ist.

16.04.2010, 13:01

Risuku

Auf diesen Beitrag antworten »

Aber wenn ich f' definiere werden doch wieder k-1 Objekte auf k Stück Abgebildet.
Durch diese neue Funktion wird doch jeweils aus Werte- und Definitionsbereich EIN Element genommen. Woher kommt dann die injektivität? verwirrt

16.04.2010, 16:59

gonnabphd

Auf diesen Beitrag antworten »

Man setzt ja voraus, dass f injektiv ist. Also ist doch f auch injektiv wenn man den Wertebereich einschränkt.

Wenn keine zwei Elemente von {1, 2, ... , k-1} das gleiche Bild unter f haben, dann können doch nicht plötzlich zwei Elemente von {1, 2, ... , k-2} durch f|A_{k-1} auf den gleichen Punkt abgebildet werden.
Denn f ist injektiv.

Einverstanden, dass die Einschränkung einer injektiven Funktion wiederum injektiv ist?

Nun zum Bildbereich. Da man in den ersten beiden Fällen voraussetzt, dass (k-2) nicht das Bild von einem Element aus A_{k-1} ist, weiss man, dass

$\begin{eqnarray*} (k-2) \notin f(A_{k-1}) \quad \Rightarrow f(A_{k-1}) \subset A_{k-1} \setminus \{ k-2 \} = A_{k-2} \end{eqnarray*}$

gilt. Soweit ok?
Wir haben jetzt erkannt, dass in den ersten beiden Fällen folgendes gilt:

$\begin{eqnarray*} f|_{A_{k-1}}: A_{k-1} \rightarrow A_{k-1} \end{eqnarray*}$ ist wieder injektiv und
$\begin{eqnarray*} f|_{A_{k-1}}(A_{k-1}) = f(A_{k-1}) \subset A_{k-2} \end{eqnarray*}$

Deshalb können wir $\begin{eqnarray*} f': A_{k-1} \rightarrow A_{k-2} \end{eqnarray*}$ definieren durch

$\begin{eqnarray*} f'(x) := f|_{A_{k-1}}(x) \quad \forall x \in A_{k-1} \end{eqnarray*}$

(Also ist f' die gleiche Funktion wie f|A_{k-1}, aber aus dem Bildbereich wurde ein Element genommen, welches ja sowieso nicht getroffen wird.)

Neue Frage »

Antworten »

Abzählbarkeit (Injektive Abbildung)

Verwandte Themen