Discrete Cheatsheet
Set Theory
\(2^S>S\)：考虑 \(Y=\{x\notin f(x)\}\) 证明不存在满射.
\(2^S>2^T\to S>T\) 可以直接由 ZFC 公理推出，但反之不可证明/证伪. 主要是因为 \(2^{S}=2^{T}\) 时无法辨别 \(S\) 和 \(T\).
承认选择公理时，有：
- 任何集合存在良序（任何集合存在最小值）
- Dedekind 有限（与任意真子集不存在双射）等价于有限
- 无限集有 \(S\sim S\times S\)
连续统假设：\(|2^{N}|=|R|\).
Abstract Algebra
Group
对称群的定义：集合到自己的双射在函数复合运算下构成群.
轮换表示：\((a_1,\dots,a_n)\) 表示 \(\sigma(a_i)=a_{i+1}\) 的映射.
中心化子：\(C_G(S)=\{g|\forall s\in S,gs=sg\}\).
单群：没有非平凡正规子群
有限 Abel 单群同构于 \(Z_p\)，非 Abel 单群的最小例子是交替群 \(A_5\).
对于子群 \(H,K\)，有
\(|HK|=|KH|=\frac{|H||K|}{|K\cap H|}\).
证明考虑 \(K/(K\cap H)\to (HK)/(H)\) 的映射，证明其为双射即可.
若 \(H\) 为正规子群，则 \(HK=KH\) 且为子群.
实际上，\(HK=KH\) 和 \(HK\) 为子群等价.
有限生成 Abel 群的结构定理：有限生成 Abel 群同构于 \(Z_r\oplus Z/n_1Z\oplus Z/n_2Z \oplus \dots Z/n_kZ\).
\(End(G)=Hom(G,G)\)
\(Aut(G)=Iso(G,G)\)
\(Inn(G)=\{\phi_g:a\to gag^{-1}|g\in G\}\)
\(Inn(G)\) 为 \(Aut(G)\) 正规子群.
小结论/易错点整理
子群相关
- \(G/H\) 不一定是子群！\(HG\) 也不一定为子群！
- 正规子群的正规子群不一定是正规子群（取 \(D8\to D4\to D2\)）
- PID 的 \(R[X]\) 不一定是 PID（考虑 \(2,x\) 生成理想）
- 大小为一半的子群一定正规（\(gH\cap H=0\)，\(Hg\cap H=0\)，故 \(gH=Hg\)）
群同态相关
- \(h_1,h_2\in Im(\phi)\) 等价于 \(h_1h_2^{-1}\in Im(\phi)\).