## 二元关系学习总结

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

(total order, AKA linear order, simple order, or (non-strict) ordering)

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

 1234567891011 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.