同余关系学习

定义

设$A=⟨S,{\ast }_1,{\ast }_2,\cdots ,{\ast }_n⟩$为代数系统，$R$为$S$上的等价关系
（1）对于运算${\ast }_i$，若$\forall a_1,b_1,a_2,b_2,\cdots ,a_{n_i},b_{n_i}\in S$($n_i$为运算${\ast }_i$的阶)，由$a_{k}R{b}_k,k=1,2,\cdots ,n_i$可得${\ast }_i\left(a_1,a_2,\cdots ,a_{n_i}\right)R{\ast }_i\left(b_1,b_2,\cdots ,b_{n_i}\right)$，则称$R$关于${\ast }_i$具有置换性质
（2）若$R$关于运算${\ast }_1,{\ast }_2,\cdots ,{\ast }_n$都具有置换性质，则称$R$为$A$上的同余关系

定理

设$h$是从$A=⟨S,{\ast }_1,{\ast }_2,\cdots ,{\ast }_n⟩$到$A^{\prime }=⟨S{,}^{\prime }{\ast }_1^{\prime },{\ast }_2^{\prime },\cdots ,{\ast }_n^{\prime }⟩$的同态映射，由$h$诱导的$S$上的二元关系$R_h$定义为
$$\forall x,y\in S,x{R}_{h}y\iff h(x)=h(y)$$
则$R_h$是$A$上的同余关系

证明：
（1）易证$R_h$是$S$上的等价关系
（2）$\forall i\in \mathbb{N}\left(1\le i\le n\right)$
$\forall a_1,b_1,a_2,b_2,\cdots ,a_{n_i},b_{n_i}\in S$,若$a_k{R}_h{b}_k,k=1,2,\cdots ,n_i$，则$h\left(a_k\right)=h\left(b_k\right),k=1,2,\cdots ,n_i$
于是
$$\begin{array}{rl}h\left({\ast }_i\left(a_1,a_2,\cdots ,a_{n_i}\right)\right)& ={\ast }_i^{\prime }\left(h\left(a_1\right),h\left(a_2\right),\cdots ,h\left(a_{n_i}\right)\right)\\ & ={\ast }_i^{\prime }\left(h\left(b_1\right),h\left(b_2\right),\cdots ,h\left(b_{n_i}\right)\right)\\ & ={\ast }_i^{\prime }\left({\ast }_i\left(b_1,b_2,\cdots ,b_{n_i}\right)\right)\end{array}$$
所以${\ast }_i\left(a_1,a_2,\cdots ,a_{n_i}\right)R_h{\ast }_i\left(b_1,b_2,\cdots ,b_{n_i}\right)$
故$R_h$是$A$上的同余关系

课后习题

1.下列关系$R$是否为$⟨\mathbb{I},+⟩$上的同余关系？
（1）$iRj$当且仅当$i\cdot j\ge 0$
（2）$iRj$当且仅当$i\le 0\wedge j\le 0\vee i>0\wedge j>0$
（3）$iRj$当且仅当$\left|i-j\right|\le 4$
（4）$iRj$当且仅当$i\ge j$

证明：
（1）$1R2,\left(-2\right)R\left(-1\right)$
而$\left(1+\left(-2\right)\right)/R\left(2+\left(-1\right)\right)$
因此不是置换关系，更不是同余关系
（2）$1R2,\left(-2\right)R\left(-1\right)$
而$\left(1+\left(-2\right)\right)/R\left(2+\left(-1\right)\right)$
因此不是置换关系，更不是同余关系
（3）$1R5,5R6,1/R6$
因此$R$不是等价关系，更不是同余关系
（4）$2R1,1/R2$
因此$R$不是等价关系，更不是同余关系

2.设$m,n\in {\mathbb{I}}_{+}$.$\mathbb{I}$上的一元关系$\ast$定义为:$\forall i\in \mathbb{I},\ast \left(i\right)=i^n$
试证明：${\equiv }_m$是代数系统$⟨\mathbb{I},\ast ⟩$上的同余关系

