Re: The seven step series

From: Brent Meeker <meekerdb.domain.name.hidden>
Date: Thu, 13 Aug 2009 13:49:05 -0700

Bruno Marchal wrote:

...

4) Key questions for the sequel, on which you can meditate:

- is there a bijection between N and NxN?      (NxN = the cartesian  
product of N with N)
- is there a bijection between N and N^N?
    

You're making me think, Bruno. :-)

A bijection between N and NxN can be constructed by enumerating all the N pairs summing to 0, followed by those summing to 1, followed by those summing to 02 as follows (per Cantor):

N <-> NxN
1       0,0
2      1,0
3      0,1
4      2,0
5      1,1
6      0,2
7      3,0
8      2,1
9      1,2
10     0,3
...

New exercises for the adventurous:

In the context of sets, 2 will represent the set {0, 1}. OK?  And 03  
will represent {0, 1, 2}, etc.

Find a bijection between NxN and N^2

   this means find a bijection between NXN and the set of functions  
from 2(= {0,1})  to N.
  

Since there are two elements in the domain {0,1}, if we write down all pairs of numbers (n,m) and map 00 to the first and 01 to the second we will have constructed all functions from 2 to N.  But above we've already enumerated all pairs of numbers, NxN.  So we just map 0 to the number in first one and 1 to the second and we have an enumerated list of the functions from 2 to N.


N <-> NxN  <->  N^2
1       0,0               {(0,0) (1,0)}
2      1,0               {(0,1) (1,0)}
3      0,1               {(0,0) (1,1)}
4      2,0               {(0,2) (1,0)}
5      1,1               {(0,1) (1,1)}
6      0,2               {(0,0) (1,2)}
7      3,0               ...
8      2,1
9      1,2
10     0,3
...

Define NxNxN by Nx(NxN), with (x,y,z) represented (bijectively) by (x, 
(y,z)) OK?

Find a bijection between NxNxN and N^3

Show that there is a bijection between NxNxNxNxNx ... xN (m times) and  
N^m, in the sense of above. That is
NxNxNxNxNx ... xN is defined by Nx(Nx(Nx ... ))))), and N^m is the set  
of functions from m to N, and m = {0, 1, ... m-1}.
  

First note that we can use the mapping NxN -> N to reduce NxNx...xN (m times) to NxNx...xN (m-1 times) by substituting for a pair in NxN the number from N determined by the above bijection.  So we can construct a bijection NxNx...xN <-> N.

Second, N^m is the set of mappings from m to all m-tuples of numbers to N.  So if we write down the m-tuples, i.e. the elements of NxNx...xN (m times) as we did the pairs above and then for each m-tuple map 0 to the first element, 1 to the second, and so forth up to the mth element we will have constructed all the functions N^m and we will have enumerated them, i.e. shown a bijection between N^m and N.  Since bijection is transitive, this also shows there is a bijection between NxNx...xN (n times) and N^m (n and m not necessarily equal).

For the very adventurous:

Find a bijection between NxNxNx ....  and N^N?
  

Hmmm?  I could say I've already proven it above or that it follows from the above by induction, but the scheme would require writing down infinitely many infinite lists so I'm not sure the above proof generalizes to N^N.

Brent

Despite perhaps the appearances, all those new exercises are rather  
easy. The above in "4)" key questions are more difficult.

Oh! I forget to ask you the simplest exercise :

Find a bijection between N and N^1,  with 1 = {0}.

N^1 is of course the set of functions from 1 to N, i.e. from {0} to N.

Don't worry, if this last exercise didn't give the clue (for the new  
exercises), I will explain why this new exercises are really simple,  
and why it is simpler than the key questions.

OK, this is food for friday and the week-end,
Ask any questions, or do any remarks. We approach surely to the first  
big theorem (Cantor).

Bruno



http://iridia.ulb.ac.be/~marchal/

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe@googlegroups.com
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

Received on Thu Aug 13 2009 - 13:49:05 PDT