From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Thu Apr 17 11:46:00 2008
Date:         Thu, 17 Apr 2008 11:44:45 -0400
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191: Partial Orderings--the rest of the story
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191: Partial Orderings--the rest of the story
------------------------------------------------------------------------

Because I would like to begin discussing graph theory on Friday, and
because I only had a very few things left that I wanted to say about
partial orderings, I'm going to say them here, and not continue
discussing them in lecture.

1.
First, a reminder (to make this more or less self-contained):

Def:
----
(a) A binary relation R on a set S _is a partial ordering of_ S
    =def
    R is reflexive ^ R is antisymmetric ^ R is transitive

(So a partial ordering differs from an equivalence relation only in
being antisymmetric rather than symmetric.)

(And part of the reason that it's called a "partial" ordering is that
there can be some elements of S that simply aren't ordered relative to
each other.)

(b) S _is a "poset"_
    =def
    there is a partial ordering R on S

2.
Examples include:
	less than or equals
	greater than or equals
	subset
	superset
	equals

(Note that the subsets of a given set (i.e., the given set's power set)
*can* be partially ordered by the "subset" relation, but there are subsets
s,t such that neither s is ordered w.r.t. t nor is t ordered w.r.t. s:
e.g., neither {1,2} or {3,4} stand in the partial order relation,
because neither is a subset of the other.) 

but *not*:
	less than
	greater than
	proper subset
	proper superset
	is older than

(each of which is not reflexive)

3.
The usual notation for a partial ordering is a symbol that looks like a
curly "less than or equals" sign, which I can't draw in this font.
So, in what follows, I'll just use the "<=" symbol for a generic partial
ordering relation.

4.
Now for the new stuff.  

Def:
----
Let (S, <=) be a poset.
Then:  S _is "totally ordered"_ (some people say:  "linearly ordered")
       =def
       (for all s,t \in S)[s<=t v t<=s]

i.e., a set is totally ordered if *any* two elements can be compared.

So, the set of subsets of a given set *is* partially ordered, but *not*
totally ordered.  The natural numbers and the integers, on the other
hand, are partially *and* totally ordered.

5.
Def:
----
Let (S, <=) be a *totally* ordered set
      (no one calls it a "toset", but they could :-).
      Then:  S _is "well ordered"_
             =def
             (for all T subset of S)[T is non-empty
                                     ->
                                     (there exists t \in T)
                                       (forall t' \in T)[t <= t']]

i.e., every non-empty subset of S is such that there is a member in it
that is smaller than any other member;

i.e., every non-empty subset of S has a smallest element.

So, the natural numbers *are* well-ordered
(because they are totally ordered
and because 0 is the smallest natural number)

But the integers are *not* well-ordered
(they are totally ordered, but there is no smallest integer).
		
6.
Finally, we have a major theorem, called 

The Well-Ordering Principle:
----------------------------

Let S be a well-ordered set (we could call it a "woset", but no one does).
Let P be a property of elements of S.

(e.g., maybe S is the set of natural numbers and P is "being even";
or maybe S is the set of letters of the alphabet and P is "being a vowel")

Then: (for all y \in S)
           [(for all x \ in S)[x <= y -> P(x)]
            -> P(y)]
      ->
      (for all s \in S)P(s)

Let's take that apart and look at it closely:
It's a conditional proposition, with an antecedent and a consequent.

	The consequent is easy:  
	  	It says that *every* element of S has property P

	The antecedent says something about *each* element in S:
	But what it says is also a conditional,
	with its own antecedent and its own consequent:

		Its consequent is easy:
			It says that the given y has P 

 		Its antecedent also says something about all elements of S:
			It's also a conditional!
			It says that if x <= y, then x has P

So, putting this all together, it says:
	
	Suppose that you choose any y in S.
	And suppose that any x-in-S-that-precedes-the-chosen-y has P
	And suppose that if that's the case, then y has P.
	Then everything in S has P.

Think of it this way:

	It says that a well-ordered set S--i.e., one that is totally
	ordered (so that any two elements can be compared in "size")
	and that has a smallest (think "first") element--has the
	following interesting property:

		To show that any member of S has property P,
		all you have to do is to choose some y in S
		and look at all the elements that precede y
		in the ordering.  

		Suppose further that if all of those elements 
		have P, then y will also have P (think dominoes).

		Then all of the elements will have P.

Sound familiar?  It should:  It's the Principle of Mathematical
Induction!  In fact, the Principle of Math Induction is logically
equivalent to the Well-Ordering Principle.