Difference between revisions of "Order terminology"
(Created page with "This page is to provide a summary of partial orders, strict partial orders and associated terminology. {{Stub page|grade=A*|msg=Useful page, could use fleshing out and...") |
m |
||
| Line 29: | Line 29: | ||
==Terms== | ==Terms== | ||
===Minimum/Maximum dual terms=== | ===Minimum/Maximum dual terms=== | ||
| + | Let {{M|(X,\preceq)}} be a [[poset]] and let {{M|Y\in\mathcal{P}(X)}} be an arbitrary subset. Then {{M|y\in Y}} is a... | ||
{| class="wikitable" border="1" | {| class="wikitable" border="1" | ||
|- | |- | ||
! Lower form | ! Lower form | ||
| − | |||
! Lower definition | ! Lower definition | ||
| + | ! Upper form | ||
! Upper definition | ! Upper definition | ||
! Comments | ! Comments | ||
| + | |- | ||
| + | ! Minimal element | ||
| + | | {{M|\forall x\in Y[x\preceq y\implies y\eq x]}} | ||
| + | ! Maximal element | ||
| + | | {{M|\forall x\in Y[x\succeq y\implies y\eq x]}} | ||
| + | | | ||
|- | |- | ||
! Least element | ! Least element | ||
| + | | {{M|\forall x\in Y[y\preceq x]}} | ||
! Greatest element | ! Greatest element | ||
| − | | {{M| | + | | {{M|\forall x\in Y[y\succeq x]}} |
| + | | | ||
|} | |} | ||
| + | {{Caveat|Be careful with these, there can be more than one minimal element, it's weird}} {{XXX|More on this later}} | ||
==Notes== | ==Notes== | ||
<references group="Note"/> | <references group="Note"/> | ||
Latest revision as of 18:45, 8 January 2017
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"
