Order terminology
This page is to provide a summary of partial orders, strict partial orders and associated terminology.
- Demote once table finished, I really want least/minimal element, because these are different.
Orders
Just as with functions we may speak of partial/total terminology. A partial function for which every two elements are comparable, is a total order (sometimes called linear). Just as a total function is a partial function that maps everything to something, a total order compares everything.
An order relation can be given in one of two forms, a strict form or a "normal" (non-strict) form, these contain exactly the same information.
If [ilmath](X,\preceq)[/ilmath] is a poset, a set with a partial order, then we get a strict partial order, [ilmath]\prec[/ilmath] defined as follows:
- [ilmath]x\prec y\iff(x\preceq y\wedge x\neq y)[/ilmath]
And of course, given a strict partial order (or sposet, [ilmath](X,\prec)[/ilmath]), [ilmath]\prec[/ilmath], we can obtain a partial order, denoted [ilmath]\preceq[/ilmath] as follows:
- [ilmath]x\preceq y\iff(x\prec y\vee x\eq y)[/ilmath]
Partial orders
When thinking of orders the first example you should think of is the subset relation. As this is a "true" partial order (it is not a total order provided you are looking at sets in the power set of a set with more than one element). Notice that for subsets of [ilmath]\{1,2,3\} [/ilmath] that in no way is:
- [ilmath]\{1,2\} [/ilmath] a subset, or superset of [ilmath]\{2,3\} [/ilmath].
A total order (like a total function) means any two elements are comparable, then the more usual examples of the natural numbers and co come in handy.
These definitions follow:
- A partial ordering, or poset, [ilmath](X,\preceq)[/ilmath], is a binary relation that is:
- Reflexive - [ilmath]\forall x\in X[x\preceq x][/ilmath]^{[Note 1]}
- Identitive / Antisymmetric - [ilmath]\forall x,y\in X[(x\preceq y\wedge y\preceq x)\implies x\eq y][/ilmath]
- Transitive - [ilmath]\forall x,y,z\in X[(x\preceq y\wedge y\preceq z)\implies x\preceq y][/ilmath]
- A strict partial ordering, or sposet, [ilmath](X,\prec)[/ilmath] (notice it is [ilmath]\prec[/ilmath] not [ilmath]\preceq[/ilmath]^{[Note 2]}), this is again a binary relation, where [ilmath]\prec[/ilmath] must be:
- Irreflexive^{[Note 3]} - [ilmath]\forall x\in X[\neg(x\prec x)][/ilmath], perhaps better written as: [ilmath]\forall x\in X[(x,x)\notin\prec][/ilmath] or [ilmath]\forall x\in X[x\not\prec x][/ilmath]; and
- Transitive - [ilmath]\forall x,y,z\in X[(x\prec y\wedge y\prec z)\implies x\prec z][/ilmath]. As before.
Terms
Minimum/Maximum dual terms
Let [ilmath](X,\preceq)[/ilmath] be a poset and let [ilmath]Y\in\mathcal{P}(X)[/ilmath] be an arbitrary subset. Then [ilmath]y\in Y[/ilmath] is a...
Lower form | Lower definition | Upper form | Upper definition | Comments |
---|---|---|---|---|
Minimal element | [ilmath]\forall x\in Y[x\preceq y\implies y\eq x][/ilmath] | Maximal element | [ilmath]\forall x\in Y[x\succeq y\implies y\eq x][/ilmath] | |
Least element | [ilmath]\forall x\in Y[y\preceq x][/ilmath] | Greatest element | [ilmath]\forall x\in Y[y\succeq x][/ilmath] |
Notes
- ↑ We write: [ilmath]a\preceq b[/ilmath] to mean [ilmath](a,b)\in\preceq[/ilmath] - as usual for relations
- ↑ Exactly as occurs with [ilmath]\le[/ilmath] and [ilmath]<[/ilmath]
- ↑ Literally, "not reflexive"