The seven step series

[Bruno Marchal]

On 12 Aug 2009, at 19:55, Bruno Marchal wrote:


>
> 1) Convince yourself that if A and B are finite sets, then there  
> exists a bijection between A and B if and only if card(A) = card(B).

Only you can convince yourself. I try to help by going very slowly,  
but people should really mind it y themselves, without hesitating to  
reread the definitions in case of doubt, or to attack me on the typo  
errors, I mean it is not very difficult, but revise well the  
definitions if problems.

I provide a detailed solution of the first problem, hints for the  
other problems, and new problems for the adventurous.


>
> 2) If A has n elements (card(A) = n), how many bijections exists  
> from A to B?
>
>      Again start with simple examples, and try to generalize.
>
>      For example, how many bijections from {a, b, c} to {1, 2}. How  
> many bijections from (a, b, c} to {a, b, c}?


How many bijections are there from {a, b, c} to {1, 2}?

Let us try to build one. A bijection is a function which has to be one-
one and onto. So I start from {a, b, c}, and I build my bijective  
function, so I open the accolades "{" , I open the parenthesis "(" of  
the first couple of my function, and I choose "a" in "{a, b, c}",  
which is the set of input/argument of my function. This very beginning  
looks like

{(a,

And I have to decide where in the set {1, 2} "a" will be sent.  
Remembering all the times that I am building a function, so that once  
"a" is sent, I can no more send it again, and that my goal here is to  
build a bijection, so that I cannot send two different elements of my  
starting set on the same element in the arrival set. Nor should I miss  
an element of the arrival set.

Well, cool, I *can* continue, I have actually two choices, I can send  
"a" on "1", or I can send "a" on 2. I decide to send it on "1",

This means (a, 1) will belong to my bijection, well, the one I try to  
build.
My "future" bijection looks like

{(a, 1),

And I have to decide where "b" is send, now:   {(a, 1), (b,

Could I send "b" to "1"? No. I can't. The function would not be one-
one! I do have a solution yet, I can send "b" on "2".
Note that our freedom has decreased, here. Now my bijection looks like

{(a, 1), (b, 2),

And I have to decide where I will send "c".  {(a, 1), (b, 2), (c,

Could I send it on "1"? No. I can't. The function would not be one-one!
Could I send it on "2"? No. I can't. The function would not be one-one!
Is there anywhere else? Well, the function is from {a, b, c} to {1,  
2}. If you want a function which i just ONTO, it is OK, send "c" on  
"1" or "2" as you wish, but none of such function can be one-one.

Or attempt has failed.

OK. Perhaps it is like in the Sudoku, and our first choice was bad. My  
be we should have send "a", not on "1", but on "2", After all we get  
two choices at the beginning. Surely we have made the bad choice. So  
let us try again:

{(a, 2),

and then

{(a, 2), (b, 1),   .... we realize with some anxiousness that the  
number of choices has gone again from 2 to 1, and now we have to send  
"c" on something which has to be different from "1" and "2", and yet  
in the arrival set {1, 2}. Zero possibility, we are trapped. Perhaps,  
we should have begin by sending "b". This would not change anything.

We have to conclude that there is no bijection from {a, b, c} to {1, 2}.

Is there a bijection from {1, 2} to {a, b, c}. No. In this case  
convince yourself that you can build a function which is one-one, but  
that there is no onto functions.

Convince yourself that if there is a bijection from A to B, then there  
is a bijection from B to A. That is why we talk also of bijection  
between A and B. Hint: show that to each bijection from A to B, you  
can associate canonically a bijection from B to A.

How many bijections from (a, b, c} to {a, b, c}? I let you search.  
Hint: look what happen to our choices above, compare to the choices in  
our previews counting.


>
> 3) can you find, or define a bijection between the infinite set N,  
> and the infinite set E = {0, 2, 4, 6, 8, ...} (E for even).


This means, by definition of bijection, can you find a function from N  
to E which is both one-one and onto.

Example:

The identity function which send n on n, that is I = {(0,0), (1,1),  
(2,2), (3, 3) ...} is a function from N to N which is onto and one-
one. It is a bijection between N and itself. But it is not a function  
from N to E.

The function which send n on 8*n, that is, f8 = {(0,0) (1,8) (2,16),  
(3, 24), ...} is a function from N to E. And it is one-one. But it is  
not onto. The number 4 in E remains untouched by it, like 6, or 66, or  
82, and many other numbers in E.

To find a bijection between N and E, just search for a function which  
is one and onto, from N to E.




>
> 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?


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.

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}.

For the very adventurous:

Find a bijection between NxNxNx ....  and N^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.

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brian Tenneson]

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

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).
>>
>>> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

Hi,

Just a reminder, for me, and perhaps some training for you. In  
preparation to the mathematical discovery of the universal machine.

exercises:

1) count the number of bijections from a set A to itself.  (= card{x  
such that x is bijection from A to A})

2) describe some canonical bijection between 2^A and the powerset of A.

3) I say that a set S is a proper subset of A if it is a subset of A,  
and different from A.
     We have seen that there is a bijection between N and 2N = {0, 2,  
4, 6, ...}. (see below *)
     2N is a proper subset of N.
     So we see that an infinite set can have a bijection with a proper  
subset.
     The question is, could that be possible for a finite set?

The bijection between N and 2N is the set {(0,0), (1,2), (2, 4), (3,  
6), (4, 8), ...}.  More schematically, if you remember the ropes:

N          2N

0 ------- 0
1 --------2
2 --------4
3 --------6
....

4) Be sure that you have been convinced by Brent  that there is a  
bijection between N and NxN, and between N and NxNxN, and etc. That is  
be sure there is a bijection between N and N^m for each N.

5) Key exercise for the sequel. First a definition. An alphabet A is a  
non empty finite set. I call its elements letter.
Exemple. A = {a, b, c},, B = {0, 1}.. By A+ I mean the set of finite  
words on the alphabet A. A word is a finite sequence of letters, from  
some alphabet, like, on the alphabet A, aaabab, abbbbcbababcccacab, etc.
IA+ is obviously infinite, it contains *notably* a, aa, aaa, aaaa,  
aaaaa, aaaaaa, aaaaaaa, ...

The word "word" has a larger meaning in math than in natural language.  
On the usual alphabet {A, B, ... Z}, an expression like  
HHYUJLIFSEFGXWKKODENN is a fully respectable word.

Show that for any alphabet A, there is a bijection between N and A+


Soon (asap, though) the proof of many theorems found by Cantor.  
Notably that there is NO bijection from N to N^N.
Then Cantor proof will be done again and again, and again, ... in  
deeper and deeper and deeper contexts.

Please ask any questions. It is not too late before we go in the  
*very* interesting matter, and very illuminating with respect to the  
question of the existence of universal machines, languages and numbers.

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

On Wed, Aug 19, 2009 at 12:12 PM, Bruno Marchal<marchal@...> wrote:
>
> Hi,
>
> Just a reminder, for me, and perhaps some training for you. In
> preparation to the mathematical discovery of the universal machine.
>
> exercises:
...
> ....
>
> 4) Be sure that you have been convinced by Brent  that there is a
> bijection between N and NxN, and between N and NxNxN, and etc. That is
> be sure there is a bijection between N and N^m for each N.

