Äquivalenzbeziehungen beweisen, Operationen auf Äquivalenzklassen konstruieren und definieren

Äquivalenzbeziehungen können auf jeder Menge definiert werden$X$.

Für eine Beziehung$R$auf einem Satz$X$,$R$ist eine Äquivalenzrelation, wenn$R$ist reflexiv, symmetrisch und transitiv. Also, um zu überprüfen/zu beweisen, dass eine Beziehung besteht$R$An$X$eine Äquivalenzrelation ist, müssen Sie das überprüfen$R$erfüllt diese drei Eigenschaften.

Gegeben sei nun eine Äquivalenzrelation$R$An$X$, für alle$x\in X$, die Äquivalenzklasse von$x$Ist$[x]_R=\{y\in X:yRx\}$. Also die Äquivalenzklasse von einigen$x\in X$ist die Menge von allem$y\in X$die verwandt sind$x$. Diese Äquivalenzklassen werden nicht wirklich "konstruiert", sondern bestimmt durch$R$.

Und Sie können jede gewünschte Operation für Äquivalenzklassen definieren.

BEISPIEL: Let$X$sei die Menge der Zeichenfolgen der Länge 1 bis 4, die vom englischen Alphabet gebildet werden, und definiere eine Beziehung$R$An$X$von$xRy$iff$x$hat die gleiche Länge wie$y$. Das kannst du zeigen$R$ist eine Äquivalenzrelation.

Nehmen Sie nun eine beliebige Schnur ab$X$, sagen wir 'xyza', dann ist die Äquivalenzklasse von 'xyza'$[xyza]_R=\{y\in X:yRxyza\}$, der Satz von Strings mit der gleichen Länge wie 'xyza', dh der Satz von Strings mit der Länge 4.

Es gibt viele Operationen, die Sie für die Äquivalenzklassen definieren können, aber das Wichtigste ist, dass jede solche Operation nur eine Ausgabe haben kann. Man könnte sagen, bei zwei Äquivalenzklassen$[x]$Und$[y]$, definieren Sie die Operation$+$, von$[x]+[y]=[xy]$. So$+$gibt die Menge aller Zeichenketten mit der gleichen Länge wie 'xy' aus, die Zeichenkette, die durch Verketten von 'x' und 'y' gebildet wird.

Während die beteiligten Konstruktionen von Beispiel zu Beispiel variieren, denke ich, dass modulare Arithmetik ein guter Prototyp ist: Sie veranschaulicht viele Ideen, denen Sie immer wieder begegnen werden, wenn Sie mit Äquivalenzbeziehungen arbeiten.

Bei der modularen Arithmetik dreht sich alles um die Äquivalenzrelation$\sim_{{\rm mod \ } n}$auf der Menge der ganzen Zahlen$\mathbb Z$, Wo

Schritt 1: Beweisen, dass die Relation eine Äquivalenzrelation ist.

Dies läuft auf die Überprüfung der drei folgenden Bedingungen hinaus:

• Reflexivität: Für alle$a \in \mathbb Z$, es ist so, dass$a \sim_{{\rm mod \ n }} a$.

• Symmetrie: Für alle$a, b \in \mathbb Z$, Wenn$a \sim_{{\rm mod \ n }} b$, Dann$b \sim_{{\rm mod \ n }} a$.

• Transitivität: Für alle$a, b, c \in \mathbb Z$, Wenn$a \sim_{{\rm mod \ n }} b$Und$b \sim_{{\rm mod \ n }} c$, Dann$a \sim_{{\rm mod \ n }} c$.

Alle drei dieser Bedingungen sollten recht einfach zu überprüfen sein!

Schritt 2: Festlegen einer Äquivalenzklasse.

Bei der Benennung einer Äquivalenzklasse ist es praktisch, sie als „die Äquivalenzklasse, die das Element enthält, zu bezeichnen$x$", Wo$x$ist ein Element in der Menge. Tatsächlich jedes gegebene Element$x$in genau einer Äquivalenzklasse enthalten ist; die Elemente, die innerhalb dieser Äquivalenzklasse liegen, sind genau die Elemente der Menge, die äquivalent sind$x$über die Äquivalenzrelation.

Zum Beispiel,

ist die Äquivalenzklasse, die das Element enthält$1$; die Elemente innerhalb dieser Äquivalenzklasse sind genau die Elemente in$\mathbb Z$die gleichwertig sind$1$unter$\sim _{{\rm mod \ } n}$.

Schritt 3: Aufzählung aller Äquivalenzklassen

Wenn Sie aufgefordert werden, alle Äquivalenzklassen einer Äquivalenzrelation aufzulisten, hilft es, sich daran zu erinnern, dass die Äquivalenzklassen eine Partition Ihrer Menge bilden, dh jedes Element der Menge in genau einer Äquivalenzklasse enthalten ist. (Wir haben diese Tatsache bereits in Schritt 2 verwendet.)

In unserem Beispiel sind die unterschiedlichen Äquivalenzklassen:

Und woher wissen wir, dass wir in dieser Liste keine Äquivalenzklassen ausgelassen haben? Denn jedes Element in$\mathbb Z$in einer der Äquivalenzklassen dieser Liste enthalten ist.

Schritt 4: Induzieren von Operationen auf Äquivalenzklassen

Ziemlich oft haben wir eine binäre Operation mit den Elementen der ursprünglichen Menge und möchten eine ähnliche binäre Operation mit den Äquivalenzklassen definieren. Beispielsweise liegt eine Operation vor$\mathbb Z$genannt Addition ($+$), also wäre es schön, wenn wir eine Art analoge Additionsoperation für die Äquivalenzklassen modulo definieren könnten$n$. Natürlich sollte jede Additionsoperation, die wir für die Äquivalenzklassen definieren, eng mit der ursprünglichen Additionsoperation für ganze Zahlen verwandt sein, sonst wäre es schwierig, sie sich als Addition vorzustellen.

Die natürlichste Definition, die wir für die Addition von Äquivalenzklassen aufschreiben können, wäre etwa so:

Aber wenn wir so etwas schreiben, müssen wir sehr vorsichtig sein. Vermuten$a'$ist ein anderes Element wie das$a \sim_{{\rm mod \ } n } a'$, und nehme an$b'$ist ein anderes Element wie das$b \sim_{{\rm mod \ } n } b'$. Dann

So

Damit unsere Definition von Addition konsistent ist, sollte es also besser so sein

Fassen wir das alles zusammen: Damit unsere Definition der Addition von Äquivalenzklassen konsistent ist, benötigen wir das

Zum Glück stimmt das! Die Definition funktioniert also, und wir können loslegen!

Aber seien Sie vorsichtig: Nicht alle Operationen mit ganzen Zahlen führen zu Operationen mit den Äquivalenzklassen. Beispielsweise können wir auf diese Weise keine Division für Äquivalenzklassen definieren, da der Konsistenztest fehlschlägt.

Ich habe diese Ressource gefunden, die auf Anfängerniveau zu sein scheint und Beispiele speziell für die Konstruktion von Ganzzahlen enthält: https://www.math.wustl.edu/~freiwald/310integers.pdf