avewright/proofwiki-math huggingface dataset:
Theorem: Equivalence of Well-Ordering Principle and Induction/Proof/PCI implies WOP

The Principle of Complete Induction implies the Well-Ordering Principle.
That is:
:Principle of Complete Induction: Given a subset $S \subseteq \N$ of the natural numbers which has these properties:
::$0 \in S$
::$\set {0, 1, \ldots, n} \subseteq S \implies n + 1 \in S$
:then $S = \N$.
implies:
:Well-Ordering Principle: Every nonempty subset of $\N$ has a minimal element.

Proof:
Let us assume that the '''PCI''' is true.
Let $\O \subsetneqq S \subseteq \N$.
We need to show that $S$ has a minimal element, and so demonstrate that the '''WOP''' holds.
{{AimForCont}} that:
:$(C): \quad S$ has no minimal element.
Let $\map P n$ be the propositional function:
:$n \notin S$
Suppose $0 \in S$.
We have that $0$ is a lower bound for $\N$.
Hence by Lower Bound for Subset, $0$ is also a lower bound for $S$.
$0 \notin S$, otherwise $0$ would be the minimal element of $S$.
This contradicts our supposition $(C)$, namely, that $S$ does not have a minimal element.
So $0 \notin S$ and so $\map P 0$ holds.
Suppose $\map P j$ for $0 \le j \le k$.
That is:
:$\forall j \in \closedint 0 k: j \notin S$
where $\closedint 0 k$ denotes the closed interval between $0$ and $k$.
Now if $k + 1 \in S$ it follows that $k + 1$ would then be the minimal element of $S$.
So then $k + 1 \notin S$ and so $\map P {k + 1}$.
Thus we have proved that:
:$(1): \quad \map P 0$ holds
:$(2): \quad \paren {\forall j \in \closedint 0 k: \map P j} \implies \map P {k + 1}$
So we see that '''PCI''' implies that $\map P n$ holds for all $n \in \N$.
But this means that $S = \O$, which is a contradiction of the fact that $S$ is non-empty.
So, by Proof by Contradiction, $S$ must have a minimal element.
That is, $\N$ satisfies the Well-Ordering Principle.
Thus '''PCI''' implies '''WOP'''.
Theorem: Equivalence of Well-Ordering Principle and Induction/Proof/WOP implies PFI

The Well-Ordering Principle implies the Principle of Finite Induction.
That is:
:Well-Ordering Principle: Every non-empty subset of $\N$ has a minimal element
implies:
:Principle of Finite Induction: Given a subset $S \subseteq \N$ of the natural numbers which has these properties:
::$0 \in S$
::$n \in S \implies n + 1 \in S$
:then $S = \N$.

Proof:
We assume the truth of '''WOP'''.
Let $S \subseteq \N$ which satisfy:
:$(D): \quad 0 \in S$
:$(E): \quad n \in S \implies n+1 \in S$.
We want to show that $S = \N$, that is, the '''PFI''' is true.
{{AimForCont}} that:
:$S \ne \N$
Consider $S' = \N \setminus S$, where $\setminus$ denotes set difference.
From Set Difference is Subset, $S' \subseteq \N$.
So from '''WOP''', $S'$ has a minimal element.
A lower bound of $\N$ is $0$.
By Lower Bound for Subset, $0$ is also a lower bound for $S'$.
By hypothesis, $0 \in S$.
From the definition of set difference, $0 \notin S'$.
So this minimal element of $S'$ has the form $k + 1$ where $k \in \N$.
We can consider the von Neumann construction of the natural numbers.
By definition of natural number addition, it is noted that $k + 1 \in \N$ is the immediate successor element of $k \in \N$.
Thus $k \in S$ but $k + 1 \notin S$.
From $(E)$, this contradicts the definition of $S$.
Thus if $S' \ne \O$, it has no minimal element.
This contradicts the Well-Ordering Principle, and so  $S' = \O$.
So $S = N$.
Thus we have proved that '''WOP''' implies '''PFI'''.
Theorem: Floor Function/Examples/Floor of 5 over 2

