System von Mengen: Beweis

07.10.2008, 22:44

eierkopf1

System von Mengen: Beweis

Hallo!

Wieder ein Beispiel, bei dem ich eigentlich die Lösung weiß, aber den Beweis nicht schaffe auszudrücken bzw. nicht weiß, was als Beweis gilt und was nicht:

Es $\begin{eqnarray*} M_j \end{eqnarray*}$ , $\begin{eqnarray*} j \in J \end{eqnarray*}$ , ein System von Mengen mit $\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \end{eqnarray*}$ . Gibt es stets zwei Mengen $\begin{eqnarray*} M_{j1}, M_{j2} \in F \end{eqnarray*}$ mit $\begin{eqnarray*} M_{j1} \cap M_{j2} =\emptyset \end{eqnarray*}$ ? (Beweis oder Gegenbeispiel).

Mein Lösungsansatz:

Das sollte bewiesen werden:
$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to M_{j1} \in F \cap M_{j2} \in F = \emptyset \end{eqnarray*}$

Ich weiß nicht, wie ich das beweisen soll. Aber es ist doch klar, wenn das System von Mengen keine Elemente enthält, dass auch 2 Teilmengen davon geschnitten leer sind, oder?

Wie beweise ich das?

mfg

07.10.2008, 23:14

Jacques

Auf diesen Beitrag antworten »

Hallo,

Nur um die Bezeichnungen zu klären: F ist der Name für das Mengensystem, oder?

Also

$\begin{eqnarray*} F = \{ M_j \,|\, j \in J \} \end{eqnarray*}$

Die Frage ist dann:

Wenn der Durchschnitt über dem Mengensystem, also

$\begin{eqnarray*} \bigcap_{j \in J} M_j = M_{j_1} \cap M_{j_2} \cap M_{j_3} \cap \ldots \end{eqnarray*}$

leer ist, gibt es dann mindestens zwei Mengen des Systems, die disjunkt sind?

Versuche es mal mit der Gegenannahme.

// edit:

Zitat:

Original von eierkopf1

Das sollte bewiesen werden:
$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to M_{j1} \in F \cap M_{j2} \in F = \emptyset \end{eqnarray*}$

Da würde ich Quantoren benutzen, und die „Relationskette“ rechts nebem dem Implikationspfeil kann man nicht eindeutig interpretieren -- die kann alles Mögliche bedeuten.

07.10.2008, 23:50

eierkopf1

Auf diesen Beitrag antworten »

Danke für die Antwort!

Das mit $\begin{eqnarray*} \in F \end{eqnarray*}$ kommt mir auch seltsam vor. Aber F ist niergends definiert. Und das Megensystem heißt $\begin{eqnarray*} M_j \end{eqnarray*}$ . verwirrt

Ich ignoriere F einfach mal bzw. denke, dass es in diesem Fall bedeutungslos ist.

Zur Relationskette:
So OK?

$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \forall M_{j1}, M_{j2} \in F: M_{j1} \cap M_{j2} = \emptyset \end{eqnarray*}$

Mein Beweis:
Ich nehme die Gegenrichtung (kann man das so ausdrücken) an:

$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cup M_{j2} = \emptyset \to FALSCH \end{eqnarray*}$

Wenn der Druchschnitt des Mengensystems $\begin{eqnarray*} M_j \end{eqnarray*}$ mit ..... leer ist, dann exestieren KEINE Teilmengen ( $\begin{eqnarray*} M_{j1} \end{eqnarray*}$ ist doch Teilmenge vom Mengensystem oder?) $\begin{eqnarray*} M_{j1} \end{eqnarray*}$ und $\begin{eqnarray*} M_{j2} \end{eqnarray*}$ aus F, für die gilt, dass ihre Vereinigungsmenge leer ist.

Darum gilt:
$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \forall M_{j1}, M_{j2} \in F: M_{j1} \cap M_{j2} = \emptyset \to WAHR \end{eqnarray*}$

Zählt sowas wieder als Beweis? Wenn ja, warum eigentlich?

mfg

08.10.2008, 00:00

Airblader

Auf diesen Beitrag antworten »

Du hast die Behauptung nun falsch notiert.
Es wird nicht behauptet, dass beliebige 2 Mengen einen leeren Schnitt haben, sondern lediglich, dass es stets zwei Mengen gibt, die einen solchen haben.

Also:

$\begin{eqnarray*} \bigcap_{j\in J} M_j = \emptyset ~\Rightarrow~ \exists j_1,j_2 \in J ~:~ M_{j_1} \cap M_{j_2} = \emptyset \end{eqnarray*}$

