noch eine ivollständige Induktion

01.06.2010, 19:05

marco12345

Auf diesen Beitrag antworten »

noch eine ivollständige Induktion

Meine Frage:
Sei M eine beliebige Menge und m=|M| die Anzahl der Elemente von M.
Zeigen sie mit Hilfe der Folständigen Induktion :

|Potenzmenge(M)| = 2^{m}

Meine Ideen:
da hab ich null idee wie ich da überhaupt ran gehe.. da bekomme ich nicht mel nen insuktionsanfang hin.. da ich kein m auf beiden seiten habe

hui juijui induktion ist ein blödes thema :-(

01.06.2010, 19:08

lgrizu

Auf diesen Beitrag antworten »

RE: noch eine ivollständige Induktion
naja, der induktionsanfang ist doch noch simpel, setzte m=0, dann ist M die leere menge, diese hat als einzige teilmenge nur die leere menge und damit eine teilmenge, also ist die mächtigkeit der potenzmenge 1=2^0.

versuch jetzt mal ne idee zu formulieren, wie es weitergehen könnte....

als tip, nimm zu einer menge M mit m elementen ein element x hinzu, wie viele teilmengen gibt es dann von M vereinigt x?

01.06.2010, 19:10

Elvis

Auf diesen Beitrag antworten »

Induktion ist prima, das hilft immer, wenn man Zählen kann. (Graf Zahl (Sesamstrasse) lässt grüssen. Big Laugh

Big Laugh

) Tipp zum Induktionsanfang: Wenn es das Thema erlaubt, sollte man immer mit 0 anfangen. Augenzwinkern

Augenzwinkern

Wieviele Element hat die leere Menge und ihre Potenzmenge ?

01.06.2010, 19:15

marco12345

Auf diesen Beitrag antworten »

moment.... da hakt es schon.. wenn ich die mächtigkeit sehe, hab ich doch die 1 und die leere menge oder? also zwei elemente... oder zählt die leere menge bei der mächtigkeit nicht mit verwirrt

verwirrt

sorry.. das ich so aufm schlauch stehe :-)

01.06.2010, 19:28

marco12345

Auf diesen Beitrag antworten »

huiiii beim induktionsanfang ist jetzt die münze gefallen.... ne leere menge ist ja kein element.. sonst wäre sie ja nicht leer... :-)

aber den schluss bekomme ich trotzdem nicht hin... irgendwie hab ich auch null ansatz.. da ich nicht weis ob ich m+1 oder so machen muss????

01.06.2010, 19:29

lgrizu

Auf diesen Beitrag antworten »

wieso denn zwei elemente?
wir beginnen die induktion mit $\begin{eqnarray*} M= \emptyset \end{eqnarray*}$ . wie viele teilmengen hat die leere menge?

edit: okay, das hätten wir also geklärt.

nach vorraussetzung gibt es also $\begin{eqnarray*} 2^n \end{eqnarray*}$ teilmengen von einer n-elementigen menge M.
wie viele teilmengen hat die menge $\begin{eqnarray*} M'=M \cup \{x\} \end{eqnarray*}$ ?

Anzeige

01.06.2010, 19:30

marco12345

Auf diesen Beitrag antworten »

genau :-) hatte ich auch gerade gesehn... aber weiter weis ich nich

01.06.2010, 19:33

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von lgrizu
.

nach vorraussetzung gibt es also $\begin{eqnarray*} 2^n \end{eqnarray*}$ teilmengen von einer n-elementigen menge M.
wie viele teilmengen hat die menge $\begin{eqnarray*} M'=M \cup \{x\} \end{eqnarray*}$ ?

01.06.2010, 19:33

marco12345

Auf diesen Beitrag antworten »

na m elemente plus noch einem ...dem x

01.06.2010, 19:35

lgrizu

Auf diesen Beitrag antworten »

wie viele teilmengen hat die menge M', nicht wie viele elemente.......

edit: man muss noch vorraussetzen, dass $\begin{eqnarray*} x \notin M \end{eqnarray*}$ ist, ansonsten haben wir ja wieder M, dann wäre M'=M......

01.06.2010, 19:41

marco12345

Auf diesen Beitrag antworten »

2 teilmengen.... die menge M und die menge X ... aber den schritt verstehe ich nich.. warum mach ich das

01.06.2010, 19:42

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von marco12345
2 teilmengen.... die menge M und die menge X ... aber den schritt verstehe ich nich.. warum mach ich das

das ist blödsinn, M hat nach vorraussetzung doch schon 2^n teilmengen, wie kommst du auf 2??????

01.06.2010, 19:47

marco12345

Auf diesen Beitrag antworten »

ehrlich gesagt geraten....

also ich denke mal dann ist es 2^n teilmengen + die teilmenge x....

mit mengen bin ich nich so fit.. ich muss kurz schauen wie ich teilmenge definiere

01.06.2010, 19:49

lgrizu

Auf diesen Beitrag antworten »

M hat 2^n teilmengen, liegt in diesen teilmengen x?
wie viele teilmengen existieren also, die x enthalten?