:$\floor {\dfrac 5 2} = 2$

Proof:
We have that:
{{begin-eqn}}
{{eqn | l = \dfrac 5 2
      | r = 2 + \dfrac 1 2
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 2
      | o = \le
      | r = \dfrac 5 2
      | c = 
}}
{{eqn | o = <
      | r = 3
      | c = 
}}
{{end-eqn}}
Hence $2$ is the floor of $\dfrac 5 2$ by definition.
{{qed}}
Theorem: Floor Function/Examples/Floor of Minus 5 over 2

:$\floor {-\dfrac 5 2} = -3$

Proof:
We have that:
{{begin-eqn}}
{{eqn | l = -\dfrac 5 2
      | r = -3 + \dfrac 1 2
      | c = 
}}
{{eqn | ll= \leadsto
      | l = -3
      | o = \le
      | r = -\dfrac 5 2
      | c = 
}}
{{eqn | o = <
      | r = -2
      | c = 
}}
{{end-eqn}}
Hence $-3$ is the floor of $-\dfrac 5 2$ by definition.
{{qed}}
Theorem: Floor Function/Examples/Floor of 14

:$\floor {14} = 14$

Proof:
We have that $14$ is an integer.
Thus this is a specific example of Real Number is Integer iff equals Floor:
$\floor x = x \iff x \in \Z$
{{qed}}
Theorem: Floor Function/Examples/Floor of Root 10

:$\floor {\sqrt {10} } = 3$

Proof:
{{begin-eqn}}
{{eqn | l = \sqrt 9
      | o = \le
      | r = \sqrt 10
      | c = 
}}
{{eqn | o = <
      | r = \sqrt 16
      | c = 
}}
{{eqn | ll= \leadsto
      | l = 3
      | o = \le
      | r = \sqrt 10
      | c = 
}}
{{eqn | o = <
      | r = 4
      | c = 
}}
{{end-eqn}}
Hence $3$ is the floor of $\sqrt {10}$ by definition.
{{qed}}
Theorem: Combination Theorem for Cauchy Sequences/Inverse Rule

Suppose $\sequence {x_n}$ does not converge to $0$.
Then:
:$\exists K \in \N: \forall n > K : x_n \ne 0$
and the sequence:
:$\sequence {\paren {x_{K + n} }^{-1} }_{n \mathop \in \N}$ is well-defined and a Cauchy sequence.

