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_0}|=N_1\).
Logic
Kripke Model：定义赋值函数 \(v:W\times Prop \to \{0,1\}\). 对于 \(w_1\le w_2\)，有 \(v(w_1,p)\le v(w_2,p)\). 其与直觉主义逻辑语义一致.
System K：\(\Gamma\to \Delta\)，指若 \(\Gamma\) 全部成立，则有 \(\Delta\) 至少一个成立.
Abstract Algebra
Group
对称群的定义：集合到自己的双射在函数复合运算下构成群.
轮换表示：\((a_1,\dots,a_n)\) 表示 \(\sigma(a_i)=a_{i+1}\) 的映射.
中心化子：\(C_G(S)=\{g|\forall s\in S,gs=sg\}\).
正规化子：\(N_G(S)=\{g|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\) 为子群等价.
指数：\([G:H]\)
有限生成 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)\) 正规子群.
忠实：\(\forall g\neq e\)，\(\exist x\)，\(gx\neq x\).
轨道：\(Gx=\{gx|g\in G\}\)
稳定子：\(Stab(x)=\{gx=x|g\in G\}\). \(G/Stab(x)\) 与 \(Gx\) 同构.
共轭作用的稳定子即中心化子 \(C(x)\).
共轭类方程：\(|G|=|C(G)|+\sum_{c_i} [G:C(c_i)]\).
\(p\) 群中心一定非平凡：由共轭类方程证明.
阶 \(p^2\) 的群要么为 \(Z_{p^2}\) 要么为 \(Z_p\times Z_p\)：考虑 \(|C(G)|\) 只能为 \(p^2\) 和 \(p\).
Sylow I：至少存在一个 Sylow-P 子群.
Sylow II：对于 Sylow-P 子群 \(P\) 和 p-子群 \(Q\)，存在 \(g\) 使得 \(Q\le gPg^{-1}\).
推论 II：Sylow-P 子群互相共轭，且若唯一则正规. 且 \(P\) 为 \(N_G(P)\) 的唯一 Sylow-P 子群.
Sylow III：\(n_p\) 为 Sylow-p 子群数量，则\(n_p=[G:N_p(P)]\)，\(n_p\equiv 1(\bmod p)\)，\(n_p|m\).
Ring
域，当且仅当交换环没有非平凡理想.
没有非平凡理想的普通环称为单环.
coprime：\(I+J=R\).
\(IJ\subseteq I\cap J\) 自动满足，而交换环上互素理想满足 \(IJ=I\cap J\).
素理想：若 \(ab\in I\) 则 \(a\in I\) 或 \(b\in I\). 交换环/素理想得到整区.
极大理想：\(I\subseteq J\subseteq R\) 的 \(J\) 满足 \(J=I\) 或 \(J=R\). 交换环/极大理想得到域. 充分必要.
主理想环种素理想=极大理想.
整区 \(R\to F\) 诱导 \(Frac(R)\to F\).
欧式整区（ED）：存在 \(R\to N\) 的映射 \(||\)，其中 \(|x|=0\) 且存在带余除法.
整区 + 素性条件（不可约=素）+ 不存在无限长因子链 = UFD
整区 -> UFD -> PID -> ED -> Field
小结论/易错点整理
- 存在左逆只能代表单射而不一定是满射.
子群相关
- \(G/H\) 不一定是子群！\(HG\) 也不一定为子群！
- 正规子群的正规子群不一定是正规子群（取 \(D8\to D4\to D2\)）
- PID 的 \(R[X]\) 不一定是 PID（考虑 \(2,x\) 生成理想）
- 大小为一半的子群一定正规（\(gH\cap H=0\)，\(Hg\cap H=0\)，故 \(gH=Hg\)）
- \(G_1\times G_2\) 的子群不一定是 \(H_1\times H_2\)（eg \(<(1,1)>\) in \(Z_2\times Z_2\)）
- 若 \(G/Z(G)\) 为循环群，则 \(G\) 为 Abel 群（考虑 \(\forall a,aZ(G)=p^kZ(G)\)，于是 \(a\in p^kZ(G)\)，然后直接验证）
- 正规子群 \(H\) 和 \(G/H\) 都是循环群，\(G\) 不一定是 Abel 群（\(H=A_3\)，\(G=S_3\)）
群同态相关
- \(h_1,h_2\in Im(\phi)\) 等价于 \(h_1h_2^{-1}\in Im(\phi)\).
- \(\ker \phi\) 不会是空集！正确的描述是 \(=\{1\}\).
环相关
- \(IJ\) 表示 \(IJ\) 生成的理想！其本身不一定为理想.
- 整环中，素元一定是不可约元，反之不一定对.
- 交换环中，极大理想一定是素理想，反之不一定对,
数论相关
- \(\gcd(a,p-1)=1\) 时，\(x\to x^a\) 为自同构，故 \(x^a=k\) 有唯一解.
\(x^2+1\)，\(x^2+x+2\)，\(x^2+2x+2\)，