Re: The seven step series

[Brent Meeker]

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 2 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 3 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 0 to the first and 1 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@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---