Äquivalenzreltaion,Äklassen und Partition

Neue Frage »

Eli Auf diesen Beitrag antworten »
Äquivalenzreltaion,Äklassen und Partition
Hi,

dieses bsp hab ich soweit verstanden:

##########
Auf der Menge

T := { Huhn, Fliege, Hund, Spatz, Ameise, Katze, Spinne, Pferd, Mensch }

betrachten wir die Relation B := "hat genauso viele Beine wie". Überzeugen Sie sich davon, dass R eine Äquivalenzrelation auf der Menge T ist! Die zugehörige Partition der Menge T ist

P := { { Huhn, Mensch, Spatz }, { Hund, Katze, Pferd }, { Spinne }, { Fliege, Ameise } }.

Zwei (von möglichen 18) Repräsentantensystemen für diese Partition sind

R1 := { Huhn, Katze, Spinne, Fliege } und R2 := { Mensch, Hund, Spinne, Ameise }.
######################

was wäre jetzt genau die ausgeschriebene relation zu T (mit der bedindung B)? ists aufgrund der relationsbedingung B automatisch eine äquivalenzrelation?

gruß
eli
Tobias Auf diesen Beitrag antworten »

Für eine Äquivalenzrelation gilt:

1.) Symmetrie: Stehen A und B in Relation, so auch B und A.
2.) Reflexivität: Jedes Tier steht zu sich selbst in Relation
3.) Transitivität: Hat Tier A soviele Beine wie Tier B und Tier B soviele wie Tier C, so sind auch A und C in Relation.

Jede Bedingung B, die 1., 2. und 3. auf T erfüllt, bildet eine Äquivalenzrelation.

Die Relation R ist eine Menge aus Tupeln:

R := { (Hund, Hund), (Huhn, Huhn), ..., (Huhn, Mensch), (Mensch, Huhn), ...}
Eli Auf diesen Beitrag antworten »

ok, danke...

und sag mal bei ordnungsrelationen gilt ja immer die beziehung <= oder?

wäre es dann zb für

M = {1,2,3}

R = {{1,1},{1,2}{1,,3},{2,3},...}

oder versteh ich das falsch?

eli
Tobias Auf diesen Beitrag antworten »

Ordnungsrelationen sind auch axiomatisch definiert. (siehe Wikipedia.de)

Die Ordnungsrelationen bezeichnet man oft mit "<", sind aber nicht zwangsläufig immer die bekannte Kleiner-Gleich-Relation. (man kann auch ganz anders ordnen). Ferner unterscheidet man partielle und totale Ordnungen.

Für dein M mit kleiner-gleich-Ordnung hast du es fast richtig erkannt. Aber bedenke:

{1,2} = {2,1}.

Deshalb: (1,2) /= (2,1).
Eli Auf diesen Beitrag antworten »

also wären doppelt soviele paare drin als ich zunächst angenommen hätte? was beduetet /= ?g

wenn wir die ordnungsrelation jetzt über die kleinergleich beziehung verstehen wäre die relation ja so definiert bzw das wäre die relationsbedidung

a R b <=> a <= b

und a R b bedeutet ja (a,b) IST ELEMENT R

soweit richtig?

was beduetet dann sowas zb

(a,b) R (c,d) <=> a-c = b²-d²

ich würde tippen auf

(a,b) UND (c,d) IST ELEMENT R
Tobias Auf diesen Beitrag antworten »

Zitat:
also wären doppelt soviele paare drin als ich zunächst angenommen hätte? was beduetet /= ?g


Nein, du musst die Mengen durch Tupel ersetzem. Mit /= meinte ich "ungleich" . Du hast Mengen für die Ordnung benutzt. In Mengen ist jedoch keine Reihenfolge definiert. Da für Ordnungen Antisymmetrie gilt, ist es nicht korrekt Mengen zu benutzen. Stattdessen benutzt man Tupel.

