Mächtigkeit von Potenzmengen Beweis

[Dominic Maier]

Hallo,

ich habe im Netz einen Beweis gefunden, dass eine Menge A zu ihrer
Potenzmenge P(A) nie gleichmächtig ist.

Der Beweis ging so (durch Widerspruch):

Man nehme an, dass es eine bijektive Abbildung gibt:

f: A --> P(A)

dann betrachte man die Menge:

M := {x aus A| x nicht Element von f(x)} die ein Element von P(A) ist

zitat von jener Website:>>>

Da f als bijektiv vorausgesetzt ist, muss es ein x in A geben mit f(x) =
M. Läge nun x in M, dann wäre nach Definition von M x nicht in f(x) = M.
Läge x dagegen nicht in M, dann wäre x in f(x) = M, wieder nach der
Definition von M. Damit haben wir einen Widerspruch erhalten, der zeigt,
dass die angenommene Bijektion f nicht existieren kann.
<<<<

Wie man dann den Widerspruch herleitet (zitat oben) ist klar, aber ich
verstehe ganz und gar nicht, wieso man M überhaupt so annehmen darf.

Es muss doch irgendwie aus der Annahme einer bijektiven Abbildung
folgen, dass M so existieren müsste...ich sehe aber beim besten Willen
nicht warum...
Vielleicht kann mir das jemand erklären.

Denn die Konstruktion von M scheint mir die Kernidee des Beweises zu
sein, und wenn man die schon nicht versteht ...*g*


mfg

Dominic

[Thomas Winterfeldt]

Post by Dominic Maier
Wie man dann den Widerspruch herleitet (zitat oben) ist klar, aber ich
verstehe ganz und gar nicht, wieso man M überhaupt so annehmen darf.

M als Teilmenge von A ist eindeutig definiert, wenn man von jedem x aus A
sagen kann, ob es in M liegt oder nicht. Wählen wir ein beliebiges x. f
bestimmt für x eindeutig eine TM von A. Diese kann x enthalten oder nicht,
so dass x eindeutig entweder in M liegt oder nicht. Somit ließe sich (wenn
eben ein solches f existierte) eindeutig sagen, ob ein x in M liegt oder
nicht. M ist vielleicht nur deshalb so schwer vorstellbar, weil seine
Konstruktion auf der Existenz von f aufbaut, wobei diese aber gerade
widerlegt wird. (liegt in der Natur des indirekten Beweises...)

Post by Dominic Maier
Es muss doch irgendwie aus der Annahme einer bijektiven Abbildung
folgen, dass M so existieren müsste...ich sehe aber beim besten Willen
nicht warum...
Vielleicht kann mir das jemand erklären.

Ich hoffe, ich konnte.
Thomas

[Jens Makait]

...M ist vielleicht nur deshalb so schwer vorstellbar, weil seine
Konstruktion auf der Existenz von f aufbaut, wobei diese aber gerade
widerlegt wird. (liegt in der Natur des indirekten Beweises...)

Man fühlt sich vielleicht auch ahnungsvoll erinnert an Dinge wie
'Die Menge aller Mengen, die sich nicht selbst enthalten'

Aber mit sowas hat dies hier wohl nichts zu tun.
Habe ich mein f, dann kann ich in der Tat sehr fix
nachprüfen, ob ein x in f(x) liegt
und damit ist M (oder besser M(f)) eindeutig
definiert.

Jens

[Horst Kraemer]

On Sun, 30 Nov 2003 15:21:45 +0100, Dominic Maier

Post by Dominic Maier
ich habe im Netz einen Beweis gefunden, dass eine Menge A zu ihrer
Potenzmenge P(A) nie gleichmächtig ist.
f: A --> P(A)
M := {x aus A| x nicht Element von f(x)} die ein Element von P(A) ist

zitat von jener Website:>>>

