Regel von de Morgan < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] n\ge3 [/mm] und die Mengen [mm] M_{i}(i=1,...,n) [/mm] Teilmengen einer Menge X. Beweisen Sie mit vollständiger Induktion die allgemeinere Form der Regel von de Morgan
[mm] C_{X}(\bigcup_{i=1}^{n}M_{i})=\bigcap_{i=1}^{n}C_{X}(M_{i})
[/mm]
Hinweis: Sie dürfen ohne Beweis die zugehörige Regel von de Morgan für zwei Elemente verwenden |
IA: Sei n=3
[mm] C_{X}(\bigcup_{i=1}^{3}M_{i})=C_{X}(M_{1}\cup M_{2}\cup M_{3})=\bigcap_{i=1}^{3}C_{X}(M_{i})=C_{x}(M_{1})\cap C_{x}(M_{2})\cap C_{x}(M_{3})=(C_{x}(M_{1})\cap C_{x}(M_{2}))\cap C_{x}(M_{3})=C_{x}(M_{1}\cup M_{2})\cap C_{x}(M_{3}=C_{x}(M_{1}\cup M_{2}\cup M_{3}) [/mm] // IA stimmt somit. Allerdings bin ich mir nicht sicher ob ich es mir nicht zu leicht gemacht hab
IV: Für ein [mm] n\ge3 [/mm] gilt: [mm] C_{X}(\bigcup_{i=1}^{n}M_{i})=\bigcap_{i=1}^{n}C_{X}(M_{i})
[/mm]
IS: [mm] n\rightarrow [/mm] n+1
[mm] C_{X}(\bigcup_{i=1}^{n+1}M_{i})=C_{X}(\bigcup_{i=1}^{n}M_{i}\cup M_{n+1})=^{(IV)} \bigcap_{i=1}^{n}C_{X}(M_{i})\cap M_{n+1}=C_{X}(M_{1})\cap C_{X}(M_{2})\cap C_{X}(M_{3})\cap...\cap C_{X}(M_{n})\cap C_{X}(M_{n+1})=\bigcap_{i=1}^{n+1}C_{X}(M_{i})
[/mm]
Das ist meine Lösung zu dieser Aufgabe, allerdings kam mir das ein bißchen einfach vor.
Wäre schön wenn mal jmd drübergucken könnte
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:07 Mo 03.11.2014 | | Autor: | fred97 |
> Sei [mm]n\ge3[/mm] und die Mengen [mm]M_{i}(i=1,...,n)[/mm] Teilmengen einer
> Menge X. Beweisen Sie mit vollständiger Induktion die
> allgemeinere Form der Regel von de Morgan
>
> [mm]C_{X}(\bigcup_{i=1}^{n}M_{i})=\bigcap_{i=1}^{n}C_{X}(M_{i})[/mm]
>
> Hinweis: Sie dürfen ohne Beweis die zugehörige Regel von
> de Morgan für zwei Elemente verwenden
> IA: Sei n=3
>
> [mm]C_{X}(\bigcup_{i=1}^{3}M_{i})=C_{X}(M_{1}\cup M_{2}\cup M_{3})=\bigcap_{i=1}^{3}C_{X}(M_{i})=C_{x}(M_{1})\cap C_{x}(M_{2})\cap C_{x}(M_{3})=(C_{x}(M_{1})\cap C_{x}(M_{2}))\cap C_{x}(M_{3})=C_{x}(M_{1}\cup M_{2})\cap C_{x}(M_{3}=C_{x}(M_{1}\cup M_{2}\cup M_{3})[/mm]
> // IA stimmt somit. Allerdings bin ich mir nicht sicher ob
> ich es mir nicht zu leicht gemacht hab
Nein, zu schwer ! Mach doch den IA für n=2 und verwende den Hinweis.
>
> IV: Für ein [mm]n\ge3[/mm] gilt:
Die IV würde ich für n [mm] \ge [/mm] 2 formulieren.
> [mm]C_{X}(\bigcup_{i=1}^{n}M_{i})=\bigcap_{i=1}^{n}C_{X}(M_{i})[/mm]
>
> IS: [mm]n\rightarrow[/mm] n+1
>
> [mm]C_{X}(\bigcup_{i=1}^{n+1}M_{i})=C_{X}(\bigcup_{i=1}^{n}M_{i}\cup M_{n+1})=^{(IV)} \bigcap_{i=1}^{n}C_{X}(M_{i})\cap M_{n+1}=C_{X}(M_{1})\cap C_{X}(M_{2})\cap C_{X}(M_{3})\cap...\cap C_{X}(M_{n})\cap C_{X}(M_{n+1})=\bigcap_{i=1}^{n+1}C_{X}(M_{i})[/mm]
Das mit den ...... kannst Du nicht machen.
Setze [mm] M_0:=\bigcup_{i=1}^{n}M_{i}
[/mm]
Dann ist [mm] C_{X}(\bigcup_{i=1}^{n+1}M_{i})=C_X(M_0 \cup M_{n+1}).
[/mm]
Mit dem Hinweis ist dann
[mm] C_{X}(\bigcup_{i=1}^{n+1}M_{i})=C_X(M_0) \cap C_X(M_{n+1})
[/mm]
Jetzt verwende die IV.
FRED
>
> Das ist meine Lösung zu dieser Aufgabe, allerdings kam mir
> das ein bißchen einfach vor.
> Wäre schön wenn mal jmd drübergucken könnte
>
>
|
|
|
| |
|
Darf ich n=2 überhaupt machen, da doch [mm] n\ge3 [/mm] sein muss
Bei Produkten und Summen darf ich doch auch ... machen warum ist das also hier nicht erlaubt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:16 Mo 03.11.2014 | | Autor: | tobit09 |
> Darf ich n=2 überhaupt machen, da doch [mm]n\ge3[/mm] sein muss
Niemand verbietet uns, folgende Behauptung zu beweisen:
Sei [mm] $n\ge\green{2}$ [/mm] und die Mengen [mm] M_{i}(i=1,...,n) [/mm] Teilmengen einer Menge X. Dann gilt [mm] C_{X}(\bigcup_{i=1}^{n}M_{i})=\bigcap_{i=1}^{n}C_{X}(M_{i}) [/mm] .
Die Behauptung aus der Aufgabenstellung folgt dann daraus:
Wenn etwas für alle [mm] $n\ge2$ [/mm] gilt, gilt es erst recht für alle [mm] $n\ge3$.
[/mm]
(Tatsächlich gilt die behauptete Gleichung auch für $n=1$.)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:03 Mo 03.11.2014 | | Autor: | Marcel |
Hallo,
> siehe vorherige
> Darf ich n=2 überhaupt machen, da doch [mm]n\ge3[/mm] sein muss
>
> Bei Produkten und Summen darf ich doch auch ... machen
> warum ist das also hier nicht erlaubt?
in Beweisen schreibt man meist .... dann, wenn man "schlampig" das machen
will, was man sauber in einem Induktionsbeweis verpacken könnte.
In der Tat kannst Du auch (ich nehme mal die von Tobi korrigierte Version)
[mm] $\underbrace{\bigcap_{i=1}^n C_X(M_i) \cap C_X(M_{n+1})}_{\text{wohl zu lesen als }\left(\bigcap_{i=1}^n C_X(M_i)\right) \cap C_X(M_{n+1})}=\left(C_X(M_1) \cap ... \cap C_X(M_n)\right) \cap C_X(M_{n+1})$
[/mm]
schreiben, und dann mit einer kleinen Begründung sagen, warum die Klammer
da weggelassen werden darf. Aber bringt Dir das was?
Und ich glaube, worauf Fred eigentlich hinweisen wollte:
Auf
[mm] $C_X(\left(\bigcup_{i=1}^n M_i\right) \cup M_{n+1})$
[/mm]
kannst Du die erwähnte Regel aus dem Hinweis anwenden - tatsächlich
kann man auch anders argumentieren, denn im Endeffekt machen wir
ja nichts anderes, als die Induktionsvoraussetzung für [mm] $n=2\,$ [/mm] zu benutzen.
(Es gibt dahingehend auch noch eine "Variante der Beweismethode mit
vollständiger Induktion":
Zu zeigen sei etwa, dass eine Aussage [mm] $A(n)\,$ [/mm] für alle $n [mm] \in \IN$ [/mm] gelte. Dann macht
man den Induktionsstart mit [mm] $n=1\,.$ [/mm] (Bei mir ist $0 [mm] \notin \IN$!). [/mm] Beim Induktionsschritt
sagt man aber dann nicht nur: "Sei $A(n)$ wahr für ein $n [mm] \in \IN\,.$ [/mm] Dann..."
sondern man sagt:
"Seien [mm] $A(k)\,$ [/mm] wahr für $k=1,...,n$ mit einem $n [mm] \in \IN\,.$ [/mm] Dann...")
Jedenfalls siehst Du damit
[mm] $C_X(\left(\bigcup_{i=1}^n M_i\right) \cup M_{n+1})=\red{\left(C_X(\bigcup_{i=1}^n M_i)\right)\,} \cap C_X(M_{n+1})\,.$
[/mm]
Und erst jetzt kannst Du die I.V. (für [mm] $n\,$) [/mm] auf den rotmarkierten Teil anwenden.
Und DANACH kannst Du dann
[mm] $\left(\bigcap_{i=1}^n C_X(M_i)\right) \cap C_X(M_{n+1})=\left(C_X(M_1) \cap ... \cap C_X(M_n)\right) \cap C_X(M_{n+1})$
[/mm]
schreiben - ich glaube, Fred hatte da eher Problem mit dem Zeitpunkt, an
dem Du das gemacht hast.
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:10 Mo 03.11.2014 | | Autor: | tobit09 |
Hallo Martin_Ph!
> IA: Sei n=3
>
> [mm]C_{X}(\bigcup_{i=1}^{3}M_{i})=C_{X}(M_{1}\cup M_{2}\cup M_{3})=\bigcap_{i=1}^{3}C_{X}(M_{i})[/mm]
Das hintere $=$ ist unbewiesen.
Wenn du es bewiesen hättest, wärst du hier mit dem Induktionsanfang fertig.
Wenn du jedoch nur den hinteren Teil deiner Gleichungs-Kette nimmst...
> [mm]\bigcap_{i=1}^{3}C_{X}(M_{i})=C_{x}(M_{1})\cap C_{x}(M_{2})\cap C_{x}(M_{3})=(C_{x}(M_{1})\cap C_{x}(M_{2}))\cap C_{x}(M_{3})=C_{x}(M_{1}\cup M_{2})\cap C_{x}(M_{3}=C_{x}(M_{1}\cup M_{2}\cup M_{3})[/mm]
...und [mm] $=C_X(\bigcup_{i=1}^3 M_i)$ [/mm] ergänzt, dann hast du den Induktionsanfang erledigt.
> IV: Für ein [mm]n\ge3[/mm] gilt:
> [mm]C_{X}(\bigcup_{i=1}^{n}M_{i})=\bigcap_{i=1}^{n}C_{X}(M_{i})[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> IS: [mm]n\rightarrow[/mm] n+1
>
> [mm]C_{X}(\bigcup_{i=1}^{n+1}M_{i})=C_{X}(\bigcup_{i=1}^{n}M_{i}\cup M_{n+1})=^{(IV)} \bigcap_{i=1}^{n}C_{X}(M_{i})\cap M_{n+1}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Das hintere Gleichheitszeichen stimmt im Allgemeinen nicht.
(Falls du dich verschrieben hast und hinten $C_X(M_{n+1})$ anstelle von $M_{n+1}}$ meintest, ist dieser Schritt nicht mehr falsch, aber unbewiesen.)
> [mm]=C_{X}(M_{1})\cap C_{X}(M_{2})\cap C_{X}(M_{3})\cap...\cap C_{X}(M_{n})\cap C_{X}(M_{n+1})=\bigcap_{i=1}^{n+1}C_{X}(M_{i})[/mm]
Das vordere Gleichheitszeichen stimmt im Allgemeinen nicht.
Viele Grüße
Tobias
|
|
|
| |
|
Ja hab mich da leider verschrieben.
Sollte [mm] C_{X}(M_{n+1}) [/mm] heißen.
Darf ich es dann trotzdem verwenden obwohl es nicht bewiesen ist?
Ich beweise es doch eig im IS oder?
Man darf doch die IV verwenden, hängt das fehlende Glied dran und löst dann wie getan auf.
oder muss ich wirklich alles für [mm] n\ge2 [/mm] machen, da das als bewiesen gilt?
Allerdings würde dann mein Induktionsschritt genauso aussehen
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:03 Di 04.11.2014 | | Autor: | Marcel |
Hallo,
> siehe vorherige
> Ja hab mich da leider verschrieben.
> Sollte [mm]C_{X}(M_{n+1})[/mm] heißen.
>
> Darf ich es dann trotzdem verwenden obwohl es nicht
> bewiesen ist?
da der Aufgabensteller es Dir so erlaubt hat: Ja. Du musst dann halt mit
dem *schlechten Gewissen* leben, oder aber:
Du beweist diese einfache Gleichheit einfach selbst.
> Ich beweise es doch eig im IS oder?
Nein - denn dort brauchst Du insbesondere, dass Du die Induktionsannahme
für [mm] $n=2\,$ [/mm] überhaupt benutzen darfst. Das steht übrigens deutlich in meiner
Antwort!
> Man darf doch die IV verwenden, hängt das fehlende Glied
> dran und löst dann wie getan auf.
>
> oder muss ich wirklich alles für [mm]n\ge2[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
machen, da das als
> bewiesen gilt?
Wenn das für alle $n \ge 2$ als bewiesen gelten würde, hättest Du nichts
mehr zu zeigen!
> Allerdings würde dann mein Induktionsschritt genauso
> aussehen
Ich schreib's Dir jetzt mal hin:
Behauptung:
$C_X(\bigcup_{i=1}^n M_i)=\bigcap_{i=1}^n C_X(M_i)$
gilt für alle natürlichen $n \ge 2\,.$
I.A. Für $n=2$ gilt
$C_X(\bigcup_{i=1}^2 M_i)=\bigcap_{i=1}^2 C_X(M_i)\,,$
anders gesagt
$C_X(M_1 \cup M_2)=C_X(M_1) \cap C_X(M_2)\,.$
Wir schreiben das mal als
$C_X(A \cup B)=C_X(A) \cap C_X(B)\,,$
wobei $A,B \subseteq X\,.$ Der Grund ist einfach:
Die Aussage für $n=2\,$ gilt ja für alle Teilmengen $M_1,M_2 \subseteq X\,.$ Nachher
werden wir aber wenigstens eine dieser Mengen nicht mehr mit $M_1$ oder die
andere nicht mehr mit $M_2$ benennen können.
Und entweder, Du sagst nun: "Okay, obiges darf ich verwenden, weil der
Aufgabensteller so glaubwürdig ist, dass ich einfach glaube, dass er damit
auch recht hat."
oder Du beweist diese Gleichung selber.
I.V.: Es sei nun $n \in \IN$ so, dass
$(\*)$ $C_X(\bigcup_{i=1}^n M_i)=\bigcap_{i=1}^n C_X(M_i)$
für alle (irgendwie gewählten) Teilmengen $M_1,...,M_n$ von $X\,.$
I.S. $n \to n+1$: Zu zeigen: Sind nun die $n+1$ Teilmengen
$M_1,...,M_n,M_{n+1}$
von $X\,$ gegeben (die könnte man jetzt auch anders benennen, aber hier
ist das egal, da in der I.V. ja die $M_j$ irgendwelche(!) Teilmengen von
$X\,$ sein dürfen $^{\red{(\*), s.u}$), dann gilt
$C_X(\bigcup_{i=1}^{n+1} M_i)=\bigcap_{i=1}^{n+1}C_X(M_i)\,.$
Beweis: Wir setzen
$A:=\bigcup_{i=1}^{n} M_i$ und $B:=M_{n+1}\,.$
Wegen
$C_X(A \cup B)=C_X(A) \cap C_X(B)$ (das ist nichts anderes, als die zu beweisende
Aussage für $n=2\,,$ wie bereits schon öfters gesagt)
gilt dann
$C_X(\bigcup_{i=1}^{n+1} M_i)=C_X\red{\,(\,}\left(\bigcup_{i=1}^{n} M_i\right) \cup M_{n+1}\red{\,)\,}=C_X(\blue{\bigcup_{i=1}^{n} M_i})$ $\cap$ $C_X(M_{n+1})\,.$
Auf den blauen Teil darfst Du nun(!!!)
($\*$)
anwenden, und es folgt damit und mit obigem erstmal
$C_X(\bigcup_{i=1}^{n+1} M_i)=\left(\bigcap_{i=1}^n C_X(M_i)\right) \cap C_X(M_{n+1})\,.$
Das ist aber auch schon die Behauptung, weil...?
---
$\red{\*}$ Bemerkung:
Du könntest im I.S. auch erstmal die zu beweisende Aussage mit Mengen
$Y_1,...,Y_{n+1} \subseteq X$
formulieren. Dann würdest Du halt
$M_1:=Y_1,$ ..., $M_n:=Y_n$
setzen, um mit den Bezeichnungen der I.V. am Ende den Induktionsschritt
unter Verwendung der Induktionsvoraussetzung (für $n\,$) zu vollenden!
(Das, was ich oben zuvor gemacht habe, wird dann auch dort genauso
gemacht werden.)
Gruß,
Marcel
|
|
|
|
