# Re: The seven step series

```
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).
>>
>>>
>>> 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