Binary relation := Propositional function or a subset of
when it's called is independent
-ary relation is similar
[order]
Propositional function is an order :=
- Transitive:
- Acyclic:
Can also use the equivalent version
Example
-
Subset inclusion or inclusion and not equal to is an order
image modified from wiki media about partial order
- of
- Tree diagram
[order-comparable] comparable :=
[comparable-component] is comparable-component :=
Partial order can be decomposed into comparable-components that are not comparable to each other. Imagine two tree diagrams that have no relation
[linear-order] linear order
Intuitively, a linear order has no branches, also called a "chain"
[maximal-linear-order] Maximal linear order chain
let with linear order. is maximal-linear-order := the following definitions are equivalent
It cannot be used to decompose partial orders. Two maximal linear order chains can have intersecting parts
[maximal-linear-order-exists] maximal-linear-order chain alaways exists