Das logische Gegenteil davon wäre:

$\begin{eqnarray*} \bigcap_{j\in J} M_j = \emptyset ~\Rightarrow~ \forall j_1,j_2 \in J ~:~ M_{j_1} \cap M_{j_2} \neq \emptyset \end{eqnarray*}$

air

08.10.2008, 00:04

Jacques

Auf diesen Beitrag antworten »

Zitat:

Original von eierkopf1

Zur Relationskette:
So OK?

$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \forall M_{j1}, M_{j2} \in F: M_{j1} \cap M_{j2} = \emptyset \end{eqnarray*}$

Bis auf den Quantor stimmt es:

Die Behauptung lautet, dass es mindestens zwei Mengen des Systems gibt, die disjunkt sind. Du sagst aber aus, dass je zwei Mengen immer disjunkt sind. Letzteres stimmt sicherlich nicht, z. B.: {{1, 2}, {1, 4}, {3, 5}}

Zum Beweis:

Ich würde die Gedanken erstmal in Worte fassen, statt gleich mit dem formalen Beweis anzufangen:

Die Gegenannahme zu „Wenn der Durchschnitt des Systems leer ist, dann gibt es zwei disjunkte Mengen“ lautet: „Es ist möglich, dass zwar der Durchschnitt leer ist, aber je zwei Elemente immer mindestens ein gemeinsames Element haben“.

Führe diese Annahme zu einem Widerspruch. Wenn je zwei Mengen niemals disjunkt sind, dann gibt es ein Objekt, das Element jeder Menge ist.

// edit:

Zitat:

Original von eierkopf1

Mein Beweis:
Ich nehme die Gegenrichtung (kann man das so ausdrücken) an:

$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cup M_{j2} = \emptyset \to FALSCH \end{eqnarray*}$

Das ist nicht richtig -- abgesehen davon, dass man die Schreibweise nicht richtig verstehen kann.

Die Negation von „A --> B“ ist „A und nicht(B)“

Also:

$\begin{eqnarray*} \bigcap_{j \in J} M_j = \varnothing \ \wedge\ \forall M_{j_1}, M_{j_2} \in F : M_{j_1} \cap M_{j_2} \neq \varnothing \end{eqnarray*}$

Zitat:

Original von eierkopf1

Wenn der Druchschnitt des Mengensystems $\begin{eqnarray*} M_j \end{eqnarray*}$ mit ..... leer ist, dann exestieren KEINE Teilmengen ( $\begin{eqnarray*} M_{j1} \end{eqnarray*}$ ist doch Teilmenge vom Mengensystem oder?) $\begin{eqnarray*} M_{j1} \end{eqnarray*}$ und $\begin{eqnarray*} M_{j2} \end{eqnarray*}$ aus F, für die gilt, dass ihre Vereinigungsmenge leer ist.

Wie kommst Du jetzt auf die Vereinigungsmenge?

Und als Begründung reicht das wahrscheinlich nicht aus, denn eigentlich behauptest Du nur etwas.

Zitat:

Original von eierkopf1

( $\begin{eqnarray*} M_{j1} \end{eqnarray*}$ ist doch Teilmenge vom Mengensystem oder?)

Nein, die $\begin{eqnarray*} M_j \end{eqnarray*}$ sind Elemente des Mengensystems.

08.10.2008, 00:09

Airblader

Auf diesen Beitrag antworten »

Man könnte auch über eine Kette gehen, indem man durch fortlaufendes Annehmen der negierten Behauptung zwei Mengen per Schnitt zu einer neuen zusammenfäßt etc.
Dies führt dann am Ende zu einem Widerspruch, da der Schnitt zweier Mengen nach Voraussetzung dann leer ist, die negierte Behauptung jedoch aussagt, dass es kein Paar von Mengen gibt, deren Schnitt leer ist - man hat nun aber nur noch zwei Mengen dortstehen.

air

08.10.2008, 00:44

Jacques

Auf diesen Beitrag antworten »

@ Airblader:

Die Negation oben ist nicht ganz richtig: „nicht(A --> B)“ ist „A und nicht(B)“. Außerdem finde ich es sinnvoll, erstmal einen Ansatz zu verfolgen. ;-)

@ eierkopf1:

