On 13 Aug 2009, at 22:52, Brian Tenneson wrote:

> > There is an explicit formula that maps N onto Q.. I found it some > years > back. I let you find it again :) I will perhaps give one, from N to NxN, (and then Q), but it is not needed. Brent's bijection is perfectly defined. Could everyone see that a bijection from N to NxN can be transformed into a bijection between N and Q? What about N and R? Hint: relate this with the problem of finding a bijection between 2^N, or N^N with N. Show that there is a bijection between R and 2^N. Show that there are bijections between R and N^N. Bruno > > > Brent Meeker wrote: >> 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/ >> >> >>> > > > > 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 -~----------~----~----~----~------~----~------~--~---