二元关系学习总结

preorder（预序）: reflexive, transitive

partial order（偏序，对应图论的有向无环图）: preorder + anti-symmetric
total preorder（完全预序）: preorder + total
equivalence（等价）: preorder + symmetric

complete（全互连，对应图论的完全连通图）: total preorder + symmetric or equivalence + total
equality（相等）: equivalence + anti-symmetric or partial order + symmetic
total order（全序）: partial order + total or total preorder + anti-symmetric

注意，上述关系中的后三个关系所用到的某些属性已经不是独立的了，例如相等关系用自反性、对称性、反对称性就可以导出传递性（因为对称性和反对称性限制了关系只能发生在每个元素自身上，自反性则保证了每个元素自身都满足这个关系。结果没有可能发生传递，因此传递性自然被满足。）

上面的提到的各种关系R所用到的各种属性：
reflexive（自反性）: for all x in X it holds that xRx
transitive（传递性）: for all x, y and z in X it holds that if xRy and yRz then xRz.
symmetric（对称性）: for all x and y in X it holds that if xRy then yRx
anti-symmetric（反对称性）: for all x and y in X it holds that if xRy and yRx then x = y
total（完全性）: for all x and y in X it holds that xRy or yRx (or both)

二元关系的其它一些常见属性：
irreflexive（非自反性）: for all x in X it holds that not xRx
coreflexive（伴自反性）: for all x and y in X it holds that if xRy then x = y
asymmetric（非对称性）: for all x and y in X it holds that if xRy then not yRx

-     PR
-    /|\
-   / | \
-  /  |  \
- /   |   \
- PA  TP  EV
- |\  /\  /|
- | \/  \/ |
- | /\  /\ |
- |/  \/  \|
- TO  EQ  CP

PR: preorder
PA: partial order
TP: total preorder
EV: equivalence
TO: total order
EQ: equality
CP: complete connection

/: anti-symmetric
|: total
\: symmetric

一个重要的未讨论过的关系：

well order（良序）: total order + well-founded

well-founded（良基关系）：every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s≠m of S, the pair (s,m) is not in R.

If a set is totally ordered, then the following are equivalent:
1. The set is well-ordered. That is, every nonempty subset has a least element.
2. Transfinite induction works for the entire ordered set.
3. Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice).


其它关系：
* Dependency relation, a symmetric, reflexive relation.
* Independency relation, a symmetric, irreflexive relation.
这两种关系是互补的。