Beweise Links- Rechtseindeutig

17.09.2009, 21:47

Hurtek

Beweise Links- Rechtseindeutig

Hallo Leute,

bin leicht verzweifelt, weil ich die Beweismethodik nicht umsetzen kann.
Vielleicht könnt ihr mir Schrittweise helfen. Bin über Hinweise dankbar (keine sofortige Lösung). Vielleicht kann man das hier "erarbeiten". Ist für euch sicherlich trivial.

Es geht um die Tatsache dass eine Relation R genau dann Linkeindeutig ist wenn die inverse Relation rechtseindeutig ist.

Wie gehe ich am besten an solche Beweise ran?
Folgende Überlegungen habe ich mir gemacht. Ich erkenne, dass es sich um eine Äquivalenz handelt "genau dann wenn".
Dann überlege ich mir welche Definitionen ich benötige (Links-, Rechtseindeutig und inverse womöglich ?!).
Diese sind mir auch bekannt doch ich kann das einfach nicht umsetzen.

Linkseindeutigkeit: Es seien zwei bel. Mengen M1 und M2. und R teilmenge des kartesichen Produktes M1 x M2.
LE bedeutet nun:

$\begin{eqnarray*} \forall x1,x2 \in M1: \forall y \in M2: (x1,y) \in R, und (x2,y) \in R \Rightarrow x1 = x2 \end{eqnarray*}$
d.h. wenn zwei Pfeile bei Y ankommen, dann sind sie gleich.

Rechteindeutig:
$\begin{eqnarray*} \forall y1,y2 \in M2: \forall x\in M1: (x,y1) \in R, und (x,y2) \in R \Rightarrow y1 = y2 \end{eqnarray*}$
d.h. von jedem x geht höchstens ein Pfeil aus.

inverse Relation:
R(inverse) = {(y,x) | (x,y) E R

17.09.2009, 22:18

Romaxx

Auf diesen Beitrag antworten »

Das ist im Prinzip ein Einzeiler.

Mache Dir klar, das folgendes gilt:

$\begin{eqnarray*} (x,y)\in R\Longleftrightarrow (y,x)\in R^{-1}\quad (*) \end{eqnarray*}$

Nun fängst du an:

Sei $\begin{eqnarray*} R \end{eqnarray*}$ linkseindeutig.

$\begin{eqnarray*} \Longleftrightarrow \end{eqnarray*}$

$\begin{eqnarray*} \forall x_1,x_2\in M_1~\forall y\in M_2: (~(x_1,y)\in R \end{eqnarray*}$ und $\begin{eqnarray*} (x_2,y)\in R\Longleftrightarrow\cdots \end{eqnarray*}$

Nutze bei $\begin{eqnarray*} \cdots \end{eqnarray*}$ nun $\begin{eqnarray*} (*) \end{eqnarray*}$

17.09.2009, 22:26

Hurtek

Auf diesen Beitrag antworten »

heißt also dass ich darauf die inverse Definition anwenden muss?
würde das dann direkt die rechtseindeutigkeit ergeben?

wird also aus x1,y und x2,y -> y1,x und y2,x..... ?

$\begin{eqnarray*} \forall y1, y2 \in M2: \forall x \in M1: (x,y1) \in R , und (x,y2) \in R \end{eqnarray*}$

oder zunächst nur?

$\begin{eqnarray*} \forall x1,x2 \in M1 \forall y \in M2: (y,x1) \in R inverse, und (y,x2) \in R inverse \end{eqnarray*}$

17.09.2009, 22:52

Romaxx

Auf diesen Beitrag antworten »

Zitat:

Original von Hurtek
oder zunächst nur?

$\begin{eqnarray*} \forall x1,x2 \in M1 \forall y \in M2: (y,x1) \in R inverse, und (y,x2) \in R inverse \end{eqnarray*}$

So in etwa.

Ich hoffe Du lässt Dich nicht von dem vielen Latex verwirren.

Bei der Inversen Relation $\begin{eqnarray*} R^{-1} \end{eqnarray*}$ haben $\begin{eqnarray*} x \end{eqnarray*}$ und $\begin{eqnarray*} y \end{eqnarray*}$ die Rollen getauscht,

d.h. wenn $\begin{eqnarray*} R \end{eqnarray*}$ linkseindeutig ist mit

$\begin{eqnarray*} \forall x_1,x_2 \in M_1~ \forall y \in M_2: (x_1,y) \in R, ~und~ (x_2,y) \in R \Rightarrow x_1 = x_2 \end{eqnarray*}$

bedeutet Rechtseindeutigkeit bei $\begin{eqnarray*} R^{-1} \end{eqnarray*}$

$\begin{eqnarray*} \forall x_1,x_2 \in M_1~ \forall y \in M_2: (y,x_1) \in R^{-1} ~und~ (y,x_2) \in R^{-1} \Rightarrow x_1 = x_2 \end{eqnarray*}$

Da $\begin{eqnarray*} (x_1,y) \in R ~und~ (x_2,y) \in R \Longleftrightarrow(y,x_1) \in R^{-1}, ~und~ (y,x_2)\in R^{-1} \end{eqnarray*}$ ist der ganze Beweis mit

$\begin{eqnarray*} \forall x_1,x_2\in M_1~\forall y\in M_2: (~(x_1,y)\in R~und~(x_2,y)\in R\Longleftrightarrow (y,x_1) \in R^{-1}, ~und~ (y,x_2)\in R^{-1})\Rightarrow x_1=x_2 \end{eqnarray*}$

geführt, denn egal was du voraussetzt, zuerst $\begin{eqnarray*} R \end{eqnarray*}$ linkseindeutig oder $\begin{eqnarray*} R^{-1} \end{eqnarray*}$ rechtseindeutig,

gilt die Äquivalenz $\begin{eqnarray*} (x,y)\in R\Longleftrightarrow (y,x)\in R^{-1} \end{eqnarray*}$ und es folgt stets aus jeder Voraussetzung $\begin{eqnarray*} x_1=x_2 \end{eqnarray*}$ .

Neue Frage »

Antworten »

Beweise Links- Rechtseindeutig

Verwandte Themen