Funktionen (Teschl/Teschl 5.2)

Eine Funktion (oder Abbildung)

f : M → N, x 7→ f (x)

ordnet jedem Element x einer Menge M (De�nitionsbereich)eindeutig ein Element y = f (x) einer Menge N (Werte- oderBildbereich) zu.

Beispiele

Student 7→ Matrikelnummer,

Digitalfoto 7→ Dateigröÿe,

f : Z→ N, n 7→ (n + 1)2,

g : R→ R, x 7→ x ·sin xx2+1

1 / 48

Gegenbeispiele

Keine Funktionen sind

I Person 7→ Handynummer,da 1. nicht jeder ein Handy hat und 2. es Personen mitmehr als einem Handy gibt.

I f : R→ R, x 7→√x ,

da die Wurzel nur für nichtnegative x de�niert ist.

f wird zur Funktion, wenn man als De�nitionsbereichstatt R die Menge R+ = {x ∈ R : x ≥ 0} betrachtet.

I Person 7→ Ehepartner,da nicht jeder verheirated ist.

Wird zur Funktion, wenn man nur verheiratete Personenbetrachtet.

I Student 7→ Studienfach,da es möglich ist, mehrere Fächer zu studieren.

2 / 48

Darstellung von Funktionen

I durch Abbildungsvorschrift (Funktionsgleichung), z. B.f (x) = x2,

I durch Wertetabelle, z. B. Adressdatenbank,I bei reellen Funktionen durch Funktionsgraphen: Mengealler Wertepaare (x , f (x)) als Punkte in der Ebene.

Graph von f (x) = 11+x2

3 / 48

Injektiv und surjektivEine Funktion f : M → N heiÿt

I injektiv, wenn für x1 6= x2 gilt f (x1) 6= f (x2).Äquivalente Formulierungen sind:�Aus f (x1) = f (x2) folgt x1 = x2� oder�Zu jedem y ∈ N gibt es höchstes ein x ∈ M mitf (x) = y .�

I surjektiv, wenn es zu jedem y ∈ N (mindestens) einx ∈ M gibt mit f (x) = y ,d. h. jedes Element y aus dem Wertebereich auchtatsächlich als Funktionswert angenommen wird.

I bijektiv, wenn sie injektiv und surjektiv ist.In diesem Fall gibt es zu jedem y ∈ M genau ein x ∈ Nmit f (x) = y .

4 / 48

BeispieleI Die Abbildung Student 7→ Matrikelnummer ist injektiv, daMatrikelnummern nicht mehrfach vergeben werden.Sie ist typischerweise nicht surjektiv, da nicht alle in Fragekommenden Matrikelnummern tatsächlich vergeben sind.

I Die Abbildung Student 7→ Geburtsdatum ist nicht injektiv.I Die Funktion f : R→ R, x 7→ x3 ist bijektiv,denn zu jedem y ∈ R gibt es genau ein x ∈ R (x = 3

√y)

mit f (x) = y .I Die Funktion f : N→ N, n 7→ n + 2 ist injektiv(aus f (m) = f (n)⇔ m + 2 = n + 2 folgt m = n).f ist nicht surjektiv, da es z. B. kein n ∈ N gibt mitf (n) = 1.

BemerkungDurch Einschränkung des Wertebereichs kann jede Funktion�surjektiv gemacht� werden.

5 / 48

injektiv, aber nicht surjektiv

6 / 48

surjektiv, aber nicht injektiv

7 / 48

weder surjektiv noch injektiv

8 / 48

bijektiv (surjektiv und injektiv)

9 / 48

Umkehrfunktion

Ist f : M → N bijektiv, so gibt es zu jedem y aus demWertebereich N genau ein x aus dem De�nitionsereich M mitf (x) = y .

Damit lässt sich die Umkehrfunktion f −1 : N → M durch�Umkehrung der Zuordung� de�nieren:

x = f −1(y)⇔ y = f (x).

Beispiel

Sitzplatz 7→ Student (im voll besetzten Hörsaal),

