Reflexivität von Relationen

30.11.2004, 17:59

shooter99

Reflexivität von Relationen

Ich habe eine Frage zu der Definiton von Reflexivität.
Folgende Zitate stammen aus dem Buch "Mathematische Grundlagen der Informatik".

Auf S.71 heißt es: "Sei R eine Relation über A.
(1) R heißt reflexiv, falls für jedes $\begin{eqnarray*} x\in A \end{eqnarray*}$ gilt xRx"

Auf S.74 ist folgendes Beispiel für eine reflexive Relation angegeben:
"Sei R = {(1,2),(2,3),(1,3)} teilmenge von $\begin{eqnarray*} \mathbb N \times \mathbb N \ \end{eqnarray*}$ . [...]
R1 = {(1,2),(2,3),(1,3),(1,1),(2,2),(3,3)} ist der reflexive Abschluss von
R"

Meine Frage:
Wieso steht die Aussage, dass R1 reflexiv ist, in Einklang mit der
Definition von S.71?
Nach der Def. von S.71 muss doch gelten, dass für alle $\begin{eqnarray*} x\in \mathbb N \end{eqnarray*}$ gilt xR1x (R1
ist Rel. über N), was aber bei R1 nicht der Fall ist, da zB 4R14, 5R15 usw.
nicht gelten. Demnach wäre R1 nicht reflexiv!?? Hilfe

30.11.2004, 22:05

DeadMilkman

Auf diesen Beitrag antworten »

RE: Reflexivität von Relationen
Die Elemente 4 und 5 z.B. kommen in der Relation nicht vor, d.h es gibt z.B. kein (1,4) also muss es auch kein (4,4) geben.
In diesem Fall ist die Relation reflexiv weil es (1,1) (2,2) und (3,3) gibt, das ist schon ausreichend.

Zeichne einfach mal den Relationsgraphen von R1, dann siehst du, dass jedes Element zu sich selbst in Relation steht und somit ist R1 reflexiv.

30.11.2004, 22:10

JochenX

Auf diesen Beitrag antworten »

demnach wäre eine leere relation reflexiv, milkman?
also das wage ich zu bezweifeln....

ich weiß es nicht genau, aber ich vermute, dass es an der ausdrucksweise "der reflexive Abschluss" liegt.
das besagt wahrscheinlich genau das, was milkman sagt, weil reflexiv an sich ist das nicht.

mfg jochen

30.11.2004, 22:43

shooter99

Auf diesen Beitrag antworten »

Also "reflexiver Abschluss" einer Menge R bedeutet einfach nur, dass die daraus entstehende Menge R1 auf jeden Fall die Eigenschaft der Reflexivität hat (wenn R diese nicht hatte).

Ist auch eindeutig im Buch definiert:
"Sei R eine Relation über A und sei P eine Eigenschaft von Relationen. Die Relation R* heißt Abschluss von R bezüglich P, wenn gilt
(1) R* besitzt die Eigenschaft P [...]"

=>Das heißt auf meine Beispielrelation bezogen, dass R1 der reflexive Abschluss von R ist und somit R1 die Eigenschaft der Reflexivität besitzt, was aber in Widerspruch zu oben genannter Def steht..

@DeadMilkman
Genau bei dieser Betrachtungsweise liegt ja mein Problem! Wenn man das so sieht, dann steht das nicht in Einklang mit der Definition von Reflexivität die ich im ersten Posting zitiert habe, welche besagt dass für die Relation für ALLE Elemente $\begin{eqnarray*} x\in A \end{eqnarray*}$ xRx gelten muss und nicht nur für die die in der Relation enthalten sind.
Hilfe

01.12.2004, 11:09

slyck

Auf diesen Beitrag antworten »

Also ich denke, das ist ein Fehler (bzw. eine Ungenauigkeit) im Buch, denn eigentlich müßte man $\begin{eqnarray*} R \subseteq \{1,2,3\} \times \{1,2,3\} \end{eqnarray*}$ definieren, und dann ist R1 der reflexive Abschluß. Ansonsten muß der reflexive Abschluß von R tatsächlich alle Tupel (n,n) enthalten mit $\begin{eqnarray*} n \in \mathbb{N} \end{eqnarray*}$ .

Und genau deshalb klappt das Argument von DeadMilkman nicht: wenn du den Relationsgraphen für R1 zeichnest, hast du unendlich viele Elemente in der Menge ... es zeigt sich also, daß der Typ (also die Grundmenge) der Relation für solche Eigenschaften ganz wchtig ist ... Und damit haben wir auch die Lösung für die leere Relation: die leere Relation definiert auf der leeren Menge ist reflexiv; auf jeder anderen Menge nicht.

