Mengenlehre und Logik

Neue Frage »

14.04.2011, 18:06	lukas123456789	Auf diesen Beitrag antworten »
Mengenlehre und Logik Meine Frage: Ich habe keine Ahnung wie man das folgende zeigt: Sei x eine endliche Menge mit genau n Elementen. Zeigen Sie, dass P(x) genau 2^n Elemente besitzt. Meine Ideen: Bisher habe ich noch keine Idee!
14.04.2011, 18:12	Iorek	Auf diesen Beitrag antworten »
Hattet ihr schon die Aussage, dass für eine endliche Menge $\begin{eqnarray} M \end{eqnarray}$ die Anzahl der k-elementigen Teilmengen von $\begin{eqnarray} M \end{eqnarray}$ gerade $\begin{eqnarray} \binom{n}{k} \end{eqnarray}$ ist? Dann lässt sich das leicht mit dem binomischen Lehrsatz zeigen.
14.04.2011, 18:18	lukas123456789	Auf diesen Beitrag antworten »
Nein, das hatten wir noch nicht. Gibt es noch eine andere Möglichkeit?
14.04.2011, 18:24	Iorek	Auf diesen Beitrag antworten »
Dann wirst du wohl den Weg über die Induktion gehen müssen (oder du zeigst die benötigte Aussage, dass $\begin{eqnarray} \binom{n}{k} \end{eqnarray}$ der Anzahl der k-elementigen Teilmengen entspricht, wobei hier eine sehr ähnliche Induktion nötig ist).
15.04.2011, 12:37	lukas123456789	Auf diesen Beitrag antworten »
Aber wir hatten folgenden Satz. Vielleicht hilft er weiter. Satz (Cantor9: Sei A eine nicht-leere Menge und sei P(A) eine Potenzmenge von A. D.h. P(A) ist die Menge aller Teilmengen von A. Dann gibt es keine Surjektion A-->P(A).
15.04.2011, 12:53	Huggy	Auf diesen Beitrag antworten »
Der Satz hilft nicht weiter. Aber der Beweis der Formel ist doch recht einfach. Jede Teilmenge der Menge lässt sich charakterisieren, indem man für jedes Element $\begin{eqnarray} a_i, \quad i = 1, ..., n \end{eqnarray}$ angibt, ob das Element in der Teilmenge ist oder nicht. Man kann also jede Teilmenge durch eine Folge von n Nullen und Einsen charakterisieren. Da es an jeder Position dieser Folge genau 2 Möglichkeiten für den Eintrag gibt, ergeben sich insgesamt $\begin{eqnarray} 2^n \end{eqnarray}$ mögliche Folgen und damit Teilmengen.
Anzeige

15.04.2011, 13:31	Mystic	Auf diesen Beitrag antworten »
Oder so: Sei $\begin{eqnarray} A_n \end{eqnarray}$ die Anzahl der Teilmengen einer n-elementigen Menge mit $\begin{eqnarray} n \in \mathbb N \end{eqnarray}$ ... Dann gilt offenbar $\begin{eqnarray} A_0 =1, \quad A_n=2A_{n-1} (n>0) \end{eqnarray}$ Auf die Rekursionsbeziehung kommt man so, dass man für einer festes Element x der n-elementigen Menge zuerst alle Teilmengen bildet, die x enthalten und anschließend alle Teilmengen, welche x nicht enthalten... Naja, und für die so rekursiv definierte Folge sollte leicht eine explizite Formel zu finden sein...
17.04.2011, 10:56	lukas123456789	Auf diesen Beitrag antworten »
Könnt ihr mir nicht zeigen, wie man so einen Beweis führt. Ich habe dieses Fach dieses Semester zum ersten Mal und keine Ahnung!!!
17.04.2011, 11:06	kiste	Auf diesen Beitrag antworten »
Du solltest mehr darauf achten was dir geschrieben wird. Du hast schon einen Beweis bekommen und einen anderen Beweisansatz der nur noch eine kleine Lücke zu füllen braucht.
17.04.2011, 12:04	lukas123456789	Auf diesen Beitrag antworten »
Ich weiß, dass das bestimmt mega einfach ist. Aber ich weiß zum Beispiel noch nicht einmal, wie man die Menge der Teilmengen bildet, die x nicht enthält, also wie man das mathematisch aufschreibt. Also das x in der Menge der Teilmenge enthaten ist, würde ich so aufschreiben: $\begin{eqnarray} x\in A_{n} \end{eqnarray}$
17.04.2011, 13:06	lgrizu	Auf diesen Beitrag antworten »
Das einfachtse ist Beweis per Induktion, mach doch einmal den Induktionsanfang. Wenn du die Boardsuche benutzt solltest du auch fündig werden, diese Aufgabe wurde hier soweit ich mich erinnern kann mehr als einmal vollständig besprochen. Hier zum Beispiel: noch eine ivollständige Induktion

Neue Frage »

Antworten »

Mengenlehre und Logik

Verwandte Themen