f (x) = 2x + 1⇒ f −1(y) = 12(y − 1).

f (x) = x3 ⇒ f −1(y) = 3√y .

10 / 48

Bestimmung der UmkehrfunktionI durch �Umkehrung� der Zuordnung einer Tabelle,I durch Au�ösung der Funktionsgleichung y = f (x) nach x ,I bei reellen Funktionen geometrisch durch Spiegelung desFunktionsgraphen an der Winkelhalbierenden y = x .

11 / 48

Verknüpfung von Funktionen

Sind f : M → R und g : M → R Funktionen, so sind auch

f + g : x 7→ f (x) + g(x), f − g : x 7→ f (x)− g(x),

f · g : x 7→ f (x) · g(x)

und fg: x 7→ f (x)

g(x)(falls g(x) 6= 0)

wieder Funktionen mit De�nitionsbereich M und Wertebereich R.

Komposition (Hintereinanderausführung)

Sind f : A→ B und g : B → C Funtionen, so ist

g ◦ f : A→ C , a 7→ g(f (a))

eine Funktion mit De�nitionsbereich A und Wertebereich C .

12 / 48

Beispiel

(1) Mit f (x) = x + 1 und g(x) = 2x ist

(f + g)(x) = 3x + 1, (f − g)(x) = 1− x ,

(f · g)(x) = 2x2 + 2x , fg(x) = 1

2+ 1

2x,

(f ◦ g)(x) = 2x + 1, (g ◦ f )(x) = 2x + 2.

(2) Mit A Menge der Studenten,

B Menge aller Tage zwischen 1900 und 2009,

f : A→ B , Student 7→ Geburtstag,

C = N natürliche Zahlen und

g : B → C , Geburtstag 7→ Lebensalter

ist g ◦ f : A→ C die Abbildung, die jedem Studenten seinAlter zuordnet.

13 / 48

BemerkungenI Die Komposition g ◦ f ist immer dann de�niert, wenn derWertebereich von f im De�nitionsbereich von g liegt.

I Ist g ◦ f de�niert, so muss f ◦ g nicht de�niert sein.I Die Komposition ist nicht kommutativ. Sind sowohl g ◦ fals auch f ◦ g de�niert, so gilt im allgemeinen nichtf ◦ g = g ◦ f .

I Die Komposition ist assoziativ, d. h. falls g ◦ f und h ◦ gde�niert sind, gilt

h ◦ (g ◦ f ) = (h ◦ g) ◦ f .

I g ist Umkehrfunktion von f genau dann, wenn(g ◦ f )(x) = x und (f ◦ g)(y) = y für alle x , y .

14 / 48

Reelle Funktionen

sind Funktionen, deren De�nitions- und WertemengeTeilmengen der reellen Zahlen R sind.

Der De�nitionsbereich ist dabei typischerweise ein Intervall(= �zusammenhängende� Teilmenge von R) bzw. eineVereinigung von Intervallen.

Zu a, b ∈ R mit a < b betrachtet man

