nyuuzyou/wikis huggingface dataset:
Equivalence Relation is Congruence for Constant Operation

== Theorem ==
Every equivalence relation is a congruence relation for the constant operation.
== Proof ==
Let $c \in S$.
By the definition of the constant operation:
:$\forall x, y \in S: x \sqbrk c y = c$
Let $\RR$ be an equivalence relation on $S$.
Every equivalence relation is reflexive, so:
:$c \mathrel \RR c$
So:
Hence the result.
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Example $11.4$
Category:Constant Operation
Category:Examples of Equivalence Relations
Category:Examples of Congruence Relations
Equivalence Relation is Congruence for Left Operation

== Theorem ==
Every equivalence relation is a congruence for the left operation $\leftarrow$.
== Proof ==
Let $\RR$ be an equivalence relation on the structure $\struct {S, \leftarrow}$.
Then:
:$x_1 \leftarrow y_1 = x_1$
:$x_2 \leftarrow y_2 = x_2$
Suppose $x_1 \mathrel \RR x_2 \land y_1 \mathrel \RR y_2$.
It follows directly that:
:$\paren {x_1 \leftarrow y_1} \mathrel \RR \paren {x_2 \leftarrow y_2}$
== Also se ==
* Equivalence Relation is Congruence for Right Operation
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Example $11.4$
Category:Left Operation
Category:Examples of Equivalence Relations
Category:Examples of Congruence Relations
Equivalence Relation is Congruence for Right Operation

== Theorem ==
Every equivalence relation is a congruence for the right operation $\rightarrow$.
== Proof ==
Let $\RR$ be an equivalence relation on the structure $\struct {S, \rightarrow}$.
Then:
:$x_1 \rightarrow y_1 = y_1$
:$x_2 \rightarrow y_2 = y_2$
Suppose $x_1 \mathrel \RR x_2 \land y_1 \mathrel \RR y_2$.
It follows directly that:
:$\paren {x_1 \rightarrow y_1} \mathrel \RR \paren {x_2 \rightarrow y_2}$
== Also see ==
* Equivalence Relation is Congruence for Left Operation
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Example $11.4$
Category:Right Operation
Category:Examples of Equivalence Relations
Category:Examples of Congruence Relations
Equivalence Relation is Congruence iff Compatible with Operation

== Theorem ==
Let $\struct {S, \circ}$ be an algebraic structure.
Let $\RR$ be an equivalence relation on $S$.
Then $\RR$ is a congruence relation for $\circ$ :
That is, $\RR$ is compatible with $\circ$.
== Proof 1 ==
== Proof 2 ==
== Sources ==
* : Chapter $\text {II}$: New Structures from Old: $\S 11$: Quotient Structures: Exercise $11.7$
Category:Equivalence Relations
Category:Congruence Relations
Category:Compatible Relations
Category:Equivalence Relation is Congruence iff Compatible with Operation
Equivalence Relation is Congruence iff Compatible with Operation/Proof 1

== Theorem ==
== Proof ==
=== Necessary Condition ===
Let $\RR$ be a congruence relation for $\circ$.
That is:
:$\forall x_1, x_2, y_1, y_2 \in S: x_1 \mathrel \RR x_2 \land y_1 \mathrel \RR y_2 \implies \paren {x_1 \circ y_1} \mathrel \RR \paren {x_2 \circ y_2}$
As $\RR$ is an equivalence relation it is by definition reflexive.
That is:
:$\forall z \in S: z \mathrel \RR z$
Make the substitutions:
It follows that:
:$\forall x, y, z \in S: x \mathrel \RR y \implies \paren {x \circ z} \mathrel \RR \paren {y \circ z}$
Similarly, make the substitutions:
It follows that:
:$\forall x, y, z \in S: x \mathrel \RR y \implies \paren {z \circ x} \mathrel \RR \paren {z \circ y}$
=== Sufficient Condition ===
Now let $\RR$ have the nature that:
Then we have:
As $\RR$ is an equivalence relation it is by definition transitive.
Thus it follows that:
:$\paren {x_1 \circ x_2} \mathrel \RR \paren {y_1 \circ y_2}$
The result follows.
Category:Equivalence Relation is Congruence iff Compatible with Operation
Equivalence Relation on Cauchy Sequences

== Lemma ==
Let $\struct {X, d}$ be a metric space.
Let $\CC \sqbrk X$ denote the set of all Cauchy sequences of elements from $X$.
Let a relation $\sim$ be defined on $\CC \sqbrk X$ by:
:$\ds \sequence {x_n} \sim \sequence {y_n} \iff \lim_{n \mathop \to \infty} \map d {x_n, y_n} = 0$
Then $\sim$ is an equivalence relation on $\CC \sqbrk X$.
== Proof ==
We must show that $\sim$ is
:reflexive,
:symmetric and
:transitive
on $\CC \sqbrk X$.
To this end, let $\sequence {x_n}, \sequence {y_n}, \sequence {z_n} \in \CC \sqbrk X$ be arbitrary.
For each $n \in \N$ we have that $\map d {x_n, x_n} = 0$ by .
Therefore $\ds \lim_{n \mathop \to \infty} \map d {x_n, x_n} = 0$.
This shows that $\sequence {x_n} \sim \sequence {x_n}$.
Thus $\sim$ is reflexive.
By , $\map d {x_n, y_n} = \map d {y_n, x_n}$ for each $n \in \N$.
Therefore:
:$\ds \lim_{n \mathop \to \infty} \map d {x_n, y_n} = \lim_{n \mathop \to \infty} \map d {y_n, x_n}$
So $\sequence {x_n} \sim \sequence {y_n}$ implies that $\sequence {y_n} \sim \sequence {x_n}$.
Thus $\sim$ is symmetric.
Finally, by , $\map d {x_n, z_n} \le \map d {x_n, y_n} + \map d {y_n, z_n}$ for each $n \in \N$.
Therefore, by the sum rule for limits of sequences:
:$\ds \lim_{n \mathop \to \infty} \map d {x_n, z_n} \le \lim_{n \mathop \to \infty} \map d {x_n, y_n} + \lim_{n \mathop \to \infty} \map d {y_n, z_n}$
Thus $\sequence {x_n} \sim \sequence {y_n}$ and $\sequence {y_n} \sim \sequence {z_n}$ together imply that $\sequence {x_n} \sim \sequence {z_n}$.
Thus $\sim$ is transitive.
So $\sim$ is shown to be reflexive, symmetric and transitive, and therefore an equivalence relation on $\CC \sqbrk X$.
Category:Cauchy Sequences
Equivalence Relation on Integers Modulo 5 induced by Squaring

== Theorem ==
Let $\beta$ denote the relation defined on the integers $\Z$ by:
:$\forall x, y \in \Z: x \mathrel \beta y \iff x^2 \equiv y^2 \pmod 5$
Then $\beta$ is an equivalence relation.
=== Number of $\beta$-Equivalence Classes ===
=== Addition Modulo $\beta$ is not Well-Defined ===
=== Multiplication Modulo $\beta$ is Well-Defined ===
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
We have that for all $x \in \Z$:
:$x^2 \equiv x^2 \pmod 5$
It follows by definition of $\beta$ that:
:$x \mathrel \beta x$
Thus $\beta$ is seen to be reflexive.
=== Symmetry ===
Thus $\beta$ is seen to be symmetric.
=== Transitivity ===
Let:
:$x \mathrel \beta y$ and $y \mathrel \beta z$
for $x, y, z \in \Z$.
Then by definition:
Thus $\beta$ is seen to be transitive.
$\beta$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
== Sources ==
* : Appendix $\text{A}.3$: Equivalence Relations: Problem Set $\text{A}.3$: $21$
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $9$
Category:Examples of Equivalence Relations
Category:Examples of Modulo Arithmetic
Category:Equivalence Relation on Integers Modulo 5 induced by Squaring
Equivalence Relation on Integers Modulo 5 induced by Squaring/Addition Modulo Beta is not Well-Defined

== Theorem ==
Let $\beta$ denote the relation defined on the integers $\Z$ by:
:$\forall x, y \in \Z: x \mathrel \beta y \iff x^2 \equiv y^2 \pmod 5$
We have that $\beta$ is an equivalence relation.
Let the $+_\beta$ operator ("addition") on the $\beta$-equivalence classes be defined as:
:$\eqclass a \beta +_\beta \eqclass b \beta := \eqclass {a + b} \beta$
Then such an operation is not well-defined.
== Proof ==
That $\beta$ is an equivalence relation is proved in Equivalence Relation on Integers Modulo 5 induced by Squaring.
From Number of Equivalence Classes we have:
We have:
Thus:
Hence the result.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $9 \ \text {(i)}$
Category:Equivalence Relation on Integers Modulo 5 induced by Squaring
Equivalence Relation on Integers Modulo 5 induced by Squaring/Multiplication Modulo Beta is Well-Defined

== Theorem ==
Let $\beta$ denote the relation defined on the integers $\Z$ by:
:$\forall x, y \in \Z: x \mathrel \beta y \iff x^2 \equiv y^2 \pmod 5$
We have that $\beta$ is an equivalence relation.
Let the $\times_\beta$ operator ("multiplication") on the $\beta$-equivalence classes be defined as:
:$\eqclass a \beta \times_\beta \eqclass b \beta := \eqclass {a \times b} \beta$
Then such an operation is well-defined.
== Proof ==
That $\beta$ is an equivalence relation is proved in Equivalence Relation on Integers Modulo 5 induced by Squaring.
Let:
We have:
Hence the result.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $9 \ \text{(ii)}$
Category:Equivalence Relation on Integers Modulo 5 induced by Squaring
Equivalence Relation on Integers Modulo 5 induced by Squaring/Number of Equivalence Classes

== Theorem ==
Let $\beta$ denote the relation defined on the integers $\Z$ by:
:$\forall x, y \in \Z: x \mathrel \beta y \iff x^2 \equiv y^2 \pmod 5$
We have that $\beta$ is an equivalence relation.
The number of distinct $\beta$-equivalence classes is $3$:
== Proof ==
That $\beta$ is an equivalence relation is proved in Equivalence Relation on Integers Modulo 5 induced by Squaring.
The set of residue classes modulo $5$ is:
:$\set {\eqclass 0 5, \eqclass 1 5, \eqclass 2 5, \eqclass 3 5, \eqclass 4 5}$
Then:
Thus we have that:
:$\eqclass 1 5^2 = \eqclass 4 5^2 = \eqclass 1 \beta$
:$\eqclass 2 5^2 = \eqclass 3 5^2 = \eqclass 2 \beta$
Hence the result.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $9$
Category:Equivalence Relation on Integers Modulo 5 induced by Squaring
Equivalence Relation on Natural Numbers such that Quotient is Power of Two

== Theorem ==
Let $\alpha$ denote the relation defined on the natural numbers $\N$ by:
:$\forall x, y \in \N: x \mathrel \alpha y \iff \exists n \in \Z: x = 2^n y$
Then $\alpha$ is an equivalence relation.
=== Equivalence Class Contains 1 Odd Number ===
=== Equivalence Class of Prime ===
=== Smallest Equivalence Class with no Prime ===
=== One of Pair of Equivalent Elements is Divisor of the Other ===
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
We have that for all $x \in \N$:
:$x = 2^0 x$
and as $0 \in \Z$ it follows that:
:$x \mathrel \alpha x$
Thus $\alpha$ is seen to be reflexive.
=== Symmetry ===
Thus $\alpha$ is seen to be symmetric.
=== Transitivity ===
Let $x \mathrel \alpha y$ and $y \mathrel \alpha z$.
Then by definition:
Thus $\alpha$ is seen to be transitive.
$\alpha$ 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 $8$
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $5$
Category:Examples of Equivalence Relations
Category:Equivalence Relation on Natural Numbers such that Quotient is Power of Two
Equivalence Relation on Natural Numbers such that Quotient is Power of Two/Equivalence Class Contains 1 Odd Number

== Theorem ==
Let $\alpha$ denote the relation defined on the natural numbers $\N$ by:
:$\forall x, y \in \N: x \mathrel \alpha y \iff \exists n \in \Z: x = 2^n y$
We have that $\alpha$ is an equivalence relation.
Let $\eqclass n \alpha$ be the $\alpha$-equivalence class of a natural number $n$.
Then $\eqclass n \alpha$ contains exactly $1$ odd number.
== Proof ==
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Natural Numbers such that Quotient is Power of Two.
Let $x$ be a natural number whose $\alpha$-equivalence class is $\eqclass x \alpha$.
If $x$ is odd, then $\eqclass x \alpha$ contains that odd number $x$
We have that $x$ is of the form $x = 2^r y$ for some $r \in \Z$ where $y$ is an odd number.
Thus by definition $y \in \eqclass x \alpha$ is an odd number which is contained in $\eqclass x \alpha$.
Thus it has been shown that an arbitrary $\eqclass x \alpha$ contains at least one odd number.
It remains to be demonstrated that $\eqclass x \alpha$ contains no more than $1$ odd number.
 $\eqclass n \alpha$ contains the odd numbers $p$ and $q$ such that $p \ne q$.
Then:
:$p = 2^n q$
for some $n \in \Z$
If $n = 0$ then $p = q$ which contradicts $q \ne p$.
Thus $n \ne 0$.
Let $n > 0$.
Then:
:$p = r q$
for $r \in \Z$ such that $r = 2^n$.
Thus $p$ is has $2$ as a divisor.
This contradicts the supposition that $p$ is odd.
Let $n < 0$.
Then:
:$p = \dfrac q {2^m}$
where $m = -n$ and so $m > 0$.
Thus:
:$q = r p$
for $r \in \Z$ such that $r = 2^m$.
 
Thus $q$ has $2$ as a divisor.
This contradicts the supposition that $q$ is odd.
Thus all cases of $n$ lead to a contradiction.
It follows that no $\alpha$-equivalence class can contain more than one odd number.
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Exercise $8$
Category:Equivalence Relation on Natural Numbers such that Quotient is Power of Two
Category:Examples of Equivalence Relations
Equivalence Relation on Natural Numbers such that Quotient is Power of Two/Equivalence Class of Prime

== Theorem ==
Let $\alpha$ denote the relation defined on the natural numbers $\N$ by:
:$\forall x, y \in \N: x \mathrel \alpha y \iff \exists n \in \Z: x = 2^n y$
We have that $\alpha$ is an equivalence relation.
Let $\eqclass p \alpha$ be the $\alpha$-equivalence class of a prime number $p$.
Then $\eqclass p \alpha$ contains no other prime number other than $p$.
== Proof ==
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Natural Numbers such that Quotient is Power of Two.
Let $p$ be a prime number whose $\alpha$-equivalence class is $\eqclass p \alpha$.
 $\eqclass p \alpha$ contains a prime number $q$ such that $q \ne p$.
Then:
:$p = 2^n q$
for some $n \in \Z$
If $n = 0$ then $p = q$ which contradicts $q \ne p$.
Thus $n \ne 0$.
Let $n > 0$.
Then:
:$p = r q$
for $r \in \Z$ such that $r = 2^n$.
Thus $p$ is a composite number with divisors $q$ and $r$ (and possibly more).
This contradicts the supposition that $p$ is prime.
Let $n < 0$.
Then:
:$p = \dfrac q {2^m}$
where $m = -n$ and so $m > 0$.
Thus:
:$q = r p$
for $r \in \Z$ such that $r = 2^m$.
 
Thus $q$ is a composite number with divisors $p$ and $r$ (and possibly more).
This contradicts the supposition that $q$ is prime.
Thus all cases of $n$ lead to a contradiction.
It follows that no $\alpha$-equivalence class can contain more than one prime number.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $5$
Category:Equivalence Relation on Natural Numbers such that Quotient is Power of Two
Equivalence Relation on Natural Numbers such that Quotient is Power of Two/One of Pair of Equivalent Elements is Divisor of the Other

== Theorem ==
Let $\alpha$ denote the relation defined on the natural numbers $\N$ by:
:$\forall x, y \in \N: x \mathrel \alpha y \iff \exists n \in \Z: x = 2^n y$
We have that $\alpha$ is an equivalence relation.
Let $c, d \in \N$ such that $c \mathrel \alpha d$.
Then either:
:$c \divides d$
or:
:$d \divides c$
where $\divides$ denotes divisibility.
== Proof ==
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Natural Numbers such that Quotient is Power of Two.
We are given that $c \mathrel \alpha d$.
, suppose $c < d$.
If $d < c$ then the same argument holds, .
By definition of $\alpha$, we have that:
:$c = 2^n d$
for some $n \in \Z$.
As $c < d$ it follows that $2^n > 1$.
That is, $n > 0$ and so $2^n \in \Z$.
So by definition $c$ is a divisor of $d$.
The result follows.
== Sources ==
* : $\S 6$. Indexed families; partitions; equivalence relations: Exercise $8$
Category:Equivalence Relation on Natural Numbers such that Quotient is Power of Two
Equivalence Relation on Natural Numbers such that Quotient is Power of Two/Smallest Equivalence Class with no Prime

== Theorem ==
Let $\alpha$ denote the relation defined on the natural numbers $\N$ by:
:$\forall x, y \in \N: x \mathrel \alpha y \iff \exists n \in \Z: x = 2^n y$
We have that $\alpha$ is an equivalence relation.
Let $\eqclass x \alpha$ denote the $\alpha$-equivalence class of a natural number $x$.
Let $r$ be the smallest natural number such that $\eqclass r \alpha$ contains no prime number.
Then $r = 9$.
== Proof ==
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Natural Numbers such that Quotient is Power of Two.
 $r$ is even.
Then $r = 2 s$ for some $s \in \N$.
Thus $s \in \eqclass r \alpha$ such that $s < r$.
This contradicts the supposition that $r$ is the smallest such natural number.
Thus $r$ has to be the smallest odd composite number, and so:
:$r = 3^2 = 9$
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $5$
Category:Equivalence Relation on Natural Numbers such that Quotient is Power of Two
Equivalence Relation on Power Set induced by Intersection with Subset

== Theorem ==
Let $A, T$ be sets such that $A \subseteq T$.
Let $S = \powerset T$ denote the power set of $T$.
Let $\alpha$ denote the relation defined on $S$ by:
:$\forall X, Y \in S: X \mathrel \alpha Y \iff X \cap A = Y \cap A$
Then $\alpha$ is an equivalence relation.
=== Equivalence Class of Empty Set ===
=== Cardinality of Set of Equivalence Classes ===
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
We have that for all $X \in S$:
:$X \cap A = X \cap A$
That is:
:$X \mathrel \alpha X$
Thus $\alpha$ is seen to be reflexive.
=== Symmetry ===
Thus $\alpha$ is seen to be symmetric.
=== Transitivity ===
Let $X \mathrel \alpha Y$ and $Y \mathrel \alpha Z$.
Then by definition:
Hence:
:$X \cap A = Z \cap A$
and so by definition of $\alpha$:
:$X \mathrel \alpha Z$
Thus $\alpha$ is seen to be transitive.
$\alpha$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $2 \ \text {(i)}$
Category:Examples of Equivalence Relations
Category:Equivalence Relation on Power Set induced by Intersection with Subset
Equivalence Relation on Power Set induced by Intersection with Subset/Cardinality of Set of Equivalence Classes

== Theorem ==
Let $A, T$ be sets such that $A \subseteq T$.
Let $S = \powerset T$ denote the power set of $T$.
Let $\alpha$ denote the relation defined on $S$ by:
:$\forall X, Y \in S: X \mathrel \alpha Y \iff X \cap A = Y \cap A$
We have that $\alpha$ is an equivalence relation.
Let $A$ be finite with $\card A = n$, where $\card {\, \cdot \,}$ denotes cardinality.
The cardinality of the set of $\alpha$-equivalence classes is given by:
:$\card {\set {\eqclass X \alpha: X \in S} } = 2^n$
== Proof ==
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Power Set induced by Intersection with Subset.
Let $U \subseteq A$.
Then $U$ is in its own $\alpha$-equivalence class.
Now suppose $U' \subseteq A$ such that $U \ne U'$.
From Intersection with Subset is Subset:
:$U \cap A = U$
and:
:$U' \cap A = U'$
So:
:$U \ne U' \implies \eqclass U \alpha \ne \eqclass {U'} \alpha$
and so there are as many $\alpha$-equivalence classes as there are subsets of $A$.
That is:
:$\card {\set {\eqclass X \alpha: X \in S} } = \powerset A$
The result follows from Cardinality of Power Set of Finite Set.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $2 \ \text {(iii)}$
Category:Equivalence Relation on Power Set induced by Intersection with Subset
Equivalence Relation on Power Set induced by Intersection with Subset/Equivalence Class of Empty Set

