Sei f : {1, . . . n} → {1, . . . , m} eine Abbildung, mit n, m ∈ ℕ.

Question

Aufgabe:

Sei f : {1, . . . n} → {1, . . . , m} eine Abbildung, mit n, m ∈ ℕ. Zeigen Sie:
(a) Ist f injektiv, dann n ≤ m.
(b) Ist f surjektiv, dann n ≥ m.
(c) Ist f bijektiv, dann n = m

Problem/Ansatz:

a) Wenn f injektiv ist, dann existiert zu jedem m ∈ M höchstens ein n ∈ N, d.h. dann, dass nie mehr als ein Element von N (Definitionsmenge) auf dasselbe Element von M (Zielmenge) abgebildet werden kann.

Also: f(x₁)=f(x₂) ⇒ x₁=x₂. Die Anzahl der Bilder unter der Abbildung von f sind dann mit der Anzahl der Elemente in der Definitionsmenge N identisch. Es folgt: |f(N)|=|N|=n. Da N eine Teilmenge von M ist gilt somit: n≤|M|=m.

b) Aufgrund der Surjektivität gilt hier: f(N)=M (|f(N)|=|M|=m). Da mehrere Elemente von N auf dasselbe Element von M abgebildet werden können, gilt folglich: m=|f(N)|≤|N|=n

c) f ist bijektiv, wenn f injektiv und surjektiv ist. Aus a) und b) folgt dann n=m.

Sind meine Lösungen soweit richtig, bzw. gibt es auch noch andere Wege, diese Aufgabe zu lösen?

Answer 1

Aloha :)

Deine Lösungen kann ich nachvollziehen. Ich würde aber bildlicher argumentieren:

a) Injektiv bedeutet, dass jedes Element der Zielmenge höchstens 1-mal getroffen wird. Hat die Zielmenge weniger Elemente als die Startmenge, wird mindestens ein Ziel-Element mehrfach getroffen. Die Abbildung wäre dann nicht injektiv. Daher muss \(n\le m\) gelten. (Höchstens so viele Pfeile wie Ziele).

b) Surjektiv bedeutet, dass jedes Element der Zielmenge mindestens 1-mal getroffen wird. Hat die Zielmenge mehr Elemente als die Ausgangsmenge, wird mindestens ein Ziel-Element nicht getroffen. Die Abbildung wäre dann nicht surjektiv. Daher muss \(n\ge m\) gelten. (Mindestens so viele Pfeile wie Ziele).

c) Bijektiv bedeutet, dass jedes Element der Zielmenge genau 1-mal getroffen wird. Daher muss \(n=m\) gelten. (Genau so viele Pfeile wie Ziele).

Comments

So könnte man es natürlich auch formulieren, ist tatsächlich sogar verständlicher. Hab im Internet auch noch die "pigeonhole principle" Erklärung gefunden, ist auch ähnlich wie deine.