Zeigen Äqu.Rel.

03.11.2009, 12:27

Zeigen Äqu.Rel.

Es sei eine reflexive, transitive rel. $\begin{eqnarray*} \leq \end{eqnarray*}$ . auf X gegeben. Nun wird ~ auf X mit $\begin{eqnarray*} x\sim y:\Leftrightarrow x\leq y\wedge y\leq x \end{eqnarray*}$ definiert.

Zeige dass ~ eine ÄR ist.

Sei x aus X, dann folgt $\begin{eqnarray*} x\leq x\wedge x\leq x \end{eqnarray*}$ . Es folgt $\begin{eqnarray*} x\sim x \end{eqnarray*}$ . REFLEXIV

Seien x,y,z aus X, dann foglt aus x~y,

$\begin{eqnarray*} x\leq y\wedge y\leq x \end{eqnarray*}$

Aus y~z folgt:

$\begin{eqnarray*} y\leq z\wedge z\leq y \end{eqnarray*}$

Damit folgt nun:

$\begin{eqnarray*} x\leq y\leq z\wedge z\leq y\leq x \end{eqnarray*}$
$\begin{eqnarray*} x\leq z\wedge z\leq x \end{eqnarray*}$

Also x~z. TRANSITIV

Aus x~y folgt:

$\begin{eqnarray*} x\leq y\wedge y\leq x\Leftrightarrow y\leq x\wedge x\leq y \end{eqnarray*}$

Es folgt also: x~y<-->y~x.

So richtig?

Kann ich reintheoreitsch, da ja "kleinergleich" als bereits reflexiv und tranisitiv definiert ist, und ~ letztlich ja ne verkettung der relation "kleinergleich" ist, schon aus der definition schließen, dass ~ reflexiv und transitiv ist? (quasi ohne rechnen)

03.11.2009, 12:44

Jacques

Auf diesen Beitrag antworten »

RE: Zeigen Äqu.Rel.
Hallo,

Zitat:

Original von RS

Sei x aus X, dann folgt $\begin{eqnarray*} x\leq x\wedge x\leq x \end{eqnarray*}$ . Es folgt $\begin{eqnarray*} x\sim x \end{eqnarray*}$ . REFLEXIV

Bei diesem Schluss benutzt Du die Reflexivität von $\begin{eqnarray*} \leq \end{eqnarray*}$ . Das würde ich auch hinschreiben.

Zitat:

Original von RS

Seien x,y,z aus X, dann foglt aus x~y,

$\begin{eqnarray*} x\leq y\wedge y\leq x \end{eqnarray*}$

Aus y~z folgt:

$\begin{eqnarray*} y\leq z\wedge z\leq y \end{eqnarray*}$

Damit folgt nun:

$\begin{eqnarray*} x\leq y\leq z\wedge z\leq y\leq x \end{eqnarray*}$
$\begin{eqnarray*} x\leq z\wedge z\leq x \end{eqnarray*}$

Also x~z. TRANSITIV

Auch da würde ich vielleicht noch die Begründungen (Transitivität von $\begin{eqnarray*} \leq \end{eqnarray*}$ ) dazuschreiben, immerhin ist $\begin{eqnarray*} \leq \end{eqnarray*}$ ja nicht die reelle „Kleiner-oder-gleich“-Relation, wo die ganzen Schlüsse selbstverständlich wären.

Zitat:

Original von RSAus x~y folgt:

$\begin{eqnarray*} x\leq y\wedge y\leq x\Leftrightarrow y\leq x\wedge x\leq y \end{eqnarray*}$

Es folgt also: x~y<-->y~x.

OK. Bei der Symmetrie reicht übrigens schon die Forderung

$\begin{eqnarray*} x \sim y \Rightarrow y \sim x \end{eqnarray*}$

für alle x, y aus der Trägermenge aus.

03.11.2009, 12:55

Auf diesen Beitrag antworten »

alles klar. das war genau der punkt, den ich wissen wollte^^.

also muss ich quasi als beleg jeweils die trans. und reflex. von "kleinergleich" anführen. danke!

hier noch ne 2. teilaufg.

