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 $(X,\preceq)$ is a poset, a set with a partial order, then we get a strict partial order, $\prec$ defined as follows:

• $x\prec y\iff(x\preceq y\wedge x\neq y)$

And of course, given a strict partial order (or sposet, $(X,\prec)$), $\prec$, we can obtain a partial order, denoted $\preceq$ as follows:

• $x\preceq y\iff(x\prec y\vee x\eq y)$

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 $\{1,2,3\}$ that in no way is:

• $\{1,2\}$ a subset, or superset of $\{2,3\}$.

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, $(X,\preceq)$, is a binary relation that is:
  1. Reflexive - $\forall x\in X[x\preceq x]$
  2. Identitive / Antisymmetric - $\forall x,y\in X[(x\preceq y\wedge y\preceq x)\implies x\eq y]$
  3. Transitive - $\forall x,y,z\in X[(x\preceq y\wedge y\preceq z)\implies x\preceq y]$
• A strict partial ordering, or sposet, $(X,\prec)$ (notice it is $\prec$ not $\preceq$), this is again a binary relation, where $\prec$ must be:
  1. Irreflexive - $\forall x\in X[\neg(x\prec x)]$, perhaps better written as: $\forall x\in X[(x,x)\notin\prec]$ or $\forall x\in X[x\not\prec x]$; and
  2. Transitive - $\forall x,y,z\in X[(x\prec y\wedge y\prec z)\implies x\prec z]$. As before.

Terms

Minimum/Maximum dual terms

Let $(X,\preceq)$ be a poset and let $Y\in\mathcal{P}(X)$ be an arbitrary subset. Then $y\in Y$ is a...

Lower form	Lower definition	Upper form	Upper definition	Comments
Minimal element	$\forall x\in Y[x\preceq y\implies y\eq x]$	Maximal element	$\forall x\in Y[x\succeq y\implies y\eq x]$
Least element	$\forall x\in Y[y\preceq x]$	Greatest element	$\forall x\in Y[y\succeq x]$

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

TODO: More on this later