Order terminology

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.

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]

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]
  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]), this is again a binary relation, where [ilmath]\prec[/ilmath] must be:
  1. Irreflexive - [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.

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]

Caveat:Be careful with these, there can be more than one minimal element, it's weird

TODO: More on this later