Da f als bijektiv vorausgesetzt ist, muss es ein x in A geben mit f(x) =
M. Läge nun x in M, dann wäre nach Definition von M x nicht in f(x) = M.
Läge x dagegen nicht in M, dann wäre x in f(x) = M, wieder nach der
Definition von M. Damit haben wir einen Widerspruch erhalten, der zeigt,
dass die angenommene Bijektion f nicht existieren kann.
<<<<
Wie man dann den Widerspruch herleitet (zitat oben) ist klar, aber ich
verstehe ganz und gar nicht, wieso man M überhaupt so annehmen darf.
Es muss doch irgendwie aus der Annahme einer bijektiven Abbildung
folgen, dass M so existieren müsste...ich sehe aber beim besten Willen
nicht warum...
Vielleicht kann mir das jemand erklären.

Sei A nicht leer.

Wenn f eine beliebige Abbildung A->P(A) ist, wird jedem a aus A eine
bestimmte Teilmenge von A zugeordnet. Fuer jedes a gilt dann

entweder a el. f(a) oder a nicht el. f(a)

Damit ist die Menge Mf:={a|a nicht el. f(a)} wohldefiniert, d.h. sie
*existiert* zunaechst einmal - egal wie f aussieht. Man koennte sagen,
sie ist eine "Funktion von f".

Jetzt nehmen wir einfach einmal an, dieses wohldefinierte Mf kaeme
einmal als Bild eines Elements aus A vor (dies koennen wir nur
annehmen wenn A nicht leer ist). Dann gibt es also ein af aus A mit
f(af) = Mf. Wenn es ein derartiges af gibt, muss wiederum entweder
gelten

entweder af el. Mf oder af nicht el. Mf

Da nun aus jeder der beiden Annahmen aufgrund der Definition von Mf
jeweils das Gegenteil folgt, folgt, dass weder af el. Mf noch af nicht
el. Mf. Es kann also kein af mit f(af)=Mf geben. Damit ist gezeigt,
dass in irgendeiner Abbildung f A->P(A) niemals die wohldefinierte
Menge Mf als Bild irgendeines a aus A vorkommen kann. Damit kann eine
Abbildung P->A(P) also niemals *surjektiv* sein. Sie kann erst recht
nie bijektiv sein, da sie dann ja surjektiv sein muesste. q.e.d.

MfG
Horst

[Jutta Gut]

Post by Horst Kraemer
On Sun, 30 Nov 2003 15:21:45 +0100, Dominic Maier

Post by Dominic Maier
ich habe im Netz einen Beweis gefunden, dass eine Menge A zu ihrer
Potenzmenge P(A) nie gleichmächtig ist.
f: A --> P(A)
M := {x aus A| x nicht Element von f(x)} die ein Element von P(A) ist

zitat von jener Website:>>>

Da f als bijektiv vorausgesetzt ist, muss es ein x in A geben mit f(x) =
M. Läge nun x in M, dann wäre nach Definition von M x nicht in f(x) = M.
Läge x dagegen nicht in M, dann wäre x in f(x) = M, wieder nach der
Definition von M. Damit haben wir einen Widerspruch erhalten, der zeigt,
dass die angenommene Bijektion f nicht existieren kann.
<<<<
Wie man dann den Widerspruch herleitet (zitat oben) ist klar, aber ich
verstehe ganz und gar nicht, wieso man M überhaupt so annehmen darf.
Es muss doch irgendwie aus der Annahme einer bijektiven Abbildung
folgen, dass M so existieren müsste...ich sehe aber beim besten Willen
nicht warum...
Vielleicht kann mir das jemand erklären.

Sei A nicht leer.
Wenn f eine beliebige Abbildung A->P(A) ist, wird jedem a aus A eine
bestimmte Teilmenge von A zugeordnet. Fuer jedes a gilt dann
entweder a el. f(a) oder a nicht el. f(a)
Damit ist die Menge Mf:={a|a nicht el. f(a)} wohldefiniert, d.h. sie
*existiert* zunaechst einmal - egal wie f aussieht. Man koennte sagen,
sie ist eine "Funktion von f".

Ergänzung: Es könnte natürlich sein, dass Mf die leere Menge ist. Das ändert
aber nichts am Beweisgedanken, weil ja auch die leere Menge ein Element der
Potenzmenge ist.