Don't you mean "for each m"?

Brent

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 19 Aug 2009, at 23:03, meekerdb @dslextreme.com wrote:

>
> On Wed, Aug 19, 2009 at 12:12 PM, Bruno Marchal<marchal@...>  
> wrote:
>>
>> Hi,
>>
>> Just a reminder, for me, and perhaps some training for you. In
>> preparation to the mathematical discovery of the universal machine.
>>
>> exercises:
> ...
>> ....
>>
>> 4) Be sure that you have been convinced by Brent  that there is a
>> bijection between N and NxN, and between N and NxNxN, and etc. That  
>> is
>> be sure there is a bijection between N and N^m for each N.
>
> Don't you mean "for each m"?

Yes. Sorry. I type too much quickly. I made other mistakes of that  
type. Hope you can see them and make the correction.
In case of doubt ask, like Brent.

Some people seems afraid asking questions, please, do. Nobody judge  
you. We have different baggages.

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

Hi,

I give the solution of the first of the last exercises.


I reason aloud. I go slowly for those who did not get some math  
courses, or just forget them.  I cannot stress the importance of the  
notion of bijection in the "mathematical discovery of the universal  
machine" (the quote means that a nuance will be added here).

Counting is not so important. Th exercise motivation is in to develop  
familiarity with the notion of function and bijection. Then counting  
things provides example of functions from N to N.


> 1) count the number of bijections from a set A to itself.  (= card{x
> such that x is bijection from A to A})


This does not seem very obvious, so let us begin with the simplest  
set, for example the one which admits the shorter description when  
written in extension, that is the empty set { }.

The question in this case is: count the number of bijection between  
{ } and { }.

Hmm... This smells the subtle trap and it may be a good advise to  
avoid the simplest set or number. Zero and the empty set may be  
simplest in term of description but may be harder conceptually.

A simple case, in this and many cases, would be a set with not much  
elements. Let us count the number of bijections from {a, b} to itself.  
i.e. the bijections from {a, b} to {a, b}.

Here some beginners could have a trouble: "I don't remember what is a  
bijection". Well, the exercise is obviously with notes. I am not yet  
asking to buy a webcam so that I can look if you are not cheating, all  
right?

Two things can happen. Either you find the passage in your diary where  
I explain bijection with the legendary story of the humans who cannot  
count, and compare the bigness of sets by using ropes.

You may remember how the farmer compare their *set* of animals,  
without being able to count. They compare two sets of animals by  
attaching a rope to ONE animal belonging to the set of your animals,  
say, and you bring that to ONE animal of your neighbor.
Three things can happen:
1) All your animals get attached to a rope, and got attached to some  
neighbor's animals, but some other animal of the neighbor are still  
freely going here and there. In this situation we say "damned, the set  
of animals of my neighbor is bigger than mine".
2) All your animals get they rope, and got attached  to the neighbor's  
animals. And all neighbor's animals are attached. In this situation we  
say "OK, my set of animals has the same cardinality than the set of my  
neighbor animals. Cardinality is the measure of set, when we compare  
it in this way. Now, this is the situation where a bijection exists.
3) All the neighbor's animal are attached to the rope, yet some of  
your own animals remain free. You can attach the rope to those free  
animals, but you will be unable to attach them to some neighbor  
animal, they are already all attached. In this situation you say  
nothing, because you are polite, you just let the neighbor saying  
"damned, the set of animals of my neighbor is bigger than mine".

  .... Or you don't remember that story, so you consult the austere  
notes with the definition. A, B ... represent sets.

A bijection between A and B is a function from A to B which is ONE-ONE  
and ONTO.

And what is a function? A set of couples (x, y), x in A, y in B,  
verifying the condition that no x in A is sent on different y in B. In  
a very large sense, the element of B depend on the element of A, and  
that dependence is represented by a couple (x, y).

