nyuuzyou/wikis huggingface dataset:
Equivalence Relation/Examples/Equal Fourth Powers over Complex Numbers/Proof 1

== Example of Equivalence Relation ==
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $z \in \C$.
Then:
:$z^4 = z^4$
Thus:
:$\forall z \in \C: z \mathrel \RR z$
and $\RR$ is seen to be reflexive.
=== Symmetry ===
Thus $\RR$ is seen to be symmetric.
=== Transitivity ===
Thus $\RR$ is seen to be transitive.
$\RR$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
Category:Equal Fourth Powers over Complex Numbers
Equivalence Relation/Examples/Equal Fourth Powers over Complex Numbers/Proof 2

== Example of Equivalence Relation ==
== Proof ==
We have that $\RR \subseteq \R \times \R$ is the relation induced by $z^4$:
:$\tuple {z, w} \in \RR \iff z^4 = w^4$
The result follows from Relation Induced by Mapping is Equivalence Relation.
Category:Equal Fourth Powers over Complex Numbers
Equivalence Relation/Examples/Equal Sine of pi x over 6 on Integers

== Example of Equivalence Relation ==
Let $\Z$ denote the set of integers.
Let $\RR$ denote the relation on $\Z$ defined as:
:$\forall x, y \in \Z: x \mathrel \RR y \iff \sin \dfrac {\pi x} 6 = \sin \dfrac {\pi y} 6$
Then $\RR$ is an equivalence relation.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.1 \ \text{(b)}$
Category:Examples of Equivalence Relations
Category:Equal Sine of pi x over 6 on Integers
Equivalence Relation/Examples/Equal Sine of pi x over 6 on Integers/Proof 1

== Example of Equivalence Relation ==
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $x \in \Z$.
Then:
:$\sin \dfrac {\pi x} 6 = \sin \dfrac {\pi x} 6$
Thus:
:$\forall x \in \Z: x \mathrel \RR x$
and $\RR$ is seen to be reflexive.
=== Symmetry ===
Thus $\RR$ is seen to be symmetric.
=== Transitivity ===
Thus $\RR$ is seen to be transitive.
$\RR$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
Category:Equal Sine of pi x over 6 on Integers
Equivalence Relation/Examples/Equal Sine of pi x over 6 on Integers/Proof 2

== Example of Equivalence Relation ==
== Proof ==
We have that $\RR \subseteq \R \times \R$ is the relation induced by $\sin \dfrac {x \pi} 6$:
:$\tuple {x, y} \in \RR \iff \sin \dfrac {x \pi} 6 = \sin \dfrac {y \pi} 6$
The result follows from Relation Induced by Mapping is Equivalence Relation.
Category:Equal Sine of pi x over 6 on Integers
Equivalence Relation/Examples/Equality

== Example of Equivalence Relation ==
Let $S$ be a set.
Let the relation $\RR$ on $S$ be defined as:
:$\forall x, y \in S: x \mathrel \RR y \iff x = y$
that is, the equality relation on $S$.
Then $\RR$ is an equivalence relation.
== Proof ==
Demonstrated in Diagonal Relation is Equivalence.
== Sources ==
* 
* 
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Even Sum

== Example of Equivalence Relation ==
Let $\Z$ denote the set of integers.
Let $\RR$ denote the relation on $\Z$ defined as:
:$\forall x, y \in \Z: x \mathrel \RR y \iff \text {$x + y$ is even}$
Then $\RR$ is an equivalence relation.
The equivalence classes are:
:$\eqclass 0 \RR$
:$\eqclass 1 \RR$
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $x \in \Z$.
Then:
:$x + x = 2 x$
and so $x + x$ is an even integer.
Thus:
:$\forall x \in \Z: x \mathrel \RR x$
and $\RR$ is seen to be reflexive.
=== Symmetry ===
Thus $\RR$ is seen to be symmetric.
=== Transitivity ===
Thus $\RR$ is seen to be transitive.
$\RR$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
We have that:
:$x \mathrel \RR 0 \iff \text {$x$ is even}$
:$x \mathrel \RR 1 \iff \text {$x$ is odd}$
and the equivalence classes of $\RR$ are $\eqclass 0 \RR$ and $\eqclass 1 \RR$ from the Fundamental Theorem on Equivalence Relations.
== Sources ==
* : Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $19$
* : Chapter $2$: Maps and relations on sets: Exercise $4$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Months that Start on the Same Day of the Week

== Example of Equivalence Relation ==
Let $M$ be the set of months of the year according to the (usual) Gregorian calendar.
Let $\sim$ be the relation on $M$ defined as:
:$\forall x, y \in M: x \sim y \iff \text {$x$ and $y$ both start on the same day of the week}$
Then $\sim$ is an equivalence relation.
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $x \in M$.
Then $x$ starts on the same day of the week as itself.
Thus $\sim$ is seen to be reflexive.
=== Symmetry ===
Let $x, y \in M$.
If $x$ starts on the same day of the week as $y$, then $y$ starts on the same day of the week as $x$.
Thus $\sim$ is seen to be symmetric.
=== Transitivity ===
Let $x, y, z \in M$.
Let $x$ start on the same day of the week as $y$.
Let $y$ start on the same day of the week as $z$.
Then $x$ starts on the same day of the week as $z$
Thus $\sim$ is seen to be transitive.
$\sim$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Exercise $7$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence

== Examples of Relations which are not Equivalences ==
=== Different Age Relation ===
=== Is the Mother Of is not Equivalence ===
=== Is the Sister Of is not Equivalence ===
=== Common Ancestor Relation ===
=== Greater Than is not Equivalence ===
=== $\forall x, y \in \R: x + y \in \Z$ is not Equivalence ===
=== Divisor Relation is not Equivalence ===
=== Sum of Integers is Divisible by $3$ is not Equivalence ===
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/Divisor Relation

== Example of Relation which is not Equivalence ==
Let $\Z_{>0}$ denote the set of (strictly) positive integers.
Let $x \divides y$ denote that $x$ is a divisor of $y$.
Then $\divides$ is not an equivalence relation.
== Proof ==
From Divisor Relation on Positive Integers is Partial Ordering we have that $\divides$ is reflexive and transitive.
But we have:
:$2 \divides 4$
and:
:$4 \nmid 2$
So $\divides$ is not symmetric and therefore not an equivalence relation.
== Sources ==
* : Chapter $2$. Equivalence Relations: Exercise $1 \ \text {(iv)}$
* 
* 
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/Greater Than

== Example of Relation which is not Equivalence ==
Let $\R$ denote the set of real number.
Let $>$ denote the usual relation on $\R$ defined as:
:$\forall \tuple {x, y} \in \R \times \R: x > y \iff \text {$x$ is (strictly) greater than $y$}$
Then $>$ is not an equivalence relation.
== Proof ==
We have that $>$ is transitive:
:$x > y, y > z \implies x > z$
But $>$ is not reflexive:
:$\forall x: x \not > x$
$>$ is not symmetric:
:$x > y \implies y \not > x$
So $\sim$ is not symmetric.
So $\sim$ is not an equivalence relation.
== Sources ==
* : $\S 2.2$. Equivalence relations: Example $32$
* : Appendix $\text{A}.2$: Cartesian Products and Relations: Problem Set $\text{A}.2$: $7 \ \text{(b)}$
::applied to a specific instance
* : Chapter $2$: Maps and relations on sets: Example $2.25$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/Is the Mother Of

== Example of Relation which is not Equivalence ==
Let $P$ denote the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {$x$ is the mother of $y$}$
Then $\sim$ is not an equivalence relation.
The same applies (trivially) to the relation:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {$x$ is the father of $y$}$
== Proof ==
For a start, no person can be his or her own mother, so: 
:$\forall x: x \nsim x$
So $\sim$ is not reflexive.
Then:
:If $x \sim y$ then $y$ is the son or daughter of $x$.
So $\sim$ is not symmetric.
Then:
:if $x \sim y$ and $y \sim z$ it follows that $x$ is the grandmother of $z$, not his or her mother.
So $\sim$ is not transitive.
== Sources ==
* : $\S 2.2$. Equivalence relations: Example $31$
* : Chapter $1$: Sets and mappings: $\S 1.4$: Equivalence relations
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/Is the Sister Of

