Thursday, October 8, 2015

A useful Lemma.  I want to build a simple proof that there is no largest number.  This little proof contains the hardest part of the proof , so it is the hardest part.

Let A be a set. 
Let 2^A be the set of functions mapping A to {0,1}; That is 
    for  f  2^A     and    a e A    then   f (a) = 0 or 1.

Let  H  be a function that That maps a subset R of 2^
    into a subset J of A.  Further H  is a 1-1 function,
    that is:   for each  f  e R    H(f) = j  e  J and j is unique 
    so that the inverse of H ,   invH  is also a function.

For any H  satisfying these conditions, 
    there is a function g 2^A  that is not in  R.


For the proof we we only need to define g so that it is clear that g is not a member of R, the range of H .

Let j be any element of the image of H,  j e J .
      Then  f  = invH(j)  is an element of R.
      Now f is an element of 2^A  and j is an element of A 
       So   f(j) is defined and f(j) is either 0 or 1.
        If f(j) =1 then define  g(j) =0.
        If f(j) =0 then define  g(j) =1.

Using this, g is defined for every member of R.
For members of A that are not members of R, 
a set that may be empty, select a member h of 2^R.
If k e  A  and k is not a member of J then

      g(k) = h(k).

Now we see that g is defined for every member of A
g is not element of R since it differs from each element
of R  at at least one element of A.

So the function g is in 2^A but g is not mapped by the function H .