0 Daumen
2,1k Aufrufe

Aufgabe:

Seien  A und B endliche Mengen mit |A|=|B|=n,f:A→B eine Abbildung.

(a) Zeigen Sie, dass die folgenden Eigenschaften äquivalent sind, d.h.(α)⇔(β)⇔(γ):

(α) f ist injektiv,

(β) f ist surjektiv,

(γ) f ist bijektiv.

(b) Beweisen Sie, dass es n! verschiedene bijektive Abbildungen zwischen A und B gibt.
Problem/Ansatz:

Zu (a)

Ich bin mir nicht sicher wie ich zeigen kann das die Eigenschaften äquivalent sind.

Wenn f injektiv ist, heißt das ja nicht das f surjektiv ist.

Zu (b)

Ich weiß zwar das die b auf jedenfall korrekt ist (da ich ein paar werte für n mal probiert habe),

hab aber keine Ahnung wie ich das allgemeingültig für f beweisen könnte.

Avatar von

2 Antworten

+1 Daumen
 
Beste Antwort

Wenn f injektiv ist, heißt das ja nicht das f surjektiv ist.

Stimmt !

Aber hier ist ja der besondere Fall zweier endlicher Mengen mit gleichviel

Elementen.

Da ist es ja so:

zu (a) ==> (b)

Wenn f Injektiv ist, gibt es nicht mehrere Elemente von A, die auf das gleiche

Element von B abgebildet werden. Also ist die Anzahl der Elemente

in f(A) gleich der in A.  Kurz |A| = |f(A) |

Nun ist aber f(A) eine Teilmenge von B, und wenn die genauso viel

Elemente wie B hat, ist sie gleich B. Also f surjektiv.

zu (b) ==> (c) :  ÄHnlich wie eben kann man argumentieren: Wenn f

surjektiv ist, dann ist f(A) = B also auch |f(A)| = |B|

und wegen der Vor.   |A| = |B| also auch |A| = |f(A)|.

Es gibt also genauso viel Bilder wie Urbilder; damit können keinem

 Urbild zwei verschiedene Bilder zugeordnet sein.

zu (c) ==> (a) ist wohl klar, das ist immer so.

Den zweiten Teil beweist du wohl am besten über vollst. Induktion nach

der Anzahl der Elemente von A.

Für n=1 ist es ja klar.

Wenn es für n gilt dann gilt bei n+1 elementigen Mengen A und B:

Sei f eine Bijektion von A nach B .

Wähle ein x∈A ( gibt es, da A nicht leer.) und betrachte alle

Bijektionen von A\{x} nach B \ {f(x)}. Diese lässt sich zu n+1

verschiedenen Bijektionen von A nach B fortsetzen, indem man

dem x jedes Mal ein anderes Element von B zuordnet.

 Und aus zwei verschiedenen f: A → B  können dabei keine

gleichen von  A\{x} nach B \ {f(x) entstehen, denn sonst wäre entweder bei

verschieden gewählten x die Bilder f(x) gleich (Widerspruch zu Injektiv) oder bei

gleicher Wahl von die Bilder verschieden, man hätte also mit einem

anderen "f" begonnen.

So entstehen also aus einer von Bijektion von A\{x} nach B \ {f(x)}n+1

Bijektionen von A nach B. Und weil es von der ersten Sorte n! gibt,

entstehen also n!*(n+1) = (n+1)! von A nach B.

Avatar von 289 k 🚀
+1 Daumen
|A|=|B|=n

Üblicherweise heißt das auch, dass A und B endlich sind. Und dann ist die Aussage unter (a) tatsächlich gültig. Erst für unendliche Mengen gilt die Aussage nicht mehr.

Wäre A oder B nicht endlich, dann wäre n eine unendliche Kardinalzahl. Und die habt ihr wahrscheinlich noch nicht besprochen.

Zu (b): vollständige Induktion.

Avatar von 107 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community