0 Daumen
1,5k Aufrufe

Ich hab eine Aufgabe in der steht.

Sei #P(X) := n, wobei X echte  Teilmenge  von Y ist und sei y_0 = Y\X

Dann soll man beweisen


# P(X u {y_0}) =2*n

Kann mir das mal jemand erklären warum 2*n und nicht normal 2 hoch n?

EDIT: Vollständige und korrekte Originalversion im Bild bei " (Duplikat) ".

Avatar von

Vom Duplikat:

Titel: Potenzmengenbeweis Mengen

Stichworte: mengenlehre

Kann mir jemand den Beweis zeigen danke voraus74589B91-0104-4E62-A2FD-67E8F635E85F.png

Sei #P(X) := n

Das ergibt streng genommen keinen Sinn.

Das Zeichen := bedeutet "wird definiert als". Dabei steht der Doppelpunkt auf der Seite die durch die andere festgelegt wird.

#P(X) ist aber eine durch X eindeutig festgelegte Zahl (nämlich die Mächtigkeit der Potenzmenge von X). Da gibt es nichts, was noch definiert werden müsste.

Das ergibt streng genommen keinen Sinn.

Streng genommen ist deine interpunktion unzureichend.

Im abgebildeten Original steht nicht #P(X) := n sondern #P(X) =: n.

Dort steht n:=#P(Y) und der Frager hat etliche Details der Aufgabe nicht richtig wiedergegeben.

2 Antworten

0 Daumen

Die Konstruktion in der Ausgabe ist so gemeint: Eine Menge X mit n Elementen wird um ein zusätzliches Element vergrößert, hat also nun (n+1) Elemente. Wieviele Elemente hat nun die Potenzmenge der vergrößerten Menge?

Avatar von 26 k

Meintest du nicht:

Die Konstruktion in der Ausgabe ist so gemeint: Eine Menge X mitElementen wird um ein zusätzliches Element vergrößert, hat also nun (k+1) Elemente. Wieviele Elemente hat nun die Potenzmenge der vergrößerten Menge?

Da habe ich mich leider völlig falsch ausgedrückt, ich versuche es noch mal:

Eine Menge X mit n Teilmengen wird um ein zusätzliches Element y_0 zu einer Menge X∪{y0} ergänzt. Beweise: #P(X∪{y_0})=2n.

Natürlich muss n eine Zweierpotenz sein, also n=2^k gelten. Und das wäre dann auch der Einstieg in den Beweis.

Müsste man dann beim Induktionschritt dies zeigen? Man setzt dann für n= 2 hoch k  ein

#P(x u {y_0})=2*(2 hoch k)

Der Induktionsanfang steht untenn

Es ist doch so:

(1) Es ist #P(X)=:n∈ℕ gegeben.

Daraus folgt

(2) X ist eine endliche Menge.

Sei nun #(X)=:k∈ℕ. Dann folgt

(3) #P(X)=n=2^k und

(4) #(X∪{y_0})=k+1 (wegen y_0∉X) und

(5) #P(X∪{y_0})=2^{k+1}=2*2^k=2*n   q.e.d.

Es ist sicher denkbar, daraus einen Induktionsbeweis zu machen, aber klarer geht es eigentlich kaum.

0 Daumen

# P(X u {y_0}) =2*n

Kann mir das mal jemand erklären warum 2*n und nicht normal 2 hoch n?

n selbst scheint irgendeine passende natürliche Zahl zu sein und nicht, wie du annimmst, die Mächtigkeit der Menge X.

D.h. n könnte durchaus 2^k sein und |X| = k.

Nur interessiert das in der aktuellen Rechnung gerade nicht.

# P(X u {y_0}) =2*n

bedeutet, dass die Potenzmenge von X u {y_0} doppelt so viele Mengen enthält wie die Potenzmenge der Menge X. Begründung: Jede Teilmenge von X ist auch Teilmenge von X u {y_0} . Ausserdem kann man jeder Teilmenge von X noch das Element y_0 hinzufügen und man hat wieder eine Teilmenge von X u {y_0}.

