Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 7

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Dies ist Dr. Ines Eisenbeis. Sie ist für die wissenschaftliche Begleitung des Projektes Vorlesungshund verantwortlich. Ihre Arbeitshypothesen sind: 1) Studierende gehen lieber zur Vorlesung, 2) Außenseiter werden aus ihrer Isolation geholt, 3) Auffälligkeiten reduzieren sich, 4) Positive Sozialkontakte werden gefördert, 5) Profs werden mehr beachtet.




Ordnungsrelationen

Eine reflexive, transitive und antisymmetrische Relation nennt man eine Ordnung, wofür man häufig ein Symbol wie verwendet. Wir geben nochmal die ausführliche Definition.


Definition  

Eine Relation auf einer Menge heißt Ordnungsrelation oder Ordnung, wenn folgende drei Bedingungen erfüllt sind.

  1. Es ist für alle .
  2. Aus und folgt stets .
  3. Aus und folgt .

Eine Menge mit einer fixierten Ordnung darauf heißt geordnete Menge. Zu jeder geordneten Menge und jede Teilmenge ist auch eine geordnete Menge, indem man direkt die Ordnungsbeziehung von übernimmt. Man spricht von der induzierten Ordnung auf .


Definition  

Eine Ordnungsrelation auf einer Menge heißt lineare Ordnung (oder totale Ordnung), wenn zu je zwei Elementen die Beziehung oder gilt.

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


Beispiel  

Auf den natürlichen Zahlen besteht zwischen und die Ordnungsrelation , also ist größergleich , wenn man von aus durch endlichfaches Nachfolgernehmen zu 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 genau dann, wenn es eine natürliche Zahl mit 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 mit Elementen sind die totalen Ordnungen einfach zu überschauen. Eine totale Ordnung auf ist das gleiche wie eine bijektive Abbildung , also eine Nummerierung von . Eine solche Nummerierung legt über , falls , eine totale Ordnung fest, und eine totale Ordnung legt eine Nummerierung fest, indem auf das kleinste Element von abgebildet wird, auf das zweitkleinste Element u.s.w. Insbesondere gibt es wegen Satz 2.4 totale Ordnungen auf . Es ist ziemlich schwierig, sich eine systematische Übersicht über alle (auch die nicht totalen) Ordnungen in einer endlichen Menge zu verschaffen.



Beispiel  

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

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



Beispiel  

Auf jeder Menge 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 auf gibt, die die beiden Eigenschaften

  1. Aus folgt für beliebige ,
  2. Aus und folgt für beliebige ,

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 , die rationalen Zahlen und die reellen Zahlen sind angeordnete Ringe bzw. Körper. Der Körper der komplexen Zahlen ist nicht angeordnet (und lässt sich auch nicht anordnen).

Verband Teiler30.png

Definition  

Man sagt, dass die natürliche Zahl die natürliche Zahl teilt (oder dass von geteilt wird, oder dass ein Vielfaches von ist), wenn es eine natürliche Zahl derart gibt, dass ist. Man schreibt dafür auch .

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



Lemma

In gelten folgende Teilbarkeitsbeziehungen.

  1. Für jede natürliche Zahl gilt und .
  2. Für jede natürliche Zahl gilt .
  3. Gilt und , so gilt auch .
  4. Gilt und , so gilt auch .
  5. Gilt , so gilt auch für jede natürliche Zahl .
  6. Gilt und , so gilt auch für beliebige natürliche Zahlen .

Beweis

Siehe Aufgabe 7.18.



Beispiel  

Wir betrachten die positiven natürlichen Zahlen zusammen mit der Teilbarkeitsbeziehung. Dies ergibt eine Ordnung auf . Die Teilbarkeitsrelation ist in der Tat reflexiv, da stets ist, wie zeigt. Die Transitivität wurde in Lemma 7.9  (3) gezeigt. Die Antisymmetrie folgt so: Aus und folgt . Da wir uns auf positive natürliche Zahlen beschränken, folgt mit der Kürzungsregel und daraus wegen auch . Also ist . Einfache Beispiele wie und zeigen, dass hier keine totale Ordnung vorliegt, da weder von noch umgekehrt geteilt wird.



Beispiel  