01.12.2004, 11:29

JochenX

Auf diesen Beitrag antworten »

hmmm, aber im buch steht eindeutig INxIN, shooter?

edit: das was Slyck da beschreibt, kenne ich als "reflexive Hülle".

01.12.2004, 12:09

slyck

Auf diesen Beitrag antworten »

Mmh, soweit ich weiß, sind aber reflexive Hülle und reflexiver Abschluß Synonyme.

Die unterschiedlichen Bezeichnungen motivieren eigentlich nur die Richtung aus der man kommt: Abschluß ist eher konstruktiv, Hülle eher beschreibend. Denn meist wird die reflexive Hülle als "kleinste Relation, die R enthält und reflexiv ist" beschrieben (was ja nicht gleich die Konstruktion angibt).

01.12.2004, 12:12

JochenX

Auf diesen Beitrag antworten »

in google führt die reflexive hülle mit 88:27 vor dem reflexiven abschluss...
nur mal ganz nebenbei bemerkt...

mfg jochen

edit: und bei seekport führt sie 9:1

01.12.2004, 16:18

shooter99

Auf diesen Beitrag antworten »

@LOED
also im Buch steht um genau zu sein $\begin{eqnarray*} \mathbb N ^{2} \end{eqnarray*}$ was aber ja nur eine andere Schreibweise für $\begin{eqnarray*} \mathbb N \times \mathbb N \end{eqnarray*}$ ist..

Hier nochmal ein etwas längerer Auschnitt aus dem Buch zu dem Abschluss einer Relation, vielleicht kann man daraus dann besser einen Fehler erkennen:

Zitat:

Definition 4.6 Sei R eine Relation über A und sei P eine Eigenschaft von Relationen. Die Relation R* heißt Abschluss von R bezüglich P, wenn gilt
(1) R* besitzt die Eigenschaft P
(2) R $\begin{eqnarray*} \subseteq \end{eqnarray*}$ R*
(3) für alle Relationen S, die R umfassen und die die Eigenschaft P besitzen, gilt R* $\begin{eqnarray*} \subseteq \end{eqnarray*}$ S

Häufig betrachtet wird der reflexive Abschluss, also der Abschluss einer Relation bzgl. der Eigenschaft der Reflexivität, der symmetrische Abschluss und der transitive Abschluss einer Relation.

Besitzt eine Relation R bereits die Eigenschaft P, dann gilt natürlich R* = R für den Abschluss R* dieser Relation bzgl. P. Man sagt dann, dass R abgeschlossen ist bzgl. P.

Beispiele 4.8. (1) Sei R = {(1,2),(2,3),(1,3)} $\begin{eqnarray*} \subseteq \mathbb N ^{2} \end{eqnarray*}$ . R ist abgeschlossen bzgl. Transitivität. R1 = {(1,2),(2,3),(1,3),(1,1),(2,2),(3,3)} ist der reflexive Abschluss von R. R2 = {{(1,2),(2,3),(1,3),(2,1),(3,2),(3,1)} ist der symmetrische Abschluss von R.
(2) Sei R = {(x,y) $\begin{eqnarray*} \in \mathbb R ^{2} \mid x^{2} + y^{2} = 1 \end{eqnarray*}$ }. R ist abgeschlossen bzgl. Symmetrie.
R1 = R $\begin{eqnarray*} \cup \end{eqnarray*}$ $\begin{eqnarray*} \bigtriangleup \end{eqnarray*}$ R ist der reflexive Abschluss von R (vgl. Satz 4.5).
R2 = R $\begin{eqnarray*} \cup \end{eqnarray*}$ (R $\begin{eqnarray*} \circ \end{eqnarray*}$ R) ist der transitive Abschluss von R (vgl. Satz 4.8).

01.12.2004, 17:50

JochenX

Auf diesen Beitrag antworten »

ja, also das ist schon unsere definition:
die kleinste relation, die obermenge der ursprungsrealtion ist und gleichzeitig die eigenschaft erfüllt.

aber ich kann da auch nicht mehr ablesen, also ist es vermutlich wirklich nur ein fehler....

mfg jochen

13.09.2007, 20:50

Penis-vergroessern

Auf diesen Beitrag antworten »

Penisvergroesserung oder Penis Vergroesserung
[zensiert]

13.09.2007, 20:54

Tomtomtomtom

Auf diesen Beitrag antworten »

Das ist sogar thematisch richtig, Körpererweiterungen gehören zur Algebra ^^

13.09.2007, 21:53

therisen

Auf diesen Beitrag antworten »

Normalerweise hätte ich auf unseren Spam-Button gedrückt, aber dein Beitrag ist a) zu komisch Big Laugh