01.06.2010, 19:58

marco12345

Auf diesen Beitrag antworten »

in diesen teilmengen von M ist kein x...
..verstehe gerad nichts wirklich

01.06.2010, 20:00

lgrizu

Auf diesen Beitrag antworten »

genau, in all den teilmengen von M ist kein x und es gibt 2^n davon.
sind die teilmengen von M auch teilmengen von M'?

01.06.2010, 20:05

marco12345

Auf diesen Beitrag antworten »

mir flattert gerad dermaßen die rübe......

aber ich glaube ja

01.06.2010, 20:07

lgrizu

Auf diesen Beitrag antworten »

richtig, wir haben also 2^n teilmengen von M', die x nicht enthalten, wenn wir jede einzelne dieser teilmengen mit x vereinigen, wie viele teilmengen gibt es, die x enthalten?

01.06.2010, 20:12

marco12345

Auf diesen Beitrag antworten »

das verstehe ich nun garnicht mehr

01.06.2010, 20:13

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von marco12345
das verstehe ich nun garnicht mehr

du weißt aber, was die vereinigung von zwei mengen ist ...?

01.06.2010, 20:16

marco12345

Auf diesen Beitrag antworten »

Also eine vereinigungs menge von A und B ist so zu sehn, das ich alle elemente aus A und B zusammenfassen kann in eine menge.... so verstehe ich das

nur x ist ja keine menge.. sondern ein element

01.06.2010, 20:37

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von marco12345
Also eine vereinigungs menge von A und B ist so zu sehn, das ich alle elemente aus A und B zusammenfassen kann in eine menge.... so verstehe ich das

nur x ist ja keine menge.. sondern ein element

Zitat:

Original von lgrizu
wieso denn zwei elemente?
wir beginnen die induktion mit $\begin{eqnarray*} M= \emptyset \end{eqnarray*}$ . wie viele teilmengen hat die leere menge?

edit: okay, das hätten wir also geklärt.

nach vorraussetzung gibt es also $\begin{eqnarray*} 2^n \end{eqnarray*}$ teilmengen von einer n-elementigen menge M.
wie viele teilmengen hat die menge $\begin{eqnarray*} M'=M \cup \{x\} \end{eqnarray*}$ ?

01.06.2010, 20:37

marco12345

Auf diesen Beitrag antworten »

dat werd ich nie lösen misst..... aber danke trotzdem

01.06.2010, 20:42

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von marco12345
dat werd ich nie lösen misst..... aber danke trotzdem

jetzt die flinte ins korn werfen ist nicht, ich geb mir nicht über ne stunde mühe, damit so was kommt......

also noch mal:
M ist eine m-elementige menge, diese hat nach vorraussetzung 2^m teilmenegen.
$\begin{eqnarray*} M'=M \cup \{x\}, x\notin M \end{eqnarray*}$ hat 2^m teilmengen, die x nicht enthalten, nennen wir diese teilmengen $\begin{eqnarray*} T_i, i=1,2,3,......2^m \end{eqnarray*}$ jetzt bilden wir die mengen $\begin{eqnarray*} T_i \cup \{x\} \end{eqnarray*}$ , wie viele dieser $\begin{eqnarray*} T_i \cup \{x\} \end{eqnarray*}$ gibt es?

01.06.2010, 20:46

marco12345

Auf diesen Beitrag antworten »

noch ne variable...boa hast du ne ausdauer

x ist ein element und keine menge... also woher kommt das x.. aus welcher menge... ich kann doch sonst keine vereinigung machen.. ich brauche doch immer zwei mengen um was zu vereinigen

01.06.2010, 20:47

lgrizu

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \{x\} \end{eqnarray*}$ ist eine einelementige menge....

edit: i ist keine variable, ist nen indize Augenzwinkern

Augenzwinkern

01.06.2010, 20:54

marco12345

Auf diesen Beitrag antworten »

Also M´hat 2^n elemente und das x

01.06.2010, 21:02

lgrizu

Auf diesen Beitrag antworten »

nein, M' hat 2^m teilmengen, die das x nicht enthalten.

wir nehmen mal ein beispiel, vielleicht klappt es ja dann:

$\begin{eqnarray*} M=\{1,2,3\} \end{eqnarray*}$ dieses M hat die teilmenegen $\begin{eqnarray*} T_1= \emptyset,~T_2=\{1\},~T_3=\{2\},~T_4=\{3\},~T_5=\{1,2\},~T_6=\{1,3\},~T_7=\{2,3\},~T_8=\{1,2,3\} \end{eqnarray*}$ .

nun betrachten wir $\begin{eqnarray*} M'=\{1,2,3\} \cup\{4\} \end{eqnarray*}$ dieses M' hat zunächst einmal unsere teilmengen $\begin{eqnarray*} T_1,T_2,...,T_8 \end{eqnarray*}$ und zusätzlich noch die teilmengen $\begin{eqnarray*} T_1 \cup \{4\},~T_2 \cup \{4\},~T_3 \cup \{4\},~T_4 \cup \{4\},~T_5 \cup \{4\},~T_6 \cup \{4\},~T_7 \cup \{4\},~T_8 \cup \{4\} \end{eqnarray*}$

