Beweis verifizieren: Laminare Familien

01.10.2007, 20:54

Tobias

Beweis verifizieren: Laminare Familien

Hallo zusammen, für eine Arbeit benötige ich einen Beweis. Vielleicht hat jemand von euch Lust, ihn auf Korrektheit zu überprüfen, da ich mir unsicher bin, etwas übersehen zu haben.

Zuerst die Definitionen:

Zwei Mengen A und B kreuzen sich, wenn sowohl die Schnittmenge als auch A\B und B\A nicht leer sind. Sie kreuzen sich also nicht, wenn sie disjunkt sind oder eine Menge in der anderen enthalten ist.

Eine Mengenfamilie $\begin{eqnarray*} L \subseteq \operatorname{Pot}(U) \end{eqnarray*}$ zu einer endlichen Trägermenge U heißt laminar, wenn alle Elemente (Mengen) sich paarweise nicht kreuzen.

Nun der Satz:
Jede laminare Familie L zur Trägermenge U, die keine einelementigen Mengen enthält, hat maximal |U| - 1 Elemente.

Und mein Beweis (?):

Induktion nach |U|.

I.A.: Jede zweielementige Trägermenge U hat nur eine laminare Familie, nämlich L = {U}. |L| = 2 - 1 = 1.

I.V.: Für jede Trägermenge $\begin{eqnarray*} U' \subset U \end{eqnarray*}$ und jede beliebige laminare Familie zur Trägermenge U' gilt die Behauptung.

I.S.: Die Idee ist, sich aus einer maximalen laminaren Familie soviele disjunkte Mengen wie möglich rauszunehmen. Damit die Induktionshypothese anwendbar ist lasse ich U nicht zu: $\begin{eqnarray*} U_1, \ldots, U_k \in L \backslash \{U\} \end{eqnarray*}$ paarweise disjunkt. Außerdem soll es keine Menge geben, die Obermenge eines der $\begin{eqnarray*} U_i \end{eqnarray*}$ ist: Für alle $\begin{eqnarray*} U' \in L \backslash \{U, U_1, \ldots, U_k \} \end{eqnarray*}$ gilt $\begin{eqnarray*} U' \subset U_i \end{eqnarray*}$ für ein i. Zu jeder Menge $\begin{eqnarray*} U_i \end{eqnarray*}$ wähle ich eine maximale (im Sinne der Kardinalität) laminare Familie $\begin{eqnarray*} L_i \end{eqnarray*}$ mit Trägermenge $\begin{eqnarray*} U_i \end{eqnarray*}$ .

Damit folger ich dann mit I.V.:
$\begin{eqnarray*} |L| = |L_1| + \ldots + |L_k| + 1 \leq (|U_1|-1) + \ldots + (|U_k| - 1) + 1 \leq |U| + k - 1 \end{eqnarray*}$

Wie man sieht geht die Ungleichung also für k > 1 auf. Den Fall k=1 kann man leicht über die Maximalitätsvoraussetzung von L ausschließen:

Ist $\begin{eqnarray*} |U \backslash U_1| \geq 2 \end{eqnarray*}$ kann ich L durch $\begin{eqnarray*} L \cup (U \backslash U_1) \end{eqnarray*}$ vergrößern.
Ist $\begin{eqnarray*} |U \backslash U_1| = 1 \end{eqnarray*}$ gilt $\begin{eqnarray*} |L| = |L_1| + 1 \leq |U_1| = |U| - 1 \end{eqnarray*}$

q.e.d. ?

02.10.2007, 22:22

Abakus

Auf diesen Beitrag antworten »

RE: Beweis verifizieren: Laminare Familien

Zitat:

Original von Tobias
Und mein Beweis (?):

Induktion nach |U|.

Wieso zeigst du nicht, dass jede Familie mit mehr oder gleich |U|-vielen Elementen die geforderten Eigenschaften nicht haben kann ? Dazu kämen ggf. noch weitere Überlegungen.

Eine Induktion passt eigentlich nicht richtig, da es ja nur endlich viele Fälle gibt.
Durch deinen I.S. sehe ich nicht richtig durch (mag ja angehen?).

Grüße Abakus smile

02.10.2007, 22:45

Tobias

Auf diesen Beitrag antworten »

RE: Beweis verifizieren: Laminare Familien
Erstmal danke für deine Antwort.

Zitat:

Wieso zeigst du nicht, dass jede Familie mit mehr oder gleich |U|-vielen Elementen die geforderten Eigenschaften nicht haben kann ?

Da fehlen mir die passenden Argumente.

Zitat:

Eine Induktion passt eigentlich nicht richtig, da es ja nur endlich viele Fälle gibt.

Das verstehe ich leider nicht. verwirrt

Zitat:

Durch deinen I.S. sehe ich nicht richtig durch (mag ja angehen?).

Meine Hauptidee ist, dass man jede laminare Familie $\begin{eqnarray*} L \end{eqnarray*}$ in k disjunkte laminare Familien aufteilen kann, indem man die "größten" disjunkten Mengen aus L raussucht. Die verbleibenden Mengen sind dann echte Teilmengen einer dieser disjunkten Mengen.