Proof:
Since $\sequence {x_n}$ does not converge to $0$, by Cauchy Sequence Is Eventually Bounded Away From Non-Limit then:
:$\exists K \in \N$ and $C \in \R_{>0}: \forall n > K: C <  \norm {x_n}$
or equivalently:
:$\exists K \in \N$ and $C \in \R_{>0}: \forall n > K: 1 < \dfrac {\norm {x_n} } C$
By {{Norm-axiom-mult|1}}:
:$\forall n > K : x_n \ne 0$
Let $\sequence {y_n}$ be the subsequence of $\sequence {x_n}$ defined as:
:$y_n = x_{K + n}$
By Subsequence of Cauchy Sequence in Normed Division Ring is Cauchy Sequence:
:$\sequence {y_n}$ is a Cauchy sequence.
So $\sequence { {y_n}^{-1} }$ is well-defined and $\sequence { {y_n}^{-1} } = \sequence {\paren {x_{K + n} }^{-1} }_{n \mathop \in \N}$.
Let $\epsilon > 0$ be given.
Let $\epsilon' = \epsilon C^2$, then $ \epsilon' > 0$.
Similarly, $\sequence {y_n}$ is a Cauchy sequence, we can find $N$ such that:
:$\forall n, m > N_2: \norm {y_n - y_m} < \epsilon'$
Thus $\forall n, m > N$:
:$(1): \quad 1 < \dfrac {\norm {y_n} } C, \dfrac {\norm {y_m} } C$
:$(2): \quad \norm {y_n - y_m} < \epsilon'$
Hence:
{{begin-eqn}}
{{eqn | l = \norm { {y_n}^{-1} - {y_m}^{-1} }
      | o = <
      | r = \dfrac {\norm {y_n} } C \norm { {y_n }^{-1} - {y_m}^{-1} } \dfrac {\norm {y_m} } C
      | c = $(1)$ above
}}
{{eqn | r = \dfrac 1 {C^2} \paren {\norm {y_n} \norm { {y_n }^{-1} - {y_m}^{-1 } } \norm {y_m} }
}}
{{eqn | r = \dfrac 1 {C^2} \norm {y_n \paren { {y_n }^{-1 } - {y_m }^{-1} } y_m}
      | c = {{Norm-axiom-mult|2}}
}}
{{eqn | r = \dfrac 1 {C^2} \norm {\paren {y_n {y_n }^{-1 } - y_n {y_m }^{-1} } y_m }
      | c = {{Ring-axiom|D}}
}}
{{eqn | r = \dfrac 1 {C^2} \norm {y_n {y_n}^{-1} y_m - y_n {y_m}^{-1} y_m}
      | c = {{Ring-axiom|D}}
}}
{{eqn | r = \dfrac 1 {C^2} \norm {y_m - y_n}
      | c = Inverse Property of a Division Ring
}}
{{eqn | r = \dfrac 1 {C^2} \epsilon'
      | o = <
      | c = $(2)$ above
}}
{{eqn | r = \dfrac 1 {C^2} \paren {\epsilon C^2}
      | c = Definition of $\epsilon'$
}}
{{eqn | r = \epsilon
}}
{{end-eqn}}
So:
:$\sequence { { {y_n}^{-1} } }$ is a Cauchy sequence in $R$ by definition.
{{qed}}
Theorem: Subsequence of Cauchy Sequence in Normed Division Ring is Cauchy Sequence

Let $\struct {R, \norm {\, \cdot \,} }$ be a normed division ring with zero: $0$.
Let $\sequence {x_n}$ be a Cauchy sequence in $R$.
Let $\sequence {x_{n_r} }$ be a subsequence of $\sequence {x_n}$.
Then:
:$\sequence {x_{n_r} }$ is a Cauchy sequence in $R$.

Proof:
Let $\epsilon > 0$.
Since $\sequence {x_n}$ is a Cauchy sequence then:
:$\exists N: \forall n,m > N: \norm {x_n - x_m } < \epsilon$
Now let $R = N$.
Then from Strictly Increasing Sequence of Natural Numbers:
:$\forall r, s > R: n_r \ge r$ and $n_s \ge s$
Thus $n_r, n_s > N$ and so:
:$\norm {x_{n_r} - x_{n_s} } < \epsilon$
The result follows.
{{qed}}
Theorem: Coprime Divisors of Square Number are Square

Let $r$ be a square number.
Let $r = s t$ where $s$ and $t$ are coprime.
Then both $s$ and $t$ are square.

Proof:
Let $p$ be a prime factor of $s$.
Then for some $n \in \Z_{>0}$:
:$p^{2 n} \divides s t$
where $\divides$ denotes the divisibility relation.
But we have that $s \perp t$ and so $p \nmid t$.
Thus $p^{2 n} \divides s$.
This holds for all prime factors of $s$.
Thus $s$ is the product of squares of primes.
Thus $s$ is square.
The same argument holds for $t$.
Hence the result.
{{qed}}
Theorem: Combination Theorem for Cauchy Sequences/Constant Rule

The constant sequence $\tuple {a, a, a, \dots}$ is a Cauchy sequence.

Proof:
Let $\sequence {x_n}$ be the constant sequence: 
:$\forall n, x_n = a$
Given $\epsilon > 0$:
:$\forall n, m \ge 1: \norm {x_n - x_m} = \norm {a - a} = \norm {0} = 0 < \epsilon$
The result follows.
{{qed}}
Theorem: Combination Theorem for Cauchy Sequences/Multiple Rule

