| | | Home | | | Back | | |
|
Mathematische Begriffe |
| Algorithmus |
| Änderungsrate |
| Äquivalenzrelation |
| Funktion |
| Rückkopplung |
| Vektor |
| Verhältnis |
| Vollständige Induktion |
| Wahrscheinlichkeit |
| Zahlenmengen |
Äquivalenzrelation
| Natürliche Zerlegungen von Mengen |
| Jede Zerlegung induziert eine Äquivalenzrelation. |
| Jede Äquivalenzrelation induziert eine Zerlegung. |
| Quotientenmengen |
Natürliche Zerlegungen von Mengen
Auf der Grundlage der Menge der natürlichen Zahlen ℕ = { 0, 1, 2, 3, 4, ... } lassen sich weitere Zahlenmengen, nämlich ℤ , ℚ , u.s.w. auf eine ganz eigentümliche Art konstruieren. Der zentrale Begriff, mit dessen Hilfe diese Konstruktionen möglich sind, ist der Begriff Äquivalenzrelation. Auch in anderen Zusammenhängen ist dieser Begriff wichtig.
Eine Relation R~ ⊂ M x M = { (x;y): x∈M und y∈M } auf einer Menge M heißt Äquivalenzrelation auf M, falls R~ transitiv, symmetrisch und reflexiv ist, das heißt, falls für alle x, y, z ∈ M das Folgende gilt:
| x ~ y und y ~ z ⇒ x ~ z | (Transitivität) |
| x ~ y ⇒ y ~ x | (Symmetrie) |
| x ~ x | (Reflexivität) |
Eine Menge M, auf der eine Äqivalenzrelation definiert ist, zerfällt sozusagen von selbst in Teilmengen Mi, und zwar so, dass für je zwei Elemente x und y einer Teilmenge Mi stets x ~ y gilt. Das Umgekehrte ist ebenfalls richtig: Jede Klasseneinteilung einer Menge M induziert in natürlicher Weise eine Äquivalenzrelation auf M.
Hierbei versteht man unter einer Zerlegung einer nichtleeren Menge M eine Menge ℳ = { M1, M2, M3, ... } von Teilmengen von M mit den zwei Eigenschaften:
| (I) | M1 ∪ M2 ∪ M3 ∪ ... = M |
| (II) | Mi ∩ Mk = { } ⇔ Mi ≠ Mk |
Die so definierten Teilmengen von M sind also paarweise disjunkt und jedes Element von M ist in genau einer dieser Teilmengen von M enthalten. Das bedeutet, dass jedes Element Mi ∈ ℳ eindeutig bestimmt und repräsentiert ist durch irgendein m ∈ Mi.
Jede Zerlegung induziert eine Äquivalenzrelation.
Sei ℳ eine Zerlegung einer nichtleeren Menge M. Dann ist die Relation R~ ⊂ M x M, definiert durch
x ~ y ⇔ x, y ∈ Mi für ein Mi ∈ ℳ
eine Äquivalenzrelation auf M.
Beweis:
Unter der Annahme, dass ℳ
eine Zerlegung von M ist, ist zu zeigen, dass die so definierte Relation R~
transitiv, symmetrisch und reflexiv ist.
(i) Seien x, y und z Elemente aus M. Dann folgt aus x~y und y~z, dass x, y
∈ Mp und y, z
∈
Mq mit Mp, Mq
∈
ℳ .
Damit haben die Mengen Mp
und Mq wenigstens ein Element gemeinsam, nämlich y.
Also können Mp und Mq nicht disjunkt sein. Da
ℳ eine Zerlegung von M ist, folgt Mp
= Mq und damit x~z.
(ii) x~y ist nach Definition von R~ gleichbedeutend mit x, y ∈ Mi mit Mi ∈ ℳ , das heißt, es gilt auch y~x.
(iii) Da nach Definition zu jedem x ∈ M ein Mi ∈ ℳ existiert mit x ∈ Mi, folgt x~x sofort.
Jede Äquivalenzrelation induziert eine Zerlegung.
Sei R~ eine Äquivalenzrelation auf einer nichtleeren Menge M. Dann ist
ℳ = { M(x) ⊂ M: x ∈ M }, definiert durch M(x) = { y ∈ M: x~y }
eine Zerlegung von M.
Beweis:
Unter der Annahme, dass R~ eine Äquivalenzrelation auf M ist, ist zu
zeigen, dass erstens die Vereinigungsmenge aller Mengen M(x) mit x
∈ M gleich M ist und zweitens, dass alle Mengen M(x)
∈
ℳ paarweise disjunkt sind.
(i) Weil R~ eine Äquivalenzrelation auf M ist, folgt für jedes x
∈ M sofort, dass x~x.
Also gilt nach
Definition der Mengen M(x), dass x
∈ M(x) und man hat M = ∪x∈M{ x }
⊆ ∪x∈M M(x)
⊆ M.
(ii) Angenommen, es gibt unter den Elementen der oben definierten Menge
ℳ zwei nicht identische
Mengen M(x) und M(y), die nicht disjunkt sind. Dann existiert mindestens ein z*
∈ M mit z* ∈ M(x)
und z*
∈ M(y), mit anderen Worten: x~z* und z*~y.
Wegen der Transitivität von R~ folgt x~y.
Sei nun z irgendein Element aus M(x), dann gilt x~z und mit x~y auch
z~y, also ist z auch Element aus M(y).
Ebenso gilt: wenn z irgendein Element aus M(y) ist, dann ist z auch
Element von M(x).
Also sind die Mengen M(x) und M(y) identisch und dies steht im Widerspruch
zur getroffenen Annahme.
Zwei beliebig heraus gegriffene Mengen M(x), M(y)
∈
ℳ sind also entweder
identisch oder disjunkt.
Quotientenmengen
Sei R~ eine Äquivalenzrelation auf einer nichtleeren Menge M. Dann heißen die zu R~ gehörenden Teilmengen
M(x) = { y ∈ M: x ~ y }
Äquivalenzklassen und die Menge
ℳ aller dieser Teilmengen - das ist die zu
R~ gehörende Zerlegung - wird Quotientenmenge von R~
genannt und mit M/~ bezeichnet.
Die zu einer Äquivalenzrelation R~ auf M gehörenden Äquivalenzklassen
M(x) werden oft auch mit dem Symbol [x] gekennzeichnet. x heißt
Repräsentant der Äquivalenzklasse [x].
Beispiel 1:
Sei n irgendeine positive natürliche Zahl. Dann hat man mit
x ~ y ⇔def (x − y) wird von n geteilt
eine Äquivalenzrelation auf der Menge der ganzen Zahlen (ℤ), definiert. Die zugehörigen Äquivalenzklassen heißen Restklassen modulo n. Wenn [x] eine solche Restklasse darstellt, dann sind folgende Aussagen gleichwertig:
y
∈ [x]
x ~ y
n | (x − y)
x ≡ y mod n
Beispielsweise sind [0] = { ..., -6, -3, 0, 3, 6, ... }, [1] = { ..., -2, 1, 4, 7, ... } und [2] = { ..., -1, 2, 5, ... } die Restklassen modulo 3 und es gilt 0 ≡ 6 mod 3 oder -4 ≡ 5 mod 3.
Die Quotientenmenge ℤ/~ ist endlich und umfasst n Elemente: [0], [1], ... [n-1].
Beispiel 2:
Sei MPf die Menge aller Pfeile in einem
dreidimensionalen euklidischen Raum, wobei ein Pfeil definiert sein soll
durch seinen Anfangspunkt, seine Richtung
und seine Länge. Seien p, q ∈ MPf,
dann hat man mit
p ~ q ⇔def p und q sind richtungs- und längengleich
eine Äquivalenzrelation auf MPf definiert. Die zugehörigen Äquivalenzklassen heißen Pfeilklassen. Die nachfolgende Zeichnung zeigt fünf verschiedene Repräsentanten einer bestimmten Pfeilklasse.
Die Quotientenmenge MPf/~, das heißt die Menge aller
Pfeilklassen im sogenannten Anschauungsraum, bildet mit geeignet
definierter Addition "+" bzw. skalarer Multiplikation "·"
ein ℝ-Vektorraum.
(→ Vektor,
Abschnitt Pfeile und Pfeilklassen).
| | | Home | | | Back | | | Top | | |