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<b } 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<x } { \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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s