Frage von leoquestiongoon, 12

maechtigkeit von mengen abbildungen?

in der vorlesung mathematik 1 wurde definiert. |M| = { M endlich mit m elementen: m M unendlich: unendluch }

kann mam daraus folgenden satz herleiten: sei f: M -> N , dann gilt: inhektivitaet von f impliziert |M| =< |N| ?

Antwort
von kreisfoermig, 4

In der Mengenlehre/Kardinalarithmetik wird ≤ einfach so definiert:

DEFINITION 1. |X| ≤ |Y| :⟺ ∃ƒ Injektion von X nach Y.

Da ist also NICHTS zu beweisen. Aber Mathematiker aus anderen Gebieten kapieren das irgendwie nicht. Gut, dann arbeiten wir kurz mit ihren Rahmen. Es wird aber schon mühselig sein, um einen richtig ausführlichen Beweis zu liefern. Das Ergebnis steht im SATZ ganz unten.

(Ich schreibe fortan X, Y statt M, N, weil die Buchstaben mich verwirren.)

DEFINITION 2. |X| = m, falls X aus m Elementen besteht für ein m∈ℕ. Ansonsten ist X unendlich und in diesem Falle definiere man |X| := ∞. Erweitere die lineare Ordnung auf ℕ zu einer auf ℕu{∞} durch ∞≤∞ und n≤∞ für alle n∈ℕ.

BEMERKUNG 3. Dass eine Menge, X, ∈ ℕ Elemente hat, heißt genauer, dass es eine Auflistung x[0], x[1], … , x[m–1] aller Elemente von X ohne Verdoppelungen gibt. Dies ist äquivalent zu der Existenz einer Bijektion der Form g : {0,1,…,m–1} —> X (nämlich g(k) = x[k], in der Tat ist eine Folge nichts anderes als eine Funktion von der Indexmenge in die Wertemenge).

DEFINITION 4. Eine Menge X heißt dann Dedekind-endlich gdw. jede Injektion ƒ : X—>X automatisch surjektiv ist.

LEMMA 5. Seien X, Y Mengen. Angenommen, es existiert eine Bijektion zwischen X und Y. Dann ist X Dedekind-endlich gdw. Y Dedekind-endlich ist.
Beweis. Sei g : X—>Y eine Bijektion. Angenommen, X sei Dedekind-endlich. Sei ƒ:Y—>Y eine Injektion. Zu zeigen: ƒ ist surjektiv. Zu diesem Zwecke beobachte, dass g¯¹ƒg : X—>X als Verkettung von injektiven Funktionen ebenfalls eine Injektion. Per Dedekind-Endlichkeit von X, ist g¯¹ƒg automatisch surjektiv. Folglich ist ƒ = g(g¯¹ƒg)g¯¹ als Verkettung von surjektiven Funktionen wiederum surjektiv. Darum ist Y Dedekind-endlich. Der Umkehrschluss gilt aus der Symmetrie der Lage (man ersetze g durch g¯¹). QED.

LEMMA 6. Sei m∈ℕ. Dann ist die Menge {0,1,…,m–1} Dedekind-endlich.

Beweis. Angenommen, dies sei nicht der Fall. Sei m die kleinste natürliche Zahl für die {0,1,…m–1} nicht Dedekind-endlich ist. Das heißt, es gibt eine Injektion, ƒ : {0,1,…,m–1}—>{0,1,…,m–1}, die nicht surjektiv ist. Darum existiert ein k₀∈{0,1,…,m–1} \ ƒ({0,1,…,m–1}). (Insbesondere ist m≠0, sonst wäre dies unmöglich.) Definiere die Abbildung

g : {0,1,...,m–1} ——→ {0,1,...,m–1}
: x ⟼ x falls x<k₀
: x ⟼ m–1 falls x=k₀
: x ⟼ x–1 falls x>k₀

Es ist einfach zu beweisen, dass dies eine Bijektion ist. Darum ist h:=gƒ als Verkettung injektiver Funktionen wiederum injektiv. Darüber hinaus gilt per Konstruktion von g, dass ƒ(x) ≠ k₀ und damit per Injektivität von g, dass h(x) = g(ƒ(x)) ≠ g(k₀) = m–1 für alle x∈{0,1,…,m–1}. Das heißt, h ist eine Funktion der Form
                    h:{0,1,…,m–1} —> {0,1,…,m–2}