edit: M ist unsere m-elementige Menge, 4 ist unser x, wie viele teilmengen existieren also,die x nicht entahlten und wie viele, die x enthalten?

01.06.2010, 21:07

marco12345

Auf diesen Beitrag antworten »

nuja also ist das x doch mit in m´ Gott

Gott

unglücklich

01.06.2010, 21:09

lgrizu

Auf diesen Beitrag antworten »

in M' ist es, denn so haben wir M' ja gebaut....

aber wie viel teilmengen gibt es denn nun, die x enthalten?

01.06.2010, 21:15

marco12345

Auf diesen Beitrag antworten »

nach deinem beispiel gibt es in M´ 2^m mengen ohne x....

aber scheinbar genau so viele mit x... boa nu bin ich richtig verwirrt

01.06.2010, 21:20

lgrizu

Auf diesen Beitrag antworten »

ist richtig Tanzen

Tanzen

, sind zusammen wie viele?

2^m teilmengen ohne x + 2^m teilmengen, die x enthalten sind $\begin{eqnarray*} 2^m+2^m=2*2^m=2^{m+1} \end{eqnarray*}$ teilmengen von einer m+1-elementigen menge.
jetzt fass noch mal alles zusammen und zeig mal deinen induktionsbeweis.....

01.06.2010, 21:21

marco12345

Auf diesen Beitrag antworten »

irgendwie macht es etwas klick... aber aufschreiben kann ich das nicht ..

oder schreibe ich da dein zahlenbeispiel ab?

01.06.2010, 21:23

lgrizu

Auf diesen Beitrag antworten »

nein, du musst das ganz allgemein machen, aber es ist doch alles gesagt, du musst das jetzt nur noch richtig zusammenbauen....
zunächst mal induktionsannahme und induktionsanfang

01.06.2010, 21:25

marco12345

Auf diesen Beitrag antworten »

induktions anfang hab ich.. der war ja leicht nachvollziehbar... aber der rest macht immer mal wieder etwas klick.. und dann stirbt der klick wieder ab in meinem kopf..
und aufschreiben geht garnicht....
mir fehlt schon die zeile worauf ich hinaus will beim induktionsschluss

01.06.2010, 21:34

lgrizu

Auf diesen Beitrag antworten »

die mächtigkeit der potenzmenge ist die anzahl der teilmengen.

ich schreib dir die induktion jetzt mal sauber hier hin:
Sei M eine m-elementige Menge
Induktionsannahme: $\begin{eqnarray*} | P(M)| =2^m \end{eqnarray*}$

Induktiosanfang: $\begin{eqnarray*} M= \emptyset \end{eqnarray*}$ , $\begin{eqnarray*} P(M)=\{\emptyset\} \end{eqnarray*}$ , also $\begin{eqnarray*} | P(M) |=1=2^0 \end{eqnarray*}$ .

Induktionsschluss:

Wir betrachten $\begin{eqnarray*} M'=M \cup \{x\} \end{eqnarray*}$ mit $\begin{eqnarray*} x \notin M \end{eqnarray*}$ .
M hat 2^m teilmengen, M' hat also 2^m teilmengen, die x nicht enthalten.
die vereinigung jeder dieser teilmengen von M mit x ergibt 2^n teilmengen, die x enthalten.
also $\begin{eqnarray*} | P(M') |=2^n+2^n=2 \cdot 2^n=2^{n+1} \end{eqnarray*}$

edit: du musst dringend elementare mengenlehre und induktion lernen, wie weit bist du mit dem anderen induktionsbeweis?

01.06.2010, 21:41

marco12345

Auf diesen Beitrag antworten »

weis garnicht was ich sagen soll... schläfst du nachts auf nem mathebuch?oder ist das ne aufgabe die immer wieder kommt.. und ich habs verpasst...

FETTEN DANK... nu kann ich ruhig schlafen :-) Tanzen

Tanzen

Tanzen

Tanzen

Tanzen

01.06.2010, 21:44

lgrizu

Auf diesen Beitrag antworten »

Zitat:

Original von marco12345
... schläfst du nachts auf nem mathebuch..

wenns das mal brächte.....

ich hoffe, du hast einigermaßen verstanden, was wir gemacht haben und wie der induktionsschluss zustandekommt,
ansonsten: viel spaß noch im board Augenzwinkern

Augenzwinkern

Wink

01.06.2010, 21:46

marco12345

Auf diesen Beitrag antworten »

danke eine kleine aufgabe hab ich heut noch zu beälltigen.. die will nur keiner :-)
vieleicht komm ich da auch so drauf die iss etwas einfacher...

02.06.2010, 18:33

Elvis

Auf diesen Beitrag antworten »

Zitat:

Original von marco12345
... schläfst du nachts auf nem mathebuch?

Drauf schlafen bringt nichts, aber als Klolektüre sind Mathebücher unschlagbar. Augenzwinkern

Augenzwinkern

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »