partial order on V: relation R of type V × V. satisfies reflexivity, anti-symmetry, transitivity
example: relation ≤ is partial order on N
example: the relation ⊆ is partial order on P(V)
partial order R on set V, then:
e.g. relation ≤ on N: for all n,m in N — n ≤ m or m ≤ n — total
e.g. relation ⊆ on P({1,2}): {1} is not a subset of {2}, {2} is not a subset of {1} — not total
if partial order R on set V, then strict partial order S corresponding to R is defined by
x S y ⟷ x R y and x ≠ y
a strict partial order is irreflexive, anti-symmetric, transitive
apparently a partial ordering relation is complicated as fuck:
so get rid of some arrows and make a Hasse diagram — omit reflexivity and transitivity
the arrows create chains that split and merge, elements in the same chain are comparable
Algorithm:
example:
<a1, b1> ≤ <a2, b2> ⟷ a1 ≤A a2 and b1 ≤B b2
ordered by points, if both are smaller
cartesian order on A × B is a partial order
<a1, b1> ≤ <a2, b2> ⟷ (a1 <A a2) ∨ (a1 = a2 ∧ b1 ≤B b2)
like in a dictionary
lexicographic order on A× B is a partial order, total if ≤A on A and ≤B on B are total
(V, ≤) is a partially ordered set, A ⊆ V, m ∈ A
m is:
Every maximum of A is a maximal element of A. If A has a maximum, it is the only maximal element.