Ordnungsrelation/Einführung/Beispiele/Textabschnitt

Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie ${}\geq ,\leq ,\preccurlyeq ,\subseteq$ verwendet. Wir geben nochmal die ausführliche Definition.

Definition

Eine Relation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

1. Es ist  ${}i\preccurlyeq i$  für alle  ${}i\in I$. 
2. Aus  ${}i\preccurlyeq j$  und  ${}j\preccurlyeq k$  folgt stets  ${}i\preccurlyeq k$. 
3. Aus  ${}i\preccurlyeq j$  und  ${}j\preccurlyeq i$  folgt  ${}i=j$. 

Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Zu jeder geordneten Menge ${}(M,\preccurlyeq )$ und jede Teilmenge  ${}N\subseteq M$  ist auch ${}N$ eine geordnete Menge, indem man direkt die Ordnungsbeziehung von ${}M$ übernimmt. Man spricht von der induzierten Ordnung auf ${}N$.

Definition

Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$ heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen  ${}x,y\in I$  die Beziehung ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt.

Man sagt auch, dass bei einer linearen Ordnung je zwei Elementen vergleichbar sind.

Beispiel

Auf den natürlichen Zahlen besteht zwischen ${}n$ und ${}k$ die Ordnungsrelation  ${}n\geq k$,  also ${}n$ ist größergleich ${}k$, wenn man von ${}k$ aus durch endlichfaches Nachfolgernehmen zu ${}n$ gelangt, wobei nullfaches Nachfolgernehmen die Zahl selbst ergibt. Dies ist eine totale Ordnung. Mit der Addition kann man dies folgendermaßen ausdrücken: Es ist  ${}n\geq k$  genau dann, wenn es eine natürliche Zahl ${}m$ mit  ${}n=k+m$  gibt.

Bemerkung  

Eine totale Ordnung auf einer endlichen Menge ist durch ein Angangselement (kleinstes Element) und dadurch gegeben, dass jedem Element (außer dem größten Element) das nächstkleinste Element zugeordnet wird. In der Skizze wird nur diese Zuordnung dargestellt, die gesamte Ordnung ergibt sich, wenn man sich Selbstpfeile und transitive Pfeile dazudenkt.

Auf einer endlichen Menge ${}M$ mit ${}n$ Elementen sind die totalen Ordnungen einfach zu überschauen. Eine totale Ordnung auf ${}M$ ist das gleiche wie eine bijektive Abbildung ${}\varphi \colon {\{1,\ldots ,n\}}\rightarrow M$, also eine Nummerierung von ${}M$. Eine solche Nummerierung legt über  ${}\varphi (i)\geq \varphi (j)$,  falls  ${}i\geq j$,  eine totale Ordnung fest, und eine totale Ordnung legt eine Nummerierung fest, indem ${}1$ auf das kleinste Element von ${}M$ abgebildet wird, ${}2$ auf das zweitkleinste Element u.s.w. Insbesondere gibt es wegen Fakt ${}n!$ totale Ordnungen auf ${}M$. Es ist ziemlich schwierig, sich eine systematische Übersicht über alle (auch die nicht totalen) Ordnungen in einer endlichen Menge zu verschaffen.

Beispiel

Es sei ${}A$ ein Alphabet und ${}W$ die Menge der Wörter über diesem Alphabet, also die Menge alle endlichen Ketten über ${}A$ oder eine Teilmenge davon, etwa die Menge der real existierenden Wörter. Auf ${}A$ sei eine totale Ordnung gegeben. Dann definiert man auf ${}W$ die sogenannte lexikographische Ordnung, indem für Wörter ${}w,z$ die Beziehung

${}w\preccurlyeq _{\text{lex}}z\,$

(${}w$ kommt im Lexikon vor ${}z$) genau dann gilt, wenn sie gleich sind oder wenn an der ersten Stelle von vorne gelesen, wo sich ${}w$ und ${}z$ unterscheiden, der Buchstabe von ${}w$ an dieser Stelle im Alphabet vor dem Buchstaben von ${}z$ an dieser Stelle kommt, was den Fall einschließen mag, dass an dieser Stelle ${}w$ keinen Buchstaben mehr hat („Vers“ kommt vor „Verstand“). Die lexikographische Ordnung ist eine totale Ordnung.

Beispiel

Auf jeder Menge ${}M$ ist die identische Relation, also die Relation, bei der jedes Element nur mit sich selbst in Relation steht, eine Ordnungsrelation.

Definition

Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung ${}\geq$ auf ${}R$ gibt, die die beiden Eigenschaften

1. Aus  ${}a\geq b$  folgt  ${}a+c\geq b+c$  für beliebige  ${}a,b,c\in R$, 
2. Aus  ${}a\geq 0$  und  ${}b\geq 0$  folgt  ${}ab\geq 0$  für beliebige  ${}a,b\in R$, 

erfüllt.