With the farmer, the couples where made with one animal x attached by  
a rope to one animal y:  (x, y).

Well let us go back to the bijections from {a, b} to {a, b}. Oh, I see  
some anxiousness can rise due to the fact that we have the same set of  
both side. Why would ever a farmer compare the bigness of its set of  
animals with the bigness of its set of animals? Is that not a pure  
mathematical absurdity?

To ease the pain, in math, consists always in simplifying, so, just to  
keep the intuition provided by the farmer, let us distinguish the  
animal's neighbor, those which makes the arrival set, by different  
letters. And let us first search the bijections from {a, b} to {c, d}.  
{a, b} is the set of my animals. {c, d} is the set of animals of my  
neighbor. OK?

Well I have to build a bijection, which is a set, so I have to begin  
by "{", indicating I am building a set. Of course, this is implicit in  
the farmer's mind, because his goal consists in just comparing the two  
sets. But our goal is to find all bijections. So we have to be clear  
about them as mathematically represented objects, and bijections, like  
functions, have been defined or represented as sets.

Now I have to choose one of my animals; let us choose a. and attach  
the rope. The description of the bijection looks like:

{(a,

I have to choose an animal belonging to the set of my neighbor's  
animals. Well, I have two choices: c or d. Let us choose c. The  
description of the bijection looks like:

{(a, c),

And then

{(a, c), (b, d)}

This *is* a function, which is ONTO and ONE-ONE.

Is there another?

Yes. I choose the other animals (cf the two choice above). But note  
already, that for the second animals I have only once choice.

The other is {(a, d), (b, c)}. Is there another one? No.

There are two bijections from {a, b} to {c, d}.  {(a, c), (b, d)}  and  
{(a, d), (b, c)}.
The set of bijections from {a, b} to {c, d} is the set {{(a, c), (b,  
d)}, {(a, d), (b, c)}}. This is more easy to build than to read.

Now the name of the element, or even what they consists in (animals,  
numbers, letters) is not relevant OK?

In particular there are as many bijection from {a, b} to {a, b} than  
from {a, b} to {c, d}. They are

{(a, a), (b, b)}

  and

{(a, b), (b, a)}

A bijection from A to A is called a permutation of A.   {(a, a), (b,  
b)} is called the identity permutation on {a, b}.

Oh, card(A) = 2 (= A has two elements) entails that there is 2  
bijections.

WE may generalize and believe that there are as many bijections from A  
to A, than there are elements in A.

OK? Let us test this theory on the simpler set {a}. How many  
bijections are there from (a} to {a}. Well, there is {(a,a)}, and  
that's all. One! Our theory succeeds.

If we infer that theory on { }, we may be tempted to say 0, for the  
number of bijections between { } and { }. But with a sample of two  
elements ...,  it is dangerous to infer too much quickly.

Let us look at {a, b, c}. Are there three bijections? And only three  
bijections? (Well if you remember the number of function from A to B  
is card(B)^card(A), so we could be astonished our conjecture is  
tenable).

And indeed, I go systematically trying to figure out how to count the  
number of bijections from A to A for a finite set A in general.

Let us build a bijection from {a, b, c} to {a, b, c}.

It has to be something like {(a , _) , (b,  ),   (c,  ) }. Given that  
in a set the order has no importance, so the choices of beginning by  
(a,  or by (b,  or by (c   is not relevant. But once I choose say {(a,  
the number of choice to complete the second bijection is relevant {(a,  
b) ..., will not give the same bijection that {(a, c), ...

So I start with {(a,  I have three choices. Let us take c for the  
first choice, how many choices there is for the next element?

Well, given that the bijective function (bijection) have to be ONE-
ONE, you loose a possibility at each choice. So there will be three  
possibility, then 2, the 1, and the bijection is completed.

So there will be 3 x 2 x 1 bijections. the number of choices are  
multiplied for the same reason that for the number of functions. Once  
a choice is made, the remaining choices are independent.

Let us look

{(a, a) (b, b), (c, c)}
{(a, a) (b, c), (c, b)}   choice: "{(a,a) ..."  multiplied by the  
bijections from {b, c} to {b, c}.

{(a, b), (b, a) (c, c)}
{(a, b), (b, c) (c, a)}

{(a, c), (b, a) (c, b)}
{(a, c), (b, b) (c, a)}

So three elements leads to 3 x 2 x 1 bijections; that is 6 bijections.

If there is n elements in the set, there will be n choices for the  
first couples, then, by the one )one condition, it will remains
(n-1) choices, then (n-2) .... up to the last 1 choice.

We have a "formula". if card(A) = n then then number of permutation on  
A, or of bijection from A to A, is n*(n-1)* ... 1.

OK?

Er, how many bijections from { } to { } ? In this case card(A) = 0.  
The formula we get does not seem to apply. What could be

0*(0-1)*(0-2)*  .... * 1   ?

At first sight it should be 0. Because 0*<anything> = 0 isn't it?    
false: 0 * any number = 0. But who could claim that the expression  
above is well determined: it is like you will never get to that "1".

I'm afraid we have to tackle the "simplest" case by reason alone,  
taking our definition seriously into account.

How many bijection are there, from { } to { }?

Well, bijections are sets, so we can begin {, and we have to put in  
that set couples (x, y) with x in { } and y in { }. But there is no x  
in { }, so we will not find any couples. So our set is empty, so we  
can close it directly, and the bijection looks like { }. It is the  
empty bijection. So we have find one, and only one.

So the number of bijections from the empty set to the empty set is  
ONE. (For the same reason, if you remember, that the number of  
functions from { } to { } is one. Card({ }^{ }) = 1).

That was the harder case.

Now let us write A° for the set of permutation on A. A permutation is  
defined by a bijection from A to A.

We have seen that if Card(A) = n, card(A°) = n*(n-1)*(n-2)* ... *1 if  
A is not empty, and Card(A°) = 1 if A is empty.

This motivates the definition of the following function from N to N,  
called factorial.
factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if  
is n is different from 0.

Note this: if n is different from 0, for each n we have that fact(n) =  
n*fact(n).

factorial is a function from N to N, so it is the following set of  
couples:

{(0, 1), (1, 1), (2, 2), (3, 6), (4, 24), (5, 120), (6, 720), (7,  
5040), (8, 40320), (9, 362880), (10, 3628800), (11, 39916800), ...}

A good thing I did not ask you to give me all the bijections from a  
set from 10 elements to itself. See that if two farmer have 10 animals  
each, they is already 3628800 bijections between their two sets of  
animals.

Compare with the exponential function, which send n to 2^n

{(0, 1), (1, 2), (2, 4), (3, 8), (4, 16), (5, 32), (6, 64), (7, 128),  
(8, 256), (9, 512), (10, 1024), (11, 2048), ...}



OK?

Bruno

>
> 2) describe some canonical bijection between 2^A and the powerset of  
> A.
>
> 3) I say that a set S is a proper subset of A if it is a subset of A,
> and different from A.
>     We have seen that there is a bijection between N and 2N = {0, 2,
> 4, 6, ...}. (see below *)
>     2N is a proper subset of N.
>     So we see that an infinite set can have a bijection with a proper
> subset.
>     The question is, could that be possible for a finite set?
>
> The bijection between N and 2N is the set {(0,0), (1,2), (2, 4), (3,
> 6), (4, 8), ...}.  More schematically, if you remember the ropes:
>
> N          2N
>
> 0 ------- 0
> 1 --------2
> 2 --------4
> 3 --------6
> ....
>
> 4) Be sure that you have been convinced by Brent  that there is a
> bijection between N and NxN, and between N and NxNxN, and etc. That is
> be sure there is a bijection between N and N^m for each N.
>
> 5) Key exercise for the sequel. First a definition. An alphabet A is a
> non empty finite set. I call its elements letter.
> Exemple. A = {a, b, c},, B = {0, 1}.. By A+ I mean the set of finite
> words on the alphabet A. A word is a finite sequence of letters, from
> some alphabet, like, on the alphabet A, aaabab, abbbbcbababcccacab,  
> etc.
> IA+ is obviously infinite, it contains *notably* a, aa, aaa, aaaa,
> aaaaa, aaaaaa, aaaaaaa, ...
>
> The word "word" has a larger meaning in math than in natural language.
> On the usual alphabet {A, B, ... Z}, an expression like
> HHYUJLIFSEFGXWKKODENN is a fully respectable word.
>
> Show that for any alphabet A, there is a bijection between N and A+
>
>
> Soon (asap, though) the proof of many theorems found by Cantor.
> Notably that there is NO bijection from N to N^N.
> Then Cantor proof will be done again and again, and again, ... in
> deeper and deeper and deeper contexts.
>
> Please ask any questions. It is not too late before we go in the
> *very* interesting matter, and very illuminating with respect to the
> question of the existence of universal machines, languages and  
> numbers.
>
> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Brent Meeker-2]

On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchal<marchal@...> wrote:
>
>
> Hi,
>
> I give the solution of the first of the last exercises.
...
> This motivates the definition of the following function from N to N,
> called factorial.
> factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if
> is n is different from 0.
>
> Note this: if n is different from 0, for each n we have that fact(n) =
> n*fact(n).

Of course you meant fact(n)=n*fact(n-1).

Brent

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 21 Aug 2009, at 01:24, meekerdb @dslextreme.com wrote:

>
> On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchal<marchal@...>  
> wrote:
>>
>>
>> Hi,
>>
>> I give the solution of the first of the last exercises.
> ...
>> This motivates the definition of the following function from N to N,
>> called factorial.
>> factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if
>> is n is different from 0.
>>
>> Note this: if n is different from 0, for each n we have that  
>> fact(n) =
>> n*fact(n).
>
> Of course you meant fact(n)=n*fact(n-1).

Yes, indeed.

Note that later we will see stronger form of recursion, but here it is  
just a "typo" mistake.

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[m.a.-2]

Some parts of this message have been removed. Learn more about Nabble's security policy.

Bruno,

           I'm terribly sorry to disappoint you and ashamed to admit that I'm "throwing in the towel". This is an idiom used in professional boxing; when a coach decides that his fighter can't take anymore punishment, he ends the fight by throwing a towel into the ring. I simply don't have the sort of mind that takes to juggling letters, numbers and symbols in increasingly fine-grained, complex arrangements. I think that in any endeavor, when we struggle towards a goal, there should be some satisfaction...some sense of accomplishment...in each step along the way. But in this quest, I find each step to be difficult and unrewarding in and of itself. Sometimes the goal is so compelling that we force ourselves to overcome huge impediments to reach it; but in this case, I already know what the goal is, and I am only motivated by the desire to understand how it is proven. Well, I must be content to leave verification of the proof to people who are far better able than I to follow its intricacies. I trust they have checked it accurately and will point out inconsistencies in this open forum if such exist. Meanwhile, I'm happy to take it on faith. I shall certainly continue to lurk here gleaning what I can from the philosophical debates whose endless probing of the foundations of existence is a source of constant fascination. Best,

                                                                                                                                                                      marty a.

 

 

 

 

 

 

 

 

          

----- Original Message -----

From: "Bruno Marchal" <marchal@...>

To: <everything-list@...>

Sent: Friday, August 21, 2009 3:47 AM

Subject: Re: The seven step series

>

>
> On 21 Aug 2009, at 01:24, meekerdb @dslextreme.com wrote:
>
>>
>> On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchal<marchal@...> 
>> wrote:
>>>
>>>
>>> Hi,
>>>
>>> I give the solution of the first of the last exercises.
>> ...
>>> This motivates the definition of the following function from N to N,
>>> called factorial.
>>> factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if
>>> is n is different from 0.
>>>
>>> Note this: if n is different from 0, for each n we have that 
>>> fact(n) =
>>> n*fact(n).
>>
>> Of course you meant fact(n)=n*fact(n-1).
>
>
> Yes, indeed.
>
> Note that later we will see stronger form of recursion, but here it is 
> just a "typo" mistake.
>
> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

Thanks for telling Marty. 

It is a pity you stop just before Cantor Theorem, but it could ask for some work if your math disposition have been dormant for a too long time. 

I am sure you could come by, because what will follow will be a recurrent use of the same idea.

The difficulty, for many, is to understand what is a mathematical computation, but to explain this we have to explain what are the mathematical objects which will computed and be computed. 

Sets of numbers and functions from numbers to numbers are those things which will be either computable or not computable. 

Up to now, I am only introducing vocabulary, so that we can avoid future misunderstanding. Numbers, sets, functions are common in "exact science", but rarely well known ... 

I will soon explain Cantor theorem. And soon after should the "mathematical discovery of the (mathematical) universal machine" appear. 

I have to explain a minimal amount of theoretical computer science to give a precise sense to the comp supervenience thesis.

I like to summarize 20th century computer science by its two main 'discoveries', really two creative bombs, the universal machine, and the other universal machine. The universal machine, and the quantum universal machine. I put 'discoveries' in quote because strictly speaking they are thesis or hypothesis. 

Take a look on what follows because it happen that some beginners understand math the day they understand the first non trivial result, but take it easy any way. It is a pleasure to share interest wherever we come from, and I appreciate your open mind,

Bruno

On 21 Aug 2009, at 16:22, m.a. wrote:

Bruno,

           I'm terribly sorry to disappoint you and ashamed to admit that I'm "throwing in the towel". This is an idiom used in professional boxing; when a coach decides that his fighter can't take anymore punishment, he ends the fight by throwing a towel into the ring. I simply don't have the sort of mind that takes to juggling letters, numbers and symbols in increasingly fine-grained, complex arrangements. I think that in any endeavor, when we struggle towards a goal, there should be some satisfaction...some sense of accomplishment...in each step along the way. But in this quest, I find each step to be difficult and unrewarding in and of itself. Sometimes the goal is so compelling that we force ourselves to overcome huge impediments to reach it; but in this case, I already know what the goal is, and I am only motivated by the desire to understand how it is proven. Well, I must be content to leave verification of the proof to people who are far better able than I to follow its intricacies. I trust they have checked it accurately and will point out inconsistencies in this open forum if such exist. Meanwhile, I'm happy to take it on faith. I shall certainly continue to lurk here gleaning what I can from the philosophical debates whose endless probing of the foundations of existence is a source of constant fascination. Best,

                                                                                                                                                                      marty a.

 

 

 

 

 

 

 

 

          

----- Original Message -----

From: "Bruno Marchal" <marchal@...>

To: <everything-list@...>

Sent: Friday, August 21, 2009 3:47 AM

Subject: Re: The seven step series

> 

> 
> On 21 Aug 2009, at 01:24, meekerdb @dslextreme.com wrote:
> 
>>
>> On Thu, Aug 20, 2009 at 12:32 PM, Bruno Marchal<marchal@...>  
>> wrote:
>>>
>>>
>>> Hi,
>>>
>>> I give the solution of the first of the last exercises.
>> ...
>>> This motivates the definition of the following function from N to N,
>>> called factorial.
>>> factorial(0) = 1, and factorial(n) = n*(n-1)*(n-2)*(n-3) * ... *1, if
>>> is n is different from 0.
>>>
>>> Note this: if n is different from 0, for each n we have that  
>>> fact(n) =
>>> n*fact(n).
>>
>> Of course you meant fact(n)=n*fact(n-1).
> 
> 
> Yes, indeed.
> 
> Note that later we will see stronger form of recursion, but here it is  
> just a "typo" mistake.
> 
> 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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Miroslav Dobsicek]

m.a. wrote:
> a towel into the ring.
> I simply don't have the sort of mind that takes to juggling letters,
> numbers and symbols in increasingly fine-grained, complex arrangements.

[...]

Marty,

If I can ask, I'd be really interested what do you think of this
socratic experiment
http://www.garlikov.com/Soc_Meth.html

Cheers,
 mirek





--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[m.a.-2]

Mirek,
             I think it must be a very effective method of teaching binary
numbers. Perhaps I'll try it on my grandchildren. My four-year-old grandson
calls VCR tapes "rectangular DVD's". So he's probably ready for abstract
thinking. Thanks for the lesson.
                                         marty a.




----- Original Message -----
From: "Mirek Dobsicek" <m.dobsicek@...>
To: <everything-list@...>
Sent: Saturday, August 22, 2009 11:05 AM
Subject: Re: The seven step series

>
> Marty,
>
> If I can ask, I'd be really interested what do you think of this
> socratic experiment
> http://www.garlikov.com/Soc_Meth.html
>
> Cheers,
> mirek
>
>
>
>
>
> >

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[m.a.-2]

Some parts of this message have been removed. Learn more about Nabble's security policy.

Mirek,

             My previous answer to your question was glib and evasive, I apologize for that, but I think your question was misleading as well. In an attempt to be kind, you asked my opinion, from a pedagogical POV, of a lesson designed to make binary arithmetic simple enough for third-grade students. I think that what you really wondered was whether the lesson would work with a math-challenged adult like me. So, because I believe you to be genuinely and unmaliciously curious and in the interest of science, I'll try to describe my experience of this lesson. 

           Did it teach me about binary numbers? The answer must be "Yes" and "No". As I studied the lesson step by step, I understood each point and felt at the end, that I had a solid grasp of the topic. Will it become part of my general knowledge? No. Will I remember it tomorrow? No. Why not? Because my sorry excuse for a brain won't try to absorb it; in fact it will try strenuously to forget it.

          I can think of several reasons for this.  1) I won't leave the safety and familiarity of base ten. After a lifetime of base-ten, base-two is disorienting and disturbing. If I were forced to live in a house with pyramidal rooms, I could do it; but as soon as I was released, I would return to a cubical house. Someone who is shaky in math to begin with, clings to the part that he finds to be solid and doesn't venture into the whirlwind of incomprehensible artifacts outside.  2) The space in my head set aside for mathematics is entirely occupied by base-ten. I use it constantly and value it as a trusty tool. I can see no way, since I don't design computers, that binary can be useful in my everyday life.  

       3) This is purely subjective, but perhaps worth mentioning. Binary arithmetic seems to me like a language of ants. I am not an entomologist or even a biologist. I don't want to know what the ants are saying. I do want to know what the Russians and Italians and Spanish are saying and I study their literatures. My mind accepts and always finds more room for information about these languages even as it refuses to accommodate binary. I know that computers and the modern world could not exist without the ants and I am grateful for all of it. But I am resigned to the sad fact that their language will always be inaccessible to me. Hope this helps,   

                                                                                                                                                                                                                                                                                                                                                                                                            marty a.

 

 

 

 

 

----- Original Message -----

From: "Mirek Dobsicek" <m.dobsicek@...>

To: <everything-list@...>

Sent: Saturday, August 22, 2009 11:05 AM

Subject: Re: The seven step series

>

> m.a. wrote:
>> a towel into the ring.
>> I simply don't have the sort of mind that takes to juggling letters,
>> numbers and symbols in increasingly fine-grained, complex arrangements.
>
> [...]
>
> Marty,
>
> If I can ask, I'd be really interested what do you think of this
> socratic experiment
> http://www.garlikov.com/Soc_Meth.html

>
> Cheers,
> mirek
>
>
>
>
>
>
--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Miroslav Dobsicek]

Hi Marty,

thanks a lot for your reply. I was really interested in whether the
lesson would work with you.

I had the pleasure to teach the binary arithmetic to kids in summer
school camps, in the grammar school and to university students as well.
Some kids/students got it quite easily some did not. And then, recently,
I have read that socratic article. Since I really like and enjoy
teaching, I spent some time analyzing the article and one of the points
I realized is that there was always some sort of satisfaction and
accomplishment at each step taken. And you said you was missing these
feelings during the introduction to the set theory.

So if you have said that you got hooked-up to math by that socratic
method... Bruno would definitely took the hint in his seveth step serii.

Cheers,
 Mirek


m.a. wrote:

>
> Mirek,
>              My previous answer to your question was glib and evasive, I
> apologize for that, but I think your question was misleading as well. In
> an attempt to be kind, you asked my opinion, from a pedagogical
> POV, of a lesson designed to make binary arithmetic simple enough for
> third-grade students. I think that what you really wondered was whether
> the lesson would work with a math-challenged adult like me. So, because
> I believe you to be genuinely and unmaliciously curious and in the
> interest of science, I'll try to describe my experience of this lesson.
>            Did it teach me about binary numbers? The answer must be
> "Yes" and "No". As I studied the lesson step by step, I understood each
> point and felt at the end, that I had a solid grasp of the topic. Will
> it become part of my general knowledge? /No/. Will I remember it
> tomorrow? /No/. Why not? Because my sorry excuse for a brain won't try
> to absorb it; in fact it will try strenuously to forget it.
>           I can think of several reasons for this.  1) I won't leave the
> safety and familiarity of base ten. After a lifetime of base-ten,
> base-two is disorienting and disturbing. If I were forced to live in a
> house with pyramidal rooms, I could do it; but as soon as I was
> released, I would return to a cubical house. Someone who is shaky in
> math to begin with, clings to the part that he finds to be solid and
> doesn't venture into the whirlwind of incomprehensible artifacts
> outside.  2) The space in my head set aside for mathematics is entirely
> occupied by base-ten. I use it constantly and value it as a trusty tool.
> I can see no way, since I don't design computers, that binary can be
> useful in my everyday life.  
>        3) This is purely subjective, but perhaps worth mentioning.
> Binary arithmetic seems to me like a language of ants. I am not an
> entomologist or even a biologist. I don't want to know what the ants are
> saying. I /do/ want to know what the Russians and Italians and Spanish
> are saying and I study their literatures. My mind accepts and always
> finds more room for information about these languages even as
> it refuses/ /to accommodate binary. I know that computers and the modern
> world could not exist without the ants and I am grateful for all of it.
> But I am resigned to the sad fact that their language will always be
> inaccessible to me. Hope this helps,  
>                                                                                                                                                                                                                                                                                                                                                                                                            
> marty a .
>  
>  
>  
>  
>  
> ----- Original Message -----
> From: "Mirek Dobsicek" < m.dobsicek@...
> <mailto:m.dobsicek@...> >
> To: < everything-list@...
> <mailto:everything-list@...> >
> Sent: Saturday, August 22, 2009 11:05 AM
> Subject: Re: The seven step series
>
>>
>> m.a. wrote:
>>> a towel into the ring.
>>> I simply don't have the sort of mind that takes to juggling letters,
>>> numbers and symbols in increasingly fine-grained, complex arrangements.
>>
>> [...]
>>
>> Marty,
>>
>> If I can ask, I'd be really interested what do you think of this
>> socratic experiment
>> http://www.garlikov.com/Soc_Meth.html
> <http://www.garlikov.com/Soc_Meth.html>
>>
>> Cheers,
>> mirek
>>

