September 3

* Partial Orders

  One way to identify a partial ordering is to prove that a relation
  is reflexive, transitive, and has no "nontrivial cycles".

  A "chain" in a binary relation R is a sequence (a1, ..., an) such that
  each (ai, ai+1) in R.  If all ai are distinct and (an, a1) in R, the
  chain is also a "cycle".  If n=1 the cycle is "trivial", otherwise the
  cycle is "nontrivial".

  Problem 1.4.8

  a) Prove that if S is any collection of sets, then R_S = {(A,B): A,B in S
  and A<=B} is a partial order.

     To prove that R_S is a partial order it is sufficient to show that R_S is
  reflexive, transitive, and has no nontrivial cycles.

  Reflexive:  A includes all of the elements of itself, so by definition of
  subset, A<=A.

  Transitive: Show that if A<=B and B<=C, then A<=C.  If B<=C, then every
  element of B is also an element of C.  Because A<=B, every element of A
  is an element of B which is also an element of C, so A<=C.

  No nontrivial cycles:  for (a1, ..., an) to form a nontrivial cycle all ai
  must be distinct, (ai, ai+1) must be in R_S, and (an, a1) must be in R_S.
  Note that for ai<=ai+1, either ai must equal ai+1 or ai has fewer elements
  than ai+1.  Since all of the ai components are distinct, we know that
  ai neq ai+1 so |a1| < |a2| < ... < |an|.  By the transitive property of "<",
  |a1| < |an|, and thus (an, a1) cannot be in R_S.  Thus R_S has no nontrivial
  cycles.


  b) Let S = 2**{1,2,3}.  Draw directed graph representing the partial
  order defined in (a).  What element or elements are minimal?

  A "minimal" element of a partial order R is an element a such that
  (b,a) in R only if b = a.

  We can spot minimal elements in the directed graph if there are no
  arrows pointing to a node or nodes in the graph except from themselves
  (these are minimal elements).

  Every finite partial order has at least one minimal element.

  One final note on binary relations:  we can use the notation
  (a,b) in R or the "infix notation" aRb.

* Closures

   Let D be a set, n>=0, and let R<=D**{n+1} be a (n+1)ary relation on D.
   D**n here means a group of size n where each component is an element of D.
   A subset B of D is said to be "closed under" relation R if b_{n+1} in B
   whenever b1, ..., bn in B and (b1, ..., b_{n+1}) in R.

   Any property of the form "the set B is closed under relations R1, ..., Rm"
   is called a "closure property" of B.

   The set of natural numbers is closed under "one less than".

   A closure property maps elements of a set onto an element of the same set.

   Functions can also have closures.  If D is a set, n>=0, and f is a function
   from D**n to D, then a subset B of D is "closed under f" if
   f(b1, ..., bn) in B for all b1, ..., bn in B.

   The natural numbers are closed under addition.

   - Are odd integers closed under multiplication?
     Yes.  The product of two odd integers is always an odd integer.

   - Are negative integers closed under subtraction?
     No.  -5 - -8 = 3, which is not a negative integer.

     What is the minimal set, of which negative integers is a subset,
     which is closed under subtraction?
     Integers are closed under subtraction.

   - Are negative integers closed under multiplication?
     No.  -5 * -8 = 40, which is not a negative integer.

     What is the minimal set, of which negative integers is a subset,
     which is closed under subtraction?
     Integers are closed under subtraction.


     If A<=D and P is a closure property defined by relations R1, ..., Rm on D,
  then there is a unique minimal set B, A<=B, and B has property P.  B is the
  "closure" of A under relations R1, ..., Rm.

     In particular, the "reflexive, transitive closure" of a binary relation
   R <= AxA, notated R*, is the closure of R under relations

      Q  = {((a,b), (b,c), (a,c)): a,b,c in A}   transitive
      Q' = {((a,a)): a in A}                     reflexive

     Include the original relation pairs and all other ordered pairs
  transitively reachable from the original pairs.

     R = {(a,b), (b,c) (c,1), (1,3)}

     R* = {(a,b), (b,c), (c,1), (1,3), (a,c), (a,1), (a,3), (b,1), (b,3), (c,3)}


     R* = R v {(a,b):  there is a chain in R from a to b}
     Similarly,
     R+ = {(a,b):  there is a chain in R from a to b}
     R+ is the transitive closure of R.  R+ need not be reflexive.