== Theorem ==
Let $A, T$ be sets such that $A \subseteq T$.
Let $S = \powerset T$ denote the power set of $T$.
Let $\alpha$ denote the relation defined on $S$ by:
:$\forall X, Y \in S: X \mathrel \alpha Y \iff X \cap A = Y \cap A$
We have that $\alpha$ is an equivalence relation.
The equivalence class of $\O$ in $S$ with respect to $\alpha$ is given by:
:$\eqclass \O \alpha = \powerset {T \setminus A}$
== Proof ==
That $\alpha$ is an equivalence relation is proved in Equivalence Relation on Power Set induced by Intersection with Subset.
We have that:
:$\eqclass \O \alpha = \set {X \in S: X \cap A = \O \cap A = \O}$
Thus:
Then:
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $2 \ \text {(ii)}$
Category:Equivalence Relation on Power Set induced by Intersection with Subset
Equivalence Relation on Square Matrices induced by Positive Integer Powers

== Theorem ==
Let $n \in \Z_{>0}$ be a (strictly) positive integer.
Let $S$ be the set of all square matrices of order $n$.
Let $\alpha$ denote the relation defined on $S$ by:
:$\forall \mathbf A, \mathbf B \in S: \mathbf A \mathrel \alpha \mathbf B \iff \exists r, s \in \N: \mathbf A^r = \mathbf B^s$
Then $\alpha$ is an equivalence relation.
== Proof ==
Checking in turn each of the criteria for equivalence:
=== Reflexivity ===
We have that for all $\mathbf A \in S$:
:$\mathbf A^r = \mathbf A^r$
for all $r \in \N$.
It follows by definition of $\alpha$ that:
:$\mathbf A \mathrel \alpha \mathbf A$
Thus $\alpha$ is seen to be reflexive.
=== Symmetry ===
Thus $\alpha$ is seen to be symmetric.
=== Transitivity ===
Let:
: $\mathbf A \mathrel \alpha \mathbf B$ and $\mathbf B \mathrel \alpha \mathbf C$
for square matrices of order $n$ $\mathbf A, \mathbf B, \mathbf C$.
Then by definition:
Thus $\alpha$ is seen to be transitive.
$\alpha$ has been shown to be reflexive, symmetric and transitive.
Hence by definition it is an equivalence relation.
== Sources ==
* : Chapter $3$: Equivalence Relations and Equivalence Classes: Exercise $6$
Category:Examples of Equivalence Relations
Category:Matrix Algebra
Equivalence Relation on Symmetric Group by Image of n is Congruence Modulo Subgroup

== Theorem ==
Let $S_n$ denote the symmetric group on $n$ letters $\set {1, \dots, n}$.
Let $\sim$ be the relation on $S_n$ defined as:
:$\forall \pi, \tau \in S_n: \pi \sim \tau \iff \map \pi n = \map \tau n$
Then $\sim$ is an equivalence relation which is congruence modulo a subgroup.
== Proof ==
We claim that $\sim$ is left congruence modulo $S_{n - 1}$, the symmetric group on $n - 1$ letters $\set {1, \dots, n - 1}$.
Notice that every element of $S_{n - 1}$ fixes $n$.
For all $\pi, \tau \in S_n$ such that $\pi \sim \tau$:
so $\pi^{-1} \circ \tau$ fixes $n$ as well.
This shows that $\pi^{-1} \circ \tau \in S_{n - 1}$.
By definition of Left Congruence Modulo Subgroup:
:$\pi \equiv^l \tau \pmod {S_{n - 1} }$
Now we show the converse.
Suppose $\pi \equiv^l \tau \pmod {S_{n - 1} }$.
Then $\pi^{-1} \circ \tau \in S_{n - 1}$.
Hence $\map {\paren {\pi^{-1} \circ \tau} } n = n$.
Then:
Therefore $\sim$ and left congruence modulo $S_{n - 1}$ are equivalent.
The fact that $\sim$ is an equivalence relation follows from Left Congruence Modulo Subgroup is Equivalence Relation.
== Sources ==
* : Chapter $2$: Subgroups and Cosets: $\S 37 \delta$
Category:Symmetric Groups