Well-Defined Relation/Examples/Less Than on Congruence Modulo 6

From ProofWiki
Jump to navigation Jump to search

Example of Well-Defined Relation

Let $x \mathrel {C_6} y$ be the equivalence relation defined on the natural numbers as congruence modulo $6$:

$x \mathrel {C_6} y \iff x \equiv y \pmod 6$

defined as:

$\forall x, y \in \N: x \equiv y \pmod 6 \iff \exists k, l, m \in \N, m < 6: 6 k + m = x \text { and } 6 l + m = y$

Let $\eqclass x {C_6}$ denote the equivalence class of $x$ under $C_6$.

Let $\N / {C_6}$ denote the quotient set of $\N$ by $C_6$.


Let us define the relation $L$ on $\N / {C_6}$ as follows:

$\tuple {\eqclass x {C_6}, \eqclass y {C_6} } \in L \iff \exists k, l, m, n \in \N, m < n < 6: x = 6 k + m, y = 6 l + n$


Then $L$ is a well-defined relation.


Proof

Let:

$x \mathrel {C_6} x'$
$y \mathrel {C_6} y'$

for arbitrary $x, y, x', y' \in \N$.

We need to demonstrate that:

$\tuple {\eqclass x {C_6}, \eqclass y {C_6} } \in L \iff \tuple {\eqclass {x'} {C_6}, \eqclass {y'} {C_6} } \in L$


So:

\(\ds \tuple {\eqclass x {C_6}, \eqclass y {C_6} }\) \(\in\) \(\ds L\)
\(\ds \leadstoandfrom \ \ \) \(\ds \exists k, l, m, n \in \N: \, \) \(\ds x\) \(=\) \(\ds 6 k + m\) Definition of $L$
\(\, \ds \land \, \) \(\ds y\) \(=\) \(\ds 6 l + n\) ... such that $m < n < 6$
\(\ds \leadstoandfrom \ \ \) \(\ds \exists k', l' \in \N: \, \) \(\ds x'\) \(=\) \(\ds 6 k' + m\) Definition of $C_6$
\(\, \ds \land \, \) \(\ds y\) \(=\) \(\ds 6 l' + n\)
\(\ds \leadstoandfrom \ \ \) \(\ds \exists k', l', m, n \in \N: \, \) \(\ds x'\) \(=\) \(\ds 6 k' + m\) ... such that $m < n < 6$
\(\, \ds \land \, \) \(\ds y'\) \(=\) \(\ds 6 l' + n\) ... gathering up from above
\(\ds \leadstoandfrom \ \ \) \(\ds \tuple {\eqclass {x'} {C_6}, \eqclass {y'} {C_6} }\) \(\in\) \(\ds L\)

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Well-Defined_Relation/Examples/Less_Than_on_Congruence_Modulo_6&oldid=517664"