Ordnungsrelation?
Wie zeige ich antisymmetrie? Reflexiv ist r, da die Bedingung x = y gilt, also gilt (x,x) Element von R. Bei antisymmetrie stehe ich leider auf dem Schlauch.
2 Antworten
Rufe dir zunächst einmal in den Kopf, was Antisymmetrie bedeutet...
Um die Antisymmetrie dieser Relation R zu zeigen, musst du zeigen, dass unter der Voraussetung, wenn zugleich (x, y) ∈ R und (y, x) ∈ R ist, dann x = y folgt.
------ Kurze Vorbemerkung ------
Ich würde mir nun erst einmal die Relation genauer anschauen, evtl. mit ein paar konkreten Beispielen, um ein Gefühl dafür zu bekommen, ob die Relation antisymmetrisch ist (bzw. ob ich evtl. gleich ein Gegenbeispiel finde, wonach die Relation dann nicht antisymmetrisch ist).
Die Zahlen a, b in der Bedingung der Relation (bei Annahme von x ungleich y) geben quasi den Abstand von x bzw. y zur nächstgrößeren durch 3 teilbaren Zahl an. Da a < b sein soll liegt also x näher an der nächsten durch 3 teilbaren Zahl als y, was sich damit widersprechen würde, wenn umgekehrt auch y näher an der nächsten durch 3 teilbaren Zahl liegen würde als x. Dementsprechend könnte man durch dieses grobe Draufschauen schon erkennen, dass die Relation antisymmetrisch ist. Jetzt muss man das natürlich noch zeigen, was ja dein eigentlichen Problem ist.
Da im zweiten Teil der Relationsbedingung quasi nur relvant ist, ob x + a bzw. y + b durch 3 teilbar ist, aber nicht wie groß x + a bzw. y + b tatsächlich sind, wird es sich anbieten, evtl. zu einfacheren Zahlen statt x bzw. y überzugehen (nämlich zu den Resten modulo 3). Aber das wirst du gleich im nächsten Abschnitt noch sehen, was ich meine.
------ Zum Beweis ------
Ich würde eine Art Widerspruchsbeweis durchführen. Dabei kann man dann den ersten Teil der Relationsbedingung mit „x = y oder ...“ unter der Annahme „x ungleich y“ wegfallen lassen...
Voraussetung: (x, y) ∈ R und (y, x) ∈ R
Annahme: x ≠ y
[Ziel ist es nun aus Voraussetung und Annahme einen Widerspruch zu folgern.]
Aus (x, y) ∈ R und x ≠ y folgt, dass es a ∈ {0, 1, 2} und b ∈ {0, 1, 2} gibt, so dass...
... gilt. Führe nun eine Division mit Rest von x bzw. y durch 3 durch. Das liefert eindeutige ganze Zahlen p, q, r, s mit...
Mit der Bedingung [*] kann man dann folgern...
Genauso kann man dann für (y, x) ∈ R und x ≠ y folgern, dass es a₂, b₂ ∈ {0, 1, 2} gibt, sodass für die gleichen r, s gilt...
Nun kann man einfach stupide alle Fälle für r, s ∈ {0, 1, 2} durchgehen, und schauen, welche a, b, a₂, b₂ jeweils möglich sind. [Das sind 9 Fälle, die zu untersuchen sind.]
- Fall [r = 0, s = 0]: In diesem Fall ist a = 0, damit r + a durch 3 teilbar. Genauso ist dann b = 0, damit s + b durch 3 teilbar. Dann wäre jedoch a < b nicht erfüllt. Dieser Fall kann also nicht eintreten.
- Fall [r = 0, s = 1]: In diesem Fall ist a₂= 2, damit s + a₂ durch 3 teilbar. Und es ist b₂ = 0, damit r + b₂ durch 3 teilbar. Dann wäre jedoch a₂ < b₂ nicht erfüllt. Dieser Fall kann also nicht eintreten.
... und so weiter. Du wirst merken, dass für r ≤ s immer die Bedingung [$] nicht erfüllt werden kann und für r ≥ s immer die Bedingung [#] nicht erfüllt werden kann.
Letztendlich kann also keiner der 9 Fälle eintreten, was einen Widerspruch darstellt, sodass also die Annahme, x wäre ungleich y, falsch gewesen sein muss. Es folgt x = y, womit die Antisymmetrie gezeigt ist.
Die Idee, die Zahlen x, y auf die Reste s, r modulo 3 zu reduzieren, entspricht auch quasi der Idee, an die Delte45 in seiner Antwort gedacht hat, eine Abbildung auf die jeweilige Restklasse modulo 3 zu betrachten.
Herr Mihisus Ansatz ist nicht zu verachten da er das Problem elementar angeht. Während mein Ansatz eher abstrakt ist.
Er benutzt das Grundprinzip das man mit Funktionen Ordnungen transportieren kann. Und dabei auf bereits bekanntes zurückgreifen kann.
Ein Kritikpunkt: # und $
r+ a1 und r+b2 sind durch 3 teilbar also gleich 3 , da b2 > 0 . a1= b2 b1= a2
Danke für die ausführliche Lösung..
Der Schlüssel ist zerkennen das a und b als Funktion f(x) unf f(y) geschrieben werden können.
x+a = 3Z ist a äquivalent zu a= 3 Z- x
y+b=3Z ist äquivalent zu b = 3Z -y
Sieht man den funktionalen Zusammenhang.
Setze f(z ) = 3Z-z dann ist a = f(x) und b =f(y) . Genauer gesagt a ist ein Element von 3Z -z . Und es ist 0,1,2 .
Das heißt f(z) ="das Element in 0,1,2 das in 3Z-z liegt
als detail ist zu beachten: das Minus vor dem z kehrt die Ordnung um.
Das heißt die gegebene Relation ordnet nach Rest von modulo 3 .
Zahlen mit gleichen Rest sind nicht Vergleichbar - ausser bei definition mit sich selbst.
Damit haben wir eine sogenannte nicht strikte partial oder Teilordnung.
Nimm a,b in R an und zeige b,a nicht in R
In dem Fall würde ich f: N--->N
f(N)= Restklasse modulo 3 definieren
m S n gilt genau dann wenn f(m) < f( n).
Antisymetrie, und Transivität folgt aus antysymetrie von < .
R= S vereinigt (x,x: x in N) ist dann eine ( partielle) Ordnungsrelation.
- https://de.wikipedia.org/wiki/Antisymmetrische_Relation#Sonderfall_Asymmetrische_Relation
- https://files.ifi.uzh.ch/ee/fileadmin/user_upload/teaching/hs08/form_grund/Relationen.pdf
Das sind nur die ersten beiden Quellen, auf die ich online gestoßen bin. (Ich hätte auch das ein oder andere Buch bei mir rumliegen, welches ich bemühen könnte, wenn dir das nicht reicht.) Und dort wird überall eine Relation als asymmetrisch definiert, wenn für alle a, b aus der Voraussetzung (a, b) ∈ R folgt, dass dann (b, a) ∉ R ist.
Die von dir genannte Bedingung mit „Es gibt (mindestens) ein (a, b) ∈ R mit (b, a) ∉ R“ ist keine übliche Definition von „asymmetrisch“, sondern eine solche Relation wäre nicht symmetrisch. [„nicht symmetrisch“ ist nicht gleichbedeutend mit „asymmetrisch“.]
Und Antisymmetrie ist wiederum dadurch definiert, dass unter der Voraussetzung, wenn (a, b) ∈ R und (b, a) ∈ R ist, folgt, dass dann a = b ist. [„antisymmetrisch“ ist nicht gleichbedeutend mit „asymmetrisch“ und auch nicht gleichbedeutend mit „nicht symmetrisch“. Allerdings ist jede asymmetrische Relation immer auch antisymmetrisch. Wenn du also zeigst, dass die Relation asymmetrisch ist, ist sich auch antisymmetrisch.]
https://en.wikipedia.org/wiki/Partially_ordered_set
Die von dir genannten Konzepte sind ein und das selbe jemandem ob man strikte oder nicht strikte Ordnung bevorzugt.
Und ja asymmetrisch ist gleichbedeutend mit nicht sympathisch. Googles Lexikon liefert das als definition.
Um es klar zu machen.
Asymmetrisch = nicht sympathisch
Antisymetrisch: Relation - = ist antisymetrisch ( das minus ist Mengendifferent).
Antisymetrisch und antireflexiv NOT ( aRb AND bRa)
Im Zusammenhang das man entweder reflexive oder antireflexive Relationen hat macht die Trennug keinen Sinn.
Merke: Eine Funktion von X auf eine geordnete Menge Y induziert immer eine strikte Ordnung von X a< b gdw. f(a) <f(b).
Und < vereinigt = ist dann eine nicht strikte Ordnung.
Das wäre nicht Antisymmetrie, sondern Asymmetrie. Und die vorliegende Relation ist auch nur antisymmetrisch, nicht asymmetrisch.
Denn beispielsweise ist für a = b = 1 nämlich (a, b) = (1, 1) ∈ R. Aber man kann nicht zeigen, dass dann (b, a) ∉ R ist, da tatsächlich (b, a) = (1, 1) ∈ R ist.