Es gibt genau eine Relation $\begin{eqnarray*} \leq auf X_{/ \sim} \end{eqnarray*}$ für die
$\begin{eqnarray*} \left[x\right]_{\sim}\leq\left[y\right]_{\sim}\Leftrightarrow x\leq y \end{eqnarray*}$ für alle x,y aus X gilt. dies relation ist dann eine ordn.rel..

Ich würde versuchen durch widerspruch zu zeigen, dass es nicht 2 (bzw. mehr) solche relationen geben kann. (sprich, dass die relationen "gleich" sind.)

Aus $\begin{eqnarray*} \left[x\right]_{\sim}\leq\left[y\right]_{\sim} \end{eqnarray*}$ folgt:

$\begin{eqnarray*} \{y\in X|x\sim y\}\subseteq \{x\in X|y\sim x\} \end{eqnarray*}$

Nun haben wir in der vorlesung nen beweis geführt, dass Äklassen entweder gleich oder deren durchschnitt leer ist. Kann ich das hier irgendwie anwenden?

Jemand en tipp wie ich die aufgabe anfangen könnte? Sprich aus welchen dingen kann ich mir denn ne zweite relation definieren um dann zu zeigen, dass beide Relationen gleich sind?

03.11.2009, 14:53

Jacques

Auf diesen Beitrag antworten »

Nur vorab: Das $\begin{eqnarray*} \leq \end{eqnarray*}$ ist nicht die normale Kleiner-oder-gleich-Relation zwischen reellen Zahlen, sondern man benutzt einfach nur dieses Zeichen für abstrakte Relationen.

Zitat:

Original von RS

Aus $\begin{eqnarray*} \left[x\right]_{\sim}\leq\left[y\right]_{\sim} \end{eqnarray*}$ folgt:

$\begin{eqnarray*} \{y\in X|x\sim y\}\subseteq \{x\in X|y\sim x\} \end{eqnarray*}$

Das kann man nicht folgern, weil die $\begin{eqnarray*} \leq \end{eqnarray*}$ -Relation gar nicht konkret bekannt ist.

Also ich verstehe die Aufgabenstellung so:

Beweisen sie, dass die Definition

$\begin{eqnarray*} [x]_\sim \preceq [y]_\sim \colon\Longleftrightarrow x \leq y \end{eqnarray*}$

wohldefiniert ist, d. h., dadurch tatsächlich eine Relation $\begin{eqnarray*} \preceq \end{eqnarray*}$ auf $\begin{eqnarray*} X_{/\sim} \end{eqnarray*}$ definiert wird.

Beweisen müsste man dafür:

Für zwei beliebige Elemente [x]~, [y]~ aus R/~ gilt

$\begin{eqnarray*} x \leq y \Rightarrow a \leq b \quad \textrm{für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

$\begin{eqnarray*} \neg(x \leq y) \Rightarrow \neg(a \leq b) \quad \textrm{für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

Ich bin mir aber nicht ganz sicher. Vielleicht kann nochmal jemand anderes was zu der Aufgabe sagen, also wie man die zu verstehen hat.

03.11.2009, 15:05

Auf diesen Beitrag antworten »

Danke erstmal für den Hinweis...

Vielleicht ne andre Idee.

Wie gesagt haben wir bestimmt, dass 2 ÄK entweder disjunkt oder gleich sind.

Ließe sich daraus nicht irgendwas machen? sprich zu zeigen, dass beide "möglichkeiten" zur selben Relation führen, bzw die zweite relation die entsteht, nicht mit den angegebenen eigenschaften der ersten korrespondiert?

Zitat:

Beweisen müsste man dafür:

Für zwei beliebige Elemente [x]~, [y]~ aus R/~ gilt

$\begin{eqnarray*} x \leq y \Rightarrow a \leq b \quad \textrm{für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

$\begin{eqnarray*} \neg(x \leq y) \Rightarrow \neg(a \leq b) \quad \textrm{für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

Wie beweise ich das?

03.11.2009, 15:44

Jacques

Auf diesen Beitrag antworten »

Also in meinen Augen ist die Aufgabenstellung nicht so gemeint, wie man erst vermuten würde:

Zeigen sie, dass es genau eine Relation mit dieser Eigenschaft gibt.

Denn die obige Eigenschaft definiert schon eine vollständige Relation, also es kann gar nicht mehrere geben:

Seien a, b Elemente von X und $\begin{eqnarray*} \preceq_1, \preceq_2 \end{eqnarray*}$ zwei Relationen mit der obigen Eigenschaft.

$\begin{eqnarray*} ([a]_{\sim}, [b]_{\sim}) \in \mathord{\preceq_1} \Longleftrightarrow a \leq b \Longleftrightarrow ([a]_{\sim}, [b]_{\sim}) \in \mathord{\preceq_2} \end{eqnarray*}$

Also die Gleichheit aller Relationen mit der Eigenschaft ist mehr oder weniger trivial.

Es könnte höchstens sein, dass die Definition in sich widersprüchlich ist:

Als Beispiel könnte gelten [2]~ = [4]~, und man betrachtet [2]~ = [4]~ und [5]~. Es gilt 2 „kleinergleich“ 5, aber 4 nicht „kleinergleich“ 5.

Ist jetzt

$\begin{eqnarray*} [2]_{\sim} \preceq [5]_{\sim} \end{eqnarray*}$

wegen

$\begin{eqnarray*} 2 \leq 5 \end{eqnarray*}$

oder

$\begin{eqnarray*} \neg ([2]_{\sim} \preceq [5]_{\sim}) \end{eqnarray*}$

wegen

$\begin{eqnarray*} \neg (4 \leq 5) \end{eqnarray*}$

?

Man kann es nicht entscheiden, die Definition wäre sinnlos.

03.11.2009, 16:45

Auf diesen Beitrag antworten »

Das "kleiner-gleich" reflexiv und transitiv ist (laut 1. Teilaufgabe) bring auch nichts oder?

03.11.2009, 17:05

Jacques

Auf diesen Beitrag antworten »

Doch, doch, diese Eigenschaften kann man benutzen. Ich war mir eben nur nicht sicher, ob man wirklich die Wohldefiniertheit nachweisen soll. Weil die Aufgabenstellung nicht so klar ist.

Man betrachtet zwei Elemente x, y aus X. Nachzuweisen ist:

Wenn $\begin{eqnarray*} x \leq y \end{eqnarray*}$ , dann gilt für alle a aus [x] und alle b aus [y] ebenso $\begin{eqnarray*} a \leq b \end{eqnarray*}$

Voraussetzung ist $\begin{eqnarray*} x \leq y \end{eqnarray*}$

Seien $\begin{eqnarray*} a \in [x]_{\sim} \end{eqnarray*}$ und $\begin{eqnarray*} b \in [y]_{\sim} \end{eqnarray*}$

Dann gilt

$\begin{eqnarray*} a \leq x \end{eqnarray*}$

$\begin{eqnarray*} x \leq y \end{eqnarray*}$

$\begin{eqnarray*} y \leq b \end{eqnarray*}$

Also wegen der Transitivität von $\begin{eqnarray*} \leq \end{eqnarray*}$ auch

$\begin{eqnarray*} a \leq b \end{eqnarray*}$

Und dann fehlt noch der Nachweis

$\begin{eqnarray*} \neg(x \leq y) \Rightarrow \neg (a \leq b) \quad \textrm{für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

// Sorry, am Ende fehlte ein Negationszeichen!

03.11.2009, 17:25

Auf diesen Beitrag antworten »

Zitat:

Original von Jacques
Und dann fehlt noch der Nachweis

$\begin{eqnarray*} \neg(x \leq y) \Rightarrow a \leq b \quad \textrm{für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

Woher kommt das? verstehe nicht warum ich genau das nachweisen muss... überseh grad glaube etwas?!

EDIT:// mit dem negationszeichen ist die aussage doch äquivalent zu $\begin{eqnarray*} a\leq b\rightarrow x\leq y \end{eqnarray*}$ ?

Da $\begin{eqnarray*} a\in \left[x\right]_{\sim} \end{eqnarray*}$ und $\begin{eqnarray*} b\in \left[y\right]_{\sim} \end{eqnarray*}$ folgt:

$\begin{eqnarray*} a\in \left[x\right]_{\sim}\leq b\in \left[y\right]_{\sim}\Rightarrow x\leq y \end{eqnarray*}$

Aus deinem oberen Nachweis folgte ja $\begin{eqnarray*} x\leq y\Rightarrow a\leq b \end{eqnarray*}$ .

Also $\begin{eqnarray*} x\leq y\Rightarrow a\in \left[x\right]_{\sim}\leq b\in \left[y\right]_{\sim} \end{eqnarray*}$ .

Ist das richtig oder bin ich grad völlig falsch?

03.11.2009, 17:29

Jacques

Auf diesen Beitrag antworten »

Tut mir leid, ich meinte

$\begin{eqnarray*} \neg (x \leq y) \Rightarrow \neg(a \leq b) \textrm{ für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

Also wenn bei zwei Äquivalenzklassen [x] und [y] die Repräsentanten x und y nicht in der Relation $\begin{eqnarray*} \leq \end{eqnarray*}$ stehen, dann dürfen auch nicht zwei andere Elemente a aus [x] und b aus [y] in der Relation $\begin{eqnarray*} \leq \end{eqnarray*}$ stehen. Sonst wäre die Definition widersprüchlich.

Die Eigenschaft

$\begin{eqnarray*} [x]_{\sim} \preceq [y]_{\sim} \end{eqnarray*}$

bzw.

$\begin{eqnarray*} \neg ([x]_{\sim} \preceq [y]_{\sim}) \end{eqnarray*}$

muss unabhängig von den gewählten Repräsentanten x und y sein. Es darf nicht mal das eine und mal das andere rauskommen.

03.11.2009, 17:35

Auf diesen Beitrag antworten »

siehe 1 post über dir...

03.11.2009, 17:49

Jacques

Auf diesen Beitrag antworten »

Der Nachweis ist nicht ganz richtig.

Eine gleichwertige Aussage zu

$\begin{eqnarray*} \neg (x \leq y) \Rightarrow \neg (a \leq b) \textrm{ für alle } a \in [x]_{\sim}, b \in [y]_{\sim} \end{eqnarray*}$

ist:

Wenn es ein $\begin{eqnarray*} a \in [x]_{\sim} \end{eqnarray*}$ gibt und ein $\begin{eqnarray*} b \in [y]_{\sim} \end{eqnarray*}$ mit $\begin{eqnarray*} a \leq b \end{eqnarray*}$ , dann folgt daraus sofort $\begin{eqnarray*} x \leq y \end{eqnarray*}$ (der Übergang von „für alle“ zu „es gibt“ ist wichtig)

Also gelte

$\begin{eqnarray*} a \in [x]_{\sim}, b \in [y]_{\sim}, a \leq b \end{eqnarray*}$

für zwei Objekte a und b.

Dann gilt

$\begin{eqnarray*} x \leq a \end{eqnarray*}$

$\begin{eqnarray*} a \leq b \end{eqnarray*}$

$\begin{eqnarray*} b \leq y \end{eqnarray*}$

und damit wegen der Transitivität

$\begin{eqnarray*} x \leq y \end{eqnarray*}$

Bei Deinem Beweis sind z. T. formale Fehler:

$\begin{eqnarray*} a\in \left[x\right]_{\sim}\leq b\in \left[y\right]_{\sim}\Rightarrow x\leq y \end{eqnarray*}$

Das ist in der Form nicht erlaubt, weil Du so [x] mit b in die Relation $\begin{eqnarray*} \leq \end{eqnarray*}$ setzt. Du müsstest dafür schreiben:

$\begin{eqnarray*} [x]_{\sim} \ni a \leq b \in [y]_{\sim} \end{eqnarray*}$

Aber ich weiß nicht, ob man das nicht lieber in zwei Zeilen schreiben sollte statt als Zeichenkette.

Neue Frage »

Antworten »

Zeigen Äqu.Rel.

Verwandte Themen