I [a, b] = {x ∈ R : a ≤ x ≤ b} (abgeschlossenes Intervall),I (a, b) =]a, b[= {x ∈ R : a < x < b} (o�enes Intervall),I [a, b) = {x ∈ R : a ≤ x < b} sowieI (a, b] = {x ∈ R : a < x ≤ b} (halbo�ene Intervalle),I [a,∞) = {x ∈ R : x ≥ a} sowieI (−∞, b] = {x ∈ R : x ≤ b} (unbeschränkte Intervalle)I und analog (a,∞), (−∞, b) sowie (−∞,∞).

15 / 48

Bemerkung

Eine durch eine Funktionsgleichung y = f (x) de�nierte reelleFunktion hat einen �natürlichen� maximalen De�nitionsbereichbestehend aus allen x ∈ R, für die f (x) sinnvoll de�niert istund eine reelle Zahl ergibt.

Beispiele

I f (x) =√x ist de�niert auf R+ = [0,∞)

I f (x) = ln x ist de�niert auf (0,∞)

I f (x) = x3 − 2x2 + 3x − 1 ist de�niert auf RI f (x) = 1

x2−1 ist de�niert aufR \ {−1, 1} = (−∞,−1) ∪ (−1, 1) ∪ (1,∞)

Der tatsächlich betrachtete De�nitionsbereich kann je nachAnwendung eine Teilmenge des maximalen De�ntionsbereichssein.

16 / 48

Invertierbarkeit reeller Funktionen

Eine auf einem Intervall de�nierte reelle Funktion ist stetig,wenn ihr Graph zusammenhängend ist.

Sie ist streng monoton wachsend, wenn für x < y giltf (x) < f (y) bzw. streng monoton fallend, wenn für x < y giltf (x) > f (y).

Es gilt: Eine stetige Funktion ist genau dann bijektiv (beigeeigneter Wahl von De�nitions- und Wertebereich), wenn siestreng monoton wachsend oder streng monoton fallend ist.

17 / 48

Spezielle reelle Funktionen

I Lineare Funtionen f (x) = ax + b,Beispiel f (x) = 4x − 1,

I Polynome oder ganzrationale Funktionenf (x) = anxn + an−1xn−1 + ...+ a1x + a0,Beispiel f (x) = 2x3 − x2 + x − 2.Hier ist n = 3, a3 = 2, a2 = −1, a1 = 1 und a0 = −2.

I (gebrochen)rationale Funktionen, z. B.f (x) = x3−2x2+x−2

3x2−x+2,

I Weitere Funktionen wie z. B.f (x) =

√x , sin x , cos x , 2x , ex , log2 x , ln x ,...

18 / 48

Polynome

sind reelle Funktionen, die sich ausschlieÿlich mit denRechenoperationen Addition, Subtraktion und Multiplikationberechnen lassen. Die allgemeine Funktionsgleichung einesPolynoms p ist

p(x) =∑n

k=0 akxk = anxn + an−1xn−1 + ...+ a1x + a0 mit

Koe�zienten a0, ..., an ∈ R.

Ist an 6= 0, so ist n = deg p ∈ N der Grad (engl. degree) von p.

Beispiel: p1(x) = x2 + 2x + 2, p2(x) = −x3,p3(x) = 2− x − x2 + 3x4 und p4(x) = 2x7 − 4x4 + 3x2 − 1sind Polynome vom Grad 2, 3, 4 bzw. 7.

Allgemein ist der Grad die höchste Potenz n, in der dieVariable x in der Funktionsgleichung auftritt.

19 / 48

Eigenschaften von Polynomen

I Polynome p(x) sind für alle x ∈ R de�niert.I Sind p und q Polynome, so sind auch p + q, p − q, p · qund p ◦ q Polynome, d. h. Summe, Di�erenz, Produktund Komposition von Polynomen ergibt jeweils wieder einPolynom.

I Konstante Funktion p(x) = a0 sind Polynome vom Grad0, der Nullfunktion p(x) = 0 wird der Grad −∞zugeordnet.

I Polynome p(x) = a1x + a0 vom Grad 1 sind lineareFunktionen, ihr Funktionsgraph ist eine Gerade.

I Quadratische Polynome p(x) = a2x2+ a1x + a0 haben denGrad 2, ihr Funktionsgraph ist eine Parabel. Dabei wirdder Graph von f (x) = x2 als Normalparabel bezeichnet.

20 / 48

Nullstellen von Polynomen

Die Nullstellen (d. h. Lösungen der Gleichung f (x) = 0) einesquadratischen Polynoms f (x) = x2 + py + q erhält man durchdie

pq�Formel: x1,2 = −p2±√(

p2

)2 − q.

Ist der Ausdruck unter der Wurzel negativ, so hat p(x) keinereellen Nullstellen.

Liegt ein quadratisches Polynom in der allgemeinen Formf (x) = ax2 + bx + c , so wird erst durch a gekürzt:

ax2 + bx + c = 0⇔ x2 + bax + c

a= 0

Beispiel: 3x2 + 3x − 6 = 0⇔ x2 + x − 2 = 0

⇔ x = −12±√(

12

)2+ 2 = −1

2±√

94= −1

2± 3

2,

d. h. die Gleichung hat zwei Lösungen x1 = −2 und x2 = 1.

21 / 48

Berechnung von Polynomen mit HornernerschemaDurch geschickte Klammerung kann die Zahl derRechenoperationen bei der Auswertung eines Polynomsvermindert werden:

f (x) = a3x3 + a2x2 + a1x + a0 = ((a3x + a2)x + a1)x + a0

Dies führt zu folgendem rekursiven Algorithmus: y1 = an,

yi+1 = yi · x + an−i für i = 1, ..., n.

Dann ist: yn+1 = f (x).

BeispielZu berechnen ist f (−1) für f (x) = 2x4−3x3 + x2 + 3x − 3(mit Grad n = 4). Man erhält y1 = a4 = 2,y2 = y1 · (−1) + a3 = −2−3 = −5,y3 = y2 · (−1) + a2 = 5+ 1 = 6,y4 = y3 · (−1) + a1 = −6+ 3 = −3 undy5 = y4 · (−1) + a0 = 3− 3 = 0. Also ist f (−1) = y5 = 0.

22 / 48

Notation als �Schema�

Berechne f (−1) für f (x) = 2x4 − 3x3 + x2 + 3x − 3:

⇒ f (−1) = 0

Erläuterung: Die obere Zeile enthält die Koe�zientena4, a3, ..., a0 des Polynoms.Die untere Zeile enthält y1, y2, ..., y5 und ergibt sich alsSumme der beiden ersten Zeilen.In der mittleren Zeile startet man links mit 0, die übrigenWerte sind der Wert jeweils links darunter multipliziert mitx = −1 (durch Pfeile markiert).Das Ergebnis f (x) = 0 erschient rechts unten.

23 / 48

Newtoninterpolation

Zu n + 1 vorgegebeben Punkten (x0, y0), (x1, y1), ..., (xn, yn) inder Ebene (wobei die xi alle verschieden sein müssen) gibt esein eindeutig bestimmtes Polynom

p(x) =n∑

j=0

ajxj = a − nxn + an−1x

n−1 + ...+ a1x + a0

vom Grad n, dessen Graph die gegebenen Punkte interpoliert,d. h. es gilt

p(x0) = y0, p(x1) = x1, ..., p(xn) = yn

bzw. kurzp(xi) = yi für i = 0, ..., n.

Eine Methode zur Berechnung von an, ..., a0 ist dieNewton�Interpolation.

24 / 48

Beispiel zur Newtoninterpolation

Gesucht ist ein Polynom p(x) mit

p(0) = 1, p(1) = 0, p(2) = 1 und p(3) = 1.

Da n + 1 = 4 Punkte vorgegeben sind, gibt es ein Polynom3. Grades, dass diese Punkte interpoliert.

25 / 48

Beispiel zur Newtoninterpolation

Gesucht ist ein Polynom p(x) mit

p(0) = 1, p(1) = 0, p(2) = 1 und p(3) = 1.

Da n + 1 = 4 Punkte vorgegeben sind, gibt es ein Polynom3. Grades, dass diese Punkte interpoliert.

26 / 48

Berechnung der Newton-Interpolation

Man macht den Ansatz

p(x) = c0+ c1 · (x− x0)+ c2 · (x− x0) · (x− x1)+ ...

...+ cn · (x − x0) · (x − x1) · ... · (x − xn−1)

und berechnet sukzessive (�Schritt für Schritt�) dieKoe�zienten c0, c1, ..., cn:

I Im 1. Schritt wird ein Polynom p0(x) = c0 vom Grad 0bestimmt mit p0(x0) = y0:c0 = p(x0) = y0,Im Beispiel mit (x0; y0) = (0; 1) erhält manc0 = p(0) = 1, also ist p0(x) = 1 die konstante Funktionmit Wert 1.

27 / 48

Berechnung der Newton-Interpolation, Fortsetzung

Im 2. Schritt wird ein Polynom p1(x) vom Grad 1 bestimmtmit p1(x0) = p0(x0) = y0 und p1(x1) = y1. Dazu macht manden Ansatz p1(x) = p0(x) + c1 · (x − x0)

und setzt x = x1 ein:

y1 = c0 + c1 · (x1 − x0) ⇔ c1 =y1−c0x1−x0 = y1−y0

x1−x0 = d0,1.

Im Beispiel mit (x1; y1) = (1; 0) erhält man

0 = y1 = p1(1) = p0(1) + c1 · (1− x0)

= 1+ c1 · (1− 0) = 1+ c1 ⇔ c1 = −1,also p1(x) = p0(x) + c1 · (x − 0) = 1− x .

28 / 48

Berechnung der Newton-Interpolation, Schritt 3

Nun bestimmt man ein Polynom p2(x) vom Grad 2 mitp2(x0) = p1(x0), p2(x1) = p1(x1) und p2(x2) = y2 mit demAnsatz p2(x) = p1(x) + c2 · (x − x0) · (x − x1).

Durch Einsetzen von x = x2 erhält man eine Gleichung für c2:

y2 = c0 + c1 · (x2 − x0) + c2 · (x2 − x0) · (x2 − x1)⇔ ...

...⇔ c2 =d1,2−d0,1x2−x0 = d0,2 mit d1,2 =

y2−y1x2−x1 .

Im Beispiel mit (x2; y2) = (2; 1) erhält man

1 = y2 = p1(x2) + c2 · (x2 − x0) · (x2 − x1)

= 1− 2+ c2 · (2− 0) · (2− 1) = −1+ 2c2

⇔ 2c2 = 2⇔ c2 = 1,

also p2(x) = 1− x + 1 · (x − 0) · (x − 1) = 1− x + x · (x − 1)

29 / 48

Schritt n + 1 der Newton�Interpolation

Im n�ten Schritt wurde pn−1(x) bestimmt mit pn−1(xi) = yifür i = 0, ..., n − 1. Man macht den Ansatz

pn(x) = pn−1(x) + cn · (x − x0) · (x − x1) · ... · (x − xn−1),

setzt x = xn ein und löst die Gleichung nach cn auf.

4. Schritt im Beispiel

Mit (x3; y3) = (3; 2) und dem Ansatzp3(x) = p2(x) + (x − x0) · (x − x1) · (x − x2) erhält man

2 = y3 = p3(3) = p2(3) + c3 · (3− 0) · (3− 1) · (3− 2)

= 1− 3+ 3 · (3− 1) + 6c3 = 4+ 6c3

⇔ 6c − 3 = −2 ⇔ c3 = −13,

also p3(x) = 1− x + x · (x − 1)− 13· x · (x − 1) · (x − 2).

30 / 48

Abschluss der Newton�Interpolation

Sind alle n + 1 Punkte �abgearbeitet�, ist dasInterpolationspolynom p(x) = pn(x).

Um eine Darstellung in der Standardformp(x) = anxn + ...a1x + a0 zu erhalten, müssen die Klammernaufgelöst werden.

Im Beispiel ist dann p(x) = p3(x) = −13x3 + 2x2 − 8

3x + 1

BemerkungenI Die Reihenfolge, in der die Punkte (xi , yi) abgearbeitetwerden, spielt für das Endergebnis keine Rolle.

I Beim Hinzufügen eines neuen Punktes (xn+1, yn+1) mussnicht die gesamte Rechnung neu ausgeführt werden,sondern man kann das vorher berechnete Polynom pn(x)als Grundlage benutzen, um in einem zusätzlichen Schrittein neues Polynom pn+1(x) zu bestimmen.

31 / 48

Das Schema der dividierten Di�erenzen

erlaubt eine übersichtliche Berechnung derNewton�Interpolation:

x0 d0 = y0 = c0x1 d1 = y1 d0,1 =

y1−y0x1−x0 = c1

x2 d2 = y2 d1,2 =y2−y1x2−x1 d0,2 =

d1,2−d0,1x2−x0 = c2

x3 d3 = y3 d2,3 =y3−y2x3−x2 d1,3 =

d2,3−d1,2x3−x1 d0,3 =

d1,3−d0,2x3−x0 = c3

... ...

Erläuterung: Die dividierten Di�erenzen dj ,i werden rekursivwie folgt berechnet:

di = yi , di−1,i =yi − yi−1xi − xi−1

und dj ,i =dj+1,i − dj ,i−1

xi − xj.

Als Ergebnis erhält man ci = d0,i für i = 0, ..., n.32 / 48

Im Beispiel

0 1 = c01 0 −1

(= 0−1

1−0

)= c1

2 1 1(= 1−0

2−1

)1(= 1−(−1)

2−0

)= c2

3 2 1(= 2−1

3−2

)0(= 1−1

3−1

)−1

3

(= 0−1

3−0

)= c3

Es folgt

p(x) = 1−1·(x−0)+1·(x−0)·(x−1)− 13·(x−0)·(x−1)·(x−2)

= −13x3 + 2x2 − 8

3x + 1.

33 / 48

Andere Klassen reeller FunktionenI (Gebrochen-)rationale Funktionen haben die Formf (x) = p(x)

q(x), wobei p(x) ein Polynom vom Grad n und

q(x) ein Polynom vom Grad m ist.f (x) ist dann de�niert für alle x mit q(x) 6= 0. DerDefnitionsbereich besteht somit aus R mit Ausnahmeendlich vieler Punkte und ist eine Vereinigung von o�enenIntervallen.Beispiel: f (x) = 2x2−x+1

x2−1 ist de�niert aufR \ {−1, 1} = (−∞; −1) ∪ (−1; 1) ∪ (1; ∞)

I Algebraische Funktionen unterscheiden sich vonrationalen Funktionen dadurch, dass sie Wurzelausdrückeenthalten. Sie treten typischerweise als Umkehrfunktionenvon Polynomen oder rationalen Funktionen auf.Beispiele:

f (x) =√x , 3

√x2 − x + 2, 1+x4·

√x+1

2x3−x+1+ 5√

x2+2√x

34 / 48

Beispiel

Die Funktion p(x) = x2 − 4x + 5 bildet das Intervall [2,∞)bijektiv auf [1,∞) ab.

Die Umkehrfunktion f −1 : [1,∞)→ [2,∞) ist einealgebraische Funktion, deren Abbildungsvorschrift man durchAu�ösung Funktionsgleichung nach y erhält:

y = x2 − 4x + 5⇔ x2 − 4x + 5− y = 0

⇔ x = 2±√4− (5− y) = 2±

√y − 1.

Für x ∈ [2,∞) muss der positive Zweig der Wurzel gewähltwerden, also ist f −1(y) = 2+

√y − 1

Transzendente Funktionen

sind weder rational noch algebraisch.

Beispiele: f (x) = 2x , ln x , cos x

35 / 48

Relationen (Teschl/Teschl 5.1)

Eine (binäre) Relation zwischen den Mengen M und N ist eineTeilmenge R der Produktmenge M × N.

Beispiele

I M Menge aller Studierenden, N Menge aller Vorlesungen,R : {(x , y) ∈ M × N : x besucht Vorlesung y}.

I R = {(x , y) ∈ R× R|x < y},I R ={(m, n) ∈ N× N|m und n haben die gleiche Quersumme},

36 / 48

Zusammenhang mit Funktionen

Ist f : M → N eine Abbildung, so de�niert

Rf = {(x , y) : y = f (x)} ⊂ M × N

eine Relation. Damit kann der Begri� Relation alsVerallgemeinerung des Abbildungsbegri�s betrachtet werden.

Zu einer gegebenen Relation R ⊂ M × N gibt es genau danneine Abbildung f : M → N mit R = Rf , wenn Rrechtseindeutig und linkstotal ist, d. h. wenn es zu jedemx ∈ M ein eindeutiges y ∈ N gibt mit (x , y) ∈ R .

Bei einer allgemeinen Relation kann es im Gegensatz dazux ∈ M geben, die mit keinem y ∈ N in Relation stehen, sowiesolche x , die mit mehreren y in Relation stehen.

37 / 48

Die Verknüpfung von Relationen

verallgemeinert die Hintereinanderausführung von Funktionen:

Zu R ⊂ A× B und S ⊂ B × C de�niert man

RS = S ◦ R= {(a, c) : ∃ b ∈ B : (a, b) ∈ R and (b, c) ∈ S} ⊂ A× C

Rn = R ◦ R ◦ ... ◦ R︸ ︷︷ ︸n mal

Beispiel

R = {(x , y) ∈ R× R : |x − y | < 1},S = {(x , y) ∈ R× R : |x − y | < 3},⇒ S ◦ R = {(x , y) ∈ R× R : |x − y | < 4},Rn = {(x , y) ∈ R× R : |x − y | < n}.

38 / 48

Die Verknüpfung von Relationen ist assoziativ, aber nichtkommutativ.

Inverse Relation zu R ⊂ A× BR−1 = {(y , x) ∈ B × A|(x , y) ∈ A× B}.Bemerkung: Die inverse Relation ist (im Gegensatz zurinversen Abbildung) immer de�niert.

n�stellige Relationen

stellen eine Verallgemeinerung des Relationsbegri�s dar:

Eine n�stellige Relation ist eine Teilmenge

R ⊂ A1 × A2 × ...× An.

Anwendung

Datenbankstrukturen −→ Relationale Algebra39 / 48

Relationen auf einer Menge

Eine besondere Rolle spielt der Fall M = N. Bei einer RelationR ⊂ M ×M spricht man auch von einer Relation auf M.

Beispiele

I M Menge von Personen,R = {(x , y) ∈ M ×M : x ist mit y befreundet}

I R = {(x , y) ∈ R× R : x < y}.

40 / 48

Bemerkung

Relationen auf einer endlichen Menge können durch(gerichtete) Graphen dargestellt werden.

Beispiel

Der Graph

stellt die RelationR = {(1, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 1), (4, 3)}auf der Menge M = {1, 2, 3, 4} dar.

41 / 48

EigenschaftenEine Relation R auf M heiÿt

I re�exiv, wenn (x , x) ∈ R für alle x ∈ M,I symmetrisch, wenn (x , y) ∈ R ⇔ (y , x) ∈ R ,I antisymmetrisch, wenn aus (x , y) ∈ R und (y , x) ∈ Rfolgt x = y ,

I transitiv, wenn (x , y) ∈ R ∧ (y , z) ∈ R ⇒ (x , z) ∈ R .

BemerkungR ist genau dann symmetrisch, wenn R−1 = R und genaudann transitiv, wenn R2 ⊂ R .

Eine Äquivalenzrelationist eine Relation auf M, die re�exiv, symmetrisch und transitivist.

42 / 48

Äquivalenzklassen

Eine Äquivalenzrelation R zerlegt M in Äquivalenzklassen.

Dabei handelt es sich um Teilmengen von M mit derEigenschaft, dass x und y genau dann zur selbenÄquivalenzklasse gehören, wenn (x , y) ∈ R .

Beispiele für ÄquivalenzrelationenI M Menge von Personen, R sie die Relation auf M mit

(x , y) ∈ R , wenn die Personen den selben Wohnort haben.Dann ist R eine Äquivalenzrelation. Eine Äquivalenzklassebesteht dann aus allen Bewohnern eines Ortes.

I R = {(x , y) ∈ Z× Z : x − y ist gerade}ist eine Äquivalenzrelation auf Z.Es gibt zwei Äquivalenzklassen: die Menge aller geradenZahlen sowie die Menge aller ungeraden Zahlen.

43 / 48

Eine Ordnungsrelationist eine Relation auf M, die re�exiv, antisymmetrisch undtransitiv ist.

Beispiele

I R = {(x , y) ∈ R× R : x ≤ y}ist eine Ordnungsrelation auf R.

I R = {(n,m) ∈ N× N : n ist Teiler von m}ist eine Ordnungsrelation auf N.

BemerkungDie �kleiner�Relation� R = {(x , y) : x < y} ist keineOrdnungsrelation auf R, da sie nicht re�exiv ist. Sie wird erstzur Ordnungsrelation, wenn statt dessen �≤� betrachtet wird.Allgemein gilt: Jede antisymmetrische und transitive Relationauf M kann zu einer Ordnungsrelation erweitert werden, indemman alle Paare (x , x) mit x ∈ M zu R hinzufügt.

44 / 48

Vollständige und partielle Ordung

I Eine vollständige Ordnung auf M ist eineOrdnungsrelation R , bei der je zwei Elemente vergleichbarsind, d. h. für alle x , y ∈ M gilt entweder (x , y) ∈ R oder(y , x) ∈ R .Beispiel:Die ≤�Relation ist eine vollständige Ordnung auf R.

I Eine partielle Ordnung ist eine Ordnungsrelation R , diekeine vollständige Ordnung ist, d. h. es gibt x und y mit(x , y) 6∈ R und (y , x) 6∈ R .Beispiel: Die Relation �n ist Teiler von M� ist eine partielleOrdnung auf N, da z. B. 2 und 3 nicht vergleichbar sind(2 ist kein Teiler von 3 und 3 ist kein Teiler von 2).

45 / 48

Beispiele mit M = {1, 2, 3, 4}

I R0 = {(1, 1), (2, 2), (3, 3), (4, 4)} ist re�exiv,symmetrisch, antisymmetrisch und transitiv.Insbesondere schlieÿen sich die Eigenschaftensymmetrisch und antisymmetrisch nicht gegenseitig aus,wenn R keine Paare (x , y) mit x 6= y enthält.R ist sowohl Äquivalenzrelation (die Äquivalenzklassensind die einelementigen Teilmengen von M) als auch(partielle) Ordnung.

I R1 = {(1, 3), (1, 4), (2, 3), (2, 4), (3, 4)} istantisymmetrisch und transitiv.Damit ist R1 ∪ R0 eine Ordnungsrelation. Da weder (1, 2)noch (2, 1) enthalten ist, handelt es sich um eine partielleOrdnung.

46 / 48

Weitere Beispiele mit M = {1, 2, 3, 4}

I R3 ={(1, 1), (1, 3), (2, 1), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2)} istnicht re�exiv, da (4, 4) 6∈ R3,nicht symmetrisch, da (2, 1) ∈ R3, aber (1, 2) 6∈ R3,nicht antisymmetrisch, da z. B. (1, 3) und (3, 1) ∈ R3