und insbesondere ist die Einschränkung H := h|{0,1,…,m–2} eine Funktion der Form
                     H : {0,1,…,m–2} –—> {0,1,…,m–2}
Als Einschränkung einer Injektiven Funktion ist H wiederum injektiv. Setze y:=h(m–1). Also y∈{0,1,…,m–2}. Per Injektivität von h gilt (H(x)=)h(x) ≠ y für alle x∈{0,1,…,m–2}. Also ist H nicht surjektiv. Darum ist m–2 nicht Dedekind-endlich. Dies widerspricht der Minimalität von m(!) Also gilt die Behauptung. QED.

LEMMA 7. Sei X⊆Y und Y Dedekind-endlich. Dann ist X Dedekind-endlich.
Beweis. Sei ƒ : X—>X eine Injektion. Zu zeigen: ƒ ist surjektiv. Erweitere zu einer Abbildung F : Y—>Y durch F(x) = ƒ(x) für x∈X und F(x) = x für x ∈ Y\X. Die Funktion ist offensichtlich noch injektiv. Da Y Dedekind-endlich ist, ist F somit surjektiv. Sei y∈X(⊆Y). Wegen Surjektivität von F existiert ein x₀∈Y mit F(x₀)=y. Wenn x₀∉X, so gilt y=F(x₀)=x₀ ≠ y, da x₀∉X und y∈X. Also x₀∈X. Darum ƒ(x₀)=F(x₀)=y. Dies zeigt, dass ƒ surjektiv ist. QED.

FOLGERUNG 8. Seien X, Y Mengen und ƒ : X —> Y injektiv. Ist Y Dedekind-endlich, so auch X.
Beweis. ƒ(X)⊆Y und laut LEMMA 7 ist ƒ(X) somit Dedekind-endlich. Nun ist ƒ(X) eine bijektive Kopie von X (vermöge der Abbildung ƒ). Laut LEMMA 5 erbt X die Dedekind-Endlichkeit von ƒ(X). QED.

LEMMA 9. Sei X Dedekind-endlich. Dann gilt |X|=m für ein m∈ℕ.
Beweis. Es bedarf hier einer Anwendung des Auswahlaxioms (AC). Ich lasse den Beweis weg. ⊣

SATZ. Seien X, Y Mengen und ƒ : X —> Y ein Abbildung.
Angenommen, ƒ sei injektiv. Dann gilt |X| ≤ |Y|.

Beweis. Fall 1. Y sei unendlich. Dann gilt |X| ≤ ∞ = |Y|.

Fall 2. X sei leer. Dann gilt |X| = 0 ≤ |Y|.

Fall 3. X sei nicht leer und |Y|=n für ein n∈ℕ. Laut BEMERKUNG 3 bedeutet dies, dass Y eine bijektive Kopie von {0,1,…,n–1} ist. Laut LEMMATA 5 & 6 ist Y Dedekind-endlich. Da ƒ : X—>Y injektiv ist, gilt laut FOLGERUNG 8, dass X Dedekind-endlich ist. Laut LEMMA 9 gilt |X|=m für ein m∈ℕ. Es bleibt zu zeigen, dass m≤n. Angenommen, dies sei nicht der Fall. Also n<m

Aus |X|=m und |Y|=n folgt laut BEMERKUNG 3 die Existenz von Bijektionen g:{0,1,…,n–1}—>Y und h:{0,1,…,m–1}—>X. Die Verkettung
                  j := g¯¹ƒh : {0,1,…,m–1}—>{0,1,…,n–1}
ist injektiv, da die Funktionen in der Komposition jeweils injektiv sind. Da n<m gilt {0,1,…,n–1}⊂{0,1,…,m–1}. Also lässt sich j als Funktion der Form
                                j : {0,1,…,m–1}—>{0,1,…,m–1}