* FINITE AND INFINITE SETS

   We know how to compare the size of finite sets
   A = {1,2,3}, B = {4,5,6,7}, |A| = 3, |B| = 4, |A| < |B|

   We know that if A<=B then |A| <= |B|.
   if AB.
   Remember this is one-to-one and onto, so the sets must have an equal
   number of elements.

   A set is finite if it is equinumerous with the set {1, 2, ..., n}, for
   a given natural number n.

   If A and {1, ..., n} are equinumerous, then the "cardinality" of A is n.

   The sets N and R are infinite, but they are not equinumerous.
   How can we distinguish between sizes of infinite sets?

   A set is "countably infinite" if it is equinumerous with N, and
   "countable" if it is finite or countably infinite.
   A set that is not countable is "uncountable".

   How do we prove that a set is countable?

   - define a bijection between the set and a known countably infinite set
     (often N is used for this purpose)

   - prove that the set is a subset of a known countably infinite set

   How can we prove that A = {x: x is even} is countable?
   A is a subset of N which is countably infinite.

   Key:  you want to show that for any element bi in the set, you
     can visit the element in finite time (i steps)

   Consider a bijection f:N->B as a way of listing the elements of the countably
   infinite set B, where bi = f(i).  Thus any element bi is listed on the ith
   step.  If A is a subset of B, we can list the elements of A the same way as
   the elements of B, only omitting the elements not included in A.

   Show the "dovetailing" method for listing elements of a union of a finite
   number of countably infinite sets.  Visit first element of first set,
   first element of second set, and so forth, then second element of each
   set, etc.

   a0    a1
   |    /|
   |   / |
   b0 /  b1   ...
   | /   |
   |/    |
   c0    c1

   Another example of dovetailing.
   Show union of countably infinite number of countability infinite sets is
   countably infinite.

   Try to define bijection between this set and N (define an ordering
   on the elements of the set such that element i of the set is visited
   on the ith step).  Let us refer to the ith element from the jth set as (i,j).

   First round:  visit one element from first set (0,0)
   Second round:  visit second element from first set (0,1), then
		  visit first element from second set (1,0)
   Third round:  visit third element from first set (0,2), then
		 visit second element from second set (1,1), then
		 visit first element from third set (2,0)
   nth round:    visit nth element of first set (0,n-1), then
		 visit n-1st element of second set (0,n-2), then
		 ..., then
		 visit first element of the nth set (n-1,1)

   In each round we visit all pairs (i,j) s.t. i+j = n-1.

   In each round there is a finite number of elements to visit (because we
   visit one element of each set and there is a finite number of sets).
   Thus for any given element (x,y) we will visit the element in a finite
   amount of time.

             ...|
               7|
               6|
     Element   5|
               4|
               3|
               2|
               1|
               0|
                +-------------------     Show dovetailing
		 0 1 2 3 4 5 6 7 ...
		      Set

   How can we use this method to show that the set of rational numbers
   is countably infinite?

   B = {x: x is rational}, x is of the form N+/N+, represent x as
       (numerator, denominator)


   - Interesting Example

   A program can be viewed as a function:  INPUT -> OUTPUT, where I/O are
   represented a binary strings representing natural numbers.
   A program is thus f:N->N.  Each such function f also suggests a program.

   How many such functions are there?  f:N->{0,1} is smaller than f:N->N,
   let's consider that.  There are as many f:N->{0,1} as there are elements
   in the power set of N.  This is shown by the function f called the
   "characteristic function" of X (X represents a subset of N), f:N->{0,1},
   defined as
             +---
      f(n) = |1 if n in X
	     |0 if n not in X
	     +---

   There are at least as many functions from N to N as |P(N)|.
   We know that P(N) is uncountable, so there are uncountably many functions
   for which we may want to write programs.

   Consider your favorite programming language.  There are a finite number of
   symbols in the language.  We can count all programs in this language by
   first alphabetizing the symbols, listing all programs of length on in order,
   then of length two in order, etc.  Such a listing would ultimately contain
   any program that can be written in the language.  This the set of all
   programs that can be written in the language is countable.

   Because programs are countable and the functions they generate are
   uncountable, there are more functions than program and there are some
   problems you might want to solve for which no program can be written
   in a given programming language.

   Can these ever be solved?  We will address some of these questions
   throughout the semester.