Sorry, wenn es brutal klingt, aber Du legst IMHO viel zuviel Wert auf irgendwelche Zeichenketten und verwendest dafür mehr Zeit als für die eigentlichen Inhalte. :-(

Da passieren Dir dann auch die Fehler.

Ich schreibe das nur nochmal, weil es mir bei den anderen Beweisen auch aufgefallen ist.

08.10.2008, 03:20

tmo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \{ \{1,2\} , \{2,3\} , \{1,3\} \} \end{eqnarray*}$ verwirrt

08.10.2008, 06:43

Airblader

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
$\begin{eqnarray*} \{ \{1,2\} , \{2,3\} , \{1,3\} \} \end{eqnarray*}$ verwirrt

mhm .. da muss ich nochmal nachdenken, wo in meiner Vorgehensweise der Fehler stecken muss.

Übrigens: Streng genommen verbietet die Aufgabenstellung gar nicht, dass $\begin{eqnarray*} j_1 = j_2 \end{eqnarray*}$ ist. Damit findet man natürlich immer zwei Mengen mit leerem Schnitt ..
Vermutlich wird aber $\begin{eqnarray*} j_1 \neq j_2 \end{eqnarray*}$ gefordert sein, oder? Augenzwinkern

Edit:
Und dabei dachte ich gestern zunächst auch an ein Gegenbeispiel und hatte praktisch genau das selbe, nur dann übersehen, dass es wirklich eins ist unglücklich

air

08.10.2008, 08:21

eierkopf1

Auf diesen Beitrag antworten »

Danke an alle für die große Mühe Mit Zunge

@Jacques

@ Bis auf den Quantor stimmt es:
Dieses stets (=immer) hat mich etwas verwirrt, deswegen dachte ich zuerst an den Allquantor. Aber jetzt ist mir klar, warum ich den Existenzquantor nehmen muss.

@Zum Beweis: Dein Vorgehen verstehe ich soweit. Nur wie begründe ich das bzw. wie führe ich das zu einem Widerspruch:

"Führe diese Annahme zu einem Widerspruch. Wenn je zwei Mengen niemals disjunkt sind, dann gibt es ein Objekt, das Element jeder Menge ist."

@ $\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cup M_{j2} = \emptyset \to FALSCH \end{eqnarray*}$

Was ist an dieser Schreibweise nicht richtig zu verstehen (außer, dass es falsch negiert ist.)

@Wie kommst Du jetzt auf die Vereinigungsmenge?

Ich dachte, dass wäre dasselbe:

$\begin{eqnarray*} \bigcap_{j \in J} M_j = \varnothing \ \wedge\ \forall M_{j_1}, M_{j_2} \in F : M_{j_1} \cap M_{j_2} \neq \varnothing \end{eqnarray*}$

und
$\begin{eqnarray*} \bigcap_{j \in J} M_j = \varnothing \ \wedge\ \forall M_{j_1}, M_{j_2} \in F : M_{j_1} \cup M_{j_2} =\varnothing \end{eqnarray*}$

@zu viel Wert auf Zeichenketten:
Es stimmt natürlich, was du sagst. Aber ich möchte es auch richtig anschreiben können, da ich auf der Tafel vorrechnen muss und es auch für Prüfungen können muss.
Aber mein größtes Problem ist immer noch: "Wie beweise ich etwas"
Mit Wahrheitstabellen war das noch kein Problem, aber jetzt bin ich mir nie sicher, was ein Beweis ist und was nicht. unglücklich

mfg

08.10.2008, 08:47

papahuhn

Auf diesen Beitrag antworten »

Zitat:

Aber ich möchte es auch richtig anschreiben können, da ich auf der Tafel vorrechnen muss und es auch für Prüfungen können muss.

Dann schau mal tmo's Beitrag.

08.10.2008, 08:53

eierkopf1

Auf diesen Beitrag antworten »

Danke für die Antwort!

Ich verstehe nicht, was du meinst. tmo hat ein Beispiel für das Mengensystem angegeben verwirrt

mfg

08.10.2008, 09:41

Huggy

Auf diesen Beitrag antworten »

tmo hat ein Gegenbeispiel gegeben!
Keine zwei seiner Mengen haben eine leere Schnittmenge. Die Schnittmenge aller drei Mengen ist ab leer.

08.10.2008, 09:42

Jacques

Auf diesen Beitrag antworten »

tmo hat ein Beispiel für ein Mengensystem gegeben, bei dem der Durchschnitt zwar leer ist, aber es trotzdem keine zwei disjunkte Mengen gibt. Damit gibt es ein Gegenbeispiel zu der Behauptung, also ist sie falsch.

Bitte entschuldige, dass Du jetzt die Mühe mit meinem falschen Ansatz hattest. unglücklich

Also mein Fehlschluss lag bei der Gegenannahme: Ich habe von „zwei Mengen sind niemals disjunkt“ auf „es gibt ein Objekt, das Element jeder Menge ist“ geschlossen. Das ist falsch, also führt die Gegenannahme nicht zu einem Widerspruch, und der Beweis funktioniert nicht.

08.10.2008, 10:07

Jacques

Auf diesen Beitrag antworten »

Aber noch zu den Schreibweisen u. s. w.:

Zitat:

Original von eierkopf1

@ $\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cup M_{j2} = \emptyset \to FALSCH \end{eqnarray*}$

Was ist an dieser Schreibweise nicht richtig zu verstehen (außer, dass es falsch negiert ist.)

Es ist einfach gar nicht klar, was Du damit meinst. Was heißt

$\begin{eqnarray*} \rightarrow \mathrm{falsch} \end{eqnarray*}$

?

Dass die ganze Aussage falsch ist? Dass eine falsche Aussage aus ihr folgt?

Zitat:

Original von eierkopf1

@Wie kommst Du jetzt auf die Vereinigungsmenge?

Ich dachte, dass wäre dasselbe:

$\begin{eqnarray*} \bigcap_{j \in J} M_j = \varnothing \ \wedge\ \forall M_{j_1}, M_{j_2} \in F : M_{j_1} \cap M_{j_2} \neq \varnothing \end{eqnarray*}$

und
$\begin{eqnarray*} \bigcap_{j \in J} M_j = \varnothing \ \wedge\ \forall M_{j_1}, M_{j_2} \in F : M_{j_1} \cup M_{j_2} =\varnothing \end{eqnarray*}$

Nein, das würde nur gelten, wenn zwei Mengen genau dann nicht disjunkt wären, wenn ihre Vereinigung die leere Menge ist.

Das stimmt aber nicht, ein Gegenbeispiel: {1, 2}, {2, 3}. Die Mengen sind nicht disjunkt, aber ihre Vereinigung ist trotzdem nicht die leere Menge.

Zitat:

Original von eierkopf1

@zu viel Wert auf Zeichenketten:
Es stimmt natürlich, was du sagst. Aber ich möchte es auch richtig anschreiben können, da ich auf der Tafel vorrechnen muss und es auch für Prüfungen können muss.

Klar, aber das ist doch immer erst der zweite Schritt. Ich würde mir zuerst überlegen, wie der Beweis überhaupt aussehen soll, und erst danach mit dem Formalisieren anfangen.

Also die Gedanken einfach erstmal in Worte fassen.

Zitat:

Original von eierkopf1

Aber mein größtes Problem ist immer noch: "Wie beweise ich etwas"
Mit Wahrheitstabellen war das noch kein Problem, aber jetzt bin ich mir nie sicher, was ein Beweis ist und was nicht. unglücklich

Also da würde ich mir einfach ein paar Musterbeweise aus Büchern o. ä. ansehen.

Du hast IMHO einen zu „formalen“ Ansatz, also Du glaubst, Du müsstest jeden Schluss durch rein formale Umformung machen. Das ist aber kaum nötig, schließlich schreibst Du die Beweise nicht für die maschinelle Überprüfung, sondern für Menschen -- und die werden z. B. den Schluss „m und n sind natürliche Zahlen, also ist m+n natürlich“ wohl auch so verstehen und nicht erst dann, wenn Du diese Aussage seitenlang in „Elementarschlüsse“ zerlegt hast. ;-)