Mit a R b <=> a <= b wird eine Relation definiert, die der "Kleiner-gleich-Ordnung" entspricht, d.h. alle Tupel, deren erste Komponente kleiner oder gleich der zweiten Komponente ist, sind in der Relation drin. Eine Relation ist schließlich nichts anderes als eine Menge. Die Relation ist reflexiv, transitiv und antisymmetrisch, also Ordnung.


Zitat:
(a,b) R (c,d) <=> a-c = b²-d²


Jetzt musst du eine Stufe "höher" denken. Stell dir vor wir haben eine Menge mit Elementen. Wie die Menge aussieht interessiert erstmal nicht. Die Menge kann aus Tieren, Äpfeln, Birnen, Autos, Zweitupel, Dreitupel, Matrizen, etc. bestehen. Eine Relation ist immer eine Teilmenge des Kreuzproduktes (denn man stellt zwei Elemente der Menge gegenüber und gibt durch eine Regel an, ob diese zwei Elemente in Relation zueinander stehen.

In deinem Beispiel oben sind die Elemente nun Tupel. Die Relationsmenge besteht dann aus Tupeln von Tupeln. Hammer

Also: x R y, wobei x := (a, b), y := (c, d).

Schauen wir uns ein Beispiel an:
Seien x := (1, 2) und y := (3, 4)

Gilt nun a-c = b²-d²?
1 - 3 = 4 - 16 <-- falsch! Also ist ((1,2), (3,4)) kein Element aus R, denn x steht nicht in Relation zu y.

Setzen wir aber x := (10, 5) und y := (1, 4) so gilt:
10 - 1 = 25 - 16 = 9. Also ist (x, y) = ((10, 5), (1, 4)) aus R.
 
 
cmenke Auf diesen Beitrag antworten »

Hmm. Und wie könnte man für so eine Relation systematisch Lösungen finden? Ich könnte das jetzt nur durch Ausprobieren.
Tobias Auf diesen Beitrag antworten »

In der Regel stellt sich nicht das Problem "systematisch Lösungen zu finden". Vielmehr lässt sich effizient testen ob zwei gegebene Elemente in Relation zueinander stehen. Es lassen sich trotzdem Lösungen finden, indem man sich Werte vorgibt und die anderen entsprechend wählt. (Ähnlich wie bei der Lösungsmenge von Gleichungssystemen, die nicht eindeutig lösbar sind.)
Eli Auf diesen Beitrag antworten »

Zitat:
Original von Tobias
Zitat:
also wären doppelt soviele paare drin als ich zunächst angenommen hätte? was beduetet /= ?g


Nein, du musst die Mengen durch Tupel ersetzem. Mit /= meinte ich "ungleich" . Du hast Mengen für die Ordnung benutzt. In Mengen ist jedoch keine Reihenfolge definiert. Da für Ordnungen Antisymmetrie gilt, ist es nicht korrekt Mengen zu benutzen. Stattdessen benutzt man Tupel.

Mit a R b <=> a <= b wird eine Relation definiert, die der "Kleiner-gleich-Ordnung" entspricht, d.h. alle Tupel, deren erste Komponente kleiner oder gleich der zweiten Komponente ist, sind in der Relation drin. Eine Relation ist schließlich nichts anderes als eine Menge. Die Relation ist reflexiv, transitiv und antisymmetrisch, also Ordnung.


also erstmal dazu...
korrekt müsste es dann:

R = {(1,1)},(1,2),(1,3),,(2,3),...}

sein, ja?g
Eli Auf diesen Beitrag antworten »

ok danke soweit für den rest, meine es verstanden zu haben und muss mich jetzt noch durch die beweisführung kämpfen, dass das eine ÄR ist Augenzwinkern
Eli Auf diesen Beitrag antworten »

Zitat:
Original von Eli
was beduetet dann sowas zb

(a,b) R (c,d) <=> a-c = b²-d²

ich würde tippen auf

(a,b) UND (c,d) IST ELEMENT R


korrekt also:

((a,b),(c,d)) IST ELEMENT R ?*g*
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »