Komposition und homogene Relationen
-
Hi Jungens, ...
ich fange gerade das Studium als Informatiker an und habe da so meine Verständnissprobleme mit eingen Aufgaben.
Ich habe hie riene Beispielaufgabe und ich komme nciht auf die Lösung, also wie ich es Beweise etc. auch google mag mir leider nciht soweit helfen, dass ich es auch verstehe.
Aufgabe:
Gegeben sei eine Produktoperation (Komposition) von homogenen Relationen über einer vorgegebenen Menge . Welche Eigenschaften treffen zu(?):
assoziativ?
kommutativ?
hat ein neutrales Element?Das ist die Aufgabe. Ich weiß was eine Komposition ist und ich kenne die Eigenschaften der Assoziativität, Kommutativität und des neutralen Elementes. Doch leider weiß ich nciht wie ich es Beweise. Also wie kann ich beweisen, dass die Komposition assoziativ ist?
Ich bitte um Hilfe im Sinne von - Nicht nur Lösung, sondern lieber warum die Lösung so ist. Mit Beispiel.
Thx für jeden schonmal der sich die Mühe macht mir zu helfen.
Gruß Jenna
-
Für ein Beispiel hab ich grad keine Zeit. Aber nimm Dir doch mal drei homogene Relationen R,S,T auf einer Menge A her. Nun schreib mal die Definition von R o (S o T) auf und die von (R o S) o T. Also jeweils in die Definition einsetzen. Nun kannste entweder zeigen, daß beide Bedingungen gleich sind (was ich stark vermute) oder Du bastelst solange dran rum, bis Dir klar ist wo der genaue Unterschied liegt. Danach kannste ein Gegenbeispiel angeben (hier wohl nicht nötig).
Bei Kommutativ würde ich ähnlich vorgehen, aber da wirste wohl ein Gegenbeispiel finden müssen.
Als Neutralelement würde ich es mal mit der Relation R = { (a,a) | a \in A } versuchen.
-
So also ich habe dann mal geschaut und müsste nur noch wissen ob das so ok ist, folgendes habe ich gemacht.
M={1,2,3}
R,S Teilmenge des kartesischen Produktes von M
R={(1,1),(1,2)}
S={(2,3),(3,3)}RoS ist definiert als { (x,z)|(x,z) in MxM und es gibt ein y [y in M und (x,y) in R und (y,z) in S] }
RoS = {(1,3)}
(1,3) notin SoR weil{ (1,3) | (1,3) in MxM ABER es gibt kein y [y in M und (1,y) in S und (y,3) in R] }
Also
RoS ungleich SoRStimmt das denn so, .... oder habe ich immernoch Fehler drinne? Damit würde ich halt beweisen das die Kommutativität nicht gilt. (bzw. möchte ich beweisen ;))
Grüße Jenna
-
Ja, das ist so korrekt, wenn auch der Aufschrieb mit {(1,3)|...} ein bißchen merkwürdig ist.
-
Ich muss jeztt leider beim nächste, das ich das ganze mit dem Beweis des neutralen Elements nicht verstehe ... grml
Ich verstehe die Relation, die du mir notiert hast, und was ein neutrales Element ist, doch weiß ich immernoch nciht wie ich es auf die Relation umsetzten soll.
Das neutrale Element von den natürlichen Zahlen ist 1, weil jede natürlich eZahl x mal 1 = x ergibt. Aber ich weiß nicht wie ich das auf die relation umsetze.
Kannst du mir das oder jemand anderes vll ein bisschen näher erläutern?
Thx Jenna
-
Was Du suchst ist eine Relation E, so dass für jede Relation R gilt: R = R o E = E o R.
Die Relation, die ich oben angegeben habe sollte genau das erreichen. Versuche mal für beliebiges R die Relation R o E auzuschreiben. Benutze dann die spezielle Definition von E um das zu vereinfachen.
-
Also, ich habe es dann mal aufgearbeitet und verstehe nur auf jedenfall welches das neutrale Element ist.
Jetzt aber der Beweiß und meine Frage ob man es so beweisen kann (?)
A = Trägermenge
E = neutrales Element
R = beliebige Relation
RoE = EoR = RRoE bsp. {(a,b)} o {(b,b)} = {(b,b)} o {(a,b)} = {(a,b)} ; a,b in A
das heißt das für E (neutrales Element) ein (b,b) Tupel für jedes Element in A existieren muss, also ...E = {(a,a)| \forall a in A}
Reicht dieses jetzt als vollständigen Beweis und ist es auch logisch?
Für mich ist es logisch, aber das muss ja nichts heißen.Grüße Jenna