Mengen Beweis /Kardinalität |
| 12.10.2014, 16:28 | MegaLe | Auf diesen Beitrag antworten » | ||
| Mengen Beweis /Kardinalität Ich komme hier bei drei Aufgaben einfach nicht weiter. Wäre super wenn mir da jemand schnell helfen könnte bzw wenigstens nen Ansatz gibt. Es sei . n>=2 Zeige, dass M auf 2^(n-1)-1 Weisen in zwei disjunkte nichtleere Teilmengen zerlegt werden kann. disjunkt: Dass das gitl sieht man, aber wo soll ich da jetzt anfangen? Bestimme Kardinalität -> Fälle Sollte stimmen, aber wie kann ich das zusammenfassen? |
||||
| 12.10.2014, 16:41 | URL | Auf diesen Beitrag antworten » | ||
| RE: Mengen Beweis /Kardinalität Wie siehst du denn, dass das gilt? Kannst du daraus nicht einen Beweis machen? Ansonsten kannst du dir als erstes überlegen, wie viele Teilmengen eine n-elementige Menge hat und was eine Teilmenge mit einer Zerlegung zu tun hat 
|
||||
| 12.10.2014, 18:01 | MegaLe | Auf diesen Beitrag antworten » | ||
Naja, das ist mein erstes "Mathe" Fach und habe keinen Plan wie ich nen Beweis herleite. Maximal eine Induktion würde ich halbwegs zusammenbekommen. Bei ner n-elementigen Menge werde ich wohl n-Teilmengen erzeugen können. Aber ich muss ja hier den beweis für genau zwei Teilmengen machen. Hat es vielleicht etwas mit Partitionen zu tun? Ich zerlege da doch auch eine n-elementige Menge in je nach wie vielen Elementen in Teilmengen. |
||||
| 12.10.2014, 18:32 | URL | Auf diesen Beitrag antworten » | ||
Dass das nicht stimmen kann, kannst du schon für den Fall n=2 sehen sind die vier Teilmengen von . Bei einer n-elementigen Menge gibt es Teilmengen (was man übrigens per Induktion zeigen kann) Die Idee ist folgende: Du nimmst eine beliebige Teilmenge und hast damit die Zerlegung von M in die beiden disjunkten Mengen und . Dann überlegst du, ob du eine andere Zerlegung bekommst, wenn du stattdessen mit beginnst. Damit weißt du, wie viele Zerlegungen es gibt. Dann musst du nur noch berücksichtigen, dass die Megen nicht leer sein sollen. |
||||
| 12.10.2014, 19:44 | MegaLe | Auf diesen Beitrag antworten » | ||
Ja gut, aber ich muss die Menge doch in zwei nichtleere Teilmengen zerlegen und du hast du vier wovon eine leer ist. Gut. für n=2 ; 4 Teilmengen n=3 ; 8 n=4; 16 usw.. heißt bei jedem Schritt kommen gleich viele Teilmengen hinzu -> 2^n bei jedem Mal gibt es eine leere Menge. auf Grund der Aufgabe: 2^n-1 Und jetzt sollen aber nicht "beliebig" viele Teilmengen entstehen sondern die Elemente auf zwei aufgeteilt werden. Heißt ich muss die einer, dreier, vierer usw eleminieren. Wenn ich dann ein bit wegnehme kommt man auf 2^(n-1) und somit halbiere ich die Möglichkeiten.... Ich hab aber keine Begründung warum ich das mache.. |
||||
| 12.10.2014, 21:28 | URL | Auf diesen Beitrag antworten » | ||
Die vier Mengen stehen zunächst mal da, um zu zeigen, dass es mehr als n Teilmengen einer n-elementigen Menge gibt. Hast du überhaupt mal versucht, meine Idee anhand des Beispiels nachzuvollziehen? |
||||
| Anzeige | ||||
|
|
||||
| 12.10.2014, 21:51 | MegaLe | Auf diesen Beitrag antworten » | ||
Ja, aber weiß nicht was mir das bringen soll. M={a,b} P={{a,b},{a},{b},{}} A={a} M\A={b} A={b} M\A={a} Hast du das so gemeint? |
||||
| 12.10.2014, 22:32 | URL | Auf diesen Beitrag antworten » | ||
ja. Und genauso für A={} M\A=M A=M M\A={} Diese beiden Zerlegungen sind nicht wirklich verschieden, oder? Sie bestehen beide aus der leeren Menge und M. Es ist ja willkürlich, was du als A genommen hast. Genauso im anderen Fall: Die Zerlegung besteht aus {a} und {b}. Also hast du aus den vier Teilmengen zwei verschiedene Zerlegungen gewonnen. Genau eine davon, namlich {}, M, enthält die leere Menge. Die musst du nach Aufgabenstellung noch wegwerfen, bleibt also in dem Fall eine Zerlegung in zwei disjunkte Mengen übrig. Im allgemeinen Fall geht es genauso. Du bekommst zunächst Paare (A, M\A). Davon gibt's für jede Teilmenge von M genau eins, insgesamt also 2^n. Jetzt unterscheidest du wie oben nicht mehr zwischen (A,M\A) und (M\A,A). Dann sind es nur noch halbsoviele "Paare", also . Dann noch das eine verbliebene "Paar" mit der leeren Menge wegwerfen, und es bleiben Zerlegungen. |
||||
| 12.10.2014, 23:52 | MegaLe | Auf diesen Beitrag antworten » | ||
Dazu noch eine Frage. Warum wird das nicht mehr unterschieden? Ich weiß wir haben oben gesagt, dass die beiden ja "gleich" sind. Aber es ist doch trotzdem eine andere Zerlegung wenn in A x ist und in B y und umgekehrt. A={abc} P={{},{abc}, {ab}{c}; {ac}{b};{bc}{a} {a}{b}{c}; +2 die ich nicht finde... Jetzt schneid ich mal die leere Menge raus 2^n -1 Dann müssen noch die mit mehr/weniger als zwei Mengen weg. Dann passt doch das was ich oben gesagt habe? Wenn ich einen bit weniger spendiere, sind die weg. Und das ist eben weil mit jedem zusätzlichem Element sich die Anzahl der Teilmengen verdoppelt. Und das sind anscheinend genau die, die ich nicht will. Würde das so auch passen? :O |
||||
| 13.10.2014, 00:11 | MegaLe | Auf diesen Beitrag antworten » | ||
Achja, kann jemand etwas zu der Kardinalität sagen? Und ich würde oben ändern nach: A n B = leere Menge -> |A u B| = |A| + |B| aber eine unterscheidung von den Teilmengen muss ich trotzdem noch machen. Wie kann ich das zeigen? |
||||
| 13.10.2014, 00:22 | URL | Auf diesen Beitrag antworten » | ||
Tut mir leid, ich kann dir überhaupt nicht folgen. Und was du jetzt noch mit der Kardinalität willst, ist mir schleierhaft. Wenn sich ein anderer Helfer berufen fühlt, bitte sehr. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
