Mächtigkeit < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 15:47 Do 20.06.2013 | | Autor: | ne1 |
| Aufgabe | | $A$, $B$, $C$ und $D$ sind beliebige Mengen. Beweise falls $|A| < |C|$ und $|B|<|D|$ dann $|A [mm] \times [/mm] B| < |C [mm] \times [/mm] D|$. |
Hallo,
ich muss also zeigen, dass es eine Injektion $f: A [mm] \times [/mm] B [mm] \rightarrow [/mm] C [mm] \times [/mm] D$ gibt und, dass es keine Surjektion $A [mm] \times [/mm] B [mm] \rightarrow [/mm] C [mm] \times [/mm] D$ gibt.
Injektion:
Aus der Annahme wissen wir, dass es folgende Injektionen gibt $g: A [mm] \rightarrow [/mm] B$ und $h: B [mm] \rightarrow [/mm] D$. Ich definiere $f$ folgendermaßen, $f(a,b) = (g(a),h(b))$. Jetzt nehmen wir zwei beliebige $(a,b),(c,d) [mm] \in [/mm] A [mm] \times [/mm] B$. Wir wissen, dass $a [mm] \not [/mm] = c$ oder $b [mm] \not [/mm] = d$. Wegen der Injektion von $g, h$ erhalten wir $f(a,b) [mm] \not [/mm] = f(c,d)$.
keine Surjektion:
Hier habe ich Schwierigkeiten.
Ich nehme an, dass es eine Surjektion $i: A [mm] \times [/mm] B [mm] \rightarrow [/mm] C [mm] \times [/mm] D$ gibt. Ich nehme ein beliebiges $(c,d) [mm] \in [/mm] C [mm] \times [/mm] D$. Aus der Definition der Surjektion, weiß ich, dass es ein $(a,b) [mm] \in [/mm] A [mm] \times [/mm] B$ gibt, so dass $i(a,b) = (c,d)$. Jetzt weiß ich nicht weiter, wie ich zum Widerspruch komme. Ist mein Ansatz überhaupt richtig? Bitte um Tipps.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:15 Do 20.06.2013 | | Autor: | Marcel |
Hallo,
(Edit: Diese Antwort ist fehlerhaft!)
> [mm]A[/mm], [mm]B[/mm], [mm]C[/mm] und [mm]D[/mm] sind beliebige Mengen. Beweise falls [mm]|A| < |C|[/mm]
> und [mm]|B|<|D|[/mm] dann [mm]|A \times B| < |C \times D|[/mm].
>
> Hallo,
>
> ich muss also zeigen, dass es eine Injektion [mm]f: A \times B \rightarrow C \times D[/mm]
> gibt und, dass es keine Surjektion [mm]A \times B \rightarrow C \times D[/mm]
> gibt.
>
> Injektion:
> Aus der Annahme wissen wir, dass es folgende Injektionen
> gibt [mm]g: A \rightarrow B[/mm] und [mm]h: B \rightarrow D[/mm]. Ich
> definiere [mm]f[/mm] folgendermaßen, [mm]f(a,b) = (g(a),h(b))[/mm]. Jetzt
> nehmen wir zwei beliebige [mm](a,b),(c,d) \in A \times B[/mm].
Du musst natürlich hier $(a,b) [mm] \not=(c,d)$ [/mm] fordern!
> Wir wissen, dass [mm]a \not = c[/mm] oder [mm]b \not = d[/mm]. Wegen der
> Injektion von [mm]g, h[/mm] erhalten wir [mm]f(a,b) \not = f(c,d)[/mm].
>
> keine Surjektion:
> Hier habe ich Schwierigkeiten.
>
> Ich nehme an, dass es eine Surjektion [mm]i: A \times B \rightarrow C \times D[/mm]
> gibt. Ich nehme ein beliebiges [mm](c,d) \in C \times D[/mm]. Aus
> der Definition der Surjektion, weiß ich, dass es ein [mm](a,b) \in A \times B[/mm]
> gibt, so dass [mm]i(a,b) = (c,d)[/mm]. Jetzt weiß ich nicht weiter,
> wie ich zum Widerspruch komme. Ist mein Ansatz überhaupt
> richtig? Bitte um Tipps.
Mach' es so: Angenommen, es sei $i [mm] \colon [/mm] A [mm] \times [/mm] B [mm] \to [/mm] C [mm] \times [/mm] D$ doch surjektiv.
Sicherlich ist nach Voraussetzung weder [mm] $C=\varnothing$ [/mm] noch [mm] $D=\varnothing\,.$ [/mm]
Sei nun [mm] $d_0 \in [/mm] D$ beliebig, aber fest. Wir betrachten
[mm] $$T:=T_{d_0}:=\{(c,d_0):\;\;c \in C\}=C \times \{d_0\} \subseteq [/mm] C [mm] \times D\,.$$
[/mm]
Wegen der Surjektivität von [mm] $i\,$ [/mm] gilt: Jedes $t [mm] \in [/mm] T$ hat ein Urbild in $A [mm] \times B\,.$
[/mm]
Also: Für alle $c [mm] \in [/mm] C$ existiert ein [mm] $(a,b)=(a_c,b_c) \in [/mm] A [mm] \times [/mm] B$ mit [mm] $i(a,b)=(c,d_0)\,.$
[/mm]
Schreibe [mm] $i=(i_1,i_2)$ [/mm] mit [mm] $i_1 \colon [/mm] A [mm] \to [/mm] C$ und [mm] $i_2 \colon [/mm] B [mm] \to D\,.$ [/mm] Dann zeigt obige Überlegung:
Für alle $c [mm] \in [/mm] C$ existiert ein [mm] $a=a_c \in [/mm] A$ mit [mm] $i_1(a)=c\,.$
[/mm]
(Denn: Für alle $t [mm] \in [/mm] T$ existiert ein $(a,b) [mm] \in [/mm] A [mm] \times [/mm] B$ mit [mm] $i(a,b)=t=(c,d_0)\,.$ [/mm] D.h., für
alle $c [mm] \in [/mm] C$ existiert ein $(a,b) [mm] \in [/mm] A [mm] \times [/mm] B$ mit [mm] $i_1(a)=c$ [/mm] und [mm] $i_2(b)=d_0$ [/mm] - insbesondere
existiert also für alle $c [mm] \in [/mm] C$ ein $a [mm] \in [/mm] A$ mit [mm] $i_1(a)=c\,.$)
[/mm]
Kann denn dann noch $|A| < [mm] |C|\,$ [/mm] gelten?
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:31 Do 20.06.2013 | | Autor: | ne1 |
Danke Marcel.
Zuerst hab ich mir das auch so ähnlich gedacht. Ich weiß aber, dass falls $|A|<|B|$ und $C [mm] \not [/mm] = [mm] \emptyset$, [/mm] dann $|A [mm] \times [/mm] C| < |B [mm] \times [/mm] C|$ nicht richtig ist. Ich kann es aber doch analog beweisen also irgendwas ist mit Deinem Beweis nicht richtig.
Ich versuche jetzt mit meinem zweiten obigen Beispiel.
Injektion: $f: A [mm] \times [/mm] C [mm] \rightarrow [/mm] B [mm] \times [/mm] C$, $g: A [mm] \rightarrow [/mm] B$ ist injektiv (Voraussetzung), dann kann man leicht zeigen, dass $f$ definiert durch $f(a,c) = (g(a),c)$ injektiv.
keine Surjektion:
Angenommen, es gibt eine Surjektion $i: A [mm] \times [/mm] C [mm] \rightarrow [/mm] B [mm] \times [/mm] C$. Nach Voraussetzung ist weder $B= [mm] \emptyset$ [/mm] noch $C = [mm] \emptyset$. [/mm] Sei nun [mm] $c_0 \in [/mm] C$ beliebig, aber fest. Wir betrachten $T := [mm] \{(b,c_0): b \in B\} [/mm] = B [mm] \times \{c_0\} \subseteq [/mm] B [mm] \times [/mm] C$.
Wegen der Surjektiviät von $i$ gibt es ein $(a,c) [mm] \in [/mm] A [mm] \times [/mm] C$ mit $i(a,c) = [mm] (b,c_0)$ [/mm] für beliebige $b [mm] \in [/mm] B$. Schreibe $i = [mm] (i_1, i_2)$ [/mm] mit [mm] $i_1: [/mm] A [mm] \rightarrow [/mm] B$ und [mm] $i_2: [/mm] C [mm] \rightarrow [/mm] C$. Für alle $b [mm] \in [/mm] B$ existiert ein $a [mm] \in [/mm] A$ mit [mm] $i_1(a) [/mm] = b$. Dann gäbe es also eine Surjektion $A [mm] \rightarrow [/mm] B$ und das steht im Widerspruch mit der Annahme $|A| < |B|$. Ich habe also $|A|<|B| [mm] \wedge [/mm] C [mm] \not [/mm] = [mm] \emptyset \Rightarrow [/mm] |A [mm] \times [/mm] C| < |B [mm] \times [/mm] C|$ bewiesen, aber ich weiß, dass es falsch ist. Entweder habe ich einen Gedankenfehler oder deine Überlegung ist falsch.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:21 Do 20.06.2013 | | Autor: | Marcel |
Hallo,
> Danke Marcel.
>
> Zuerst hab ich mir das auch so ähnlich gedacht. Ich weiß
> aber, dass falls [mm]|A|<|B|[/mm] und [mm]C \not = \emptyset[/mm], dann [mm]|A \times C| < |B \times C|[/mm]
> nicht richtig ist.
woher weißt Du das? Kannst Du mir das beweisen oder mal mit einem
Beispiel belegen?
> Ich kann es aber doch analog beweisen
> also irgendwas ist mit Deinem Beweis nicht richtig.
Das kann zwar sein, sehe ich aber nicht ohne Weiteres ein.
> Ich versuche jetzt mit meinem zweiten obigen Beispiel.
>
> Injektion: [mm]f: A \times C \rightarrow B \times C[/mm], [mm]g: A \rightarrow B[/mm]
> ist injektiv (Voraussetzung), dann kann man leicht zeigen,
> dass [mm]f[/mm] definiert durch [mm]f(a,c) = (g(a),c)[/mm] injektiv.
>
> keine Surjektion:
> Angenommen, es gibt eine Surjektion [mm]i: A \times C \rightarrow B \times C[/mm].
> Nach Voraussetzung ist weder [mm]B= \emptyset[/mm] noch [mm]C = \emptyset[/mm].
> Sei nun [mm]c_0 \in C[/mm] beliebig, aber fest. Wir betrachten [mm]T := \{(b,c_0): b \in B\} = B \times \{c_0\} \subseteq B \times C[/mm].
>
> Wegen der Surjektiviät von [mm]i[/mm] gibt es ein [mm](a,c) \in A \times C[/mm]
> mit [mm]i(a,c) = (b,c_0)[/mm] für beliebige [mm]b \in B[/mm]. Schreibe [mm]i = (i_1, i_2)[/mm]
> mit [mm]i_1: A \rightarrow B[/mm] und [mm]i_2: C \rightarrow C[/mm]. Für
> alle [mm]b \in B[/mm] existiert ein [mm]a \in A[/mm] mit [mm]i_1(a) = b[/mm]. Dann
> gäbe es also eine Surjektion [mm]A \rightarrow B[/mm] und das steht
> im Widerspruch mit der Annahme [mm]|A| < |B|[/mm]. Ich habe also
> [mm]|A|<|B| \wedge C \not = \emptyset \Rightarrow |A \times C| < |B \times C|[/mm]
> bewiesen, aber ich weiß, dass es falsch ist. Entweder habe
> ich einen Gedankenfehler oder deine Überlegung ist falsch.
Dann sag' mir bitte, warum das falsch ist. Dann kann ich auch in meinem
Beweis nachgucken, ob ich irgendwo "geschludert" habe. Mit Deiner Aussage,
dass Du weißt, dass $|A| < |B| [mm] \Rightarrow [/mm] |A [mm] \times [/mm] C| < |B [mm] \times [/mm] C|$ falsch ist,
ist uns da nicht wirklich geholfen.
Ich glaube, ich kann mir aber selbst was zusammenbasteln:
Sei $|A|=2$ und $|B|=3$ und [mm] $C=\IN\,.$ [/mm] Dann sind $A [mm] \times [/mm] C$ und $B [mm] \times [/mm] C$ beide
gleichmächtig zu [mm] $\IN\,.$
[/mm]
Ich schau' mir jetzt mal an, wo es da "hakt"!
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:41 Do 20.06.2013 | | Autor: | Marcel |
Hallo,
also, schauen wir es uns an:
> Danke Marcel.
>
> Zuerst hab ich mir das auch so ähnlich gedacht. Ich weiß
> aber, dass falls [mm]|A|<|B|[/mm] und [mm]C \not = \emptyset[/mm], dann [mm]|A \times C| < |B \times C|[/mm]
> nicht richtig ist. Ich kann es aber doch analog beweisen
> also irgendwas ist mit Deinem Beweis nicht richtig.
>
> Ich versuche jetzt mit meinem zweiten obigen Beispiel.
>
> Injektion: [mm]f: A \times C \rightarrow B \times C[/mm], [mm]g: A \rightarrow B[/mm]
> ist injektiv (Voraussetzung), dann kann man leicht zeigen,
> dass [mm]f[/mm] definiert durch [mm]f(a,c) = (g(a),c)[/mm] injektiv.
>
> keine Surjektion:
> Angenommen, es gibt eine Surjektion [mm]i: A \times C \rightarrow B \times C[/mm].
> Nach Voraussetzung ist weder [mm]B= \emptyset[/mm] noch [mm]C = \emptyset[/mm].
> Sei nun [mm]c_0 \in C[/mm] beliebig, aber fest. Wir betrachten
> [mm]T := \{(b,c_0): b \in B\} = B \times \{c_0\} \subseteq B \times C[/mm].
>
> Wegen der Surjektiviät von [mm]i[/mm] gibt es ein [mm](a,c) \in A \times C[/mm]
> mit [mm]i(a,c) = (b,c_0)[/mm] für beliebige [mm]b \in B[/mm]. Schreibe [mm]i = (i_1, i_2)[/mm]
> mit [mm]i_1: A \rightarrow B[/mm] und [mm]i_2: C \rightarrow C[/mm].
ich glaube, hier ist der Knackpunkt. Ich habe da einfach mal so [mm] $i_1$ [/mm] und [mm] $i_2$
[/mm]
ins Spiel gebracht. Wir müssen das anders machen, und eher solche [mm] $i_1$ [/mm] und
[mm] $i_2$ [/mm] definieren.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:24 Do 20.06.2013 | | Autor: | Marcel |
Hallo,
also, ich habe gemerkt, dass da wirklich ein Patzer in der anderen Antwort
war. Machen wir es also mal anders:
> [mm]A[/mm], [mm]B[/mm], [mm]C[/mm] und [mm]D[/mm] sind beliebige Mengen. Beweise falls [mm]|A| < |C|[/mm]
> und [mm]|B|<|D|[/mm] dann [mm]|A \times B| < |C \times D|[/mm].
>
> Hallo,
>
> ich muss also zeigen, dass es eine Injektion [mm]f: A \times B \rightarrow C \times D[/mm]
> gibt und, dass es keine Surjektion [mm]A \times B \rightarrow C \times D[/mm]
> gibt.
>
> Injektion:
> Aus der Annahme wissen wir, dass es folgende Injektionen
> gibt [mm]g: A \rightarrow B[/mm] und [mm]h: B \rightarrow D[/mm]. Ich
> definiere [mm]f[/mm] folgendermaßen, [mm]f(a,b) = (g(a),h(b))[/mm]. Jetzt
> nehmen wir zwei beliebige [mm](a,b),(c,d) \in A \times B[/mm]. Wir
> wissen, dass [mm]a \not = c[/mm] oder [mm]b \not = d[/mm]. Wegen der
> Injektion von [mm]g, h[/mm] erhalten wir [mm]f(a,b) \not = f(c,d)[/mm].
>
> keine Surjektion:
angenommen, es gäbe doch eine Surjektion $i: A [mm] \times [/mm] B [mm] \to [/mm] C [mm] \times D\,.$ [/mm] Wir schreiben
[mm] $i=(i_1,\,i_2)\,,$ [/mm] wobei hier aber [mm] $i_1 \colon [/mm] A [mm] \times [/mm] B [mm] \to [/mm] C$ und [mm] $i_2 \colon [/mm] A [mm] \times [/mm] B [mm] \to [/mm] D$ seien. (Ein wesentlicher
Unterschied zu dem, was ich in der anderen, falschen, Antwort geschrieben
hatte!)
Halten wir [mm] $b_0 \in [/mm] B$ fest: Dann ist [mm] $i_1(A \times \{b_0\}) \subsetneqq C\,,$ [/mm] weil ja [mm] $i_1$ [/mm] nicht surjektiv sein
kann.
So, ehrlich gesagt weiß ich jetzt gerade auch nicht mehr weiter (außer, dass
ich etwas analoges mit [mm] $i_2(\{a_0\} \times [/mm] B)$ formulieren kann). Vielleicht
muss/kann man mit dem Cantorschen Diagonalverfahren weiter verfahren...
Ich stelle die Frage mal nur auf halb beantwortet, auch, wenn sie eher nach
wie vor unbeantwortet ist. 
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 16:37 Sa 22.06.2013 | | Autor: | ne1 |
Danke nochmal Marcel.
Ja, jetzt können wir tatsächlich für $f: A [mm] \times [/mm] B [mm] \rightarrow [/mm] C [mm] \times [/mm] D$, [mm] $f_1: [/mm] A [mm] \times [/mm] B [mm] \rightarrow [/mm] C$ und [mm] $f_2: [/mm] A [mm] \times [/mm] B [mm] \rightarrow [/mm] D$ schreiben. Das bestätigen sogar mein Buch :).
Ich glaube, ich habe den Ansatz gefunden. Mir fehlt aber noch der entscheidende Schritt.
Ich muss beweisen $|A|<|C| [mm] \wedge [/mm] |B|<|D| [mm] \Rightarrow [/mm] |A [mm] \times [/mm] B|<|C [mm] \times [/mm] D|$.
$|A|<|C| [mm] \wedge [/mm] |B|<|D| [mm] \Rightarrow [/mm] |A [mm] \times [/mm] B|<|C [mm] \times [/mm] D|$ ist dasselbe wie $|C [mm] \times [/mm] D| [mm] \le [/mm] |A [mm] \times [/mm] B| [mm] \Rightarrow [/mm] |C| [mm] \le [/mm] |A| [mm] \vee [/mm] |D| [mm] \le [/mm] |B|$. Das ist äquivalent mit [mm] $(\exists [/mm] f) f: A [mm] \times [/mm] B [mm] \rightarrow [/mm] ^{surj.} C [mm] \times [/mm] D [mm] \Rightarrow (\exists [/mm] g) g: A [mm] \rightarrow [/mm] ^{surj.} C [mm] \vee (\exists [/mm] h) h: B [mm] \rightarrow [/mm] ^{surj.} D$. Jetzt können wir deine Definition verwenden also [mm] $(\exists f_1) f_1: [/mm] A [mm] \times [/mm] B [mm] \rightarrow [/mm] ^{surj.} C [mm] \wedge (\exists f_2)f_2: [/mm] A [mm] \times [/mm] B [mm] \rightarrow [/mm] ^{surj.} D [mm] \Rightarrow (\exists [/mm] g) g: A [mm] \rightarrow [/mm] ^{surj.} C [mm] \vee (\exists [/mm] h) h: B [mm] \rightarrow [/mm] ^{surj.} D$.
Jetzt schreibe ich $i: A [mm] \rightarrow [/mm] A [mm] \times [/mm] B$ und $j: B [mm] \rightarrow [/mm] A [mm] \times [/mm] B$. Es reicht jetzt zu zeigen, dass es eine Surjektion [mm] $f_1 \circ [/mm] i: A [mm] \rightarrow [/mm] C$ oder [mm] $f_2 \circ [/mm] j: B [mm] \rightarrow [/mm] D$ gibt.
Ich nehme mir jetzt ein beliebiges $c [mm] \in [/mm] C$. Wir wissen, dass es ein $(a,b) [mm] \in A\times [/mm] B$ gibt, so dass [mm] $f_1(a,b) [/mm] = c$ (weil [mm] f_1 [/mm] surjektiv). Es muss kein $a [mm] \in [/mm] A$ geben, so dass [mm] $(f_1 \circ [/mm] i)(a) = c$ (siehe Skizze unten). Jetzt nehmen wir ein $d [mm] \in [/mm] D$. Es gibt ein $(a,b) [mm] \in [/mm] A [mm] \times [/mm] B$, so dass [mm] $f_2(a,b) [/mm] = d$ (weil [mm] f_2 [/mm] surjektiv). Dann kann es auf jeden Fall ein $b [mm] \in [/mm] B$ geben, so dass [mm] $(f_2 \circ [/mm] j)(b) = d$. Warum es so ist, ist, wie gesagt, der entscheidende Schritt und hier komme ich jetzt nicht weiter :D. Ich muss es natürlich präzise formulieren. In der Skizze hat man bisschen mit abzählen und deshalb ist das so "selbstverständlich". Es ist mir klar, dass ich es so nicht machen darf. Das mit der Skizze ist natürlich nur ne Anschauung. Vielleicht habt Ihr ne Idee warum das so ist und wie ich das jetzt formulieren kann.
Skizze:
http://i.imgur.com/EhD45cs.png
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Di 23.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 So 21.07.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