:$\sequence {a x_n}$ is a Cauchy sequence.

Proof:
Follows directly from Product Rule for Normed Division Ring Sequences, setting
:$\sequence {y_n} := \sequence {x_n}$
and:
:$\sequence {x_n} := \tuple {a, a, a, \ldots}$
{{qed}}
Theorem: Combination Theorem for Cauchy Sequences/Difference Rule

:$\sequence {x_n - y_n}$ is a Cauchy sequence.

Proof:
From Multiple Rule for Normed Division Ring Sequences:
:$\sequence {-y_n} = \sequence {\paren {-1} y_n}$ is a Cauchy sequence. 
From Sum Rule for Normed Division Ring Sequences:
:$\sequence {x_n - y_n} = \sequence {x_n + \paren {-y_n} }$ is a Cauchy sequence.
{{qed}}
Theorem: Combination Theorem for Cauchy Sequences/Combined Sum Rule

:$\sequence {a x_n + b y_n }$ is a Cauchy sequence.

Proof:
From the Multiple Rule for Normed Division Ring Sequences:
:$\sequence {a x_n}$ is a Cauchy sequence
:$\sequence {b y_n}$ is a Cauchy sequence.
The result now follows directly from the Sum Rule for Normed Division Ring Sequences:
:$\sequence {a x_n + b y_n}$ is a Cauchy sequence.
{{qed}}
Theorem: Congruent Integers in Same Residue Class

Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let $\Z_m$ be the set of residue classes modulo $m$:
:$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \dotsc, \eqclass {m - 1} m}$
Let $a, b \in \set {0, 1, \ldots, m -1 }$.
Then:
:$\eqclass a m = \eqclass b m \iff a \equiv b \pmod m$

Proof:
By definition of the set of residue classes modulo $m$, $\Z_m$ is the quotient set of congruence modulo $m$:
:$\Z_m = \dfrac \Z {\RR_m}$
where $\RR_m$ is the congruence relation modulo $m$ on the set of all $a, b \in \Z$:
:$\RR_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$
By the Fundamental Theorem on Equivalence Relations, $\Z_m$ is a partition of $\Z$.
Thus:
:$\eqclass a m = \eqclass b m$
{{iff}}:
:$x \in \eqclass a m \iff x \in \eqclass b m$
{{iff}}:
:$a \equiv b \pmod m$
{{qed}}
Theorem: Residue Classes form Partition of Integers

Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let $\Z_m$ be the set of residue classes modulo $m$:
:$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \dotsc, \eqclass {m - 1} m}$
Then $\Z_m$ forms a partition of $\Z$.

Proof:
By definition of the set of residue classes modulo $m$, $\Z_m$ is the quotient set of congruence modulo $m$:
:$\Z_m = \dfrac \Z {\RR_m}$
where $\RR_m$ is the congruence relation modulo $m$ on the set of all $a, b \in \Z$:
:$\RR_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$
By the Fundamental Theorem on Equivalence Relations, $\Z_m$ is a partition of $\Z$.
{{qed}}
Theorem: Cardinality of Set of Residue Classes

Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let $\Z_m$ be the set of residue classes modulo $m$.
Then:
:$\card {Z_m} = m$
where $\card {\, \cdot \,}$ denotes cardinality.

Proof:
By definition of the set of residue classes modulo $m$, $Z_m$ is the quotient set of congruence modulo $m$:
:$\Z_m = \dfrac \Z {\RR_m}$
where $\RR_m$ is the congruence relation modulo $m$ on the set of all $a, b \in \Z$:
:$\RR_m = \set {\tuple {a, b} \in \Z \times \Z: \exists k \in \Z: a = b + k m}$
Thus by definition $\Z_m$ is the '''set of residue classes modulo $m$''':
:$\Z_m = \set {\eqclass 0 m, \eqclass 1 m, \ldots, \eqclass {m - 1} m}$
Hence:
{{begin-eqn}}
{{eqn | l = \card {\Z_m}
      | r = \card {\set {0, 1, \ldots, m - 1} }
      | c = 
}}
{{eqn | r = m
      | c = 
}}
{{end-eqn}}
{{qed}}
Theorem: Structure Induced by Ring with Unity Operations is Ring with Unity