02.10.2007, 23:20

Abakus

Auf diesen Beitrag antworten »

RE: Beweis verifizieren: Laminare Familien

Zitat:

Original von Tobias

Zitat:

Wieso zeigst du nicht, dass jede Familie mit mehr oder gleich |U|-vielen Elementen die geforderten Eigenschaften nicht haben kann ?

Da fehlen mir die passenden Argumente.

Die wären dann zu finden. So wie ich es verstehe, soll U eine endliche Menge sein (?), sei also |U| = n. Angenommen F ist nun eine solche laminare Familie zu U mit (mindestens) n Elementen. Gesucht ist jetzt ein Widerspruch.

Zitat:

Eine Induktion passt eigentlich nicht richtig, da es ja nur endlich viele Fälle gibt.

Das verstehe ich leider nicht. verwirrt

Die Behauptung ist ja nur für eine Familie F mit höchstens (n-1)-vielen Elementen richtig.

Zitat:

Wie lautet deine Induktionsbehauptung erstmal, d.h. was willst du zeigen ?

Grüße Abakus smile

02.10.2007, 23:53

Tobias

Auf diesen Beitrag antworten »

Ich mache Induktion über die Mächtigkeit der Trägermenge U.

Also zu zeigen:

Ist $\begin{eqnarray*} L \subseteq \operatorname{Pot}(U) \end{eqnarray*}$ laminare Familie zu einer endlichen Trägermenge U, dann gilt $\begin{eqnarray*} |L| \leq |U| - 1 \end{eqnarray*}$ .

Meine Induktionshypothese ist, dass für jede laminare Familie $\begin{eqnarray*} L' \subseteq \operatorname{Pot}(U') \end{eqnarray*}$ mit $\begin{eqnarray*} U' \subset U \end{eqnarray*}$ die Behauptung $\begin{eqnarray*} |L'| \leq |U'| - 1 \end{eqnarray*}$ gilt.

03.10.2007, 14:06

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Tobias
Ich mache Induktion über die Mächtigkeit der Trägermenge U.

Also zu zeigen:

Ist $\begin{eqnarray*} L \subseteq \operatorname{Pot}(U) \end{eqnarray*}$ laminare Familie zu einer endlichen Trägermenge U, dann gilt $\begin{eqnarray*} |L| \leq |U| - 1 \end{eqnarray*}$ .

Meine Induktionshypothese ist, dass für jede laminare Familie $\begin{eqnarray*} L' \subseteq \operatorname{Pot}(U') \end{eqnarray*}$ mit $\begin{eqnarray*} U' \subset U \end{eqnarray*}$ die Behauptung $\begin{eqnarray*} |L'| \leq |U'| - 1 \end{eqnarray*}$ gilt.

Ich vermisse erstmal eine Grundmenge, zB kannst du $\begin{eqnarray*} U \subseteq \mathbb R \end{eqnarray*}$ betrachten. Statt Induktionshypothese würde ich eher von Induktionsvoraussetzung sprechen.

OK, jetzt bin ich etwas weitergekommen mit meinem Verständnis und stecke jetzt bei dieser Zeile:

Zitat:

Damit folger ich dann mit I.V.:
$\begin{eqnarray*} |L| = |L_1| + \ldots + |L_k| + 1 \leq (|U_1|-1) + \ldots + (|U_k| - 1) + 1 \leq |U| + k - 1 \end{eqnarray*}$

Die I.V. geht ja nur beim ersten Kleinergleich-Zeichen ein. Wie kommst du auf das erste "=" und das letzte Kleinergleich-Zeichen ?

Grüße Abakus smile

03.10.2007, 14:39

Tobias

Auf diesen Beitrag antworten »

Grundmenge ist U selbst. U kann beliebige endliche Menge sein.

Nun zu deiner Frage:

Beim letzten kleiner-gleich-Zeichen ist mir doch glatt nen Verdreher passiert:
Es muss - k + 1 heißen und nicht +k - 1.

Also:

$\begin{eqnarray*} (|U_1| - 1) + \ldots + (|U_k| - 1) + 1 = (|U_1| + \ldots + |U_k|) - k + 1 \leq |U| - k + 1 \end{eqnarray*}$ .

Da die $\begin{eqnarray*} U_i \end{eqnarray*}$ paarweise disjunkt sind, gilt $\begin{eqnarray*} |U| \geq \sum_{i=1}^{k} |U_i| \end{eqnarray*}$ .

So ist die Behauptung jetzt auch für k > 1 gültig. Sorry für diesen kleinen Dreher.

Nun zur ersten Gleichung:
$\begin{eqnarray*} |L| = \sum_{i=1}^{k}|L_i| + 1 \end{eqnarray*}$

Ich habe L als maximale laminare Familie angenommen. L kann nur dann maximal sein, wenn alle in L echt enthaltenen laminare Teilfamilien maximale Größe haben. Außerdem ist in jedem maximalen L auch immer die Trägermenge selbst drin (deshalb + 1 am Ende).

