Gleichmächtigkeit. Beweise: |A|<|C| und |B|<|D| => |AxB|<|CxD|.

Question

Seien A, B, C und D beliebige Mengen. Beweise |A|<|C| und |B|<|D| => |AxB|<|CxD|.

Wenn ich das richtig verstanden habe, muss ich zeigen, dass es eine Injektion AxB -> CxD gibt und dass es keine Surjektion AxB -> CxD gibt. Die Injektion habe ich schon gemacht. Wie mache ich die Surjektion? Widerspruchsbeweis? Ich nehme an es gibt eine Surjektion AxB -> CxD und wie mache ich es weiter?

Answer 1

Seien A, B, C und D beliebige Mengen. Beweise |A|<|C| und |B|<|D| => |AxB|<|CxD|.

Es ist zu zeigen, dass die eine Menge mächtiger ist als die andere. Gleichmächtigkeit ist nicht verlangt. Deshalb genügt:

|AxB| = |A|*|B|  

          |nach Voraussetzung 1

< |C|*|B|

           |nach Voraussetzung 2

< |C|*|D| = |CxD|        qed.

Anmerkung: Benutzt wurde hier, dass das die Mächtigkeit des Kreuzprodukts 2er Mengen gleich dem Produkt der Mächtigkeiten der beiden Mengen ist.

Comments

Das darf ich aber so nicht. Erstens ich weiß gar nicht wie man sich das vorstellen kann, wenn A eine unendliche Menge ist also welche zahl ich z.B. |N| zuordnen kann. Das ist schon glaube ich eine höhere Mathematik. In meinem Skript wurde das mit Injektion bzw. Surjektion gemacht.

---

In der Tat ist die Aussage für endliche Mengen trivial. Nach den gegebenen Voraussetzungen gibt es Injektionen I:A->C und J:B->D, die nicht surjektiv sind. Dazu lässt sich eine Abbildung K:AxB->CxD durch K(a,b)=(I(a),J(b))∈CxD für (a,b)∈AxB konstruieren. Nun muss man noch begründen, warum K injektiv sein muss, aber nicht surjektiv sein kann.

---

Dein letzter Vorschlag ist total falsch. Wenn ich zeige, dass deine Funktion K injektiv aber nicht surjektiv ist, dann kriege ich nur |AxB| =< |CxD|. Um |AxB| < |CxD| zu beweisen, muss ich zeigen, dass es keine Surjektion geben kann und nicht, dass eine bestimmte Funktion keine Surjektion ist, was Du Vorgeschlagen hast.