# Re: The seven step series

```Brent,

I said: this is food for Friday and the week-end, and you provide
```
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).
>
>>
>> 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