Dipper Relation is Congruence for Multiplication

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $m \in \N$ be a natural number.

Let $n \in \N_{>0}$ be a non-zero natural number.


Let $\RR_{m, n}$ be the dipper relation on $\N$:

$\forall x, y \in \N: x \mathrel {\RR_{m, n} } y \iff \begin {cases} x = y \\ m \le x < y \text { and } n \divides \paren {y - x} \\ m \le y < x \text { and } n \divides \paren {x - y} \end {cases}$


Then $\RR_{m, n}$ is a congruence relation for multiplication.


Proof

From Dipper Relation is Equivalence Relation we have that $\RR_{m, n}$ is an equivalence relation.

From Equivalence Relation is Congruence iff Compatible with Operation, it is sufficient to show that:

$\forall x, y, z \in \N: x \mathrel {\RR_{m, n} } y \implies \paren {x z} \mathrel {\RR_{m, n} } \paren {y z}$

and:

$\forall x, y, z \in \N: x \mathrel {\RR_{m, n} } y \implies \paren {z x} \mathrel {\RR_{m, n} } \paren {z y}$

Furthermore, because Natural Number Addition is Commutative, it is sufficient to demonstrate the first of these only.


First let $x = y$.

We have that:

$x = y \implies x z = y z$

and so:

$\paren {x z} \mathrel {\RR_{m, n} } \paren {y z}$


Otherwise, we have that:

$x \ne y$ and $x, y \ge m$

Without loss of generality, let $x < y$.

If not, then as $\RR_{m, n}$ is symmetric we can rename $x$ and $y$ as necessary.


First note that if $z = 0$, then:

$\paren {x z} = \paren {y z}= 0$

and so:

$\paren {x z} \mathrel {\RR_{m, n} } \paren {y z}$


Otherwise we have that $z \ge 1$ and so both $x z \ge m$ and $y z \ge m$.


Then:

\(\ds x\) \(\RR_{m, n}\) \(\ds y\)
\(\ds \leadsto \ \ \) \(\ds n\) \(\divides\) \(\ds \paren {y - x}\) Definition of $\RR_{m, n}$
\(\ds \leadsto \ \ \) \(\ds \exists k \in \N_{>0}: \, \) \(\ds k n\) \(=\) \(\ds \paren {y - x}\) Definition of Divisor of Integer
\(\ds \leadsto \ \ \) \(\ds \exists k \in \N_{>0}: \, \) \(\ds k z n\) \(=\) \(\ds \paren {y z - x z}\) as $z \in \N_{>0}$
\(\ds \leadsto \ \ \) \(\ds n\) \(\divides\) \(\ds \paren {y z - x z}\) Definition of Divisor of Integer
\(\ds \paren {x z}\) \(\RR_{m, n}\) \(\ds \paren {y z}\) Definition of $\RR_{m, n}$

Hence the result.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Dipper_Relation_is_Congruence_for_Multiplication&oldid=568732"