Ein angeordneter Ring ist also nicht nur ein Ring, auf dem es zusätzlich noch eine totale Ordnung gibt, sondern die Ordnung muss auch mit den algebraischen Verknüpfungen in der beschriebenen Weise verbunden sein. Ein angeordneter Ring, der ein Körper ist, heißt angeordneter Körper. Die ganzen Zahlen ${}\mathbb {Z}$, die rationalen Zahlen ${}\mathbb {Q}$ und die reellen Zahlen ${}\mathbb {R}$ sind angeordnete Ringe bzw. Körper. Der Körper der komplexen Zahlen ${}{\mathbb {C} }$ ist nicht angeordnet (und lässt sich auch nicht anordnen).

Definition

Man sagt, dass die natürliche Zahl ${}a$ die natürliche Zahl ${}b$ teilt (oder dass ${}b$ von ${}a$ geteilt wird, oder dass ${}b$ ein Vielfaches von ${}a$ ist), wenn es eine natürliche Zahl ${}c$ derart gibt, dass  ${}b=c\cdot a$  ist. Man schreibt dafür auch ${}a{|}b$.

Achtung! Die Teilbarkeitsbeziehung in ${}\mathbb {N}$ sollte man allein innerhalb der natürlichen Zahlen behandeln. Man vermeide Formulierungen wie, dass ${}a$ die Zahl ${}b$ teilt, wenn bei der Division von ${}b$ durch ${}a$ kein Rest bleibt oder dass der Bruch ${}{\frac {b}{a}}$ ganzzahlig ist. Solche Charakterisierungen mit deutlich komplizierteren Strukturen verdunkeln den einfachen Sachverhalt.

Lemma

In ${}\mathbb {N}$ gelten folgende Teilbarkeitsbeziehungen.

1. Für jede natürliche Zahl ${}a$ gilt ${}1\,{|}\,a$ und ${}a\,{|}\,a$.
2. Für jede natürliche Zahl ${}a$ gilt ${}a\,{|}\,0$.
3. Gilt ${}a\,{|}\,b$ und ${}b\,{|}\,c$, so gilt auch ${}a\,{|}\,c$.
4. Gilt ${}a\,{|}\,b$ und ${}c\,{|}\,d$, so gilt auch ${}ac\,{|}\,bd$.
5. Gilt ${}a\,{|}\,b$, so gilt auch ${}ac\,{|}\,bc$ für jede natürliche Zahl ${}c$.
6. Gilt ${}a\,{|}\,b$ und ${}a\,{|}\,c$, so gilt auch ${}a\,{|}\,{\left(rb+sc\right)}$ für beliebige natürliche Zahlen ${}r,s$.

Beweis

Siehe Aufgabe.

$\Box$

Beispiel

Wir betrachten die positiven natürlichen Zahlen ${}\mathbb {N} _{+}$ zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine Ordnung auf ${}\mathbb {N} _{+}$. Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ${}n{|}n$ ist, wie  ${}m=1$  zeigt. Die Transitivität wurde in Fakt  (3) gezeigt. Die Antisymmetrie folgt so: Aus ${}n=ak$ und ${}k=bn$ folgt  ${}n=(ab)n$.  Da wir uns auf positive natürliche Zahlen beschränken, folgt mit der Kürzungsregel  ${}ab=1$  und daraus wegen  ${}a,b\leq ab$  auch  ${}a=b=1$.  Also ist  ${}k=n$.  Einfache Beispiele wie $2$ und $3$ zeigen, dass hier keine totale Ordnung vorliegt, da weder ${}2$ von ${}3$ noch umgekehrt geteilt wird.

Beispiel

Es sei ${}M$ eine beliebige Menge und  ${}R={\mathfrak {P}}\,(M)$  die Potenzmenge davon. Dann sind die Elemente aus  ${}R={\mathfrak {P}}\,(M)$  - also die Teilmengen von ${}M$ - durch die Inklusionsbeziehung ${}\subseteq$ geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus  ${}T_{1}\subseteq T_{2}$  und  ${}T_{2}\subseteq T_{3}$  die Inklusion  ${}T_{1}\subseteq T_{3}$  folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen ${}T_{1},T_{2}$ sind genau dann gleich, wenn ${}T_{1}\subseteq T_{2}$ und umgekehrt ${}T_{2}\subseteq T_{1}$ gilt.

Beispiel

Es sei ${}X$ eine Menge (beispielsweise ein reelles Intervall, oder ein topologischer Raum), so ist die Menge der (stetigen) Funktionen ${}f\colon X\rightarrow \mathbb {R}$ geordnet, indem man  ${}f\geq g$  dadurch definiert, dass  ${}f(x)\geq g(x)$  für jeden Punkt  ${}x\in X$  sein muss. Dies ist offensichtlich keine totale Ordnung.

Definition

Es sei ${}(M_{i},\leq _{i})$, ${}i\in I$, eine Familie von geordneten Mengen. Dann nennt man die auf der Produktmenge  ${}M=\prod _{i\in I}M_{i}$  durch

${}(x_{i})_{i\in I}\leq (y_{i})_{i\in I}\,,$

falls

${}x_{i}\leq _{i}y_{i}\,$

für alle  ${}i\in I$  gilt, die Produktordnung.

In Beispiel werden die reellen Zahlen so oft genommen, wie es ${}X$ vorgibt. Dort liegt also eine Produktordnung vor.