WEEK 6

M: Midterm  
W: Proof of Proposition I.2.6(b). Theory towards the proving that \in is a linear ordering
on \omega.
   I.2.7. Proposition. The relation \in is irreflexive on \omega 
            Corollary. \in is a strict partial ordering on \omega
            Definition. A strict partial ordering R is linear on A if and only if for all
                               elements x,y from A we have: 
                                    x R y    or    x = y     or    y R x.
   I.2 8. Proposition. \in is a strict linear ordering on \omega  (The proof will come later.)
   I.2.9. Lemma. For every x,y from \omega we have the following:
                           If S x \in y then either S(x)\in y or S(x) = y
PROBLEMS FOR DISCUSSIONS:    
   1. Show that for every x from \omega we have: either O \in x or else O = x; here O is
       the empty set.  
   2. Assume A is a nonempty subset of \omega such that the union of A is equal to A. Show
       that A = \omega. (Hint: Show that A is inductive. Apply the fact that every element 
       of \omega is a transitive set.)
   3. Let B = {O, S(O)} where O is the empty set.  (Thus, taking into account our
       representation of natural numbers, B = {0,1}.) Notice that  B = S(S(O)).  By
       Exercise 2(c) from W, Week 5, the power set of B (briefly P(B)) is transitive.
       However, P(B) contains sets that are not transitive -- try to find some.
F: Completion of the proof of Proposition I.2.9. Proof of Proposition I.2.8. Well-orderings.
    I.2.10. Definition. A strict linear ordering R on a set A is a well-ordering if and only
               if every nonempty subset of A has an R-least element. (An R-least element of
               B is an element a \in B such that a R b whenever b is in B and is distict from a.)
    I.2.11. Proposition. The relation \in is a well-ordering on \omega.
PROBLEMS FOR DISCUSSIONS:
   1. Show that the definition of a well-ordering makes also sense for for linear orderings 
       that are not strict; try to understand where the difference is and that it is not relevant. 
       In future, we will only consider strict well-ordering, unless explicitly stated otherwise.
   2. Assume that R is a partial ordering (strict or non-strict; this is not relevant) on the 
        set A, and that R has the following property: If B is a nonempty subset of A then B 
       has an R-least element (in the sense explained in Definition I.2 10). Show that R is 
       a well-ordering on A. (Note: this involves showing that R is a linear ordering.)
   3. Assume that R is a well-ordering on a set A and that A' is a subset of A. Show that
       R is a well-ordering on A'. (More precisely, we have to view  R as a binary relation 
       on A', so strictly speaking we should consider the intersection of R with A' x A' instead 
       of R.)
   4. Let R be a well-ordering on a set A, let a be some object that is not an element
       of A, and let A' be the union of A with {a}. (So A' is obtained by adding a to A.) Define
       a binary relation R' on A' as follows:
       -- R' agrees with R on A, i.e. for x,y \in A we have    x R y  if and only if  x R' y
       -- If x \in A then  x R' a
       -- NOT  a  R' a
       Show that R' is a strict linear ordering on A'; in this case R' is called
       an end-extension of R (Try to understand why.)
       Show that R' is a well-ordering on A'.
    5. (a) Assume x \in \omega. Show that \in is a well-ordering on x
        (b) Show that \in is a well-ordering on S(\omega), S(S(\omega)), ...
        (c) In general show: If x is a transitive set and \in is a well-ordering on x then S(x) is
             also a transitive set and \in is a well-ordering on S(x).