Ich habe die $\begin{eqnarray*} U_i \end{eqnarray*}$ ja paarweise disjunkt gewählt. Daraus folgt, dass auch die maximalen laminaren Familien $\begin{eqnarray*} L_i \end{eqnarray*}$ paarweise disjunkt sind. Also $\begin{eqnarray*} L = \bigcup_{i=1}^{k} L_i \cup \{U\} \end{eqnarray*}$ .

Edit: Skizze angehängt:
Der große Kreis ist die Trägermenge von L, also U. Die grauen Kreise sind die U_i. Sie sind disjunkt und es gibt in $\begin{eqnarray*} L \backslash \{U\} \end{eqnarray*}$ keine Mengen, die Obermengen dieser $\begin{eqnarray*} U_i \end{eqnarray*}$ sind.

03.10.2007, 17:40

Abakus

Auf diesen Beitrag antworten »

Zitat:

Grundmenge ist U selbst. U kann beliebige endliche Menge sein.

U selbst ist ja variabel, da du die Behauptung für alle endlichen Mengen zeigen willst. Und die "Menge" aller endlichen Mengen ist wohl keine Menge mehr, sondern eine Klasse. Ohne irgendeine Grundmenge oder weitere Überlegungen läufst du hier in logische Probleme rein, aber es ist ja kein Problem hier eine Grundmenge festzulegen.

Einmal angenommen, du hättest folgendes gezeigt:

$\begin{eqnarray*} |L| \leq |U| - k + 1 \end{eqnarray*}$ .

Was wäre nun gewonnen ? Diese Ungleichung brauchst du genau für $\begin{eqnarray*} k = 2 \end{eqnarray*}$ , nicht jedoch für irgendein $\begin{eqnarray*} k \end{eqnarray*}$ .

Ich gehe dabei davon aus, dass die zu zeigende Ungleichung scharf ist und nicht verbessert werden kann.

Grüße Abakus smile

03.10.2007, 17:58

Tobias

Auf diesen Beitrag antworten »

Also ich sehen keinen Grund die Menge U in irgendeiner Weise einschränken zu müssen. Sie hat die Eigenschaft "endlich" und das reicht. Ob sie aus Äpfeln oder Birnen besteht ist ja egal.

Das k muss ich erstmal einsetzen um die Allgemeingültigkeit meines Beweises aufrecht zu erhalten. Am Ende des Beweises stellt sich dann heraus, dass die Gleichung für k=2 "maximale Schärfe" hat. Dies ist ein nettes Nebenprodukt, zeigt es doch, dass eine laminare Familie L dann maximal groß ist, wenn die maximalen laminaren Teilfamilien zu den Trägermengen $\begin{eqnarray*} S \end{eqnarray*}$ und $\begin{eqnarray*} U\backslash S \end{eqnarray*}$ in ihr vorkommen (für eine Menge $\begin{eqnarray*} S \subset U \end{eqnarray*}$ ).

03.10.2007, 20:29

Abakus

Auf diesen Beitrag antworten »

Zitat:

Original von Tobias
Also ich sehen keinen Grund die Menge U in irgendeiner Weise einschränken zu müssen. Sie hat die Eigenschaft "endlich" und das reicht. Ob sie aus Äpfeln oder Birnen besteht ist ja egal.

Du sagst ja, U ist eine Menge. Mengen kommen nach den Axiomen der Mengenlehre aber irgendwo her. Du könntest zB in deiner Klasse die Äquivalenzrelation "gleichmächtig" einführen und mit den Äquivalenzklassen arbeiten.

Zitat:

Das k muss ich erstmal einsetzen um die Allgemeingültigkeit meines Beweises aufrecht zu erhalten. Am Ende des Beweises stellt sich dann heraus, dass die Gleichung für k=2 "maximale Schärfe" hat. Dies ist ein nettes Nebenprodukt, zeigt es doch, dass eine laminare Familie L dann maximal groß ist, wenn die maximalen laminaren Teilfamilien zu den Trägermengen $\begin{eqnarray*} S \end{eqnarray*}$ und $\begin{eqnarray*} U\backslash S \end{eqnarray*}$ in ihr vorkommen (für eine Menge $\begin{eqnarray*} S \subset U \end{eqnarray*}$ ).

Du könntest ggf. gleich von k=2 ausgehen, indem du (k-1)-viele Mengen deiner Zerlegung zu einer zusammenfasst. Wie du das genau formulierst, kannst du ja noch überlegen. In jedem Fall musst du den Fall k=2 speziell betrachten.

So wie jetzt zeigst du wohl etwas mehr als die Behauptung dann und könntest die Struktur solcher laminarer Familien noch besser beschreiben (nämlich unter welchen Bedingungen es bessere Schranken in der zu zeigenden Ungleichung gibt).

Grüße Abakus smile

Neue Frage »

Antworten »

Beweis verifizieren: Laminare Familien

Verwandte Themen