== Example of Relation which is not Equivalence ==
Let $P$ denote the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {$x$ is the sister of $y$}$
Then $\sim$ is not an equivalence relation.
== Proof ==
For a start, no person can be his or her own sister, so: 
:$\forall x: x \nsim x$
So $\sim$ is not reflexive.
Then:
:If $x \sim y$ then it is not necessarily the case that $y$ is the sister of $x$.
This is because $y$ may be male, and so would be the brother of $x$.
So $\sim$ is not symmetric.
Let us assume that $\sim$ specifically means has the same father and mother as, and does not encompass half-siblings.
Thus:
:if $x \sim y$ and $y \sim z$ it follows that $x$ is the sister of $z$.
So $\sim$ is transitive.
== Sources ==
* : Appendix $\text{A}.2$: Cartesian Products and Relations: Problem Set $\text{A}.2$: $7 \ \text{(c)}$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/People of Different Age

== Example of Relation which is not Equivalence ==
Let $P$ be the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {the age of $x$ and $y$ on their last birthdays was not the same}$
Then $\sim$ is not an equivalence relation.
== Proof ==
:$\sim$ is antireflexive, as everybody is the same age as themselves.
:$\sim$ is symmetric, as two people are either the same age or they are not.
:$\sim$ is not transitive, because if $a \sim b$ and $b \sim c$, it is impossible to say whether $a \sim c$.
== Sources ==
* : Appendix $\text{A}.2$: Cartesian Products and Relations: Example $\text{A}.2$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/People with Common Ancestor

== Example of Equivalence Relation ==
Let $P$ be the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {$x$ and $y$ have an ancestor in common}$
Then $\sim$ is not an equivalence relation.
== Proof ==
We have that $\sim$ is reflexive and symmetric.
But $\sim$ is not transitive:
Let $a$ and $b$ be half-siblings, whose mother is $d$ and whose fathers are $e$ and $f$ respectively.
Then $a \sim b$ as they share an ancestor $d$.
Let $a$ and $g$ be full siblings, whose mother is $i$ and whose father is $e$.
Then $g \sim a$ as they share father $e$ and mother $i$.
But $b$ and $g$ do not have the same father or mother, and it is possible that they share no ancestor.
And in that case:
:$g \nsim b$
== Sources ==
* : Chapter $2$. Equivalence Relations: Exercise $1 \ \text {(iii)}$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/Sum is Integer

== Example of Relation which is not Equivalence ==
Let $\R$ denote the set of real numbers.
Let $\sim$ denote the relation defined on $\R$ as:
:$\forall \tuple {x, y} \in \R \times \R: x \sim y \iff x + y \in \Z$
Then $\sim$ is not an equivalence relation.
== Proof ==
We have that $\sim$ is symmetric:
:$x + y \in \Z \implies y + x \in \Z$
from Real Addition is Commutative.
But $\sim$ is non-reflexive:
:$2 \cdotp 3 + 2 \cdotp 3 = 4 \cdotp 6 \notin \Z$
for example.
Also, $\sim$ is non-transitive:
for example.
So $\sim$ is not an equivalence relation.
== Sources ==
* : Chapter $2$. Equivalence Relations: Exercise $1 \ \text {(ii)}$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Non-Equivalence/Sum of Integers is Divisible by 3

== Example of Relation which is not Equivalence ==
Let $\Z$ denote the set of integers.
Let $\RR$ denote the relation on $\Z$ defined as:
:$\forall x, y \in \Z: x \mathrel \RR y \iff \text {$x + y$ is divisible by $3$}$
Then $\RR$ is not an equivalence relation.
== Proof ==
Let $x = 1$.
Then:
:$x + x = 2$
and so $x + x$ is not divisible by $3$.
Thus $\RR$ is seen to be non-reflexive.
Hence by definition $\RR$ is not an equivalence relation.
== Sources ==
* : Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $20$
* : Chapter $2$: Maps and relations on sets: Exercise $4$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/People of Same Age

== Example of Equivalence Relation ==
Let $P$ be the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {the age of $x$ and $y$ on their last birthdays was the same}$
That is, that $x$ and $y$ are the same age.
Then $\sim$ is an equivalence relation.
== Sources ==
* : $\S 2.2$. Equivalence relations: Example $30$
* : $\S 2.3$. Partitions: Example $34$
* : Appendix $\text{A}.2$: Cartesian Products and Relations: Example $\text{A}.2$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/People with Same First Name

