There is an explicit formula that maps N onto Q.. I found it some years
back.
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/
>
>
> >
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
