形似 Peano 公理的一些公理族的例子

‍

1. 有限序列：在有限集上建立前趋与后继运算（S, +, -）

• 0 \in S, \omega \in S

  0 和 \omega 分别被称为序列的首和尾。

• \forall a \in S: a \ne 0^-, a \ne \omega^+

  首项没有前趋，末项没有后继。

• \forall a \in S: \begin{aligned}a \ne \omega \to \exists a_1 \in S: a_1 = a^+ \\ a \ne 0 \to \exists a_1 \in S: a_1 = a^- \end{aligned}

  每一项都存在前趋和后继，公理 II 特别规定的除外。

• \forall a, b, a_1, b_1 \in S: \begin{aligned}a\ne b\ne \omega, a_1=a^+, b_1=b^+\to a_1\ne b_1\\a\ne b\ne 0, a_1=a^-, b_1=b^-\to a_1\ne b_1\\\end{aligned}

  不同的元素有不同的后继和前趋。这里的连不等号的意思是各元素两两不等。

• \forall T\subset S : 0 \in T \land(\forall a \in S\setminus \{\omega\}: a \in T \to a^+\in T) \iff T=S

  数学归纳原理。

2. 并查集：只规定每个节点的父节点（S, *, ~）

• \forall a \in S: \exists! a_1 \in S: a_1 = a^*

  每个节点都有一个父节点。

• \exists o \in S, o^*=o

  存在根节点，它的父节点是它自己。

• \forall T \subset S: (\forall o \in S: o^*=o \to o \in T) \land (\forall a \in S: a^* \in T \to a \in T) \iff T=S

  各分支同时提携根节点时的归纳法。

• \begin{aligned}\forall a &\in S: a\sim a\\\forall a, b&\in S: a \sim b \iff b \sim a\\\forall a, b, c&\in S: a\sim b, b\sim c\implies a\sim c\end{aligned}

  并查集的元素存在一个等价关系，它表示两个元素属于同一个分支，是可达的。

• \forall o_1, o_2 \in S, o_1^* = o_1 \ne o_2 = o_2^*: \lnot (o_1\sim o_2)

  并查集元素不可达性的判断，即两个不同的根之间是不可达的。

• \forall a, b \in S: a \sim b \iff a^* \sim b^*

  可达的两个元素，各自父节点是可达的。

  因为这样不断迭代地取父下去，要么达到共同的根节点，根据自反性得到可达性，要么达到不同的根节点，那么必然不可达。

其实没考虑有环的问题。事实上因为归纳法的起点是一元环的根，所以更多元环因为没有根所以其实是被自动忽略的，因为没有归纳奠基。