--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[m.a.-2]

Hello Mirek,
                    Let us recall that Socrates was famous for setting up
straw men who usually agreed to every step of his proof and were finally
forced by logic, against their previous judgments, to accept his
conclusions. I would dearly love to see an unedited video of the Binary
lesson you cite. As a former teacher, I suspect there would be a lot more
"noise" of every variety than is communicated by the clear, short questions
and even shorter answers of this lesson.
                   To his credit, Bruno has definitely tried to supply
interesting situations to illustrate his points, but either they weren't
interesting enough or the problem was too complex to master no matter how
imaginative the presentation. I may never reach the seventh step but from
here, the mountain top looks magnificent with the sun rising behind it.
Best,
                                                                             
                                                                             
                                            marty a.





----- Original Message -----
From: "Mirek Dobsicek" <m.dobsicek@...>
To: <everything-list@...>
Sent: Wednesday, August 26, 2009 7:10 AM
Subject: Re: Learning binary numbers



Hi Marty,

thanks a lot for your reply. I was really interested in whether the
lesson would work with you.

I had the pleasure to teach the binary arithmetic to kids in summer
school camps, in the grammar school and to university students as well.
Some kids/students got it quite easily some did not. And then, recently,
I have read that socratic article. Since I really like and enjoy
teaching, I spent some time analyzing the article and one of the points
I realized is that there was always some sort of satisfaction and
accomplishment at each step taken. And you said you was missing these
feelings during the introduction to the set theory.

