Es sei A eine nichtleere Menge. Bestimmen der Mächtigkeit ihrer Potenzmenge P(A):

Question

die Aufgabe lautet: Es sei A eine nicht leere endliche Menge (Meine Erkenntnis: also gibt es mindestens ein x in der Menge A). Bestimmen Sie die Mächtigkeit ihrer Potenzmenge (A).

Ansatz: Die Mächtigkeit (Also die Anzahl der Elemente in der Menge A) der Potenzmenge lässt sich folgendermaßen berechnen: |P(A)| = 2^|A|.

Woher soll ich nun die Mächtigkeit bestimmen, wenn ich nur weis, dass A eine nichtleere endliche Menge ist, also es endliche n in A gibt und das leere Element ({} oder 0) nicht Element der Menge A ist?

Florian T. S.

Answer 1

|P(A)| = 2^|A| ist das richtige Ergebnis. Mehr ist nicht gefragt. Ein Beweis wäre vielleicht nicht schlecht.

Comments

Könntest du mir eventuell bitte den Beweis zeigen oswald? Das würde mich sehr interessieren.

---

Per vollständiger Induktion.

IA: {1} hat als Teilmengen {} und {1}

IS: {1, ... , n+1} hat die gleichen Teilmengen wie {1, ... , n} und noch ein paar zusätzliche. Die zusätzlichen kommen zustande indem zu jeder Teilmenge von {1, ... , n} das Element n+1 hinzugefügt wird.

---

Ok das habe ich verstanden :-) Mit der V. Induktion habe ich mich schon vor dem Studium auseinandergesetzt :-)
Danke oswald!

---

Hey oswald,

wir sollen die Aufgabe doch per Induktion zeigen. Kann ich das genauso notieren wie du
vorgegangen bist? Die Aufgabe ist etwas wackelig, damit meine ich, dass man das
dadurch ja nicht vollständig "beweist".

Gruß :-)

---

Ob die Formulierung meines Beweises reicht, kommt auf das Publikum an, an das der Beweis gerichtet ist.

Meine Formulierung war an Leute gerichtet, die kürzlich angefangen haben, Mathematik zu studieren, und noch lernen müssen, die Ideen des Beweises mathematisch zu präzisieren.

Deine Formulierung sollte an Leute gerichtet sein, die du davon überzeugen musst, dass du sowohl Induktionsbeweise verstanden hast, als auch elementare Rechentechniken kennst. Natürlich muss deine Formulierung dann etwas ausführlicher sein, als meine.

---

Danke für die Rückantwort :-)
Alles klar, ich würde dann meinen Beweis nochmal kommentieren,
könntest du eventuell dann noch einmal bitte drüber schauen? Wäre echt super!
Gruß

---

Mach ich.       

---

Ich habe mal folgendes notiert:

Sei X ⊆ A und es existieren endlich viele n in der Menge X, da auch A eine endliche Menge besitzt.
Zudem ist A eine nichtleere Menge, woraus folgt, dass X ebenfalls eine nichtleere Menge ist, da
X ⊆ A gilt. Sei nun A(1) eine wahre Aussage, dann folgt, dass auch X(1) eine wahre Aussage ist,
da X ⊆ A. Annahme: A(n+1) ist wahr. Wenn n+1 ∈ von A ist, dann muss auch n+1 ∈ von X sein, da
X ⊆ A gilt.

Glaube aber, dass ich das dadurch nicht bewiesen habe :-/

---

"Sei X ⊆ A" ist kein guter Anfang. Dadurch wählst du eine Teilmenge von A aus, die dann für den Rest des Beweise festgelegt ist (auch wenn du nicht gesagt hast, wie sie genau ausgewählt ist).

Aus A≠∅ folgt keinesfalls X≠∅. Vielmehr gilt ∅⊆A für jede beliebige Menge A. Dehalb ist insbesondere X=∅ auch dann möglich, wenn A≠∅ ist.

Induktionsanfang: Sei n=1 und A eine Menge mit |A|=n. Dann ist P(A) = {∅, A}, also |P(A)| = 2 = 2¹.

Induktionsschluss: Sei n∈ℕ und es gelte |P(A)|=2ⁿ für alle Mengen A mit |A|=n.

Sei B eine Menge mit |B|=n+1. Ferner sei b∈B, P₀={S∈P(B) | b∉S} und P_b ={S∈P(B) | b∈S}. Dadurch ist P(B) = P₀ ⊍ P_b (insb. P₀∩P_b=∅, also |P(B)| = |P₀|+|P_b|).

Es gilt dann P₀=P(B\{b}), also |P₀|=|P(B\{b})|=2ⁿ, da |B\{b}| = n ist.

Außerdem gilt P_b={S⊍{b} | S∈P₀}, also |P_b|=|P₀|=2ⁿ.

Damit ist |P(B)| = |P₀| + |P_b| = 2ⁿ+2ⁿ=2·2ⁿ=2ⁿ⁺¹.

---

Woran kann man erkennen, dass die leere Menge ein Teil einer Menge ist?
Angenommen A sei eine nichtleere Menge, und X sei Teilmenge von A,
dann verstehe ich (zumindest jetzt), dass in X trotzdem die leere Menge
enthalten kann, aber nicht in A enthalten sein muss.

Beispiel: A={1,2,3,{∅, 1}, 4}. Sei X = {∅, 1}, dann ist X ja eine Menge
innerhalb einer Menge. Mich verwirrt, dass dann ∅ nicht auch in A ist,
da ∅ ja in X enthalten ist und ein Teil von A ist.

Ansonsten habe ich alles, bis auf den Schritt P₀={S∈P(B) | b∉S} verstanden.
Mir ist nur unklar, warum b nicht Element von S ist und woher die Menge
S nun stammt.

Vielen Dank oswald für deine Hilfe :-)

---

> Woran kann man erkennen, dass die leere Menge ein Teil einer Menge ist?

Es ist unklar, was mit "Teil einer Menge". Es gbt zwei fundamentale Beziehungen bei Mengen, die Element-Beziehung ∈ und die Teilmengenbeziehung ⊆.

Die Element-Beziehung ist nun mal so definiert, dass zwar {∅, 1}∈{1,2,3,{∅, 1}, 4} und ∅∈{∅, 1} ist, aber nicht ∅∈{1,2,3,{∅, 1}, 4}. Die Element-Beziehung ist nicht transitiv.

Die Teilmengen-Beziehung ist nun mal so definiert, dass U⊆M :⇔ ∀u (u∈U⇒u∈M). Der Allquantor postuliert dabei nicht die Existenz eines u, sondern gibt nur an, wie sich die u verhalten müssen falls sie existieren.

P₀={S∈P(B) | b∉S} ist die Menge aller Teilmengen von B, in denen b nicht vorkommt.

Answer 2

Man kann von einer endlichen unbekannten Menge, deren Mächtigkeit man nicht kennt, die Mächtigkeit der Potenzmenge nicht zahlenmäßig bestimmen.

|P(A)| = 2^|A| , weiter geht es nicht.

Edit: Man könnte höchstens (vgl. Oswald in A1) diese bekannte Formel mit vollständiger Induktion beweisen. Aber dann wäre der Aufgabentext sehr unklar gestellt.

Comments

Danke Wolfgang! Jetzt hat sich meine Verwirrung aufgelöst :-)