Sei eine beliebige Menge und die Potenzmenge davon. Dann sind die Elemente aus - also die Teilmengen von - durch die Inklusionsbeziehung geordnet. Die Reflexivität bedeutet einfach, dass eine jede Menge in sich selbst enthalten ist und die Transitivität bedeutet, dass aus und die Inklusion folgt. Die Antisymmetrie ist dabei ein wichtiges Beweisprinzip für die Gleichheit von Mengen: Zwei Mengen sind genau dann gleich, wenn und umgekehrt gilt.



Beispiel  

Sei eine Menge (beispielsweise ein reelles Intervall, oder ein topologischer Raum), so ist die Menge der (stetigen) Funktionen geordnet, indem man dadurch definiert, dass für jeden Punkt sein muss. Dies ist offensichtlich keine totale Ordnung.



Definition  

Es sei , , eine Familie von geordneten Mengen. Dann nennt man die auf der Produktmenge durch

falls

für alle gilt, die Produktordnung.

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



Ordnungstreue Abbildungen

Definition  

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt ordnungstreu (oder monoton), wenn für alle mit stets auch gilt.

Monotonicity example1.svg

Monotone Abbildungen zwischen und sind aus den Anfängervorlesungen bekannt. Ordnungstreue Abbildungen sind einfach die relationstreuen Abbildungen, wenn die beteiligten Relationen Ordnungen sind.


Definition  

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt ordnungsvolltreu, wenn für alle genau dann gilt, wenn gilt.

Wenn total geordnet und die Abbildung injektiv ist, so muss man nicht zwischen ordnungstreu und ordnungsvolltreu unterscheiden, sonst aber schon. Zu eine Teilmenge einer geordneten Menge mit der induzierten Ordnung ist die Inklusion ordnungsvolltreu. Wenn man dagegen eine Teilmenge mit einer schwächeren Ordnung, beispielsweise der identischen Ordnung versieht, so ist die Inklusion zwar ordnungstreu, aber nicht ordnungsvolltreu. Eine ordnungsvolltreue Abbildung ist stets injektiv.



Lemma

Es sei eine geordnete Menge und die Potenzmenge von .

Dann ist die Abbildung

ordnungsvolltreu und injektiv ist, wobei die Potenzmenge mit der Inklusion versehen ist.

Beweis

Siehe Aufgabe 7.28.


Diese Aussage besagt, dass die Inklusionsbeziehung zwischen Teilmengen in einem gewissen Sinne die universelle Ordnungsbeziehung ist, da sich jede geordnete Menge als Unterobjekt davon realisieren lässt. Beispielsweise gilt für reelle Zahlen die Beziehung genau dann, wenn

gilt. Allerdings muss man dafür auch einen hohen Preis bezahlen, nämlich, dass man einfache Elemente mit großen Mengen identifizieren und dann unnötigen Ballast mitschleppen muss, und dass man total geordnete Mengen in nicht total geordnete Mengen einbettet. Dennoch sind solche und ähnliche universelle Überlegungen für theoretische Überlegungen wichtig, siehe Aufgabe 4.13, oder das Konzept der durch eine ganze Zahl erzeugten Untergruppe (siehe die nächste Vorlesung), oder Satz 9.22, oder die Definition einer Äquivalenzklasse für ähnliche Konstruktionen.

Wir erwähnen noch die folgende Variante einer ordnungstreuen Abbildung.


Definition  

Es seien und zwei Mengen, auf denen jeweils eine Ordnung definiert ist. Eine Abbildung

heißt monoton fallend, wenn für alle mit stets gilt.

Statt monoton fallend sagt man manchmal auch antimonoton. Dies ist nicht ein wirklich eigenständiger Begriff, da man ja eine Ordnungsrelation wie jede Relation auf einer Menge umkehren kann, also die Rolle der beiden Elemente vertauschen kann.



Extremaleigenschaften

Definition  

Sei eine geordnete Menge. Ein Element heißt größtes Element von , wenn für jedes gilt.


Definition  

Sei eine geordnete Menge. Ein Element heißt kleinstes Element von , wenn für jedes gilt.


Definition  

Sei eine geordnete Menge. Ein Element heißt maximal (in ) oder ein maximales Element (von ), wenn es kein Element , , mit gibt.


Definition  

Sei eine geordnete Menge. Ein Element heißt minimal (in ) oder ein minimales Element (von ), wenn es kein Element , , mit gibt.

