Brent, I said: this is food for Friday and the week-end, and you provide already the solutions!
It is OK, and you are correct. Thanks for playing. I add short comments. I have not much time till monday, and I intend to come back on some issues. I will comment the important recent post by David though. On 13 Aug 2009, at 22:49, 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 > ... OK. I hope everyone see that your bijection is indeed one-one and onto. Each number is sned on one couple, and each couple is touched by the bijection. I take it as a function from N to NxN. > > > >> 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. OK. > > > 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. I will come back on this next week. A simple way to see that there is indeed a bijection between NxNx.... and N^N, consists in observing that an element of NxNx... is really an infinite-uple. A couple is a 2- uple, a triple is a 3-uple, and an element of NxNxNx... is really an infinity-uple (a, b, c, ....). This is just a sequence of number. The canonical bijection is given by (a, b, c, ...) ====> {(0, a), (1, b), (2, c), ....} A function from N to N is really just an infinite sequence of numbers. This generalize your correspondence above between NxN and N^2 (with 2 = {0, 1}). So now we know that there is a bijection between NxNxNx ...xN (m times) and N^m. And you have shown all those sets can be put "in bijection" with N. And we know that the infinite cartesian product NxNx... is "in bijection" with N^N. But the question which remains is: does there exist a bijection between NxNx.... and N? > > > > >> 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. You did not solve this one? Too much easy perhaps :) An element of N^1 is a function from {0} to N. They have the shape {(0, x)}. They can have only one couple. So the canonical simplest bijection is n ====> {(0, n)} Quite like your bijection (n, m) =====> {(0, n) (1, m)} between NxN and N^2 above. Summary: There are bijections between N, and N^1, and N^2, and ... N^m, for each m. But is there a bijection between N and 2^N ? Is there a bijection between N and 3^N ? Is there a bijection between N and m^N ? Is there a bijection between N and N^N ? I let people meditate on this, 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 -~----------~----~----~----~------~----~------~--~---