Avatar von 162 k 🚀

n ist die Mächtigkeit der Menge X, denn das steht ausdrücklich in der Aufgabe.

@Az0815: Nochmals lesen :)

#P(X) := n,

n ist die Mächtigkeit der Potenzmenge von X.

Du hast recht, aber das war mir eigentlich auch klar! :-)

Jedenfalls ist n nicht "irgendeine passende natürliche Zahl", sondern eben #P(X) und damit natürlich selbst eine 2er Potenz und #P(X∪{y_0})=2*n dann auch.

Mom ich versteh das jetzt nicht

Wie kann das denn Das doppelte sein

In der Aufgabe steht nur das y eine teilmenge ist es kann ja auch nur die leere menge enthalten??

Wenn X eine echte Teilmenge von Y ist, dann kann Y nicht leer sein.

X u {y_0}.

ist die Menge X vereinigt mit der einelementigen Menge, die nur y_0 enthält.

Offenbar ist y_0 nicht in X enthalten.

 sei y_0 = Y\X

Ok wenn man das jetzt beweisen würde mit vollständige Induktion

IA: n=1

#P(x u{y_0} ) =2 =2n weil die Potenzemenge von x nur die leere menge, also ein Element  und von {y_0} wären 2 Element  die leere menge und sich selbst oder??

Wie würde man den indukttionschritt denn machen ?

Du hast das immer noch nicht verstanden, da ist nix mit Induktion. Zu zeigen ist einfach nur $$\#P(X\cup\{y_0\})=2\cdot\#P(X).$$ In der Formulierung der Aufgabe wird \(n\) nur als Abkuerzung für \(\#P(X)\) verwendet.

Ich bin jetzt völlig verwirrt ich dachte ich muss für n= 2hoch k einsetzen

Lies einfach nochmals meine Antwort und kümmere dich nicht um die darauf folgende Diskussion in den Kommentaren.

Du musst (und darfst) für \(n\) ueberhaupt nichts "setzen". Das ist eine Abkuerzung für \(\#P(X)\). Entsprechend steht da (richtig rum geschrieben!) auch \(n:=\#P(X)\). In Worten: \(n\) ist definiert als die Anzahl der Teilmengen von \(X\).

Wenn man die Abkuerzung eliminiert, wird die Sache voellig \(n\)-frei: $$\#P(X\cup\{y_0\})=2\cdot\#P(X)$$ Fang an, das zu zeigen und vergiss \(n\).

Zwar verstehe ich wenn jede Teilmenge von X automatisch  auch Teilmenge von X u {y0} ist. und auch wenn man jeder Teilmenge von X ein y0 hinzufügt  ergibt zwar das Doppelte das hab ich verstanden 

#P(X ∪ {y0})= #P({y∈Y I y1, y2 ,..,yn∈ X  v  y0 ∈ Y}

= #P({y ∈ Y I y1,y2,..,yn ∈ X}) U #P({y∈ Y I y∈ Y)

=  #P({y ∈ Y I y0,y1,y2,..,yn ∈ X}) U #P({y ∈ Y Iy0, y1,y2,..,yn ∈ X})  ( die zweite Potenzmenge ist von Y, ich wollte die Teilmenge X  so rausziehen )

= 2*#P(X)

ich glaub das ist nicht richtig aber ich weiß jetzt auch nicht genau wie man auf  2 #P(X)   

Ich wiederhole:

Begründung: Jede Teilmenge von X ist auch Teilmenge von X u {y_0} . Ausserdem kann man jeder Teilmenge von X noch das Element y_0 hinzufügen und man hat wieder eine Teilmenge von X u {y_0}.

n+n = 2*n

#P({x1 ∈ X  ∧ x1 ∈ X u {y0}}) ∪ ....∪ #P({ xn ∈ X ∧ xn∈ X u {y0}})

ich versteh das einfach nicht, ist egal trotzdem danke

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community