Beweis zu Äquivalenzklassen

05.12.2012, 21:52

Ploki

Beweis zu Äquivalenzklassen

Meine Frage:
Seien X eine Menge und ~ eine Äquivalenzrelation auf X.

Zeigen Sie : Der Durchschnitt zweier verschiedener Aquivalenzklassen ist leer.

Meine Ideen:
Ich hab den Beweis fertig. Weiß aber nicht ob er korrekt ist. Wäre euch echt dankbar, wenn das jemand kontrollieren könnte.

Beweis:

Seien $\begin{eqnarray*} \tilde{x} , \tilde{y} \end{eqnarray*}$ Äquivalenzklassen und Teilmengen von X.

zz.: $\begin{eqnarray*} \tilde{x} , \tilde{y} \end{eqnarray*}$ haben kein gemeinsames Element $\begin{eqnarray*} \Leftrightarrow \tilde{x} \cap \tilde{y} = \varnothing \end{eqnarray*}$
----------------------------------------------------------------------------------------------------------

"=>":

Also zz.: $\begin{eqnarray*} \tilde{x} , \tilde{y} \end{eqnarray*}$ haben kein gemeinsames Element $\begin{eqnarray*} \Rightarrow \tilde{x} \cap \tilde{y} = \varnothing \end{eqnarray*}$

Beweis durch Kontraposition: (p => q) <=> (non p => non q)

zz.: $\begin{eqnarray*} \tilde{x} \cap \tilde{y} \neq \varnothing\Rightarrow \tilde{x}, \tilde{y} \end{eqnarray*}$ haben ein gemeinsames Element

Sei $\begin{eqnarray*} x \in (\tilde{x} \cap \tilde{y}) \end{eqnarray*}$ beliebig. $\begin{eqnarray*} \Rightarrow x \in \tilde{x} \wedge x \in \tilde{y} \end{eqnarray*}$ . Also haben $\begin{eqnarray*} \tilde{x} \end{eqnarray*}$ und $\begin{eqnarray*} \tilde{y} \end{eqnarray*}$ ein gemeinsames Element.

----------------------------------------------------------------------------------------------------------
"<=":

Also zz.: $\begin{eqnarray*} \tilde{x} \cap \tilde{y} = \varnothing \Rightarrow \tilde{x} , \tilde{y} \end{eqnarray*}$ haben kein gemeinsames Element

Wieder Beweis durch Kontraposition:

zz.: $\begin{eqnarray*} \tilde{x}, \tilde{y} \end{eqnarray*}$ haben ein gemeinsames Element $\begin{eqnarray*} \Rightarrow \tilde{x} \cap \tilde{y} \neq \varnothing \end{eqnarray*}$

Wenn nun $\begin{eqnarray*} \tilde{x} \end{eqnarray*}$ und $\begin{eqnarray*} \tilde{y} \end{eqnarray*}$ ein gemeinsames Element haben, dann existiert eine nichtleere Menge $\begin{eqnarray*} A\subseteq X \end{eqnarray*}$ , sodass $\begin{eqnarray*} \tilde{x} \cap \tilde{y} = A \end{eqnarray*}$ . Und damit ist $\begin{eqnarray*} \tilde{x} \cap \tilde{y} \end{eqnarray*}$ nicht leer.

q.e.d.
----------------------------------------------------------------------------------------------------------

05.12.2012, 23:02

weisbrot

Auf diesen Beitrag antworten »

RE: Beweis zu Äquivalenzklassen

Zitat:

zz.: $\begin{eqnarray*} \tilde{x} , \tilde{y} \end{eqnarray*}$ haben kein gemeinsames Element $\begin{eqnarray*} \Leftrightarrow \tilde{x} \cap \tilde{y} = \varnothing \end{eqnarray*}$

das ist doch nicht was zu zeigen ist geschockt

! das ist elementare mengenlehre.
ist dir beim beweisen nicht aufgefallen, dass du überhaupt nicht benutzt, dass es sich um äquivalenzklassen handelt?
zu zeigen ist: $\begin{eqnarray*} \tilde{x} \neq \tilde{y}\Rightarrow \tilde{x} \cap \tilde{y} = \varnothing \end{eqnarray*}$
lg

06.12.2012, 01:03

Ploki

