离散数学

证明Lagrange定理

设H是有限群G的子群，则H的阶整除G的阶

陪集：设\(<H,\ *>\)为\(<G,\ *>\)的子群，对任一\(a\in G\)，定义\(AH=A*H=\{a*H\ |\ h\in H\}\)为元素\(a\)关于\(H\)的左陪集（同理可定义右陪集）

证明思路为先证明三个与陪集相关的前置定理，然后导出拉格朗日定理

定理1(不等则不交)

设\(<H,\ *>\)为\(<G,\ *>\)的子群， \(aH\)和\(bH\)是任意两个左陪集，则或者\(aH=bH\)，或者\(aH\cap bH=\emptyset\)

证明

假设\(aH\neq bH=\emptyset\)，(试证\(aH=bH\))

\(aH\cap bH\neq \emptyset\)，则必存在公共元素\(f\)，\(f\in aH\cap bH\)

则\(\exists h_1,\ h_2 \in H，f=a*h_1=b*h_2\),

\(\therefore a=b*h_2*h_1^{-1}\)

下证\(aH\subseteq bH\):

\(\forall x\in aH,\ \exists h_3\in H,\ x=a*h_3\)

\(\therefore x=b*h_2*h_1^{-1}*h_3\) (带入\(a\))

由H中运算封闭知: \(h_2 * h_1^{-1}*h_3 \in H\)

\(\therefore x\in bH\)

同理可证\(bH \subseteq aH\)

因此\(aH=bH\)

定理2(同阶)

设\(<H,\ *>\)为\(<G,\ *>\)的子群，则H的任意左陪集的大小(基数)是相同的，即\(\forall a,b \in G,\ |aH|=|bH|=|H|\)

证明

设\(H={h_1,h_2,...,h_m}\)，则\(aH={a*h_1，a*h_2,...,a*h_m}\)

定义\(f:H\rightarrow aH，\forall h\in H，f(h)=a*h\)，则\(f\)为单射

\(\because \forall h_1,h_2\in H\)，若\(h_1 \neq h_2\) ，则\(ah_1 \neq ah_2\) (由消去律)

而\(f\)显然为满射， \(\therefore f\)为双射

\(\therefore |aH|=|H|\)

定理3(划分)

设\(<H,\ *>\)为\(<G,\ *>\)的子群，则\(H\)的所有左陪集构成\(G\)的一个划分

证明

1. 先证\(H\)的所有左陪集的并集为\(G\)，即\(\forall a\in G\)有\(\underset{a\in G}{\cup}aH=G\)

   由于\(H \subseteq G\)，且\(G\)对\(*\)封闭，所以\(\underset{a\in G}{\cup}aH\subseteq G\)

   下证\(\underset{a\in G}{\cup}aH\supseteq G\):

   由\(H \supseteq \{e\}，aH \supseteq \{a*e\}=\{a\}\)

   可得\(\underset{a\in G}{\cup}aH\supseteq \underset{a\in G}{\cup}\{a\}=G\)

2. 由定理1可知，\(G\)中两个元素的陪集要么相等，要么不交

由1和2可得\(H\)的所有左陪集构成\(G\)的一个划分

定理4(Lagrange)

设\(<H,\ *>\)为\(<G,\ *>\)的子群，且\(|G|=n，|H|=m\)，则\(m/n\)

设\(H\)的不同左陪集有\(k\)个，那么\(n=|G|=k|H|=km\)

证毕。