第九课：归纳定义、数学归纳法、有序组、笛卡尔积、关系¶

Page 2-9 — 自然数的集合定义¶

皮亚诺公理刻画自然数：
P1: 至少有一个自然数，记作0
P2: 若n是自然数，则n恰有一个直接后继n'
P3: 0不是任何自然数的直接后继
P4: 若m'=n'则m=n
P5: 没有不满足上述条件的对象是自然数
集合论中定义自然数：
0 = ∅
1 = {∅} = {0}
2 = {∅,{∅}} = {0,1}
3 = {0,1,2}
后继运算：x' = x∪{x}
特点：0∈1∈2∈3…且0⊆1⊆2⊆3…
运算的归纳定义：
加法：x+0=x, x+y'=(x+y)'
乘法：x×0=0, x×y'=x×y+x
例：3+2 = (3+1)' = ((3+0)')' = (3')' = 4' = 5

Page 10-13 — 归纳原理与数学归纳法 ⭐¶

要证∀x(x∈A→P(x))，其中A是归纳定义集合： 1. 归纳基础：基础条款中的元素满足P 2. 归纳推理：假设已有元素x满足P(x)，证明操作生成的g(x)也满足P(g(x))
数学归纳法（自然数上的特例）： 1. 归纳基础：P(0)为真 2. 归纳推理：假设P(k)为真，推出P(k+1)也为真 3. 结论：对所有自然数n，P(n)为真

💡 人话：数学归纳法就像推倒多米诺骨牌——先推倒第一块（基础），再证明如果前一块倒了下一块也会倒（归纳），那么所有骨牌都会倒。

Page 11 — 证明例子¶

证明：命题公式中左括号数=右括号数 - 基础：命题变元p，L(p)=R(p)=0 - 归纳：设L(A)=R(A), L(B)=R(B) - L(¬A) = L(A)+1 = R(A)+1 = R(¬A) ✓ - L(A→B) = L(A)+L(B)+1 = R(A)+R(B)+1 = R(A→B) ✓

Page 15-16 — 有序组¶

有序对⟨a,b⟩：第一分量a，第二分量b
相等条件：⟨a,b⟩=⟨c,d⟩ ⟺ a=c且b=d（顺序重要！）
n元有序组⟨a₁,...,aₙ⟩：推广到n个分量

Page 17-18 — 笛卡尔积¶

笛卡尔积A×B = {⟨a,b⟩ | a∈A ∧ b∈B}
一般A×B≠B×A（顺序重要！）
可推广到n个集合：A₁×A₂×...×Aₙ
Aⁿ = A×A×...×A（n次）
若|A|=m, |B|=n，则|A×B|=m×n

Page 20-27 — 二元关系¶

二元关系R ⊆ A×B（A到B的二元关系）
前域dom(R) = {x | ∃y(⟨x,y⟩∈R)}
值域ran(R) = {y | ∃x(⟨x,y⟩∈R)}
A上的二元关系：R ⊆ A×A
关系矩阵Mʀ：m行n列的0-1矩阵
m=|A|，n=|B|
Mʀ[i][j]=1 ⟺ ⟨aᵢ,bⱼ⟩∈R
关系图：结点=元素，有向边=关系对

Page 30-37 — 关系的运算¶

补关系R̄ = (A×B)−R
逆关系R⁻¹ = {⟨y,x⟩ | ⟨x,y⟩∈R}
(R⁻¹)⁻¹ = R
(A×B)⁻¹ = B×A
∅⁻¹ = ∅
合成关系R∘S = {⟨x,z⟩ | ∃y(xRy ∧ ySz)}
R⊆A×B，S⊆B×C
合成对应矩阵乘法：∧代乘，∨代加

💡 人话：关系的合成就是"两步并一步"。比如"叔侄关系" = 兄弟关系 ∘ 父子关系。

Page 42-46 — 关系合成与幂运算¶

合成性质：
R∘(S∪T) = (R∘S)∪(R∘T)（左分配律）
R∘(S∩T) ⊆ (R∘S)∩(R∘T)（⚠单向）
(R∘S)∘T = R∘(S∘T)（结合律）
(R∘S)⁻¹ = S⁻¹∘R⁻¹
幂运算：Rⁿ = R∘...∘R（n次合成），R⁰ = Eₐ
Rᵐ∘Rⁿ = R^(m+n)
(Rᵐ)ⁿ = R^(mn)
⭐幂关系有限定理：设|A|=n，R是A上二元关系
则存在0≤i<j≤2^(n²)，使得Rⁱ=Rʲ
证明：A上的二元关系总数是2^(n²)，由鸽笼原理，0~2^(n²)之间有2^(n²)+1个幂关系，必有重复

Page 47-49 — 函数¶

函数f:X→Y是特殊的二元关系f⊆X×Y
两个条件： 1. 前域和定义域重合：dom(f)=X 2. 单值性：⟨x,y⟩∈f且⟨x,y'⟩∈f ⇒ y=y'
函数也称作映射或变换
不是所有关系都是函数——例：整除关系2|4且2|8，不满足单值性