Auf diesen Beitrag antworten »

RE: Beweis zu Äquivalenzklassen
Das fand ich auch ein bisschen komisch, dass ich nie eine Eigenschaft der Äquivalenzrelation verwendet habe =)

Jedenfalls, danke für deine schnelle Antwort!

Ich probiers mal direkt, ohne Kontraposition.

Also zz. $\begin{eqnarray*} \tilde{x} \neq \tilde{y}\Rightarrow \tilde{x} \cap \tilde{y} = \varnothing \end{eqnarray*}$

Aufgrund der Reflexivität von ~, gilt $\begin{eqnarray*} x \in \tilde{x} \end{eqnarray*}$ und $\begin{eqnarray*} y \in \tilde{y} \end{eqnarray*}$ ,für alle x,y aus X.

Wie komm ich nun weiter?

06.12.2012, 19:13

weisbrot

Auf diesen Beitrag antworten »

RE: Beweis zu Äquivalenzklassen
ja, das stimmt schonmal aber ich glaube nicht dass dich das besonders weiterbringt.
du musst eben benutzen, dass ~x und ~y nicht gleich sind (-> was heißt das genau?). und dann vielleicht mittels widerspruch oder kontraposition zeigen, dass sie kein gemeinsames element haben können (denn hätten sie ein gemeinsames element, dann....).
lg

06.12.2012, 20:14

Ploki

Auf diesen Beitrag antworten »

Kann ich es eventuell so zeigen?

$\begin{eqnarray*} x \not\in \tilde{y} \Rightarrow \tilde{x} \cap \tilde{y} = \varnothing \end{eqnarray*}$

Nun mit Kontraposition:

$\begin{eqnarray*} \tilde{x} \cap \tilde{y} \neq \varnothing \Rightarrow x \in \tilde{y} \end{eqnarray*}$

Sei nun z aus X im Durchschnitt, dann folgt, dass z ~ x und z ~ y. Wegen der Symmetrie folgt: x ~ z und z ~ y. Wegen der Transitivität folgt, dass x ~ y, für alle x,y,z aus X.

Kann ich nun folgern, dass $\begin{eqnarray*} x \in \tilde{y} \end{eqnarray*}$ ?

06.12.2012, 20:24

weisbrot

Auf diesen Beitrag antworten »

dass es reicht $\begin{eqnarray*} x \not\in \tilde{y} \end{eqnarray*}$ zu nehmen anstatt $\begin{eqnarray*} \tilde{x}\neq\tilde{y} \end{eqnarray*}$ musst du aber auch erstmal zeigen.
dein beweis wäre übrigends dann richtig.
aber ich denke es wäre einfach kontraposition über die eigendliche aussage, also angenommen der schnitt ist nicht leer, dann müssen die beiden äquivalenzklassen gleich sein.
lg

06.12.2012, 20:44

Ploki

Auf diesen Beitrag antworten »

ok ich versuchs

zz.: $\begin{eqnarray*} \tilde{x} \cap \tilde{y} \neq \varnothing \Rightarrow \tilde{x} = \tilde{y} \end{eqnarray*}$

Sei nun z aus X im Durchschnitt, dann folgt, dass z ~ x und z ~ y. Wegen der Symmetrie folgt: x ~ z und z ~ y. Wegen der Transitivität folgt, dass x ~ y, für alle x,y,z aus X. (ident zu vorher)

Nun ist $\begin{eqnarray*} \tilde{x} \subseteq \tilde{y} \end{eqnarray*}$ und da auch y ~ x gilt(symmetrie), gilt auch $\begin{eqnarray*} \tilde{y} \subseteq \tilde{x} \end{eqnarray*}$

und damit gilt: $\begin{eqnarray*} \tilde{y} = \tilde{x} \end{eqnarray*}$

07.12.2012, 14:15

weisbrot

Auf diesen Beitrag antworten »

mh, joh, einverstanden!
vielleicht könnte man noch ein wort darüber verlieren warum denn die inklusionen wirklich gelten (weils eben äq.klassen sind - also für a in [x] gilt a ~ x und wegen x ~ y (trans.) auch a ~ y also a in [y]).. aber von mir aus richtig so.
lg

Neue Frage »

Antworten »

Beweis zu Äquivalenzklassen

Verwandte Themen