Order terminology

From Maths
Jump to: navigation, search

This page is to provide a summary of partial orders, strict partial orders and associated terminology.

Stub grade: A*
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Useful page, could use fleshing out and having things link to it.
  • Demote once table finished, I really want least/minimal element, because these are different.


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]
TODO: I need a link to the proof that these are the same

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:
    1. Reflexive - [ilmath]\forall x\in X[x\preceq x][/ilmath][Note 1]
    2. Identitive / Antisymmetric - [ilmath]\forall x,y\in X[(x\preceq y\wedge y\preceq x)\implies x\eq y][/ilmath]
    3. 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:
    1. 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
    2. Transitive - [ilmath]\forall x,y,z\in X[(x\prec y\wedge y\prec z)\implies x\prec z][/ilmath]. As before.


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]
Caveat:Be careful with these, there can be more than one minimal element, it's weird
TODO: More on this later


  1. We write: [ilmath]a\preceq b[/ilmath] to mean [ilmath](a,b)\in\preceq[/ilmath] - as usual for relations
  2. Exactly as occurs with [ilmath]\le[/ilmath] and [ilmath]<[/ilmath]
  3. Literally, "not reflexive"