So if you have said that you got hooked-up to math by that socratic
method... Bruno would definitely took the hint in his seveth step serii.

Cheers,
 Mirek





--~--~---------~--~----~------------~-------~--~----~
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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

On 26 Aug 2009, at 13:10, Mirek Dobsicek wrote:

> So if you have said that you got hooked-up to math by that socratic
> method... Bruno would definitely took the hint in his seveth step  
> serii.



I appreciate very much the Socratic method, and I apply it as much as  
possible. The UDA itself is a sequence of questions, and I teach  
students mainly by asking questions.

But this really can work only if the students ask themselves questions  
too.

For some reason some people does not dare to ask question. I think  
they could be afraid to slow me down, but it does not matter, given  
that there is no deadline. I try to encourage to ask questions, even  
out-of-line, but without too much success. I guess a question of taste  
is involved, and personal history with math, lack of thrust in  
oneself, and I can't force anybody to take the time to study, prepare  
questions, etc.

Of course, I don't think I could use a pure socratic method, like in  
your example, because there is much more material involved.

Another difficulty comes from the fact that the level and background  
of those participating are very different, and it is hard, especially  
with so few feedback to satisfy everybody. It is already very  
different according to the fact that you have or not get some "modern  
math" in high school or not ...

I am preparing, slowly (I'm rather busy),  the next "seven step  
serie". Please ask question if anything is unclear. Any question or  
remark can help, you, me, and some others.

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

[Bruno Marchal]

Hi,

I sum up, a little bit, and then I go quickly, just to provide some motivation for the sequel.

We have seen the notion of set. We have seen examples of finite sets and infinite sets.

For example the sets 

A = {0, 1, 2},

B = {2, 3}

are finite.

The set N = {0, 1, 2, 3, ...} is infinite.

We can make the union of sets, and their intersection:

A union B = {x such-that x is in A OR x is in B} = {0, 1, 2, 3}

A intersection B = {x such-that x is in A AND x (the same x) is in B} = {2}. 2 is the only x being both in A and B.

OK?

We have seen the notion of subset. X is a subset of Y, if each time that x is in X, x is also in Y.

And we have seen the notion of powerset of a set. The powerset is the set of all subset of a set.

Example: the powerset of {2, 3} is the set {{ }, {2}, {3}, {2, 3}}.

OK?

In particular we have seen that the number of element of the powerset of a set with n elements is 2^n.

Example: {2, 3} has two elements, and the powerset of {2, 3}, i.e.  {{ }, {2}, {3}, {2, 3}} has 2^2 = 4 elements. OK?

We have seen the notion of function from a set A to a set B.

It is just a set of couples (x, y) with x in A and y in B. x is supposed to be any elements of A, and y some element of B.

To be a function, a set of couples has to verify the *functional condition* that no x is send to two or more different y. This is because we want y be depending on x. Think about the function which describes how the temperature  evolves with respect to time: an instant t cannot be "send" on two different temperature.

Let A = {1, 2} and B = {a, b, c}

F1 = {(1, a), (2, a)}

F2 = {(1, c}, (2, a)}

F1 and F2 are functions. 

But the following are not:

G1 = {(1, a), (2, b}, (2, c)}  because 2 is send on two different elements

G2 = {(1, a), (2, b), (1, b)} because 1 is send on two different elements.

OK?

We have then consider the set of all functions from A to B, written B^A, and seen that this number is equal to 

card(B) ^card(A)  where card(A) is the number of elements of A.    A is supposed to be a finite set, and later we will see how Cantor will generalize the notion of cardinal for infinite sets.

We have then studied the notion of bijection.

A function from A to B is a bijection from A to B when it is both

- ONE-ONE  two different elements of A are send to two different elements of B

- ONTO, this means that all elements of B are in the range of the function, i.e. for any y in B there is some couple (x, y) in the function.

Example: F from {a, b} to {1, 2} with F = {(a, 1}, (b, 2)} is a bijection, but G = {(a, 1), (b, 1)} is not because G is not ONTO, nor ONE-ONE.

OK?

We have seen that if A and B are two finite sets, then we have

A and B have the same number of element if and only if there exists a bijection from A to B.

OK?

Now I can give you the very ingenious idea from Cantor. Cantor will say that two INFINITE sets have the same cardinality if and only if there exists a bijection between them.

This leads to some surprises.

Let N = {0, 1, 2, 3, ...} be the usual set of all natural numbers. This is obviously an infinite set, all right?

Let 2N = {0, 2, 4, 6, ....} be the set of even numbers. This is obviously a subset of N OK?, and actually an infinite subset of N.

Now consider the function from N to 2N which send each n on 2*n. This function is one-one. Indeed if n is different from m, 2*n is different from 2*m. OK?

And that function, from N to 2N is onto. Indeed any element of 2N, has the shape 2*n for some n, and (n, 2*n) belongs to the function.

In extension the bijection is {(0, 0), (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), (6, 12), ...} 

So here we have the peculiar fact that a bijection can exist between a set and some of its proper subset. (A subset of A is a proper subset of A if it is different of A). 

The first who discovered this is GALILEE. But, alas, he missed Cantor discovery. Like Gauss later, such behavior was for them an argument to abandon the study of infinite sets. They behave too much weirdly for them.

OK?

At first sight we could think that all infinite sets have the same cardinality. After all those sets are infinite, how could an infinite  set have a bigger cardinality than another infinite set? This is the second surprise, and the main discovery of Cantor: the fact that there are some infinite sets B such that there is no bijection between N and B.

Cantor will indeed show that there is no bijection between N and N^N, nor between N and 2^N. We will study this.

Cantor will prove a general theorem, know as Cantor theorem, which asserts that for ANY set A, there are no bijection between A and the powerset of A.

The powerset operation leads to a ladder of "bigger infinities".  I will come back with some detail later.

Some surprises were BAD surprises. Conceptual problems which Cantor will "hide" in its desk, to treat them later. The so-called paradoxes of "naïve set theory". The root of what has been called the crisis in mathematics.

For example, we could naively consider the set of all sets. Often called the universal set, or Universe (of sets). Surely no set can be bigger that this one? But by Cantor theorem the powerset of the universe has to be bigger than the universe. So there is a problem.

And the naïve conception of sets will lead to many other problems. Torgny Tholerus has mentioned some other problems, if you remember.

So what?

Mainly three approaches have been proposed to solve those conceptual problems.

1) The most liberal one, suggested by Hilbert, who was fond of Cantor theory. He said that no one will drive us away from Cantor Paradise. He suggested to build a formal system capable of talking about sets, and capable of proving the main theorem of Cantor, but free of the paradoxes. This will lead to the modern axiomatic trend in mathematics. Hilbert asked for the proof of the consistency of such formal theories, and this will be shown just impossible, by Gödel. Despite this, most mathematicians have followed this path, explicitly or implicitly. In most axiomatic set theories, the axiom will prevent, for example, the existence of a universal set or universe. To be sure, some highly non standard axiomatic set theory allows a Universal set to exist, for example Quine new foundations (cf some post by Brian and Adam).

