note-math

二元关系 := 命题函数 $𝑝 : 𝐴 \times 𝐵 \to {0, 1}$ or $𝐴 \times 𝐵$ 的子集

$𝐴 \times 𝐵$ 时称为 $𝐴, 𝐵$ 独立无关

$𝑛$ 元关系类似

order_(tag)

命题函数 $< : 𝐴^{2} \to {0, 1}$ 是序 := $\forall 𝑎, 𝑏, 𝑐 \in 𝐴$

传递: $(𝑎 < 𝑏) \land (𝑏 < 𝑐) ⟹ 𝑎 < 𝑐$
无环: $\neg ((𝑎 < 𝑏) \land (𝑏 < 𝑎))$

也可以用等价的 $\leq$ 版本

Example

子集的包含 $\subset$ 或者包含且不等于 $⊊$ 是序

image modified from wiki media about partial order
$ℕ, ℤ, ℚ, ℝ$ 的 $<, \leq$
树图

order-comparable_(tag) $𝑎, 𝑎^{'} \in 𝐴$ comparable := $(𝑎 \leq 𝑎^{'}) \lor (𝑎^{'} \leq 𝑎)$

comparable-component_(tag) $𝐴_{𝑖} \subset 𝐴$ is comparable-component := $\forall 𝑎 \in 𝐴, (\exists 𝑎_{𝑖} \in 𝐴_{𝑖}, comparable (𝑎, 𝑎_{𝑖}) ⟹ 𝑎 \in 𝐴_{𝑖})$

偏序可以分解为相互不 comparable 的 comparable-component. 想象两个毫无关系的树图

linear-order_(tag) $𝐴$ 线序

$\forall 𝑎, 𝑎^{'} \in 𝐴, comparable (𝑎, 𝑎^{'})$

直观上, 线序没有分支, 也称为 "链"

maximal-linear-order_(tag) 极大线序链

let $𝐵 \subset 𝐴$ with $<$ 线序. $𝐵$ is maximal-linear-order := 以下定义等价

$\forall 𝑎 \in 𝐴, (\forall 𝑏 \in 𝐵, comparable (𝑎, 𝑏) ⟹ 𝑎 \in 𝐵)$
$\forall linear-order 𝐶 \subset 𝐴, (𝐵 \subset 𝐶 ⟹ 𝐵 = 𝐶)$

它并不能用于分解偏序. 两个极大线序链可以有相交的部分

maximal-linear-order-exists_(tag) maximal-linear-order chain alaways exists

related to #link(<axiom-of-choice>)[]?