Aufgabe zu Teilmengen |
| 06.11.2009, 10:38 | TheBoss | Auf diesen Beitrag antworten » | ||
| Aufgabe zu Teilmengen Beweisen oder widerlegen Sie: Jede endliche nichtleere Menge besitzt ebenso viele Teilmengen mit gerader wie mit ungerader Elementeanzahl... Ich weiß nicht, ob ich die Aufgabe richtig angeh, ich weiß nur, dass ich Hilfe bauche ^^ Nehmen wir uns jetzt mal als Beispiel die Menge A= (1,2), so besitzt diese ja 4 Teilmengen, nämlich: leere Menge, 1, 2 und 1,2... Haben wir die Menge A2 = (1,2,...,k), so besitzt sie 2^k Elemente.. Da uns die leere Menge nicht interessiert, müssten wir doch, um z.B. alle geraden Teilmengen herauszufinden, folgende Formel aufstellen: (2^k) / 2 ... Oder? Ist es bis hier hin richtig oder hab ich nen falschen Ansatz ? Und wie gehts weiter? |
||||
| 06.11.2009, 10:46 | tmo | Auf diesen Beitrag antworten » | ||
Versuche mal herauszufinden, was die Identität mit deiner Aufgabe zu tun haben könnte 
Falls du nicht draufkommst, kannst du auch deinen Ansatz verfolgen. Sei . Für die Anzahl der Teilmengen, die geradezahlig viele Elemente enthalten und die Anzahl der Teilmengen, die ungeradezahlig viele Elemente enthalten, gilt dann . Darauf kann man ne Induktion loslassen. |
||||
| 06.11.2009, 11:09 | TheBoss | Auf diesen Beitrag antworten » | ||
Induktion war auch schon meine Vermutung, nur wusste ich nicht, wie ich die ansetzen sollte =/ Ist das dann vlt.: (1+ a + a^2 + ... + a^n) / 2 = 1/2 *^2 ^n ?? Mir fehlt da cder Ansatz! |
||||
| 06.11.2009, 11:11 | tmo | Auf diesen Beitrag antworten » | ||
Sind wir jetzt bei der Ratestunde? Du sollst hier einen Beweis führen. Da muss man schon etwas nachdenken. Gib dir Zeit zum nachdenken doch einfach mal. Indem du zunächst Induktionsanfang und Induktionsvorraussetzung hinschreibst. Und mir dann sagst, was du im Induktionsschritt zu zeigen hast. |
||||
| 06.11.2009, 18:28 | TheBoss | Auf diesen Beitrag antworten » | ||
Die Induktionsbehauptung ist, dass jede endliche nichtleere Menge ebenso viele Teilmengen mit gerader wie mit ungerader Elementeanzahl besitzt... Nur komme ich einfach nicht auf die Formel, die das zeigen soll: ? = 0,5 * 2^k Deswegen war ja meine Vermutung für den In duktionsanfang: Für k=1 0,5 * 2^1 = (1 + a)/2 Nur das ist ja völliger Murks... Zu den Voraussetzungen kann ich nur sagen, dass die Gleichung ausm Indzuktionsanfang richtig sein muss und der Induktionsschritt ist dann n ---> n+1! Die Voeaussetzungen für eine Induktion sind mir auch deutlich... Nur kann ich dir das alles nicht bestimmen, weil ich keinen Schimmer habe, mit was ich meinen Term gleichsetzen soll! |
||||
| 06.11.2009, 18:42 | AD | Auf diesen Beitrag antworten » | ||
Hinter den meisten Formeln stehen erstmal Inhalte. Du stürzt dich sofort auf die Formeln, ohne über den Inhalt nachzudenken, und stehst dann ratlos da. Bei einem Induktionsbeweis wie hier über Teilmengen überlegt man sich doch erstmal, wie man die Teilmengen (ob nun gerad- oder ungeradzahlig) einer (k+1)-elementigen Menge auf die Teilmengen der k-elementigen Menge zurückführen kann (Induktionsvoraussetzung!), dann erst sollte man zu "zählen" anfangen. |
||||
| Anzeige | ||||
|
|
||||
| 06.11.2009, 18:51 | TheBoss | Auf diesen Beitrag antworten » | ||
Weißt, es wurde uns an einem Beispiel gezeigt, aber zuvor habe ich den Begriff Induktion noch nie gehört, außer in Zusammenhang mit Chemie... Im Inet hab ich auch nichts verständliches gefunden.. Die Induktionsregel ist mir klar, aber sie anzuwenden üpberhaupt nicht.. Nu sitz ich diesen gottverdammten Tag an dieser Aufgabe und komm nicht weiter.. Eure Hinweise sind nett gemeint, nur bringen sie einem kompletten Laien einfach nichts.. Ich will die Aufgabe lösen, nur oack ichs einfach net.. Deswegen hab ich mich an euch gewandt! |
||||
| 06.11.2009, 18:59 | AD | Auf diesen Beitrag antworten » | ||
Ich hab immer gedacht, die Induktion wird im Gymnasium (oder welchem Bildungsweg auch immer hin zum Abitur) behandelt? P.S.: Induktion in der Chemie kenne ich wiederum nun nicht, nur die aus der Elekrodynamik.
|
||||
| 06.11.2009, 19:10 | TheBoss | Auf diesen Beitrag antworten » | ||
Bei mir wars nicht so (Herzlichen Dank Zentralabitur!).. Nur versteh mich bitte, ich möchte mal irgendwas erreichen, nachdem ich jetzt schon die ganze Zeit überlege.. Ich habe ja zumindest nen Ansatz mit dem 0,5 * k ^2 .. nur weiß ich nicht, mit was ich das gleichsetzen soll bzw. wie ich darauf komme... |
||||
| 06.11.2009, 19:10 | tmo | Auf diesen Beitrag antworten » | ||
Nicht verpflichtend. Zumindest nicht in Rheinland-Pfalz. In meinem Leistungskurs wurde sie nicht behandelt. Meine Schwester hat sie auf der selben Schule 2 Jahrgänge drüber im LK gehabt. |
||||
| 06.11.2009, 19:17 | TheBoss | Auf diesen Beitrag antworten » | ||
Ach Leute, ich habs versucht.. Aber was nicht sein soll, soll wohl nicht sein.. Ich dachte, ich würde hier jemanden finden, der mir wirklich weiterhelfen kann.. Mir ist ja bewusst, dass ihr mir keine Lösung vorgeben wollt, das möcht ich auch nicht, aber zumindest n vernünftiger Ansatz wäre schön gewesen... Naja ich muss es wohl man mit mir allein ausmachen... Ist es möglich meinen Account wieder zu löschen? Das hier scheiont nicht meine Welt zu sein! Wäre schön, wenn ihr es für mich erledigen könntet! |
||||
| 07.11.2009, 01:55 | AD | Auf diesen Beitrag antworten » | ||
"Kenn ich nicht, weiß ich nicht, hatt ich nicht, will ich nicht ... aber gebt mir einen vernünftigen (!) Ansatz." Was du verlangst, ist was für Zauberkünstler. Ich sehe hier jede Menge vernünftige Ansätze, aber du lässt keinen an dich heran. 
|
||||
| 07.11.2009, 11:14 | Mystic | Auf diesen Beitrag antworten » | ||
Hm, also einen vernünftigen Ansatz kenn ich noch, der zwar die Idee des induktiven Beweises verwendet, aber kein induktiver Beweis ist... Um sie zu verdeutlichen, nehmen wir an, der Geschäftsführer einer Diskothek möchte bei einem Event, das er veranstaltet hat, feststellen, ob mehr Männer oder Frauen anwesend sind... Er bittet dazu den DJ eine Platte aufzulegen, bei der sich erfahrungsgemäß garantiert alle potenziellen Paare auf die Tanzfläche begeben... Zu seiner Verwunderung stellt er fest, dass keine Besucher übriggeblieben sind, die nicht auf der Tanzfläche sind, woraus er den messerscharfen Schluss zieht, dass es gleich viele männliche wie weibliche Besucher geben muss... Als er nach Hause kommt, sieht er seinen Sohn über eben der Aufgabe brüten, die in diesem Thread gestellt wurde... Blitzschnell schießt es ihm durch den Kopf, dass dieses Prinzip der Paarbildung vielleicht auch hier anwendbar ist, wobei in jedem Paar jeweils eine Menge eine gerade und die andere Menge eine ungerade Anzahl von Elementen hat... Nun gibt es auf Mengen aber bereits eine ganz natürliche (ungeordnete) Paarbildung nämlich , wobei die Komplementärmenge zu A bezeichnet,... Er probiert das einmal mit den Teilmengen der Menge M={1,2,3} aus und präsentiert dann seinem Sohn stolz die Lösung mit den Paaren mit der Bemerkung, dass das im allgemeinen Fall ganz genauso geht... Aber der holt ihn schnell wieder in die Realität zurück, indem er darauf hinweist, dass dies nur in 50% der Fälle so funktioniert, nämlich genau dann wenn die Menge M eine ungerade Anzahl von Elementen hatte, wie eben in diesem Beispiel ... Ok, das stimmt offensichtlich, aber kann man diese Beweisidee nicht vielleicht doch auch für Mengen M mit einer geraden Anzahl von Elementen in irgendeiner Form "retten"? Der Geschäftsführer und sein Sohn setzen sich jedenfalls hin und überlegen angestrengt, ob man dies nicht z.B. irgendwie auf den schon bekannten Fall, wo M eine ungerade Anzahl von Elementen hat, zurückspielen kann... Tja, und vielleicht ist diese Frage ja auch dem TE zugänglich, sozusagen als allerletzter Versuch? 
|
||||
| 07.11.2009, 15:56 | TheBoss | Auf diesen Beitrag antworten » | ||
Ich schreibe jetzt einfach mal alles auf, was ich weiß... Also die Behauptung ist, dass jede nichtleere Mednge genauso viele gerade wie ungerade Teilmengen hat! Um die Anzahl der Teilmengen auszurechnen, können wir die Formel 2^k zu Hilfe nehmen! Ist k nun eine 3, dann haben wir 8 Teilmengen, die da lauten: 1, 2, 3, 12, 13, 23, 123, leere Menge... Wir haben also, wenn wir die leere Menge nicht betrachten, 4 ungerade Teilmengen (1,2,3,123) und 3 gerade Teilmengen (12,13,23)... Das bedeutet, dass es hier keine gleiche Anzahl von geraden und ungeraden Teilmengen gibt oder? Und das müsste man ja dann noch auf k beziehen... Also wenn meine Überlegung richtig sein sollte, müsste sich ja ergeben, dass die Aussage falsch ist! Nur wie...
|
||||
| 07.11.2009, 17:44 | AD | Auf diesen Beitrag antworten » | ||
Da fehlt eine: Die leere Menge ist auch eine Teilmenge, und zwar eine mit der geraden Elementanzahl Null. |
||||
| 07.11.2009, 18:10 | Mystic | Auf diesen Beitrag antworten » | ||
Ich hab dir doch oben hingeschrieben, wie für eine 3-elementige Menge die Teilmengen aussehen und wie man da die "Paare" bildet: Insbesondere ist da die leere Menge auch dabei, warum in aller Welt willst du die ausschließen??! Die hat doch 0 Elemente und 0 ist eine gerade Zahl, da durch 2 teilbar, d.h., die leere Menge ist genauer eine Teilmenge mit einer geraden Anzahl von Elementen... (edit: wie Arthur oben schon gesagt hat) Wie schaut das jetzt bei den Teilmengen von aus? Hier funktioniert zwar die obige Paarbildung nicht mehr, denn in jedem Paar haben nun beide Mengen entweder eine gerade oder eine ungerade Anzahl von Elementen, aber es funktioniert eine andere Paarbildung, wo die "Partner" verschiedene "Paritäten" haben, nämlich ... Du solltest dir mal alle diese Paare wirklich hinschreiben und dir dann überlegen, inwieweit dir das hilft, dass die Behauptung für Teilmengen von ja schon bewiesen wurde... |
||||
| 07.11.2009, 21:55 | TheBoss | Auf diesen Beitrag antworten » | ||
Wenn mich nicht alles täuscht, funktioniert es für die von dir genannte Menge nicht: Gerade Teilmengen: 2,4, 12, 13, 14, 23, 24, 34, 1234, 0 (8 Mengen) Ungerade Teilmengen: 1,3,123,124,134,234 (6 Mengen) |
||||
| 07.11.2009, 22:07 | Mystic | Auf diesen Beitrag antworten » | ||
Einer der wenigen Dinge, die du richtigerweise immer wieder festgestellt hast ist die Tatsache, dass eine -elementige Menge Teilmengen haben muss, in deiner Aufzählung fehlen daher irgendwo zwei, und zwar bei den ungeraden, dafür gehören bei den geraden Teilmengen zwei weg, die du aber offenbar ohnehin nicht mitgezählt hast, also dann richtig in deiner Schreibweise Gerade Teilmengen: 0,12,13,14,23,24,34,1234 (8 Teilmengen) Ungerade Teilmengen: 1,2,3,4,123,124,134,234 (8 Teilmengen) Wenn es also bereits daran scheitert, die Teilmengen von {1,2,3,4} überhaupt einmal richtig aufzuzählen, so sehe ich echt schwarz für das eigentliche Problem...
|
||||
| 07.11.2009, 22:13 | TheBoss | Auf diesen Beitrag antworten » | ||
Sry ist schon spät ^^ Natürlich müssen 2 und 4 noch den ungeraden hinzugezählt werden... Also das Ganze hat jetzt für die Mengen A=(1,2), A=(1,2,3) und A=(1,2,3,4) geklappt... Somit ist meine Vermutung, dass die Behauptung, dass es gleichviele gerade und ungerade Teilmengen gibt, wahr ist! Nur wie geh ich jetzt an den Beweis ran? |
||||
| 07.11.2009, 22:31 | Mystic | Auf diesen Beitrag antworten » | ||
Diese Frage ist doch etwas seltsam angesichts der vielen Lösungsvorschläge, die in diesem Thread schon präsentiert wurden, u.a. auch von mir selbst... Du solltest jetzt nur endlich mal einen davon aufgreifen, und auch mal selbst irgendetwas Brauchbares dazu beisteuern... |
||||
| 07.11.2009, 22:43 | TheBoss | Auf diesen Beitrag antworten » | ||
Es gibt sicherlich Vorschläge, nur verstehe ich sie ebn nicht, sonst hätte ich schon längst was draus gemacht... Für mich ist dieses Thema absolutes Neuland, vlt. solltest du das auch mal nachvollziehen können.. Ich geb mir wirklich Mühe, schon seit 2 Tagen, nur leider kann ich aus den Vorschlägen bisher nichts rausziehen! Ich möcht nicht aufgeben, aber langsam hab ich das Gefühl, ich tret auf der gleichen Stelle und komm net voran.. Deinen Vorschlag halt ich bisher am hilfreichsten, nur weiß ich nicht, wie ich ihn anwenden soll: Bei einem Induktionsbeweis wie hier über Teilmengen überlegt man sich doch erstmal, wie man die Teilmengen (ob nun gerad- oder ungeradzahlig) einer (k+1)-elementigen Menge auf die Teilmengen der k-elementigen Menge zurückführen kann (Induktionsvoraussetzung!), dann erst sollte man zu "zählen" anfangen. |
||||
| 07.11.2009, 22:55 | TheBoss | Auf diesen Beitrag antworten » | ||
Noch eine Überlegung von mir... Um alle Teilmengen zu bestimmen, schreiben wir 2^k , wenn wir jetzt nur die geraden Mengen bestimmen wollen, schreiben wir 2^(k-1) , sollte die Behauptung stimmen... Daher gibt sich für die ungeraden Mengen: 2^k - 2^(k-1) = 2^(k-1) ... Das wäre jetzt noch ne Idee von mir... Völlig uninterewssant oder führt mich das irgendwie weiter? |
||||
| 07.11.2009, 23:37 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, wenn die Behauptung stimmt, dass es gleich viele "gerade" wie "ungerade" Teilmengen - nennen wir sie mal der Einfachheit halber so - einer k-elementigen Menge gibt, dann wäre das tatsächlich je Teilmengen von den insgesamt Teilmengen, doch bringt uns das nicht wirklich weiter... Probieren doch mal am Beispiel M={1,2,3,4} alle Teilmengen in (diesmal geordneten) Paaren hinzuschreiben, wobei die erste Menge das Element 4 nicht enthält, die zweite aber schon, also 1. ({ },{4}) 2. ({1},{1,4}) 3. ({2},{2,4}) 4. ({3},{3,4}) 5. ({1,2},{1,2,4}) 6. ({1,3},{1,3,4}) 7. ({2,3},{2,3,4}) 8. ({1,2,3},{1,2,3,4}) Wie du siehst, kommt jede Teilmenge von {1,2,3,4} in genau einem Paar vor...Wenn wir nun schon wissen, dass es gleich viele gerade wie ungerade Teilmengen von {1,2,3} gibt, die als jeweils erste Komponente der obigen Paare auftreten, was sagt uns das über die Anzahl der geraden und ungeraden Teilmengen von {1,2,3,4} ? Das ist die Gretchenfrage hier und wenn du die nicht schlüssig beantworten kannst, dann hat es wenig Sinn weiterzumachen... |
||||
| 07.11.2009, 23:55 | TheBoss | Auf diesen Beitrag antworten » | ||
Was möchtest du jetzt hören ^^ ? Dass die Anzahl an geraden und ungeraden bei A=(1,2,3,4) auch gleich groß ist? Oder das die Anzahl der geraden Teilmengen das doppelte der Anzahl der Teilmengen von A=(1,2,3) ist? Oder versteh ich deine Frage falsch? Für A=(1,2,3,4) sind es (2^4)/2 gerade Teilmengen, also 8! |
||||
| 08.11.2009, 00:14 | Mystic | Auf diesen Beitrag antworten » | ||
Natürlich möche ich hören, dass die Anzahl der geraden und ungeraden Teilmengen von {1,2,3,4} auch gleich groß ist, aber vor allem wie kommst du zu diesem Schluß? Und zwar nur unter Betrachtung meiner Liste oben und nur unter Verwendung der folgenden 2 Tatsachen: 1. Die jeweils ersten Komponenten der Paare (also gewissermaßen die "1.Spalte") enthalten gleich viele gerade wie ungerade Teilmengen, da sie ja nur aus Teilmengen von {1,2,3} bestehen, für die wir das schon gezeigt haben. 2. Jedes Paar (also gewissermaßen jede "Zeile") enthält offensichtlich eine gerade und eine ungerade Teilmenge von {1,2,3,4} (in irgendeiner Reihenfolge) Wenn du diese Schlußfolgerung "sauber" führen kannst, dann wäre das ein Riesenschritt in Richtung eines allgemeinen Beweises... |
||||
| 08.11.2009, 00:32 | TheBoss | Auf diesen Beitrag antworten » | ||
Wenn man das Ganze für k=5 macht, steht in jeder Zeile auch wieder eine gerade und eine ungerade Zahl, nur, dass es eben wieder die doppelte Menge an Teilmengen ist, im Vergleich zu k=4! Und das ist dortlaufend so, dass sich die Teilmengen immer verdoppeln... Aber inwieweit kann ich die erkannte Schlussfolgerung "sauber" führen? Bzw. was genau meinst du damit? |
||||
| 08.11.2009, 09:29 | Mystic | Auf diesen Beitrag antworten » | ||
Das Problem ist, du weichst meinen Fragen immer wieder aus, hier z.B. auf den anderen Fall k=5, obwohl ich dich ja ausdrücklich gebeten hatte, den Beweis für k=4 zu führen... Ich werde dir das noch schnell vorführen, wie ich das gemeint hatte und dann die Diskussion hier damit abschließen, da wir irgendwie nicht vom Fleck kommen... Schauen wir uns dazu nochmals untenstehende Liste aller Teilmengen von {1,2,3,4} an, von der wir zeigen, dass sie insgesamt gleich viele gerade wie ungerade Teilmengen enthält.... 1. ({ },{4}) 2. ({1},{1,4}) 3. ({2},{2,4}) 4. ({3},{3,4}) 5. ({1,2},{1,2,4}) 6. ({1,3},{1,3,4}) 7. ({2,3},{2,3,4}) 8. ({1,2,3},{1,2,3,4}) Wir wissen nun bereits, dass dies für die 1.Spalte (bestehend aus den ersten Komponenten aller Paare) zutrifft, da dies ja nur Teilmengen von {1,2,3}, für welche wir das ja schon gezeigt haben... Angenommen, dies wäre in der 2.Spalte (bestehend aus den zweiten Komponenten aller Paare) nicht so und es gäbe z.B. mehr ungerade Teilmangen als gerade... Für diese Paare wäre aber dann die erste Komponente gerade, d.h., es gäbe dann in der ersten Spalte mehr gerade als ungerade Teilmengen, Widerspruch... Es gibt somit auch in der 2.Spalte gleich viele gerade wie ungerade Teilmengen von {1,2,3,4}, somit gilt dies auch insgesamt für alle Teilmengen von {1,2,3,4}, die ja alle in diesen zwei Spalten aufgelistet sind... |
||||
| 08.11.2009, 10:27 | TheBoss | Auf diesen Beitrag antworten » | ||
Es lässt sich ja insgesamt eine Folge erkennen: bei k=2 waren es 2 gerade, bei k=3 waren es 4 und bei k=4 waren es 8... kann man das denn nicht vlt. die Menge aller geraden Zahlen gleich (2^n)/2 setzen? also: 2,4,6,8,...,2^(k-1) = (2^k)/2 oder denk ich da jetzt zu weit? |
||||
| 08.11.2009, 10:35 | AD | Auf diesen Beitrag antworten » | ||
Du denkst vor allem immer nur im Kreis. Mystic hat jetzt schon mehrfach angesetzt dir klarzumachen, dass bei Hinzunahme eines Elements zur Gesamtmenge - also im Beispiel sich a) die Anzahl der Teilmengen insgesamt verdoppelt, und b) sich die Teilmengen zu Paaren "eins gerade + eins ungerade" aufteilen lassen. Ersteres sichert, dass die Anzahl der Teilmengen insgesamt ist, das hast du soweit verstanden, und das wiederholst du ja auch immer wieder. Aber es ist irgendwie nicht zu erkennen, ob und wie weit b) zu dir durchgedrungen ist. Denn b) ist ja prinzipiell schon das, was du nachweisen sollst!!! |
||||
| 08.11.2009, 12:54 | TheBoss | Auf diesen Beitrag antworten » | ||
Ich habe es schon verstanden, was Mystic mir erläutern wurde und das ist (abgwesehen von den Paaren) ja auch schon das, was mir von Anfang an klar war, nur möchte ich das ja gern allgemein aufschreiben um den Beweis durchführen zu können! Und das schaff ich allein eben nicht.. Versteht mich nicht falsch, das grundsätzliche Verständnis ist von Anfang an da, nur das in eine Formel umzuwandeln gelingt mir nicht! |
||||
| 08.11.2009, 14:09 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, Arthur hat es wunderbar auf den Punkt gebracht, genauer auf den Punkt b), wo auch ich die allergrößten Zweifel habe, dass du ihn wirklich verstanden hast... Du sagst z.B., du würdest den Beweis gerne "allgemein" anschreiben und übersiehst dabei völlig, dass ich das oben zwar für M={1,2,3,4} alles aufgeschrieben habe, damit du dir das bessser vorstellen kannst, aber dass meine Argumentation tatächlich ganz allgemein war... Abgesehen von winzigen Änderungen, indem man M={1,2,3,4} allgemeiner durch die Menge M={1,2,...,n} für ein n>1 ersetzt und die Paarbildung betrachtet, sowie auch wieder die Liste der Paare läßt sich nämlich meine Argumentation oben fast Wort für Wort übernehmen... Ich habe eben oben in dem Sinne "sauber" argumentiert, als mein Argument mutatis mutandis auch für den allgemeinen Fall gilt... Übrigens: "Formeln" im üblichen Sinne gibt es bei diesem Beweis keine, wenn du sowas suchst, so wärst du mit der allerersten Beweisidee, welche von tmo vorgeschlagen wurde, nämlich dem Beweis der Formel wobei hier gerade die Anzahl der k-elementigen Teilmengen von M={1,2,...,n} ist, besser beraten... |
||||
| 08.11.2009, 14:49 | TheBoss | Auf diesen Beitrag antworten » | ||
Aber muss ich nicht jetzt immer noch beweisen, dass es wirklich für alle n gilt? Die Verallgemeinerung kann ich nachvollziehen, aber das reicht ja noch nicht oder? |
||||
| 08.11.2009, 15:07 | Mystic | Auf diesen Beitrag antworten » | ||
Was genau fehlt deiner Meinung nach noch? 
|
||||
| 08.11.2009, 15:14 | TheBoss | Auf diesen Beitrag antworten » | ||
Weiß nicht... Vlt. isses einfach so, dass ich nicht glauben kann, dass es das wirklich gewesen sein soll.. Weil ich mich immer darauf fixiert hatte, ne Formel zu beweisen... Hab wohl einfach zu kompliziert gedacht =/ |
||||
| 08.11.2009, 17:02 | Mystic | Auf diesen Beitrag antworten » | ||
Man könnte allenfalls noch erwähnen, dass man für einen induktiven Beweis nach obigem Muster einen Induktionsanfang braucht, das ist hier der Fall n=1, den man direkt nachrechnen muss...Ich bin aber oben davon ausgegangen, dass die Behauptung für ungerades n auf dem von mir skizzierten Wege schon allgemein bewiesen war... Ja, viele Wege führen nach Rom, wie es so schön heißt... Als kleine Ergänzung noch eine Beweisvariante, dir mir persönlich fast am besten gefällt, da sie leicht zu merken ist... Sei M={1,2,...,n} für ein n>0 und a ein beliebiges, aber im folgenden festes Element von M. Es ist dann die Abbildung eine selbstinverse Permutation von ... Anschaulich gesprochen wird durch Anwendung von f auf X der Menge X das Element a hinzugefügt, wenn es vorher nicht in X enthalten war, sonst wird es aus X entfernt... Inbesondere sieht man sofort, dass X und f(X) auf jeden Fall eine verschiedene Parität haben, was ihre Mächtigkeiten betrifft... Ist dann U die Menge der "ungeraden" Teilmengen und G die Menge der "geraden" Teilmengen von M, so müssen wir also dann zeigen, dass |G|=|U| ist... Betrachten wir dazu die beiden Einschränkungen f|U: U -> G und f|G: G ->U von f, so sind diese als Folge der Bijektivität von f immer noch injektiv, d.h., es gilt und , woraus tatsächlich folgt... |
||||
| 09.11.2009, 08:31 | Mystic | Auf diesen Beitrag antworten » | ||
Vielleicht sollte ich hier die Geschichte vom dem Geschäftsführer der Disco und seinem Sohn noch zu Ende erzählen...Es war inzwischen spät nachts geworden und die beiden brüteten noch immer über der Aufgabe...Insbesondere wurmte es dem Vater, dass seine Idee mit der Paarbildung, welche bei Mengen mit einer ungeraden Anzahl von Elementen so wunderbar funktioniert hatte, auf Mengen mit einer geraden Anzahl von Elementen nicht anwendbar sein sollte... Er betrachtete nochmals das Beispiel M={1,2,3,4}, wie schon so oft vorher, und hatte plötzlich die Idee, es genau mit der Paarbildung ({ },{4}) ({1},{1,4}) ({2},{2,4}) ({3},{3,4}) ({1,2},{1,2,4}) ({1,3},{1,3,4}) ({2,3},{2,3,4}) ({1,2,3},{1,2,3,4}) zu versuchen, auf welche auch wir oben gekommen waren, nämlich jede Teilmenge von {1,2,3} wird gepaart mit der der um 4 vergrößerten Teilmenge, was also dann insgesamt 8 Paare ergibt... Nun hatte der gute Mann noch nie in seinem Leben von vollständiger Induktion gehört, daher kam er gar nicht erst auf die Idee, es damit zu versuchen... Zum Glück brauchte er sie aber gar nicht: Da jedes Paar genau eine gerade und eine ungerade Teilmenge enthielt, genau wie im Beispiel M={1,2,3} mit der Paarung (Teilmenge,Komplementärmenge), und andererseits auch alle Teilmengen von {1,2,3,4} in obiger Auflistung genau einmal vorkommen, war auch so der Beweis erbracht, dass es genausoviele gerade wie ungerade Teilmengen von {1,2,3,4} geben musste... Stolz zeigte er diese Lösung seinem Sohn mit der Bemerkung, dass der allgemeine Fall einer n-elementigen Menge M nun wirklich genauso gehen sollte...Dieser schaute sich das nur kurz an, um dann freudig zuzustimmen, das war offensichtlich die Lösung... Am nächsten Tag wurde in der Übungsstunde jemand zu diesem Beispiel aufgerufen, der offenbar keine Ahnung von einem allgemeinen Beweis hatte und glaubte, die Aufgabe so lösen zu können, indem er die Richtigkeit der Behauptung für einige kleine Werte von n nachwies... Da die Zeit schon fortgeschritten war, sprang der Professor dann irgendwann ein und führte den Beweis mit vollständiger Induktion korrekt zu Ende...Da zeigte unser Sohn auf, und führte im Detail aus, dass diesselbe Idee auch ohne vollständige Induktion funktioniert, genau so wie sein Vater dies in der Nacht zuvor gemacht hatte...Er hatte seinen Professor noch nie so perplex gesehen... |
||||
| 09.11.2009, 12:01 | AD | Auf diesen Beitrag antworten » | ||
Genau das, also in Formelform gegossen hatte ich auch schon vor ein paar Tagen posten wollen, habe es dann aber zur Vermeidung zusätzlicher Verwirrung gelassen. Aber wenn du es jetzt schon ansprichst: Ja, Induktion ist wirklich nicht mal nötig zum Beweis der gleichen Anzahlen geradzahliger und ungeradzahliger Mengen - lediglich muss man noch anmerken, dass der Schluss (und überhaupt auch die Behauptung) erst für funktioniert. Aber dass die Behauptung für n=0 mit lediglich der einen geradzahligen leeren Teilmenge nicht gilt, sollte ohnehin trivialerweise klar sein.
|
||||
| 09.11.2009, 15:07 | Mystic | Auf diesen Beitrag antworten » | ||
Ja, die Voraussetzung n>0 war mir jederzeit bewußt, wenngleich es stimmt, dass ich sie nirgendwo erwähnt habe...Ganz im Gegensatz eben zur Tatsache, dass man vollständige Induktion oder überhaupt ein induktives Argument bei meiner Argumentation ja eigentlich gar nicht braucht, was mir peinlicherweise lange überhaupt nicht aufgefallen ist... Erst bei der Betrachtung der Permutation auf für ein festes , die ja in der Zyklendarstellung nur Zyklen der Länge 2 hat, ist es mir dann wie Schuppen von den Augen gefallen... Noch peinlicher hätte es für mich allerdings kommen können, wenn ich durch den Threadersteller darauf hingewiesen worden wäre, wozu es dann gottseidank doch nicht gekommen ist...
|
||||
| 12.10.2012, 19:05 | Carren | Auf diesen Beitrag antworten » | ||
Hallo, Ich habe fleißig eure Diskussion verfolgt und finde den beweis von Mystic sehr elegant. Ich habe eine Frage zu deiner Schreibweise: Warum nimmst du die Verknüpfung [latex]\Delta[\latex] ? Ich kenne diese nur als begriff für eine Differenz beim Differentialquotienten. Ich hoffe du kannst mir das vlt kurz erklären. LG |
||||
| 12.10.2012, 20:09 | Mystic | Auf diesen Beitrag antworten » | ||
Für zwei Teilmengen A und B einer Menge M ist und wird symmetrische Differenz von A und B genannt... Obige Abbildung ist damit (für eines festes ) eine Involution (=selbstinvers) auf und wird mit der Verknüpfung zu einer abelschen Gruppe... |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