Gruß
Jutta

[Horst Kraemer]

On Tue, 2 Dec 2003 08:55:27 +0100, "Jutta Gut"

Post by Jutta Gut

Post by Horst Kraemer
On Sun, 30 Nov 2003 15:21:45 +0100, Dominic Maier

Post by Dominic Maier
ich habe im Netz einen Beweis gefunden, dass eine Menge A zu ihrer
Potenzmenge P(A) nie gleichmächtig ist.
f: A --> P(A)
M := {x aus A| x nicht Element von f(x)} die ein Element von P(A) ist

zitat von jener Website:>>>

Da f als bijektiv vorausgesetzt ist, muss es ein x in A geben mit f(x) =
M. Läge nun x in M, dann wäre nach Definition von M x nicht in f(x) = M.
Läge x dagegen nicht in M, dann wäre x in f(x) = M, wieder nach der
Definition von M. Damit haben wir einen Widerspruch erhalten, der zeigt,
dass die angenommene Bijektion f nicht existieren kann.
<<<<
Wie man dann den Widerspruch herleitet (zitat oben) ist klar, aber ich
verstehe ganz und gar nicht, wieso man M überhaupt so annehmen darf.
Es muss doch irgendwie aus der Annahme einer bijektiven Abbildung
folgen, dass M so existieren müsste...ich sehe aber beim besten Willen
nicht warum...
Vielleicht kann mir das jemand erklären.

Sei A nicht leer.
Wenn f eine beliebige Abbildung A->P(A) ist, wird jedem a aus A eine
bestimmte Teilmenge von A zugeordnet. Fuer jedes a gilt dann
entweder a el. f(a) oder a nicht el. f(a)
Damit ist die Menge Mf:={a|a nicht el. f(a)} wohldefiniert, d.h. sie
*existiert* zunaechst einmal - egal wie f aussieht. Man koennte sagen,
sie ist eine "Funktion von f".

Ergänzung: Es könnte natürlich sein, dass Mf die leere Menge ist. Das ändert
aber nichts am Beweisgedanken, weil ja auch die leere Menge ein Element der
Potenzmenge ist.

Ja. Mf={} impliziert bereits direkt: es gibt kein a mit f(a)={},

MfG
Horst

[Marc Olschok]

Post by Dominic Maier
Hallo,
ich habe im Netz einen Beweis gefunden, dass eine Menge A zu ihrer
Potenzmenge P(A) nie gleichmaechtig ist.
f: A --> P(A)
M := {x aus A| x nicht Element von f(x)} die ein Element von P(A) ist

zitat von jener Website:>>>

Da f als bijektiv vorausgesetzt ist, muss es ein x in A geben mit f(x) =
M. Laege nun x in M, dann waere nach Definition von M x nicht in f(x) = M.
Laege x dagegen nicht in M, dann waere x in f(x) = M, wieder nach der
Definition von M. Damit haben wir einen Widerspruch erhalten, der zeigt,
dass die angenommene Bijektion f nicht existieren kann.
<<<<
Wie man dann den Widerspruch herleitet (zitat oben) ist klar, aber ich
verstehe ganz und gar nicht, wieso man M ueberhaupt so annehmen darf.

Diese Menge M erhaelt man als Teilmenge von A durch Aussonderung
durch die Eigenschaft "x nicht Element von f(x)".

Post by Dominic Maier
Es muss doch irgendwie aus der Annahme einer bijektiven Abbildung
folgen, dass M so existieren muesste...ich sehe aber beim besten Willen
nicht warum...

Wie gesagt, die Menge M gibt es immer.
Die Annahme "f ist surjektiv" wird dort wirksam, wo man folgert,
dass M im Bild von f liegt.

Im wesentlichen wird folgende Aussage bewiesen:

Ist f: A ---> P(A) eine Abbildung, dann liegt
M_f := { x in A | x nicht Element von f(x) }
nicht im Bild von f.
Insbesondere gibt es keine surjektive Abbildung von A nach P(A).

Marc