2) The least liberal one, suggested by Brouwer (the main opponent to Cantor and Hilbert). To abandon classical logic, and "set realism". This consists in abandoning the law of the excluded middle (p or ~p) in mathematics, and this will lead to intuitionist mathematics and philosophy, which is a form of mathematical solipsism. 

3) Intermediate solutions. One will consist in searching a weaker notion of function, capable of satisfying both the intuitionist and the classical mathematicians. This will lead mathematicians to the notion of computable functions, and when Cantor reasoning is applied again, this will lead to the (mathematical) notion of universal machine. In my opinion: this is the biggest discovery ever done by humanity. And both UDA and AUDA are just non sensical without that discovery (and this explains why I insist on this). Note that from empirical data, we can guess that "nature" has done that discovery and has exploited it again, and again, and again, and again ....

                                                                                           * * *

Exercise: if you have not yet done them, or understand them, please take some time to just think about those questions. I have to solve them properly to proceed. You may try to read Brent's correct answer to some of those questions.

Show that there is a bijection between the following sets:

N and 2N, 3N, 4N, 5N, ....     (nN = the set of multiple of n).

N and Z    (Z = all integers, that is postive and negative integers, Z = {... -3, -2, -1, 0, 1, 2, 3, ...}

N and Q  (Q = the reduced fractions, or the decimal periodics)

N and NxN 

N and NxNxN.

The powerset of A (finite set) and the set of functions from A to {0, 1}

The powerset of N and the set of functions from N to {0, 1}.

The powerset of N and the real numbers.  (real numbers = finite of infinite decimals).

                                    *                               *                                    *

Take it easy, and enjoy if you have the time and taste,

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@...
To unsubscribe from this group, send email to everything-list+unsubscribe@...
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---