== Example of Equivalence Relation ==
Let $P$ be the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {$x$ and $y$ have the same first name}$
Then $\sim$ is an equivalence relation.
== Sources ==
* : Appendix $\text{A}.3$: Equivalence Relations: $(5)$
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/People with Same Parents

== Example of Equivalence Relation ==
Let $P$ be the set of people.
Let $\sim$ be the relation on $P$ defined as:
:$\forall \tuple {x, y} \in P \times P: x \sim y \iff \text {both of the parents of $x$ and $y$ are the same}$
Then $\sim$ is an equivalence relation.
== Sources ==
* : Chapter $1$: Sets and mappings: $\S 1.4$: Equivalence relations
Category:Examples of Equivalence Relations
Equivalence Relation/Examples/Points on Same Line

== Example of Equivalence Relation ==
Let $P$ be the set of points in the plane.
Let $\sim$ be the relation on $P$ defined as:
:$\forall x, y \in P: x \sim y \iff \text {$x$ and $y$}$ both lie on the same horizontal line
Then $\sim$ is an equivalence relation.
== Proof ==
In the Cartesian plane, the characteristic of a horizontal line is that the $y$ coordinates of all its points are equal.
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $p = \tuple {x, y} \in P$.
Then $p$ is trivially on the same horizontal line as itself.
Thus $\sim$ is seen to be reflexive.
=== Symmetry ===
Let $p_1 = \tuple {x_1, y_1}, p_2 = \tuple {x_2, y_2} \in P$.
Let $p_1 \sim p_2$.
Then $y_1 = y_2$, and so $y_2 = y_1$.
Hence $p_2 \sim p_1$
Thus $\sim$ is seen to be symmetric.
=== Transitivity ===
Let $p_1 = \tuple {x_1, y_1}, p_2 = \tuple {x_2, y_2}, p_3 = \tuple {x_3, y_3} \in P$.
Let $p_1 \sim p_2$.
Let $p_2 \sim p_3$.
Then $y_1 = y_2$ and $y_2 = y_3$.
Hence $y_1 = y_3$ and so $p_1 \sim p_3$.
Thus $\sim$ is seen to be transitive.
$\sim$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
== Sources ==
* : Introduction $\S 3$: Equivalence relations
* : $\S 6$. Indexed families; partitions; equivalence relations: Exercise $7$
Category:Examples of Equivalence Relations
Equivalence Relation Induced by Preordering/Examples/Finite Set Difference on Natural Numbers

== Example of Equivalence Relation Induced by Preordering ==
Consider the preordering $\RR$ on the powerset of the natural numbers:
:$\forall a, b \in \powerset \N: a \mathrel \RR b \iff a \setminus b \text { is finite}$
where $\setminus$ denotes set difference.
Let $\sim_\RR$ denote the equivalence relation on $\powerset \N$ induced by $\RR$.
Then the $\sim_\RR$-equivalence class of an element $a$ of $\powerset \N$ is defined as:
:$\eqclass a {\sim_\RR} = \set {b \in \powerset \N: a \symdif b \text { is finite} }$
where $\symdif$ denotes symmetric difference.
== Proof ==
We have that:
The result follows by definition of $\sim_\RR$-equivalence class.
== Sources ==
* : Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $39 \ \text{(b)}$
Category:Examples of Equivalence Relations Induced by Preorderings
Equivalence Relation induced by Congruence Relation on Quotient Structure is Congruence

