www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Analysis-Induktion" - Regel von de Morgan
Regel von de Morgan < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Regel von de Morgan: Tipp/Korrektur
Status: (Frage) beantwortet Status 
Datum: 12:59 Mo 03.11.2014
Autor: Martin_Ph

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



        
Bezug
Regel von de Morgan: Antwort
Status: (Antwort) fertig Status 
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
>  
>  


Bezug
                
Bezug
Regel von de Morgan: Rückfrage
Status: (Frage) beantwortet Status 
Datum: 14:12 Mo 03.11.2014
Autor: Martin_Ph

Aufgabe
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?

Bezug
                        
Bezug
Regel von de Morgan: Antwort
Status: (Antwort) fertig Status 
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$.)

Bezug
                        
Bezug
Regel von de Morgan: Antwort
Status: (Antwort) fertig Status 
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

Bezug
        
Bezug
Regel von de Morgan: Antwort
Status: (Antwort) fertig Status 
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]


> 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

Bezug
                
Bezug
Regel von de Morgan: IS
Status: (Frage) beantwortet Status 
Datum: 16:11 Di 04.11.2014
Autor: Martin_Ph

Aufgabe
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?

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

Bezug
                        
Bezug
Regel von de Morgan: Antwort
Status: (Antwort) fertig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Analysis-Induktion"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]