Bei einer total geordneten Menge fallen die Konzepte größtes Element und maximales Element zusammen, im Allgemeinen muss man sie aber sorgfätig unterscheiden. Ein größtes Element ist, wenn es existiert, eindeutig bestimmt und dann auch das einzige maximale Element.

In einer endlichen geordneten Menge gibt es stets maximale und minimale Elemente.

Das abgeschlossene Intervall besitzt die als kleinstes und die als größtes Element, das offene Intervall besitzt weder minimale noch maximale Elemente.

In der Menge der natürlichen Zahlen mit der durch die Teilbarkeitrelation gegebenen Ordnung ist das kleinste Element, da die jede Zahl teilt, und die ist das größte Element, da die von jeder Zahl geteilt wird. Auf mit der Teilbarkeitsrelation sind genau die Primzahlen die minimalen Elemente, es gibt keine maximalen Elemente. Bei einer Potenzmenge mit der durch die Inkusion gegebenen Ordnung ist die leere Menge das kleinste Element und die Gesamtmenge das größte Element. Wenn man die leere Menge aus der Potenzmenge herausnimmt, so sind die einelementigen Teilmengen die minimalen Elemente (diese nennt man auch Atome).


Definition  

Sei eine geordnete Menge und eine Teilmenge. Ein Element heißt obere Schranke für , wenn für jedes gilt.


Definition  

Sei eine geordnete Menge und eine Teilmenge. Ein Element heißt untere Schranke für , wenn für jedes gilt.


Definition  

Sei eine geordnete Menge und eine Teilmenge. Ein Element heißt Supremum von , wenn die kleinste obere Schranke von ist.


Definition  

Sei eine geordnete Menge und eine Teilmenge. Ein Element heißt Infimum von , wenn die größte untere Schranke von ist.

Für das offene Intervall ist jede reelle Zahl eine obere Schranke und ist das Supremum.

Wir besprechen einige weitere Teilbarkeitsbegriffe und erfassen sie mit unserem ordnungstheoretischen Vokabular.


Definition  

Seien natürliche Zahlen. Dann heißt eine natürliche Zahl gemeinsamer Teiler der , wenn jedes teilt ().

Eine natürliche Zahl heißt größter gemeinsamer Teiler der , wenn ein gemeinsamer Teiler ist und wenn jeder gemeinsame Teiler dieses teilt.

Die Elemente heißen teilerfremd, wenn ihr größter gemeinsamer Teiler ist.

Ein gemeinsamer Teiler ist eine untere Schranke von bezüglich der Teilbarkeitsrelation und der größte gemeinsame Teiler ist das Infimum davon.


Definition  

Zu einer Menge von natürlichen Zahlen

heißt eine natürliche Zahl ein gemeinsames Vielfaches, wenn ein Vielfaches von jedem ist, also von jedem geteilt wird.

Die Zahl heißt ein kleinstes gemeinsames Vielfaches der , wenn ein gemeinsames Vielfaches ist und wenn jedes andere gemeinsame Vielfache ein Vielfaches von ist.

Ein gemeinsames Vielfaches ist eine obere Schranke von und das kleinste gemeinsame Vielfache ist das Supremum davon.


Beispiel  

Zu natürlichen Zahlen bildet die Menge aller gemeinsamer Teiler der eine endliche Menge, die bezüglich der Teilbarbeit geordnet ist. Dabei ist der größte gemeinsame Teiler in in der Tat das größte Element und ist der kleinste gemeinsame Teiler. Es ist keineswegs selbstverständlich, dass es einen größten gemeinsamen Teiler gibt, das hängt mit der eindeutigen Primfaktorzerlegung zusammen und folgt beispielsweise aus Satz 8.4. Unter der Ordnungsrelation gibt es in natürlich ein größtes Element, es ist aber eine zahlentheoretische Besonderheit, dass dieses Element von allen anderen gemeinsamen Teilern geteilt wird.

Die Menge der gemeinsamen Vielfachen von ist unendlich und ist ebenfalls über die Teilbarkeit geordnet. Das kleinste gemeinsame Vielfache ist darunter das kleinste Element, und zwar bezüglich der Teilbarkeitsrelation als auch bezüglich der Größergleichrelation.



<< | Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)