== Theorem ==
Let $\struct {A, \oplus}$ be an algebraic structure.
Let $\RR$ be a congruence relation on $\struct {A, \oplus}$.
Let $\SS$ be a congruence relation on the quotient structure $\struct {A / \RR, \oplus_\RR}$ defined by $\RR$.
Let $\TT$ be the relation on $A$ defined as:
:$\forall x, y \in A: x \mathrel \TT y \iff \eqclass x \RR \mathrel \SS \eqclass y \RR$
Then:
:$\TT$ is a congruence relation on $\struct {A, \oplus}$
and:
:there exists a unique isomorphism $\phi$ from $\paren {A / \RR} / \SS$ to $A / \TT$ which satisfies:
::$\phi \circ q_\SS \circ q_\RR = q_\TT$
:where $q_\SS$, $q_\RR$ and $q_\TT$ denote the quotient epimorphisms as appropriate.
=== Corollary ===
== Proof ==
Recall that by definition $\RR$ and $\SS$ are equivalence relations.
First it is demonstrated that $\TT$ is an equivalence relation.
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
We have:
:$\forall a \in A: a \in \eqclass a \RR$
Hence as $\SS$ is an equivalence relation, therefore reflexive:
:$\forall a \in A: \eqclass a \RR \mathrel \SS \eqclass a \RR$
That is:
:$\forall a \in A: a \mathrel \TT a$
Thus $\TT$ is seen to be reflexive.
=== Symmetry ===
Thus $\TT$ is seen to be symmetric.
=== Transitivity ===
Let $a, b, c \in A$ such that 
Then we have:
Thus $\TT$ is seen to be transitive.
Hence $\TT$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
It remains to be demonstrated that $\TT$ is a congruence relation.
Let $x_1, y_1, x_2, y_2 \in A$ such that:
Then we have:
Hence by definition of congruence relation:
:$\TT$ is a congruence relation on $\struct {A, \oplus}$.
Now we have:
From Composite of Epimorphisms is Epimorphism, $q_\SS \circ q_\RR$ is an epimorphism.
We also have that $q_\TT$ is an epimorphism.
From the Quotient Theorem for Epimorphisms, there exists a unique isomorphism $\phi: \paren {A / \RR} / \SS \to A / \TT$ which satisfies $\phi \circ \paren {q_\SS \circ q_\RR} = q_\TT$.
This theorem can be illustrated by means of the following commutative diagram:
::$\begin{xy}\xymatrix@L+2mu@+1em{
 A \ar[r]^*{q_\TT}
 \ar[d]^*{q_\RR}
&
 A / \TT
\\ 
 A / \RR \ar[r]_*{q_\SS}
&
 \paren {A / \RR} / \SS \ar@{-->}[u]_*{\phi}^*{\cong}
}\end{xy}$
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 12$: Homomorphisms: Exercise $12.17 \ \text {(a)}$
Category:Congruence Relations
Category:Quotient Structures
Equivalence Relation induced by Congruence Relation on Quotient Structure is Congruence/Corollary

== Corollary to Equivalence Relation induced by Congruence Relation on Quotient Structure is Congruence ==
Let $\struct {A, \oplus}$ be an algebraic structure.
Let $\RR$ and $\TT$ be congruence relations on $\struct {A, \oplus}$ such that $R \subseteq T$.
Let $\SS$ be the relation on the quotient structure $\struct {A / \RR, \oplus_\RR}$ which satisfies:
:$\forall X, Y \in A / \RR: X \mathrel \SS Y \iff \exists x \in X, y \in Y: x \mathrel \TT y$
Then:
:$\SS$ is a congruence relation on $\struct {A / \RR, \oplus_\RR}$
and:
:there exists a unique isomorphism $\phi$ from $\paren {A / \RR} / \SS$ to $A / \TT$ which satisfies:
::$\phi \circ q_\SS \circ q_\RR = q_\TT$
:where $q_\SS$, $q_\RR$ and $q_\TT$ denote the quotient epimorphisms as appropriate.
== Proof ==
Recall that by definition $\RR$ and $\TT$ are equivalence relations.
First it is demonstrated that $\SS$ is an equivalence relation.
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
Let $X \in A / \RR$.
Then as $\TT$ is an equivalence relation, therefore reflexive:
:$\forall x \in X: x \mathrel \TT x$
Thus by definition of $\SS$:
:$\forall X \in A / \RR: X \mathrel \SS X$
Thus $\SS$ is seen to be reflexive.
=== Symmetry ===
Thus $\SS$ is seen to be symmetric.
=== Transitivity ===
Let $X, Y, Z \in A / \RR$ such that 
Then we have:
Thus $\SS$ is seen to be transitive.
Hence $\TT$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
It remains to be demonstrated that $\SS$ is a congruence relation.
Let $X_1, Y_1, X_2, Y_2 \in A / \RR$ such that:
Then we have:
Hence by definition of congruence relation:
:$\SS$ is a congruence relation on $\struct {A / \RR, \oplus_\RR}$.
Thus we have that:
:$\RR$ is a congruence relation on $\struct {A, \oplus}$
and:
:$\SS$ is a congruence relation on the quotient structure $\struct {A / \RR, \oplus_\RR}$ defined by $\RR$.
By definition of quotient structure:
:$\forall x, y \in A: x \mathrel \TT y \iff \eqclass x \RR \mathrel \SS \eqclass y \RR$
where $\eqclass x \RR$ is the equivalence class under $\RR$ of $x$.
Hence the criteria of Equivalence Relation induced by Congruence Relation on Quotient Structure is Congruence are fulfilled.
Hence from Equivalence Relation induced by Congruence Relation on Quotient Structure is Congruence:
:there exists a unique isomorphism $\phi$ from $\paren {A / \RR} / \SS$ to $A / \TT$ which satisfies:
::$\phi \circ q_\SS \circ q_\RR = q_\TT$
:where $q_\SS$, $q_\RR$ and $q_\TT$ denote the quotient epimorphisms as appropriate.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 12$: Homomorphisms: Exercise $12.19 \ \text {(a)}$
Category:Congruence Relations
Category:Quotient Structures
Equivalence Relation inducing Closed Quotient Set of Magma is Congruence Relation

