= Ordered Sets =

'''Ordered sets''' are [[Analysis/Sets|sets]] with an '''ordering'''.

<<TableOfContents>>

----



== Description ==

A [[Analysis/Sets|set]] does not inherently have an '''ordering'''. For some sets however, it is possible to specify one.

Consider the set of natural numbers. All members of the set can be ordered by the 'less than' binary operator (''<''). This is sometimes called the '''standard ordering''' for set of the natural numbers.

An ordering must satisfy two properties:
 * ''∀ x,y ∈ A'' either ''x=y'', ''x<y'', or ''y<x''
 * transitivity: if ''x<y'' and ''y<z'', then ''x<z''

As a counter-example, consider the [[Analysis/PowerSet|power set]] of natural numbers and an ordering by subsets (''⊆''). Transitivity is satisfied. But two valid members of this set are ''{1}'' and ''{2}'', and none of the following are true:
 * ''{1}⊆{2}''
 * ''{2}⊆{1}''
 * ''{1}={2}''

A common prototype is '''dictionary ordering'''. For example, the set of ''Q x Q'' (i.e., all pairs as Cartesian coordinates) can be ordered by dictionary ordering; ''(a,b) < (c,d)'' if
 * ''a < c'', or
 * ''a = c'' AND ''b < d''

----



== Bounds ==

Consider a subset ''A ⊆ S''.
 * If ''∃ b ∈ S'' such that ''∀ a ∈ A a ≤ b'', then ''A'' is '''bounded above''' by ''b'', and ''b'' is an '''upper bound''' for ''A''.
 * If instead ''∀ a ∈ A b ≤ a'', then ''A'' is '''bounded below''' by ''b'', and ''b'' is a '''lower bound''' for ''A''.

There are also concepts of '''least upper bound''' (or supremum) and '''greatest lower bound''' (or infimum).

A universe ''S'' is said to have a least upper bound property if every non-empty ''A ⊆ S'' has a least upper bound that is also a member of ''S''. Importantly, the set of rational numbers does not have this property.



----
CategoryRicottone