die nicht surjektiv ist, da j({0,1,…,m–1}) ⊆ {0,1,…,n–1} ⊂ {0,1,…,m–1} strikt! Andererseits ist j injektiv. Per Definition ist also {0,1,…,m–1} nicht Dedekind-endlich. Dies widerspricht LEMMA 6, das das Gegenteil beweist.

Widerspruch! Also gilt |X|=m≤n=|Y|.

Zusammenfassung. Aus Fällen 1–3 geht hervor, dass |X|≤|Y|. QED.

Kommentar von kreisfoermig ,

ANMERKUNG. Wenn man die ganze Vorarbeit wegräumt und versucht „intuitiv“ (was auch immer das heißt!) heranzugehen, würde man zu diesem Punkt kommen:

…Man hat ƒ : X —> Y injektiv mit Y={y[0],y[1],…,y[n–1]}. Dann kann man eine Teilmenge J ⊆ {0,1,…,n–1} so dass ƒ(X) = {y[j] | j∈J}. An dieser Stelle gibt es die Versuchung, zu sagen:
        Also gibt es m≤n Elemente in J, wir listen die auf: j(0), j(1), … , j(m–1), und dann fortzusetzen, indem man die Elemente aus X so auflistet als x[0],x[1],…,x[m–1], wobei x[k] = ƒ¯¹(y[j(k)]) für alle k. Dann hätte man wohl |X|=m ≤ n=|Y|. QED

Doch die erste Aussage (Also gibt es m≤n Elemente in J) wurde hier gar nicht rechtfertigt! Man muss formal (nicht bloß intuitiv) rechtfertigen, dass es dieses m gibt. Hier wäre ein Versuch:

  • J⊆{0,1,…,n–1} ist nicht leer, da X und damit ƒ(X) nicht leer sind (Fallvoraussetzung).
  • setze also j(0) = Min J.
  • für k=1 bis n:
    Falls J = {j(i) | i<k}, stopp! Setze m=k.
    Ansonsten, {j(i) | i<k} ⊂ J strikt. Setze j(k) = Min J \ {j(i) | i<k}.

Entweder gibt es 1≤k≤n wo das „stopp!“-Kriterium auftritt, und damit gilt J={j(i) | i<m} für ein m. Ansonsten gibt es j(0),j(1),…,j(n)∈J paarweise verscheiden. Wir wollen diesen Fall ausschließen und ja mit dem Argument oben fortsetzen. Doch wie? Intuitiv „wissen“ wir, dass dieser Fall nicht gehen dürfte, da ja „|J|≤n“ (das haben wir aber nicht bewiesen). Doch wir müssen das formal rechtfertigen, ohne in einem Kreis zu verlaufen (Mathe besteht aus Beweisen nicht Bauchgefühl!). Formal beweist man wie folgt: wir haben aus diesem Zustand eine Abbildung
                  j : {0,1,…,n–1} —–> {j(0),j(1),…,j(n–1)}
                                                  ⊂ J ⊆ {0,1,…,n–1}
welche gemäß der Rekursion oben injektiv jedoch nicht surjektiv ist. Hier tritt als einziger Widerspruch die Definition von Dedekind-Endlichkeit ein: dies ist unmöglich, da {0,1,…,n–1} Dedekind-endlich ist.

Deshalb habe ich die ganzen Sachen über Dedekind-Endlichkeit vor dem Satz ausgelegt und bewiesen, da sie auf jeden Fall in einem ausführlichen formalen Beweis gebraucht werden.

Antwort
von 0Ichputzhiernur, 4

Die Zielmenge kann nicht kleiner sein, als die Definitionsmenge, gleich allerdings schon. Also gilt Zielmenge größer/gleich Definitionsmenge :)

Also ja man kann es herleiten =) Theoretisch ist deine Frage damit beantwortet, da du nicht explizit um die Herleitung bittest ;)

Sollte dies der Fall sein, dann schreib einfach einen Kommentar, dann formuliere ich sie dir aus, aber da ich mir nicht sicher bin, ob du sie möchtest mache ich mir jetzt noch nicht die Mühe :D

Liebe Grüße und eine schöne Woche ^^

Bella

Keine passende Antwort gefunden?

Fragen Sie die Community