== Theorem ==
Let $\struct {S, \circ}$ be a magma.
Let $\circ_\PP$ be the operation induced by $\circ$ on $\powerset S$, the power set of $S$.
Let $\RR$ be an equivalence relation on $S$.
Let $S / \RR$ denote the quotient set of $S$ induced by $\RR$.
Let the algebraic structure $\struct {S / \RR, \circ_\PP}$ be closed.
Then:
:$\RR$ is a congruence relation for $\circ$
and:
:the operation $\circ_\RR$ induced on $S / \RR$ by $\circ$ is the operation induced on $S / \RR$ by $\circ_\PP$.
== Proof ==
Let $x_1, y_1, x_2, y_2 \in S$ be arbitrary, such that:
To demonstrate that $\RR$ is a congruence relation for $\circ$, we need to show that:
:$\paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
We have:
Since $\struct {S / \RR, \circ_\PP}$ is closed:
:$\eqclass {x_1} \RR \circ_\PP \eqclass {y_1} \RR \in S / \RR$
From the definition of a quotient set:
:$\eqclass {x_1} \RR \circ_\PP \eqclass {y_1} \RR = \eqclass z \RR$ for some $z \in S$
From the definition of an operation induced on $\powerset S$:
:$\eqclass z \RR = \set {a \circ b: a \in \eqclass {x_1} \RR, b \in \eqclass {y_1} \RR}$
hence:
:$x_1 \circ y_1, x_2 \circ y_2 \in \eqclass z \RR$
From the definition of an equivalence class:
:$\paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
This shows that $\RR$ is a congruence relation for $\circ$.
We also have, by the equivalence of statements $(2)$ and $(4)$ in Equivalence Class Equivalent Statements:
:$\eqclass {x_1 \circ y_1} \RR = \eqclass z \RR = \eqclass {x_1} \RR \circ_\PP \eqclass {y_1} \RR$
This shows that the operation induced on $S / \RR$ by $\circ_\PP$ is the operation $\circ_\RR$ induced on $S / \RR$ by $\circ$.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.10$
Category:Quotient Structures
Category:Congruence Relations
Equivalence Relation is Circular

== Theorem ==
Let $\RR \subseteq S \times S$ be an equivalence relation.
Then $\RR$ is also a circular relation.
== Proof ==
Let $x, y, z \in S$ be arbitrary such that:
:$\tuple {x, y} \in \RR$ and $\tuple {y, z} \in \RR$
We have that $\RR$ is transitive.
Hence:
:$\tuple {x, z} \in \RR$
We also have that $\RR$ is symmetric.
Hence:
:$\tuple {z, x} \in \RR$
We have demonstrated that:
:$\tuple {x, y} \in \RR$ and $\tuple {y, z} \in \RR \implies \tuple {z, x} \in \RR$
and $\RR$ is circular by definition.
== Sources ==
Category:Equivalence Relations
Category:Circular Relations