Satz von der Potenzmenge(2) < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:23 Mo 13.03.2006 | | Autor: | clown99 |
| Aufgabe | Zeigen Sie, es gibt keine bijektive Abbildung $ f:X->Pot(X) $
"Ich werde versuchen, Dir die Stelle im Beweis zu erklären.
Wir haben
$ f:X->Pot(X) $ bijektiv
Das bedeutet. Jedem Element x von X wird eine Teilmenge Y von X zugeordnet.
Man könnte etwa f(x) = $ [mm] \{x\} [/mm] $ haben.
Dann ist immer $ x [mm] \in [/mm] Y = f(x) $
Oder: f(x) = $ X [mm] \setminus \{x\} [/mm] $.
Dann ist immer $ x [mm] \not\in [/mm] Y = f(x) $
Die Menge $ [mm] Z:=\{x \in X : x \not\in f(x) \} [/mm] $ hängt also stark von der Abblidung f ab. Z ist eine Teilmenge von X, also Element von Pot(X).
Es müsste also ein $ z [mm] \in [/mm] X $ geben, mit f(z)=Z, da f bijektiv ist. Man hat aber dann
$ z [mm] \in [/mm] Z [mm] \Leftrightarrow [/mm] z [mm] \not\in [/mm] f(z) = Z $
Das ist der gewünschte Widerspruch.
Zwischen einer Menge und ihrer Potenzmenge kann es keine Bijektion geben. "
|
Ich habe die Antwort auf eine zu dem Thema bereits gestellte Frage zitiert.
Leider ist mir immer noch nicht klar, wieso f(z) = Z sein soll. Geht man denn nicht von mehreren Elementen in Z aus. Müsste nicht für z1 [mm] \in [/mm] Z dann gelten f(z1) = Z1 mit Z1 [mm] \subseteq [/mm] Z, dies bedeutet dann ja Z1 [mm] \in [/mm] Pot(X).
Angenommen X = {1, 2, 3}, dann gilt doch für
Pot(X) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} {1, 2, 3}}.
Falls nämlich z1 = elementar1,2 wäre f(z1) = Z1 = {1, 2} und bei
z2 = elementar1,3 wäre Z2 = {1, 3}. Soweit wären ja Z1, Z2 Pot(X).
Nähmen wir unser gesamtes z = {elnix, el1,2, el1,3, el2,3, el1,2,3}, bestünde Z aus der Menge {elnix, el1,2, el1,3, el2,3, el1,2,3}, was so nicht geht, weil mehrere Elemente nicht gleichzeitig in einer Menge bestehen und es kein elementares Nix gibt, nur die elementare leere Menge?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:29 Di 14.03.2006 | | Autor: | DaMenge |
Hallo,
> Ich habe die Antwort auf eine zu dem Thema bereits
> gestellte Frage zitiert.
Also ich finde den Beweis recht schön und logisch, kannst du noch einen Link zur Quelle angeben, also von dort, wo du zitierst?
> Leider ist mir immer noch nicht klar, wieso f(z) = Z sein
> soll. Geht man denn nicht von mehreren Elementen in Z aus.
> Müsste nicht für z1 [mm]\in[/mm] Z dann gelten f(z1) = Z1 mit Z1
> [mm]\subseteq[/mm] Z, dies bedeutet dann ja Z1 [mm]\in[/mm] Pot(X).
>
> Angenommen X = {1, 2, 3}, dann gilt doch für
> Pot(X) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} {1, 2,
> 3}}.
ja, f soll eine bijektive Abbildung (insbesondere surjektiv) von X nach Pot(X) sein, d.h. in deinem Beispiel, sollen alle 8 Elemente aus Pot(X) als Bilder von f auftreten, d.h. alle dieser 8 Elemente hat (min.) ein Urbild x in X (, und jedes Urbild ist einelementig)
Weil Z ja eine Teilmenge von X ist, ist Z in Pot(X) enthalten und muss daher ein einelementiges Urbild z in X haben, denn f soll surjektiv sein.
(Übrigens kannst du anhand des Beweises dir auch mal überlegen, ob man "bijektiv" durch injektiv oder surjektiv in der Behauptung ersetzen könnte..)
> Falls nämlich z1 = elementar1,2 wäre f(z1) = Z1 = {1, 2}
> und bei
> z2 = elementar1,3 wäre Z2 = {1, 3}. Soweit wären ja Z1, Z2
> Pot(X).
> Nähmen wir unser gesamtes z = {elnix, el1,2, el1,3, el2,3,
> el1,2,3}, bestünde Z aus der Menge {elnix, el1,2, el1,3,
> el2,3, el1,2,3}, was so nicht geht, weil mehrere Elemente
> nicht gleichzeitig in einer Menge bestehen und es kein
> elementares Nix gibt, nur die elementare leere Menge?
hier verstehe ich leider nicht genau, worauf du hinaus willst.
(außerdem was soll "elementar" und elnnix sein z.B.)
sagst du aber bitte noch etwas zur Quelle ?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:02 Di 14.03.2006 | | Autor: | clown99 |
> > Angenommen X = {1, 2, 3}, dann gilt doch für
> > Pot(X) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3} {1, 2,
> > 3}}.
> ja, f soll eine bijektive Abbildung (insbesondere surjektiv) von X nach
> Pot(X) sein, d.h. in deinem Beispiel, sollen alle 8 Elemente aus Pot(X)
> als Bilder von f auftreten, d.h. alle dieser 8 Elemente hat (min.) ein Urbild > x in X (, und jedes Urbild ist einelementig)
> Weil Z ja eine Teilmenge von X ist, ist Z in Pot(X) enthalten und muss
> daher ein einelementiges Urbild z in X haben, denn f soll surjektiv sein.
Mindestens ein einelementiges Urbild z in X oder.
> > Falls nämlich z1 = elementar1,2 wäre f(z1) = Z1 = {1, 2}
> > und bei
> > z2 = elementar1,3 wäre Z2 = {1, 3}. Soweit wären ja Z1, Z2
> > Pot(X).
> > Nähmen wir unser gesamtes z = {elnix, el1,2, el1,3, el2,3,
> > el1,2,3}, bestünde Z aus der Menge {elnix, el1,2, el1,3,
> > el2,3, el1,2,3}, was so nicht geht, weil mehrere Elemente
> > nicht gleichzeitig in einer Menge bestehen und es kein
> > elementares Nix gibt, nur die elementare leere Menge?
>
> hier verstehe ich leider nicht genau, worauf du hinaus
> willst.
> (außerdem was soll "elementar" und elnnix sein z.B.)
Ich gehe davon aus, dass die Urbilder einelementig sind. Das wollt ich mit diesem elementar für 2 und mehr Elemente sowie mit elnix für die leere Menge als logisches Urbildelement ausdrücken. Z müsste ja alle restlichen einelementigen Urbildelemente neben 1, 2 und 3 umfassen. All diese Elemente zusammen wären z und f(z) wäre ja die Teilmenge Z [mm] \subset [/mm] X für die doch gilt Z [mm] \in [/mm] Pot(X).
Was mit dem Beweis allgemein ausgesagt werden soll ist mir klar, doch scheiter ich an der Vorstellung von Z.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:48 Di 14.03.2006 | | Autor: | DaMenge |
Hi,
> > Weil Z ja eine Teilmenge von X ist, ist Z in Pot(X)
> enthalten und muss
> > daher ein einelementiges Urbild z in X haben, denn f soll
> surjektiv sein.
>
> Mindestens ein einelementiges Urbild z in X oder.
Hier sind beide Sätze richtig.
Du betonst nur zusätzlich die (mögliche) Anzahl von Urbildern, die hier jedoch irrelevant ist, denn die Existenz eines Urbildes reicht schon aus.
> Ich gehe davon aus, dass die Urbilder einelementig sind.
> Das wollt ich mit diesem elementar für 2 und mehr Elemente
> sowie mit elnix für die leere Menge als logisches
> Urbildelement ausdrücken. Z müsste ja alle restlichen
> einelementigen Urbildelemente neben 1, 2 und 3 umfassen.
> All diese Elemente zusammen wären z und f(z) wäre ja die
> Teilmenge Z [mm]\subset[/mm] X für die doch gilt Z [mm]\in[/mm] Pot(X).
>
> Was mit dem Beweis allgemein ausgesagt werden soll ist mir
> klar, doch scheiter ich an der Vorstellung von Z.
>
Wie schon in anderen Antworten gesagt wurde : du versuchst dir etwas vorzustellen, was nicht geht.
Wir machen es mal an einem noch kleinerem Beispiel :
X={1,2} , dann hat Pot(X) ja 4 Elemente, d.h. aber, dass auch X (mindestens) 4 Elemente haben müsste, damit es überhaupt eine surjektive Abbildung geben kann...
(sagen wir mal, dass f(1)={2} und f(2)={1,2} , dann fehlen aber einfach noch zwei Elemente x und y, so dass f(x)={1} und f(y)=leere Menge )
Man kann allgemein zeigen (für endliche Mengen):
wenn [mm] $f:A\to [/mm] B $
surjektiv, dann [mm] $|A|\ge [/mm] |B|$
injektiv, dann [mm] $|A|\le [/mm] |B|$
bijektiv, dann $|A|=|B|$
und es ist ja klar, dass immer gilt $|X|< |Pot(X)|$ , oder?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:03 Di 14.03.2006 | | Autor: | clown99 |
Jau, das leuchtet mir ein. Ok, ich glaube, ich verstehe jetzt wie das mit dem z gemeint ist. Es wird einfach nur ein z gesucht, dass die Definition der Menge Z erfüllt. Dabei spielt es keine Rolle, wie vielelementig es ist. Dieses z gibt es nicht, weil es nicht auf die Teilmenge Z geworfen werden kann.
1. Wird z auf Z geworfen, wäre es kein Element aus Z, weil ja f(z) = Z gilt.
2. Wird z nicht auf Z geworfen, wäre es ein Element aus Z, es bildet aber wegen Punkt 1 keine Teilmenge Z.
Ist die Vorstellung meines Z denn soweit richtig, also müsste es nicht so aussehen. Mir ist klar, dass es laut Definition der Menge Z, kein z, wie auch kein Z gibt. Ach, passt scho.
Danke für die Antworten :)
|
|
|
| |
|
Hallo zusammen,
da mir der in der Aufgabenstellung gepostete Beweis doch etwas schwammig scheint, erlaub ich mir mal, ihn ordentlich
zu schreiben.
Wir wollen zeigen: Wenn X eine Menge ist, so gibt es keine surjektive Abbildung [mm] f\colon X\to [/mm] Pot(X).
Beweis durch Widerspruch.
Annahme: X beliebige Menge, und [mm] f\colon X\to [/mm] Pot(X) surjektiv.
Wir werden nun diese Annahme zum Widerspruch führen.
Wenn es solches f gäbe, so betrachte die Teilmenge [mm] Y\subsetes [/mm] X definiert als
[mm] Y=\{x\in X\: |\: x\not\in f(x)\}
[/mm]
Wenn f also surjektiv wäre, so gäbe es dann auch ein [mm] x_0\in [/mm] X mit [mm] f(x_0)=Y.
[/mm]
Dann gäbe es für das Enthaltensein/Nichtenthaltensein von [mm] x_0 [/mm] in Y nur zwei Möglichkeitem,
wir führen beide zum Widerspruch.
Fall 1: [mm] x_0\in [/mm] Y, dann gilt also nach Def. von Y [mm] \:\: x_0\in Y=f(x_0) [/mm] und damit [mm] x_0\not\in [/mm] Y, Widerspruch.
Fall 2: [mm] x_0\not\in [/mm] Y, dann gilt nach Def. von Y aber [mm] x_0\in [/mm] Y, Widerspruch.
Fertig.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:10 Di 14.03.2006 | | Autor: | clown99 |
Wieder dieselbe Frage, wieso soll f(x0) = Y gelten. Wie hat man sich bezogen auf mein Beispiel x0 vorzustellen. Ist es quasi das Sammelsurium aller nichteineinlementigen Urbilder. In meinem Beispiel das der 5 els? Durch den Widerspruch wird gezeigt, dass diese Urbildelemente der Menge Y nicht real existent sind, ok, aber hab ich mir das da richtig gedacht mit meinem Beispiel?
|
|
|
| |
|
Hallo,
also Du versuchst gerade ein Beispiel zu konstruieren, für etwas, was es bewiesenermaßen nicht gibt. Mit anderen Worten, Du findest auch ein solches Beispiel nicht.
Die Idee, wie man auf das [mm] $x_0$ [/mm] kommt, ist sehr einfach. Da $f$ bijektiv (oder wie völlig ausreichend ist: surjektiv) ist, folgt: für die Teilmenge $Y$ gibt es ein [mm] $x_0\in [/mm] X$ mit [mm] $f(x_0)=Y$. [/mm] Man nimmt das [mm] $x_0$ [/mm] nicht in die Hand. Da Du keine surjektive Abbildung [mm] $f:X\to [/mm] Pot(X)$ konstruieren kannst, wirst Du es auch nicht schaffen den Widerspruch anhand eines Beispieles Dir plausibel zu machen, weil die Voraussetzung für diesen Widerspruch garnicht konstruiert werden kann ...
--
Gruss
Matthias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:17 Di 14.03.2006 | | Autor: | mathiash |
Werter Matthias,
könnt es nicht klappen, wenn wir in einer konzentrierten Aktion es gemeinsam probieren,
dass wir dann doch noch'n surjektives f hinbekommen ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:13 Di 14.03.2006 | | Autor: | kretschmer |
Hallo Mathiash,
da ich des Konjunktivs nicht mächtig bin, fühltest Du Dich wohl verpflichtet obige Mitteilung zu verfassen.
Hallo insgesamt,
das brachte mich aber mal dazu, mir zu überlegen, ob es nicht Spezialfälle gibt, die eine solche surjektive Antwort haben, also ob der Beweis irgendeine versteckte Annahme macht, die nicht in jedem Fall gilt. Dies ist aber nicht der Fall und ich hoffe alle, die sich fragen, nachdem sie die Mitteilung von Mathiash gelesen haben, ob es solche gibt, haben nun eine passende Antwort.
--
Gruß
Matthias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:57 Do 22.11.2007 | | Autor: | mg07 |
Die Abbildung f: X -> Pot(X) ist surjektiv und bildet damit jede Teilmenge von X ab. Also wird gefordert, dass es genügend x X gibt, so dass f(X) = Pot(X) gilt. Das ist ja nicht so, allein die Menge aller einelementigen Teilmengen von X in Pot(X) umfasst so viele Elemente wie in X vorhanden sind.
Man konstruiert sich ein Y, dessen Elemente x [mm] \in [/mm] X über f Teilmengen f(x) abbilden, in denen sie nicht enthalten sind. Damit enthält Y auch die x [mm] \in [/mm] X, welche es nicht gibt, aber geben muss.
Also beinhaltet Y egal welches f man wählt, diese notwendigen, aber nicht existenten x [mm] \in [/mm] X. Sie existieren nicht, also sind sie auch in keiner Teilmenge aus Pot(X). Darüberhinaus kann es je nach Def. von f auch existierende x [mm] \in [/mm] X in Y geben (X = {1} und f(1) = {}, damit z.B. 1).
Da Y aus Elementen aus X besteht, bildet Y eine Teilmenge von X und muss über ein [mm] x_0 [/mm] mit [mm] f(x_0)=Y [/mm] abgebildet werden können. Wäre [mm] x_0 \in [/mm] Y, so müsste es wegen [mm] x_0 \not\in [/mm] Y doch nicht drinliegen Gelte [mm] x_0 \not\in [/mm] Y, so würde [mm] x_0 [/mm] die Bedingung von Y mit [mm] x_0 \not\in f(x_0)=Y [/mm] erfüllen und wäre damit doch drin.
Nachvollziehen kann ich die Schritte schon, aber wieso kann man sagen, dass dadurch keine surjektive Abbildung f: X -> Pot(X) existiert?
|
|
|
| |
|
Hallo,
man hat eine Menge X gegeben.
Die Frage ist, ob es eine surjektive Abbildung f v. X auf die Potenzmenge von X, [mm] \mathcal{P}(X) [/mm] geben kann.
Das ist nicht der Fall, und den Beweis führt man per Widerspruch.
Angenommen, es gäbe eine surjektive Abbildung
f: X [mm] \to \mathcal{P}(X).
[/mm]
Nun definiert man ein Element Y von [mm] \mathcal{P}(X), [/mm] also eineTeilmenge v. X, wie folgt
> [mm]Y=\{x\in X\: |\: x\not\in f(x)\}[/mm]
>
> Die Menge Y besteht aus mindestens den x [mm]\in[/mm] X, die nicht
> exisiteren,
???
Die Menge [mm] Y\subseteq [/mm] X besteht aus allen Elementen v. X, die nicht in (der Menge (!)) f(x) liegen.
> aber für die notwendige Bedingung einer
> surjektiven Abbildung vorhanden sein müssen.
???
Da die Abbildung f nach Voraussetzung surjektiv ist, gibt es ein Element [mm] x_0\in [/mm] X, so, daß [mm] f(x_0)=Y [/mm] gilt.
(Denn Y ist ja in [mm] \mathcal{P}(X).)
[/mm]
> Für diese x
> [mm]\in[/mm] X gilt egal welches f man wählt
Wir haben hier kein f zu wählen.
Unser f ist die als surjektiv angenommene Funktion unserer Voraussetzung.
> >Fall 1: [mm]x_0\in[/mm] Y, dann gilt also nach Def. von Y
[mm] x_0\not\in f(x_0)=Y. [/mm] Widerspruch! [mm] x_0 [/mm] kann nicht gleichzeitig drin sein in Y und nicht drin.
> [mm]x_0[/mm] darf kann nicht in Y liegen, weil in Y alle x [mm]\in[/mm] liegen,
> für die gilt: x [mm]\not\in[/mm] f(x)
>
> >Fall 2: [mm]x_0\not\in[/mm] Y, dann gilt nach Def. von Y aber
> [mm]x_0\in[/mm] Y, >Widerspruch.
>
> würde [mm]x_0[/mm] nicht in Y liegen, so gelte [mm]x_0 \not\in f(x_0)=Y,[/mm]
> womit es drinläge
> Mir fehlt einfach der Zusammenhang. Wie kommt man auf so
> eine Idee, wieso hat man dann gezeigt, dass es keine solche
> surjektive Abb. f gibt.
Die Annahme, daß es solch eine Abbildung gibt, führt zu einem Widerspruch.
Also gibt es keine solche Abbildung.
> Wie kommt man auf so
> eine Idee,
Erfahrung, Wissen, Intuition, Inspiration - und viele Fehlversuche...
(In diesem speziellen Fall allerdings muß man sich den Beweis nicht selbst ausdenken, das ist Standard, Literatur, das kennt "man".)
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:28 Do 22.11.2007 | | Autor: | mg07 |
> Die Menge $ [mm] Y\subseteq [/mm] $ X besteht aus allen Elementen v. X, die nicht in (der Menge (!)) f(x) liegen.
Ich führe mal ein Beispiel auf, um mir sichergehen zu können, dass ich Y auch richtig konstruiere.
Sei X = {1,2}, dann gilt Pot(X) = {{},{1},{2},{1,2}}
Für f gelte:
f(1) = {1}
f(2) = {}.
Es fehlen noch die "nicht existierenden" x3,x4 [mm] \in [/mm] X mit sagen wir
f(x3) = {2}
f(x4) = {1,2}
Soweit würde dann wegen $ [mm] Y=\{x\in X\: |\: x\not\in f(x)\} [/mm] $ gelten:
Y = {1,x3,x4}
Nur um den Schritt jetzt klarzuhaben, was man genau in Y packt.
|
|
|
| |
|
> > Die Menge [mm]Y\subseteq[/mm] X besteht aus allen Elementen v. X,
> die nicht in (der Menge (!)) f(x) liegen.
>
> Ich führe mal ein Beispiel auf, um mir sichergehen zu
> können, dass ich Y auch richtig konstruiere.
>
> Sei X = {1,2}, dann gilt Pot(X) = {{},{1},{2},{1,2}}
>
> Für f gelte:
> f(1) = {1}
> f(2) = {}.
>
> Es fehlen noch die "nicht existierenden" x3,x4 [mm]\in[/mm] X mit
> sagen wir
> f(x3) = {2}
> f(x4) = {1,2}
>
> Soweit würde dann wegen [mm]Y=\{x\in X\: |\: x\not\in f(x)\}[/mm]
> gelten:
> Y = {1,x3,x4}
>
> Nur um den Schritt jetzt klarzuhaben, was man genau in Y
> packt.
Hallo,
ich weigere mich, für nicht existente Elemente irgendwelche Funktionswerte zu definieren.
Dein Beispiel ist auch aus folgendem Grund uninteressant: für endliche Mengen X ist das Ganze doch kein Thema, bzw. eines, welches einen zum Einschlafen bringt.
Wenn X n Elemente enthält, wissen wir, daß die Potenzmenge [mm] 2^n [/mm] Elemente hat, und daher kann es sowieso keine Bijektion geben.
Der interessante Fall bezieht sich auf Mengen, die nicht endlich sind, nur dafür brauchen wir die Konstruktion der Menge Y.
Gruß v. Angela
|
|
|
|