08.10.2008, 11:29

eierkopf1

Auf diesen Beitrag antworten »

@Jacques

Kein Problem. Ich lerne aus diesem Fehler Freude

Dh. Wenn ich annehme, dass die Aussage Z richtig ist. Dann nehme ich das Gegenteil $\begin{eqnarray*} \neg Z \end{eqnarray*}$ an und sehe, dass es keinen eindeutigen Widerspruch gibt (= es gibt Beispiele, bei denen die Gegenannahme stimmt) und sehe dann auch, dass die Aussage Z falsch sein muss, oder?

Wenn ich das weiß, dann könnte ich eigentlich mit dem Beispiel von vorne beginnen und gleich ein Gegenbeispiel dazu suchen. Dh, ich beweise nicht allgemein (dh, ohne ein Gegenbeispiel anzugeben), dass die Aussage falsch ist, SONDERN es reicht völlig aus, nur ein Gegenbeispiel anzugeben, oder?

Mein Beispiel ist dann so fertig gelöst:
$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cap M_{j2} = \emptyset \end{eqnarray*}$

Ich gebe das Gegenbeispiel an:
$\begin{eqnarray*} \{\{1, 2\},\{1, 3\},\{2, 3\} \} \end{eqnarray*}$

Damit ist bewiesen, dass die obige Aussage falsch ist.