Let $\struct {R, +, \circ}$ be a ring with unity whose unity is $1_R$.
Let $S$ be a set.
Let $\struct {R^S, +', \circ'}$ be the structure on $R^S$ induced by $+'$ and $\circ'$.
Then $\struct {R^S, +', \circ'}$ is a ring with unity whose unity is $f_{1_R}: S \to R$, defined by:
:$\forall s \in S: \map {f_{1_R} } s = 1_R$

Proof:
By Structure Induced by Ring Operations is Ring then $\struct {R^S, +', \circ'}$ is a ring.
We have from Induced Structure Identity that the constant mapping $f_{1_R}: S \to R$ defined as:
:$\forall x \in S: \map {f_{1_R} } x = 1_R$
is the identity for $\struct {R^S, \circ'}$.
The result follows by definition of ring with unity and unity of ring.
{{qed}}
Category:Rings of Mappings
Category:Rings with Unity
5rqmmpykqgm8c2kdn94fo2bus367hci
Theorem: Cauchy Sequences form Ring with Unity

Let $\struct {R, +, \circ, \norm {\, \cdot \,} }$ be a normed division ring.
Let $\struct {R^\N, +, \circ}$ be the ring of sequences over $R$ with unity $\tuple {1, 1, 1, \dotsc}$.
Let $\CC \subset R^\N$ be the set of Cauchy sequences on $R$.
Then:
:$\struct {\CC, +, \circ}$ is a subring of $R^\N$ with unity $\tuple {1, 1, 1, \dotsc}$.

Proof:
The Subring Test used to prove the result.
By Constant Rule for Cauchy sequences:
:the constant sequence $\tuple {1, 1, 1, \dotsc}$ is a Cauchy sequences.
Hence:
:$\CC \neq \O$
Let $\sequence {x_n}, \sequence {y_n} \in \CC$.
By definition of pointwise addition:
:$\sequence {x_n} + \paren {-\sequence {y_n}} = \sequence {x_n - y_n}$.
By Difference Rule for Normed Division Ring Sequences:
:$\sequence {x_n - y_n}$ is a Cauchy sequence.
Hence:
:$\sequence {x_n} + \paren {- \sequence {y_n}} \in CC$.
By definition of pointwise product:
:$\sequence {x_n} \circ \sequence {y_n} = \sequence {x_n \circ y_n}$.
By Product Rule for Normed Division Ring Sequences:
:the sequence $\sequence {x_n \circ y_n}$ is a Cauchy sequence.
Hence:
:$\sequence {x_n} \circ \sequence {y_n} \in \CC$.
By the Subring Test the result follows.
{{qed}}
Theorem: Equivalence Relation on Power Set induced by Intersection with Subset

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.

Proof:
Checking in turn each of the criteria for equivalence:
Theorem: Structure Induced by Commutative Ring Operations is Commutative Ring

Let $\struct {R, +, \circ}$ be a commutative ring.
Let $S$ be a set.
Let $\struct {R^S, +', \circ'}$ be the structure on $R^S$ induced by $+'$ and $\circ'$.
Then $\struct {R^S, +', \circ'}$ is a commutative ring.

Proof:
By Structure Induced by Ring Operations is Ring then $\struct {R^S, +', \circ'}$ is a ring.
From Structure Induced by Commutative Operation is Commutative, so is the pointwise operation $\circ$ induces on $R^S$.
The result follows by definition of commutative ring.
{{qed}}
Category:Rings of Mappings
d9gcno26rkxm8oz0gfxy8wkr83wucul
Theorem: Equivalence Relation on Power Set induced by Intersection with Subset/Equivalence Class of Empty Set

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:
{{begin-eqn}}
{{eqn | l = X
      | o = \in
      | r = \eqclass \O \alpha
      | c = 
}}
{{eqn | ll= \leadsto
      | l = X \cap A
      | r = \O
      | c = {{Defof|Equivalence Class}}
}}
{{eqn | ll= \leadsto
      | l = X \cap A
      | o = \subseteq
      | r = \relcomp T A
      | c = Empty Intersection iff Subset of Complement
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \subseteq
      | r = T \setminus A
      | c = {{Defof|Relative Complement}}
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \in
      | r = \powerset {T \setminus A}
      | c = {{Defof|Power Set}}
}}
{{eqn | ll= \leadsto
      | l = \eqclass \O \alpha
      | o = \subseteq
      | r = \powerset {T \setminus A}
      | c = {{Defof|Subset}}
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | l = X
      | o = \in
      | r = \powerset {T \setminus A}
      | c = 
}}
{{eqn | ll= \leadsto
      | l = X \cap A
      | r = \O
      | c = reversing the above argument
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \alpha
      | r = \O
      | c = 
}}
{{eqn | ll= \leadsto
      | l = X
      | o = \in
      | r = \eqclass \O \alpha
      | c = 
}}
{{eqn | ll= \leadsto
      | l = \powerset {T \setminus A}
      | o = \subseteq
      | r = \eqclass \O \alpha
      | c = {{Defof|Subset}}
}}
{{end-eqn}}
{{qed}}
Theorem: Equivalence Relation on Power Set induced by Intersection with Subset/Cardinality of Set of Equivalence Classes

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.
{{qed}}
Theorem: Reflexive and Symmetric Relation is not necessarily Transitive

Let $S$ be a set.
Let $\alpha \subseteq S \times S$ be a relation on $S$.
Let $\alpha$ be both reflexive and symmetric.
Then it is not necessarily the case that $\alpha$ is also transitive.

Proof:
Proof by Counterexample:
Let $S = \set {a, b, c}$.
Let:
: $\alpha = \set {\tuple {a, a}, \tuple {b, b}, \tuple {c, c}, \tuple {a, b}, \tuple {b, a}, \tuple {b, c}, \tuple {c, b} }$
By inspection it is seen that $\alpha$ is both reflexive and symmetric.
However, we have:
:$a \mathrel \alpha b$ and $b \mathrel \alpha c$
but it is not the case that $a \mathrel \alpha c$.
Hence $\alpha$ is both reflexive and symmetric but not transitive.
{{qed}}
Theorem: Reflexive and Symmetric Relation is not necessarily Transitive

Let $S$ be a set.
Let $\alpha \subseteq S \times S$ be a relation on $S$.
Let $\alpha$ be both reflexive and symmetric.
Then it is not necessarily the case that $\alpha$ is also transitive.

Proof:
Proof by Counterexample:
Let $S = \Z$ be the set of integers.
Let $n \in \Z$ such that $n > 1$.
Let $\alpha$ be the relation on $S$ defined as:
:$\forall x, y \in S: x \mathrel \alpha y \iff \size {x - y} < n$
where $\size x$ denotes the absolute value of $x$.
It is seen that:
:$\forall x \in \Z: \size {x - x} = 0 < n$
and so:
:$\forall x \in \Z: x \mathrel \alpha x$
Thus $\alpha$ is reflexive
Then it is seen that:
:$\forall x, y \in \Z: \size {x - y} = \size {y - x}$
and so if $\size {x - y} < n$ then so is $\size {y - x} < n$.
That is, if $x \mathrel \alpha y$ then $y \mathrel \alpha x$.
Thus $\alpha$ is symmetric.
Now let $x = -\paren{n - 1}, y = 0, z = n - 1$.
We have:
{{begin-eqn}}
{{eqn | l = \size {x - y}
      | r = n - 1
}}
{{eqn | l = \size {y - z}
      | r = n - 1
}}
{{end-eqn}}
and so both $x \mathrel \alpha y$ and $y \mathrel \alpha z$.
But:
{{begin-eqn}}
{{eqn | l = \size {x - z}
      | r = \size {-\paren {n - 1} - \paren {n - 1} }
}}
{{eqn | r = 2 n - 2
}}
{{eqn | o = \ge
      | r = n + 2 - 2
      | c = as $n \ge 2$
}}
{{eqn | r = n
      | c = as $n \ge 2$
}}
{{eqn | ll= \leadsto
      | l = \neg \size {x - z}
      | o = <
      | r = n
      | c = 
}}
{{end-eqn}}
Thus:
:$\neg x \mathrel \alpha z$
and so $\alpha$ is not transitive.
Hence $\alpha$ is both reflexive and symmetric but not transitive.
{{qed}}
Theorem: Symmetric and Transitive Relation is not necessarily Reflexive

Let $S$ be a set.
Let $\alpha \subseteq S \times S$ be a relation on $S$.
Let $\alpha$ be both symmetric and transitive.
Then it is not necessarily the case that $\alpha$ is also reflexive.

Proof:
Proof by Counterexample:
Let $S = \Z$ be the set of integers.
Let $\alpha$ be the relation on $S$ defined as:
:$\forall x, y \in S: x \mathrel \alpha y \iff x = y = 0$
{{begin-eqn}}
{{eqn | l = x
      | o = \alpha
      | r = y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x
      | r = y = 0
      | c = 
}}
{{eqn | ll= \leadsto
      | l = y
      | r = x = 0
      | c = 
}}
{{eqn | ll= \leadsto
      | l = y
      | o = \alpha
      | r = x
      | c = 
}}
{{end-eqn}}
Thus $\alpha$ is symmetric.
Now let $x \mathrel \alpha y$ and $y \mathrel \alpha z$
Then:
:$x = y = 0, y = z = 0$
and so
:$x \mathrel \alpha z$
Now let $x = \Z$ such that $x \ne 0$.
Then it is not the case that:
:$x \mathrel \alpha x$
and so $\alpha$ is not reflexive.
Hence $\alpha$ is both symmetric and transitive but not reflexive.
{{qed}}
Theorem: Symmetric and Transitive Relation is not necessarily Reflexive

Let $S$ be a set.
Let $\alpha \subseteq S \times S$ be a relation on $S$.
Let $\alpha$ be both symmetric and transitive.
Then it is not necessarily the case that $\alpha$ is also reflexive.

Proof:
Proof by Counterexample:
Let $S = \set {1, 2}$ be a set.
Let $\RR$ be the relation on $S$ defined as:
:$\forall x, y \in S: x \mathrel \RR y \iff x = y = 2$
{{begin-eqn}}
{{eqn | l = x
      | o = \RR
      | r = y
      | c = 
}}
{{eqn | ll= \leadsto
      | l = x
      | r = y = 2
      | c = 
}}
{{eqn | ll= \leadsto
      | l = y
      | r = x = 2
      | c = 
}}
{{eqn | ll= \leadsto
      | l = y
      | o = \RR
      | r = x
      | c = 
}}
{{end-eqn}}
Thus $\alpha$ is symmetric.
Now let $x \mathrel \RR y$ and $y \mathrel \RR z$
Then:
:$x = y = 2, y = z = 2$
and so:
:$x \mathrel \RR z$
Now let $x = 1$.
Then it is not the case that:
:$x \mathrel \RR x$
and so $\RR$ is not reflexive.
Hence $\RR$ is both symmetric and transitive but not reflexive.
{{qed}}
Theorem: Equivalence Relation on Natural Numbers such that Quotient is Power of Two

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.

Proof:
Checking in turn each of the criteria for equivalence:
Theorem: Equivalence Relation on Natural Numbers such that Quotient is Power of Two/Equivalence Class of Prime

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$.
{{AimForCont}} $\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.
{{qed}}