Abbildung auf Potenzmenge < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:53 Di 27.10.2009 | | Autor: | Doemmi |
| Aufgabe | | Es sei X eine Menge und f : X [mm] \to \mathcal{P}(X) [/mm] eine Abbildung von X in die zugehörige Potenzmenge. Man zeige, dass f nicht surjektiv sein kann. |
Sei die Menge X := {1,2,3}, dann ist [mm] \mathcal{P}(X) [/mm] = { [mm] \emptyset, [/mm] {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3} }.
Nunja, ich kann mir jetzt nicht wirklich die Abbildung vorstellen, vielleicht ist das Beispiel auch schlecht...
zz.: [mm] \forall [/mm] p [mm] \in \mathcal{P} \exists [/mm] x [mm] \in [/mm] X : f(x) = p
Ich brauche eine Idee...
|
|
| |
|
Hallo Doemmi,
überlege dir, warum die Kardinalität der Potenzmenge immer grösser ist, als die Kardinalität von X, dann hast dus 
Und eine bestimmte Funktion dir vorzustellen, wird dir wohl nicht gelingen, weil du es für JEDE Funktion zeigen sollst, aber als Erklärung zur Vorstellung.
Überlege dir, warum zu jedem [mm] $x\in [/mm] X$ erstmal gilt [mm] $\{x\} \in \mathcal{P}(X)$ [/mm] und dann gibts halt in [mm] \mathcal{P}(X) [/mm] aber noch mehr Elemente, d.h. f kann nicht ALLE Elemente in der Potenzmenge treffen, weil es halt einfach "zu wenig Urbilder" gibt.
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:38 Di 27.10.2009 | | Autor: | Doemmi |
Ich bin mir nicht klar darüber, wie ich beweisen kann, dass die Mächtigkeit von X kleiner als die ihrer Potenzmenge ist.
Ich habe mir einen Beweis im Internet zusammengefasst, verstehe ihn aber nicht so ganz:
Sei f surjektiv und sei M eine Menge.
M := { [mm] x\in [/mm] X | x [mm] \in [/mm] f(x) } [mm] \in \mathcal{P}(X)
[/mm]
f bildet Elemente von X auf Teilmengen von X ab, also Elemente von [mm] \mathcal{P}(X).
[/mm]
M ist Teilmenge von X, also auch von [mm] \mathcal{P}(X)
[/mm]
Da f surjektiv [mm] \Rightarrow \exists [/mm] x [mm] \in [/mm] X : f(x) = M
Sei x [mm] \in [/mm] M [mm] \Rightarrow [/mm] (Def. M) x [mm] \not\in [/mm] f(x), aber f(x) = M
Sei x [mm] \not\in [/mm] M [mm] \Rightarrow [/mm] (Def. M) x [mm] \in [/mm] f(x), aber f(x) = M
Da wäre dann der Widerspruch.
Wie sieht es denn eigentlich mit einelementigen Mengen und deren Potenzmengen aus oder der leeren Menge?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:22 Mi 28.10.2009 | | Autor: | pelzig |
> Ich habe mir einen Beweis im Internet zusammengefasst,
> verstehe ihn aber nicht so ganz:
>
> Sei f surjektiv und sei M eine Menge.
> [mm]M := \{ x\in X | x \in f(x) \} \in \mathcal{P}(X)[/mm]
Nein, du musst definieren [mm] $M:=\{x\in X\mid x\not\in f(x)\}$, [/mm] sonst klappt es nicht.
> f bildet Elemente von X auf Teilmengen von X ab, also
> Elemente von [mm]\mathcal{P}(X).[/mm]
> M ist Teilmenge von X, also auch von [mm]\mathcal{P}(X)[/mm]
>
> Da f surjektiv [mm]\Rightarrow \exists[/mm] x [mm]\in[/mm] X : f(x) = M
>
> Sei x [mm]\in[/mm] M [mm]\Rightarrow[/mm] (Def. M) x [mm]\not\in[/mm] f(x), aber f(x)
> = M
> Sei x [mm]\not\in[/mm] M [mm]\Rightarrow[/mm] (Def. M) x [mm]\in[/mm] f(x), aber f(x)
> = M
>
> Da wäre dann der Widerspruch.
Richtig.
> Wie sieht es denn eigentlich mit einelementigen Mengen und
> deren Potenzmengen aus oder der leeren Menge?
Der Beweis funktionert trotzdem. Für endliche und die leere Menge ist die Aussage sowieso klar, da dann [mm] $\#\mathcal{P}(X)=2^{\#X}$ [/mm] ist.
Gruß, Robert
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 07:17 Mi 28.10.2009 | | Autor: | Doemmi |
Vielen Dank für die Hilfe, eine Frage hab ich noch zu dem Thema:
Die Kardinalität der Potenzmenge zu einer Menge A ist ja so definiert:
[mm] \mathcal{P}(A) [/mm] := { Y | Y [mm] \subseteq [/mm] A } = 2{#A}
Wie kann man das beweisen, bzw. wie kommt man darauf?
|
|
|
| |
|
Hallo,
Du meinst sicher: [mm] |\mathcal{P}(A)|=2^{|A|}. [/mm] (Die Betragsstriche stehen für Mächtigkeit der Menge)
Ich beschränke mich auf eine endliche Menge A.
Du kannst das per Induktion zeigen.
Beh.: Es sei [mm] A_n:=\{a_1,..., a_n\} [/mm] eine n-elementige Menge. Dann ist [mm] |\mathcal{P}(A)|=2^{n} [/mm] für alle [mm] n\in \IN.
[/mm]
Nun versuch mal eine Induktion.
Wenn's nicht gleich klappt, nicht sofort nachfragen.
Mach Dir dann mal ein Beispiel, etwa n=2 und schau, was passiert, wenn Du Deine Menge um ein Element erweiterst.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:25 Mi 28.10.2009 | | Autor: | Doemmi |
Beh.: Es sei [mm]A_n:=\{a_1,..., a_n\}[/mm] eine n-elementige Menge.
Dann ist [mm]|\mathcal{P}(A)|=2^{n}[/mm] für alle [mm]n\in \IN.[/mm]
IA: n = 1
Sei [mm] A_{1} [/mm] := { [mm] a_{1} [/mm] } [mm] \Rightarrow \mathcal{P}(A) [/mm] = { [mm] \emptyset, {a_{1} } [/mm] }
[mm] \Rightarrow |\mathcal{P}(A)|=2^{1} [/mm] = 2
Für n = 1 stimmt die Aussage
IV: Beh. gelte für bel., aber festes n...
IS: n [mm] \to [/mm] n + 1
Sei [mm] A_{n+1} [/mm] := [mm] {a_{1}, ... , a_{n+1}}
[/mm]
zz. [mm] |\mathcal{P}(A)|=2^{n+1} [/mm] = 2 * 2{n}
Anhand des Versuchs, wenn ich ein Element mehr in die Menge packe, bestätigt sich, dass dann die Potenzmenge die doppelte Kardinalität hat, aber ich weiß nicht, wie ich das, also den Induktionsschritt beweisen kann.
|
|
|
| |
|
Hallo Tommy,
> Beh.: Es sei [mm] $A_n:=\{a_1,..., a_n\}$ [/mm] eine n-elementige Menge.
> Dann ist [mm] $|\mathcal{P}(A)|=2^{n}$ [/mm] für alle [mm] $n\in \IN$
[/mm]
>
> IA: $n = 1$
> Sei [mm] $A_{1} [/mm] := [mm] \{ a_{1} \} \Rightarrow \mathcal{P}(A) [/mm] = [mm] \{ \emptyset, \{a_{1} \}\}$
[/mm]
> [mm] $\Rightarrow |\mathcal{P}(A)|=2^{1}= [/mm] 2$
>
> Für $n = 1$ stimmt die Aussage
>
> IV: Beh. gelte für bel., aber festes n...
>
> IS: $n [mm] \to [/mm] n + 1$
>
> Sei [mm] $A_{n+1} [/mm] := [mm] \{a_{1}, ... , a_{n+1}\}$
[/mm]
> zz.
> [mm] $|\mathcal{P}(A)|=2^{n+1} [/mm] = 2 [mm] \cdot{} 2^{n}$
[/mm]
>
> Anhand des Versuchs, wenn ich ein Element mehr in die Menge
> packe, bestätigt sich, dass dann die Potenzmenge die
> doppelte Kardinalität hat, aber ich weiß nicht, wie ich
> das, also den Induktionsschritt beweisen kann.
Nimm mal o.b.d.A. an, dass [mm] $A_{n+1}=A_n\cup\{x\}$ [/mm] ist mit [mm] $x\notin A_n$
[/mm]
Dann betrachte die möglichen Teilmengen von [mm] $A_{n+1}$, [/mm] die x nicht enthalten (siehe IV) und diejenigen, die x enthalten.
Bzw. in deiner Notation ist ja [mm] $a_{n+1}$ [/mm] auch nicht in [mm] $A_n$ [/mm] 
Schaue dir also wieder diejenigen Teilmengen von [mm] $A_{n+1}$ [/mm] an, die [mm] $a_{n+1}$ [/mm] nicht enthalten und diejenigen, die es enthalten...
Wieviele gibt's davon?
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:25 Mi 28.10.2009 | | Autor: | pelzig |
> Überlege dir, warum zu jedem [mm]x\in X[/mm] erstmal gilt [mm]\{x\} \in \mathcal{P}(X)[/mm]
> und dann gibts halt in [mm]\mathcal{P}(X)[/mm] aber noch mehr
> Elemente, d.h. f kann nicht ALLE Elemente in der
> Potenzmenge treffen, weil es halt einfach "zu wenig
> Urbilder" gibt.
Tja, das ist zwar hübsch anschaulich aber so kann man das mathematisch einfach nicht beweisen. Sobald die Mengen unendlich werden, ist das alles nicht mehr so klar, zum Beispiel kann ich ja sagen zu [mm] $n\in\IN$ [/mm] liegt auch [mm] $2n\in\IN$, [/mm] aber es gibt in [mm] $\IN$ [/mm] noch wesentlich mehr Elemente als die geraden Zahlen, also kann es keine Surjektion von [mm] $\IN$ [/mm] auf [mm] $\IN$ [/mm] geben... das ist natürlich Murx.
Mit diesem Argument hast du nämlich lediglich gezeigt, dass es keine Surjektion [mm] $\Phi:X\to\mathcal{P}(X)$ [/mm] gibt mit [mm] $\Phi(x)=\{x\}$, [/mm] aber wer sagt dir, dass man es nicht vielleicht schafft wenn man sich nicht so dämlich anstellt?
Gruß, Robert
|
|
|
|
