Binary Operation on Natural Numbers on which Congruence Relations induce Convex Equivalence Classes

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\N$ denote the set of natural numbers: $\set {0, 1, 2, \ldots}$

Let $\circ$ be a binary operation on $\N$ with the following properties:

$\paren {\text O 1}: \quad$ $\circ$ has an identity element $e$
$\paren {\text O 2}: \quad$ Every equivalence relation $\RR$ on $\N$ whose equivalence classes are convex subsets of $\N$ is a congruence relation for $\circ$.


Then $\circ$ is the max operation on $\N$:

$\forall a, b \in \N: a \circ b = \max \set {a, b}$


Proof

Let $a, b \in \N$ where $e \le a < b$.

Let $\RR_1$ be an equivalence relation on $\N$ with equivalence classes:

$\closedint 0 {b - 1}, \set b, \hointr {b + 1} \infty$

By inspection, each of these equivalence classes are non-empty convex subsets of $\N$.

Hence $\RR_1$ is a congruence relation for $\circ$.

We have:

$\paren {e \mathrel {\RR_1} a} \land \paren {b \mathrel {\RR_1} b}$

Since $\RR_1$ is a congruence relation for $\circ$, we have:

$b = \paren {e \circ b} \mathrel {\RR_1} \paren {a \circ b}$

Since $\eqclass b {\RR_1} = \set b$, we have:

$a \circ b = b = \max \set {a, b}$

Similarly, we have:

$\paren {b \mathrel {\RR_1} b} \land \paren {a \mathrel {\RR_1} e}$

Since $\RR_1$ is a congruence relation for $\circ$, we have:

$\paren {b \circ a} \mathrel {\RR_1} \paren {b \circ e} = b$

Since $\eqclass b {\RR_1} = \set b$, we have:

$b \circ a = b = \max \set {a, b}$


Next we let $\RR_2$ be an equivalence relation on $\N$ with equivalence classes:

$\closedint 0 {b - 1}, \hointr b \infty$

By inspection, each of these equivalence classes are non-empty convex subsets of $\N$.

Hence $\RR_2$ is a congruence relation for $\circ$.

We have:

$\paren {e \mathrel {\RR_2} \paren {b - 1}} \land \paren {\paren {b - 1} \mathrel {\RR_2} \paren {b - 1}}$

Since $\RR_2$ is a congruence relation for $\circ$, we have:

$b - 1 = \paren {e \circ \paren {b - 1}} \mathrel {\RR_2} \paren {\paren {b - 1} \circ \paren {b - 1}}$

Since $\eqclass {b - 1} {\RR_2} = \closedint 0 {b - 1}$, we have:

$\paren {b - 1} \circ \paren {b - 1} \le \paren {b - 1}$

As the choice of $b - 1 \ge e$ is arbitrary, we can conclude:

$b \circ b \le b$

We also have:

$\paren {b \mathrel {\RR_2} b} \land \paren {b \mathrel {\RR_2} \paren {b + 1}}$

Since $\RR_2$ is a congruence relation for $\circ$, we have:

$\paren {b \circ b} \mathrel {\RR_2} \paren {b \circ \paren {b + 1}} = b + 1$

Since $\eqclass b {\RR_2} = \hointr b \infty$, we have:

$b \circ b \ge b$

Combining this with the previous result, we have:

$b \circ b = b$


By the Trichotomy Law, for any $m, n \in \N$ where $m, n \ge e$, we have one of the following:

$m > n \ge e$
$m = n \ge e$
$n > m \ge e$

and by the above, we have shown that in each case:

$m \circ n = \max \set {m, n}$


Now we will show that $e = 0$.

Aiming for a contradiction, suppose $e > 0$.

Let $\RR_3$ be an equivalence relation on $\N$ with equivalence classes:

$\set 0, \hointr 1 \infty$

By inspection, each of these equivalence classes are non-empty convex subsets of $\N$.

Hence $\RR_3$ is a congruence relation for $\circ$.

We have:

$\paren {0 \mathrel {\RR_3} 0} \land \paren {e \mathrel {\RR_3} b}$

Since $\RR_3$ is a congruence relation for $\circ$, we have:

$0 = \paren {0 \circ e} \mathrel {\RR_3} \paren {0 \circ b}$

Since $\eqclass 0 {\RR_3} = \set 0$, we have:

$0 = 0 \circ b$


Now note that:

$\paren {0 \mathrel {\RR_1} a} \land \paren {b \mathrel {\RR_1} b}$

Since $\RR_1$ is a congruence relation for $\circ$, we have:

$0 = \paren {0 \circ b} \mathrel {\RR_1} \paren {a \circ b} = b$

But $0 \not \mathrel {\RR_1} b$.

This is a contradiction.

Therefore we must have $e = 0$.

This implies that for any $m, n \in \N$, we must have $m, n \ge e$.

We have already shown that for any $m, n \ge e$, we have $m \circ n = \max \set {m, n}$.

Hence the result.

$\blacksquare$


Sources