und nicht transitiv, da (2, 1), (1, 3) ∈ R3, aber (2, 3) 6∈ R3

I R4 = {(1, 1), (1, 4), (2, 2), (3, 3), (4, 1), (4, 4)} ist re�exiv,symmetrisch und transitiv, also eine Äquivalenzrelation.Die Äquivalenzklassen sind {1, 4}, {2} und {3}.

I R5 =

{(1, 1), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 3), (3, 4), (4, 4)}ist eine totale Ordnung.Sie beschreibt die �Reihenfolge� 2, 3, 1, 4.

47 / 48

HüllenI Die re�exive Hülle [R]re� einer Relation R auf M erhältman, idem man zu R alle Paare (x , x) mit x ∈ Mhinzufügt.

I Die symmetrische Hülle [R]symm von R erhält man,indem man zu R alle Paare (y , x) hinzufügt, für die(x , y) ∈ R ist.Es ist [R]symm = R ∪ R−1.

I Die transitive Hülle [R]trans von R ist die kleinstetransitive Relation, in der R als Teilmenge enthalten ist.Es ist [R]trans = R ∪ R2 ∪ R3 ∪ ...

Beispiel M = {1, 2, 3, 4} und R = {(1, 2), (2, 3), (3, 4)}

[R]re� = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)}

[R]symm = {(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3)}

[R]trans = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}48 / 48