# Ordered sets

Order: An order on a set is defined as a relation ${ \leq }$ that is reflexive, transitive and antisymmetric i.e

${ a\leq a }$.
${ a\leq b }$ and ${ b \leq c }$ ${ \Rightarrow }$ ${ a \leq c }$.
${ a \leq b}$ and ${ b \leq a }$ ${ \Rightarrow }$ ${ a = b }$.

A function ${ f(x)}$ is said to be order preserving if ${ a \leq b }$ ${ \Rightarrow }$ ${ f(a) \leq f(b) }$. A set ${ M }$ is said to be ordered or simply ordered if for every pair of elements ${ a }$ and ${ b }$ in M, ${ a \leq b}$ or ${ b \leq a }$. If this is not true for every pair, the set is said to be partially ordered. A mapping is said to be an order isomorphism if ${ f(a) \leq f(b) }$ ${ \Rightarrow }$ ${ a \leq b }$.

Two sets that are order isomorphic to each other are said to have the same order type. If a set is finite with ${ n }$ elements, it has order type ${ n }$. The order type of the set of natural numbers is ${ \omega }$. Hence, a set having order type ${ \omega }$ has power ${ \aleph_{0} }$. But a set having power ${ \aleph_{0} }$ need not have order type ${ \omega }$ since the set can be ordered in many ways (in fact, uncountably many ways) and hence can have uncountably many order types.

We say that ${ a if ${ a\leq b }$ and ${ a\neq b }$.

Well ordered set: A non empty set S is said to be well ordered if every non empty subset of S has a least element i.e. ${ Q\subset S }$ and ${ Q\neq \Phi }$ ${ \Rightarrow }$ ${\exists}$ a ${ \in }$ Q such that ${ a ${ \forall }$ ${ x\in Q }$.

eg: The set of natural numbers is well ordered. The intervals [0,1], (2,100) are not well ordered since not every subset has a least element.