**Preorder, Poset, and totally ordered** – Definitions, examples, and their degeneration.
We all know about totally ordered sets. They are sets which can be put on a line, like a chain or a necklace, a string of pearls. These can be captured by four axioms like this:
1. **reflexivity:** x≤x
2. **transitivity:** x≤y and y≤z imply x≤z
3. **antisymmetry:** if x≤y and y≤x then x=y
4. **trichotomy:** for all x,y we either have x≤y or y≤x.
And the canonical example are the integers with the ordering relation ≤ as we know it. Now, a poset is a structure where 4 doesn't hold, and a preorder is one where neither 3 nor 4 hold. Then what do these axioms mean, what do they _do_?
*Axiom 4* makes sure that every pair of elements is related. It excludes parallel structures and this axiom is what causes the set to collapse to a string. When Axiom 4 doesn't hold we may get a directed acyclic graph (DAG) instead. Well, sort of, as a directed acyclic graph does not necessarily imply transitivity, a poset does. More on transitivity below.
Given a total order (like the integers with ≤) we can degenerate it by adding 'parallel structure' (e.g. an element ε which is just like 3 but not identical to it).
*Axiom 3* suppresses cycles. It says that the only cycles are indentity arrows.
Given a total order (like the integers with ≤) we can create a cycle by adding a backward relation like (5≤2). Note that if axiom 3 / antisymmetry does not hold, axiom 4 cannot hold either, as the 'and' is incompatible with the 'either-or'.
What does the transitivity *axiom 2* do? That's a funny one. It implies associativity, and says that if you find two arrows that can be combined because their ends match, you're allowed to talk about the combined arrow. It actually says that the combined arrow has to be among our collected arrows.
You can break this structure by taking out a combined arrow, e.g. insisting that 2 and 4 cannot be compared, even though 2≤3 and 3≤4. Strike out the corresponding arrow, mark it red, you don't have enough gas to drive two routes...
As I said earlier, a poset is usually drawn as a DAG without outlining each and every matching combination of arrows. That's because people (and algorithms) have no trouble to understand that once we find a connected path between two points that those points are also connected. So people will often draw a DAG when they actually want to talk about posets.