证明：容易证明${\equiv }_m$是等价关系
设$a,b\in \mathbb{I}$，$a{\equiv }_{m}b$
$$\begin{array}{rl}\ast \left(a\right)-\ast \left(b\right)& =a^n-b^n\\ & =\left(a-b\right)\left(a^{n-1}+a^{n-2}b+\cdots +b^{n-1}\right)\\ \Rightarrow \ast \left(a\right){\equiv }_m\ast \left(b\right)& \end{array}$$

3.$\mathbb{I}$上的二元关系$R$定义为$\forall i,j\in \mathbb{I}$，$iRj$当且仅当$\left|i\right|=\left|j\right|$。
$R$是$⟨\mathbb{I},+⟩$上的同余关系吗？$R$是$⟨\mathbb{I},\cdot ⟩$上的同余关系吗？

解：
$R$不是$⟨\mathbb{I},+⟩$上的同余关系
$1R\left(-1\right),\left(-2\right)R2$
但是$\left(1+\left(-2\right)\right)/R\left(-1+2\right)$
因此不是

$R$是$⟨\mathbb{I},\cdot ⟩$上的同余关系
$\forall a,b,c,d\in \mathbb{I},aRb,cRd$
$$\left|ac\right|=\left|bd\right|\Rightarrow \left(a\cdot c\right)R\left(b\cdot d\right)$$

5.试证明：同一代数上的同余关系的交仍为同余关系。并举例说明他们的合成不一定的是同余关系

证明：
设代数系统$⟨A,{\ast }_1,{\ast }_2,\cdots ,{\ast }_m⟩$,
${\ast }_i$的阶为$n_i$
$R_1,R_2$为$⟨A,{\ast }_1,{\ast }_2,\cdots ,{\ast }_m⟩$上的同余关系

设$a_1,a_2,\cdots ,a_{n_i},b_1,b_2,\cdots ,b_{n_i}\in A,a_i\left(R_1\cap R_2\right)b_i$
因此$a_i{R}_1{b}_i,a_i{R}_2{b}_i$
进而$\ast \left(a_1,a_2,\cdots ,a_n\right)R_1\ast \left(b_1,b_2,\cdots ,b_n\right)$
$\ast \left(a_1,a_2,\cdots ,a_n\right)R_2\ast \left(b_1,b_2,\cdots ,b_n\right)$
因此$\ast \left(a_1,a_2,\cdots ,a_n\right)\left(R_1\cap R_2\right)\ast \left(b_1,b_2,\cdots ,b_n\right)$
$R_1\cap R_2$为$⟨A,{\ast }_1,{\ast }_2,\cdots ,{\ast }_m⟩$上的同余关系

考虑 A = { 0 , 1 , 2 } , S = < A , 1 A > A=\left\{0,1,2\right\},S=\left A={0,1,2},S=⟨A,1A​⟩
$$M_{R_1}=\left(\begin{array}{ccc}1& 1& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}\right)M_{R_2}=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 1\\ 0& 1& 1\end{array}\right)$$
容易验证$R_1,R_2$是等价关系
合成之后
$$M_{R_1\circ R_2}=\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 0& 1& 1\end{array}\right)$$
不满足对称性，因此$R_1\circ R_2$不是等价关系，进而不是同余关系

6.设$S=⟨A,\ast ⟩$为代数系统，其中$\ast$为一元运算，$R$为$A$上的等价关系。举例说明$R$不一定是$S$上的同余关系

解：
设 A = { a , b , c } A=\left\{a,b,c\right\} A={a,b,c}
$\ast \left(a\right)=c,\ast \left(b\right)=b,\ast \left(c\right)=c$
因此$S=⟨A,\ast ⟩$为代数系统
等价关系
$$M_R=\left(\begin{array}{ccc}1& 1& 0\\ 1& 1& 0\\ 0& 0& 1\end{array}\right)$$
容易验证$R$是等价关系
$$aRb,\ast \left(a\right)/R\ast \left(b\right)$$
因此$R$不是$S$上的同余关系

参考：
离散数学（刘玉珍）