Vollständige Induktion und Mengen |
| 22.11.2005, 16:32 | Folliot | Auf diesen Beitrag antworten » |
| Vollständige Induktion und Mengen mit Hilfe der vollständigen Induktion ist zu beweisen: Ist A eine endliche Menge und B eine Teilmenge von A, so ist auch B eine endliche Menge und es gilt |B|<=|A|. Dass es tatsächlich so ist, leuchtet ohne Frage jedem ein. Mir ist ferner auch klar, wie vollständige Induktion funktioniert, nur mit dieser Methode auf Mengen zu operieren ist mir irgendwie unklar, auch wenn Mengen letzten Endes nichts anderes sind als z.B. die Menge der natürlichen Zahlen (selbstverständilich inkl. der Null)... Behaupt: s.o. Mein Beweisansatz: (Induktion über die Elemente) I.A.: Für |A|=0 gilt A={}. (Also A entspricht der leeren Menge, und somit der kleinsten anzunehmenden Menge) Dann gilt auch für jede Teilmenge von A, also auch für die Teilmenge B: |B|=0. I.S.: n ->n+1 A sei eine endliche Menge mit |A|=n+1 Elementen. Dann gilt für die Mächtigkeit der Teilmenge B: |B|<=n+1. Also: und A Teilmenge von B. Es existieren also n+1 Elemente in A, und da laut Induktionsvoraussetzung B Teilmenge von A ist, kann B entweder leer sein oder enthält ebenfalls eines dieser n+1 Elemente. Hier sehe ich dann nur folgende zwei Fälle: A enthält lediglich ein Element, oder A enthält mehr Elemente. In jedem Fall ist B höchstens gleichmächtig wie A oder enthält weniger Elemente. In jedem Fall ist B aber endlich, da A endlich ist. So und nun?!? Mit diesem Ansatz weiss ich nicht weiter was es da zu beweisen gibt...Und auch nicht so recht, wie dies formal zu Papier zu bringen ist... In der Übungsgruppe wurde noch folgendes dazu gesagt, dass im Induktionsschritt/-schluss zwei Fälle zu unterscheiden sind: Fall 1 leuchtet ein und entspricht dem was ich oben bereits sprachlich formuliert habe. Den zweiten Fall verstehe ich nicht. Ich habe hier in Klammern das dahinter ausgeführt, so wie ich dieses deute... 1) A'= A\{a} >= B (A' entspricht also der Menge A ohne das Element a UND ist grösser / gleich B. Damit ist offen ob A' Elemente enthält, oder auch leer ist, denn in jedem Fall ist A' ja "kleinstensfalls" gleich B. Somit ist die Behauptung erfüllt) 2) A' ist keine Teilmenge von B B'=B'\{a} ist Teilmenge von A (also B' ist quasi eine leere Menge und die ist bekanntlich Teilmenge jeder Menge), |B|=|B'|+1<=|A'|+|A| Jetzt bin ich über schnelle Hilfe sehr dankbar! Grüsse & schon einmal vielen Dank für Eure Mühe, Folliot |
||
| 22.11.2005, 19:08 | irre.flexiv | Auf diesen Beitrag antworten » |
Du musst immer die Induktionsvoraussetzung im Auge haben. Ist und so ist . Im IS betrachtest du nun die Menge mit . Nun ist die Frage ob auch gilt. Jetzt kann es ja sein das dieses a in B ist oder auch nicht, genau die beiden Fälle musst du unterscheiden. Wenn nämlich a nicht in B ist dann ist B auf jeden Fall Teilmenge A'. Wenn aber a in B ist dann ist B natürlich keine Teilmenge von A'. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
