Subset Product/Examples/Congruence Modulo Initial Segment of Natural Numbers
Jump to navigation
Jump to search
Example of Subset Product
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let $\N_{<m}$ denote the initial segment of the natural numbers $\N$:
- $\N_{<m} = \set {0, 1, \ldots, m - 1}$
Let $\RR_m$ denote the equivalence relation:
- $\forall x, y \in \Z: x \mathrel {\RR_m} y \iff \exists k \in \Z: x = y + k m$
For each $a \in \N_{<m}$, let $\eqclass a m$ be the equivalence class of $a \in \N_{<m}$ under $\RR_m$:
- $\eqclass a m := \set {a + z m: z \in \Z}$
Let $\Z_m$ be the set defined as:
- $\Z_m := \set {\eqclass a m: a \in \N_{<m} }$
Let $+_\PP$ denote the operation induced on $\powerset \Z$ by integer addition.
Then the algebraic structure $\struct {\Z_m, +_\PP}$ is closed in the sense:
- $\forall \eqclass a m, \eqclass b m \in \Z_m: \eqclass a m +_\PP \eqclass b m \in \Z_m$
Proof
From Equivalence Class Example: Congruence Modulo $\N_{<m}$:
- $\RR_m$ is an equivalence relation
- $\eqclass a m$ is the equivalence class of $a \in \N_{<m}$ under $\RR_m$.
Let $\eqclass a m, \eqclass b m \in \RR_m$ be arbitrary.
Then we have:
\(\ds \eqclass a m +_\PP \eqclass b m\) | \(=\) | \(\ds \set {a + z_1 m + b + z_2 m: z_1, z_2 \in \Z}\) | Definition of $\eqclass a m$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \set {a + b + \paren {z_1 + z_2} m: z_1, z_2 \in \Z}\) | rearranging | |||||||||||
\(\ds \) | \(=\) | \(\ds \set {a + b + z m: z \in \Z}\) | where $z = z_1 + z_2 \in \Z$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \eqclass {a + b} m\) | Definition of $\eqclass {a + b} m$ |
It also follows that:
- $\forall a, b \in \N_{<m}: \eqclass a m = \eqclass b m \iff a = b$
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {II}$: New Structures from Old: $\S 9$: Compositions Induced on the Set of All Subsets