Stimmts?

@ $\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cup M_{j2} = \emptyset \to FALSCH \end{eqnarray*}$

Ich meine, dass diese Aussage falsch ist.

Zum Rest: Ich werds versuchen Augenzwinkern

Aber Lehrbücher haben wir keine. unglücklich

mfg

08.10.2008, 11:47

Jacques

Auf diesen Beitrag antworten »

Zitat:

Original von eierkopf1

Dh. Wenn ich annehme, dass die Aussage Z richtig ist. Dann nehme ich das Gegenteil $\begin{eqnarray*} \neg Z \end{eqnarray*}$ an und sehe, dass es keinen eindeutigen Widerspruch gibt (= es gibt Beispiele, bei denen die Gegenannahme stimmt) und sehe dann auch, dass die Aussage Z falsch sein muss, oder?

Das ist so nicht richtig. Ich würde es einfach so formulieren: Die Behauptung ist ja von der Form „für alle x gilt y“. Wenn Du jetzt einfach ein Gegenbeispiel findest, also ein x, das nicht die Eigenschaft y hat, dann ist die Behauptung doch widerlegt.

Zum Beispiel: „Alle natürlichen Zahlen sind gerade“. Dann gibt man einfach 1 als Gegenbeispiel an: 1 ist natürlich, aber ungerade. Also stimmt die Aussage nicht.

Deine obige Formulierung ist deswegen falsch, weil man aus der Tatsache, dass man auf keinen Widerspruch trifft, wirklich gar nichts folgern kann. Man kann auch von einer falschen Annahme auf wahre Folgerungen kommen!

Dieses Prinzip mit der Gegenannahme funktioniert nur in einem ganz bestimmten Schema: Man nimmt das Gegenteil der Behauptung als wahr an und zeigt, dass sich daraus ein Widerspruch ergibt. Dann kann man folgern, dass die ursprüngliche Behauptung wahr ist.

Zitat:

Original von eierkopf1

Wenn ich das weiß, dann könnte ich eigentlich mit dem Beispiel von vorne beginnen und gleich ein Gegenbeispiel dazu suchen. Dh, ich beweise nicht allgemein (dh, ohne ein Gegenbeispiel anzugeben), dass die Aussage falsch ist, SONDERN es reicht völlig aus, nur ein Gegenbeispiel anzugeben, oder?

Mein Beispiel ist dann so fertig gelöst:
$\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cap M_{j2} = \emptyset \end{eqnarray*}$

Ich gebe das Gegenbeispiel an:
$\begin{eqnarray*} \{\{1, 2\},\{1, 3\},\{2, 3\} \} \end{eqnarray*}$

Damit ist bewiesen, dass die obige Aussage falsch ist.

Stimmts?

Ja! Ich würde nur noch eine Begründung dazuschreiben:

Behauptung: Wenn der Durchschnitt über einem Mengensystem leer ist, dann findet man immer mindestens zwei disjunkte Mengen.

Falsch! Gegenbeispiel: {{1, 2}, {2, 3}, {3, 1}}. Der Durchschnitt über dem System ist zwar leer, aber man findet trotzdem keine zwei disjunkten Mengen! Also ist die Behauptung falsch.

Zitat:

Original von eierkopf1

@ $\begin{eqnarray*} \bigcap_{j\in J} M_j =\emptyset \to \exists M_{j1}, M_{j2} \in F: M_{j1} \cup M_{j2} = \emptyset \to FALSCH \end{eqnarray*}$

Ich meine, dass diese Aussage falsch ist.

Dann schreibe das mit „nicht(...)“. Denn Deine Schreibweise ist auf jeden Fall nicht „offziell“, und man kann sie auch nicht ohne Erklärung verstehen.

Zitat:

Original von eierkopf1

Zum Rest: Ich werds versuchen Augenzwinkern

Aber Lehrbücher haben wir keine. unglücklich

Die kannst Du Dir aber privat zulegen. Augenzwinkern

Neue Frage »

Antworten »

System von Mengen: Beweis

Verwandte Themen