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 02 as follows (per Cantor):
>>
>> N <-> NxN
>> 01 0,0
>> 2 1,0
>> 03 0,1
>> 04 2,0
>> 05 1,1
>> 06 0,2
>> 07 3,0
>> 08 2,1
>> 09 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 00 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.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Fri Aug 14 2009 - 09:35:00 PDT