The seven step series

[Bruno Marchal]

I give the solution to the last exercises.

On 26 Aug 2009, at 19:06, Bruno Marchal wrote:

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 2N. Just take the function F which sends any number n on 2*n. that function is the set

{(0,0), (1, 2), (2, 4), (3, 6), (4, 8),  ...}

It is one-one. Indeed suppose it is not one-one. This means that a number n and a different number m are send on the same number k. This means k = 2n = 2m. Divide by two, and you get n = m. So n = m, and n different from m. Absurd. So F is one -one.

And F is onto. If F was not onto, it means there is an even number, in 2N, which cannot be divided by two. Absurd.

Note. There is a "canonical" bijection between the set of all functions from N to N, i.e. N^N, and the set of infinite sequence of number.

It is, for example,  the association between

{(0,0), (1, 2), (2, 4), (3, 6), (4, 8),  ...}    and 0, 2, 4, 6, 8, 10, ....

A function from N to N is really an infinite sequence of natural numbers. The bijection is canonical, because it is fixed by the "canonic" order on the natural numbers : 0, 1, 2, 3, .... So, a sequence of numbers like 1, 1, 1, 2, 1, 1, 78, 2, 1, .... could be seen as a shorthand for the function (which really is a set of couples):

{(0,1), (1, 1), (2, 1), (3, 2), (4, 1),  (5, 1), (6, 78), (7, 2), (8, 1), ...} 

Mathematician are used to identify objects when there are such "canonical" bijection.

----

N and 3N. same reasoning. Using the note I can write the bijection from N to 3N, by the sequence

0, 3, 6, 9, 12, 15, 18, 21, 24, ...

It is onto (on 3N, of course), because all multiple of three appears in the sequence, and it is one-one, because no two different numbers can give identical results when multiplied by three.

Same reasoning for any nN. OK?

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

0, 1, -1, 2, -2, 3, -3, 4, -4, -5, -5, ....

Onto, clearly I go through all integers. There is no integers which will never appear, soon or later, in the sequence.

One-one: I never put twice the same integers in the sequence, by construction. OK?

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

I give two proofs. 

a) I gave the exercise consisting in showing that there is a bijection between N and  A+, the set of finite words on an alphabet A. An alphabet is just a finite set. We call the element of an alphabet letter. I will give the solution of that exercise later. In the meantime, I use it. Please recall me to give the answer if I forget, OK? This is actually important, and those who follows this list should remember, perhaps, I have already prove it more than once (cf lexicographical order).

The bijection from N to Q follows directly from this when you see that any fraction can be described by a word on the alphabet {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, /}. Of course this gives a bijection between N and the fractions. For having a bijection between N and the rational numbers, use Euclid Algorithm for reducing the fraction, and be careful not to put a rational numbers twice in the sequence.

This infinite task gives you the description of a bijection between N and Q.

b) I use the exercise below, already solved by Brent. I explain:

N and NxN 

I wrote the elements of NxN in the usual rectangular cartesian way:

. 

.

(0, 3) (1, 3) (2, 3) (3, 3) ...

(0, 2) (1, 2) (2, 2) (3, 2) ...

(0, 1) (1, 1) (2, 1) (3, 1) ...

(0, 0) (1, 0) (2, 0) (3, 0) ...

OK?

Now, take a pen, and pass on the obliques lines :

(0, 0)

(0, 1) (1, 0)

(0, 2) (1, 1) (2, 0)

(0, 3) (1, 2) (2, 1) (3, 0)

etc.

And hang them together: obtaining a sequence going through all couples in NxN:

(0, 0) (0, 1) (1, 0) (0, 2) (1, 1) (2, 0) (0, 3) (1, 2) (2, 1) (3, 0) ....

To extract a bijection between N and Q, from this just interpret the couples as fraction (x, y) ===> x/y. Put x/y in your sequence is satisfied: y is different from 0, x/y has been reduced, and x/y does not already belong to the sequence.

Note that this is really an algorithm, which shows that not only there is abijection between N and Q, but the bijection is computable (as we will study later). Those who can program can write a program generating (soon or later) all rational numbers. And all couples of NxN, etc. Up to now, all bijections given were computable.

N and NxNxN.

NxNxN is really Nx(NxN), which can be made cartesian:

etc.

3 etc.

2    (0, 0, 2)   (0, 1, 2)  etc.

1    (0, 0, 1)   (0, 1, 1)  etc.

0    (0, 0, 0)   (0, 1, 0)   (1, 0, 0) etc.

      (0, 0)       (0, 1)       (1, 0)        (0, 2)     (1, 1) etc.

OK? By hanging the obliques in the manner described above, you get a sequence going through all elements of NxNxN.

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

I explain on an example:

Take the set {0, 1, 2, 3, 4, 5}. It has six elements.

We have to find a bijection from its powerset (set of its subsets) and the set {0, 1}^{0, 1, 2, 3, 4, 5}, i.e. the set of functions from {0, 1, 2, 3, 4, 5} to {0, 1}.

Well the "canonical" bijection will consist in associating a subset to the function which send the element of the subset on 1, and the elements not in the subset, on 0.

For example: {2, 5} is send, by that canonical bijection, on {(0, 0), (1, 0), (2, 1), (3, 0), (4, 0), (5, 1)}

{ } is send on {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0)}

{0, 1, 2, 3, 4, 5} is send on {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1)}

Such a function from a subset B of A to {0, 1} is the characteristic function of B in A.

Convince yourself that the function which send a subset on such a characteristic function, is one-one and onto. No two subsets are send on a same characteristic function, and all subsets have a characteristic function. So the powerset of A will be often identified with the set {0, 1}^A.

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

The fact that a subset can be infinite does not change anything. For example the subset 2N of N will have the following characteristic function:

{(0, 1), (1, 0), (2, 1), (3, 0), (4, 1), (5, 0), (6, 1), (7, 0), (8, 1), ....

which can be written 

1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ....

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

Hints for those interested. It is more involved. We will not need this in the sequel, but it smoothes the background to be aware of the result, and have some idea how this can be justified.

You can see there is a bijection between the real numbers in the open interval (0 1) and 2^N, by writing them in binary. They will have the shape 0, 0100110 ...., that is mainly a infinite sequence of 0 and 1, which can be interpreted as characteristic functions for subsets of N. 

But in the decimal notation we have that 10, 99999... is the same as 11,0000000 ... . You can verify this if you remember the technic I gave you to find a fraction corresponding to a periodic decimal. For the same reason, in binary, the real number

0,100000.... is the same as 0,0111111.... The subset {1} should not have the same characteristic sequence than {2, 3, 4, 5, 6, 7, ...} as would happen with 0,100000... equal to 0,011111111..... You have to work a bit more for making this working properly.

Then you can find a bijection between the interval (0, 1) and R, by using some trigonometric function.

Next: I will do some antic mathematic, and prove the irrationality of the square root of two, for many reasons, including some thought about what is a proof. And then I will prove Cantor theorem. Then I will define what is a computable function. I will explain why Cantor "reasoning" seems to prove, in that context, the impossibility of the existence of universal machine, and why actually Cantor "reasoning" will just make them paying the big price for their existence.

Any question, any comment?  I guess that I am too quick for some, too slow for others.

Don't forget the exercise: show that there is always a bijection between A+ and N. 

(A+ = set of finite strings on the alphabet A). This is important and will be used later.

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

[Miroslav Dobsicek]

Hi Bruno,

I am puzzled by one thing. Is the Axiom of dependent choice (DC) assumed
implicitly somewhere here or is it obvious that there is no need for it
(so far)?

Thanks!
 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]

Hi Mirek,


On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote:


> I am puzzled by one thing. Is the Axiom of dependent choice (DC)  
> assumed
> implicitly somewhere here or is it obvious that there is no need for  
> it
> (so far)?

I don't see where I would have use it, and I don't think I will use  
it. Cantor's theorem can be done in ZF without any form of choice  
axioms.  I think.

Well, I may use the (full) axiom of choice by assuming that all  
cardinals are comparable, but I don't think I will use this above some  
illustrations.

If you suspect I am using it, don't hesitate to tell me. But so far I  
don't think I have use it.

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

[Miroslav Dobsicek]

The reason why I am puzzled is that I was recently told that in order to
prove that

* the union of countably many countable sets is countable

one needs to use at least the Axiom of Countable Choice (+ ZF, of
course). The same is true in order to show that

* a set A is infinite if and only if there is a bijection between A and
a proper subset of A

(or in another words,

* if the set A is infinite, then there exists an injection from the
natural numbers N to A)

Reading the proofs, I find it rather subtle that some (weaker) axioms of
choices are needed. The subtlety comes from the fact that many textbook
do not mention it.

In order to understand a little bit more to the axiom of choice, I am
thinkig if it has already been used in the material you covered or
whether it was not really needed at all. Not being able to answer it, I
had to ask :-)

Please note that I don't have any strong opinion about the Axiom of
Choice. Just trying to understand it. May I ask about your opinion?

Mirek





Bruno Marchal wrote:

> Hi Mirek,
>
>
> On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote:
>
>
>> I am puzzled by one thing. Is the Axiom of dependent choice (DC)  
>> assumed
>> implicitly somewhere here or is it obvious that there is no need for  
>> it
>> (so far)?
>
> I don't see where I would have use it, and I don't think I will use  
> it. Cantor's theorem can be done in ZF without any form of choice  
> axioms.  I think.
>
> Well, I may use the (full) axiom of choice by assuming that all  
> cardinals are comparable, but I don't think I will use this above some  
> illustrations.
>
> If you suspect I am using it, don't hesitate to tell me. But so far I  
> don't think I have use it.
>
> Bruno
>

--~--~---------~--~----~------------~-------~--~----~
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]

Ouh la la ... Mirek,

You may be right, but I am not sure. You may verify if this was not in  
a intuitionist context. Without the excluded middle principle, you may  
have to use countable choice in some situation where classical logic  
does not, but I am not sure.
I know that in intuitionist math, the definition of infinite set by  
"there is an injection on a subset" is NOT equivalent with the  
traditional definition.

My opinion on choice axioms is that there are obviously true, and this  
despite I am not a set realist.

I am glad, nevertheless that ZF and ZFC have exactly the same  
arithmetical provability power, so all proof in ZFC of an arithmetical  
theorem can be done without C, in ZF. This can be seen through the use  
of Gödel's constructible models.

I use set theory informally at the metalevel, and I will not address  
such questions. As I said, I use Cantor theorem for minimal purpose,  
and as a simple example of diagonalization.

I am far more puzzled by indeterminacy axioms, and even a bit  
frightened by infinite game theory .... I have no intuitive clues in  
such fields. And yet, the few I understand makes me doubt even of the  
consistency of ZFC. But this is 99% due, I think, to my own  
incompetence in the subject.

Bruno


On 01 Sep 2009, at 14:30, Mirek Dobsicek wrote:

>
> The reason why I am puzzled is that I was recently told that in  
> order to
> prove that
>
> * the union of countably many countable sets is countable
>
> one needs to use at least the Axiom of Countable Choice (+ ZF, of
> course). The same is true in order to show that
>
> * a set A is infinite if and only if there is a bijection between A  
> and
> a proper subset of A
>
> (or in another words,
>
> * if the set A is infinite, then there exists an injection from the
> natural numbers N to A)
>
> Reading the proofs, I find it rather subtle that some (weaker)  
> axioms of
> choices are needed. The subtlety comes from the fact that many  
> textbook
> do not mention it.
>
> In order to understand a little bit more to the axiom of choice, I am
> thinkig if it has already been used in the material you covered or
> whether it was not really needed at all. Not being able to answer  
> it, I
> had to ask :-)
>
> Please note that I don't have any strong opinion about the Axiom of
> Choice. Just trying to understand it. May I ask about your opinion?
>
> Mirek
>
>
>
>
>
> Bruno Marchal wrote:
>> Hi Mirek,
>>
>>
>> On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote:
>>
>>
>>> I am puzzled by one thing. Is the Axiom of dependent choice (DC)
>>> assumed
>>> implicitly somewhere here or is it obvious that there is no need for
>>> it
>>> (so far)?
>>
>> I don't see where I would have use it, and I don't think I will use
>> it. Cantor's theorem can be done in ZF without any form of choice
>> axioms.  I think.
>>
>> Well, I may use the (full) axiom of choice by assuming that all
>> cardinals are comparable, but I don't think I will use this above  
>> some
>> illustrations.
>>
>> If you suspect I am using it, don't hesitate to tell me. But so far I
>> don't think I have use it.
>>
>> 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
-~----------~----~----~----~------~----~------~--~---

[Miroslav Dobsicek]

Bruno Marchal wrote:
> Ouh la la ... Mirek,
>
> You may be right, but I am not sure. You may verify if this was not in  
> a intuitionist context. Without the excluded middle principle, you may  
> have to use countable choice in some situation where classical logic  
> does not, but I am not sure.

Please see
http://en.wikipedia.org/wiki/Countable_set
the sketch of proof that the union of countably many countable sets is
countable is in the second half of the article. I don't think it has
anything to do with the law of excluded middle.

Similar reasoning is described here
http://at.yorku.ca/cgi-bin/bbqa?forum=ask_a_topologist_2008;task=show_msg;msg=1545.0001


> My opinion on choice axioms is that there are obviously true, and this  
> despite I am not a set realist.

OK, thanks.

> I am glad, nevertheless that ZF and ZFC have exactly the same  
> arithmetical provability power, so all proof in ZFC of an arithmetical  
> theorem can be done without C, in ZF. This can be seen through the use  
> of Gödel's constructible models.

I am sorry, but I have no idea what might an "arithmetical provability
power" refer to. Just give me a hint ...

> I use set theory informally at the metalevel, and I will not address  
> such questions. As I said, I use Cantor theorem for minimal purpose,  
> and as a simple example of diagonalization.

OK. Fair enough.

> I am far more puzzled by indeterminacy axioms, and even a bit  
> frightened by infinite game theory .... I have no intuitive clues in  
> such fields.

Do you have some links please? Just to check it and write down few new
key words.

Cheers,
 Mirek

> On 01 Sep 2009, at 14:30, Mirek Dobsicek wrote:
>
>> The reason why I am puzzled is that I was recently told that in  
>> order to
>> prove that
>>
>> * the union of countably many countable sets is countable
>>
>> one needs to use at least the Axiom of Countable Choice (+ ZF, of
>> course). The same is true in order to show that
>>
>> * a set A is infinite if and only if there is a bijection between A  
>> and
>> a proper subset of A
>>
>> (or in another words,
>>
>> * if the set A is infinite, then there exists an injection from the
>> natural numbers N to A)
>>
>> Reading the proofs, I find it rather subtle that some (weaker)  
>> axioms of
>> choices are needed. The subtlety comes from the fact that many  
>> textbook
>> do not mention it.
>>
>> In order to understand a little bit more to the axiom of choice, I am
>> thinkig if it has already been used in the material you covered or
>> whether it was not really needed at all. Not being able to answer  
>> it, I
>> had to ask :-)
>>
>> Please note that I don't have any strong opinion about the Axiom of
>> Choice. Just trying to understand it. May I ask about your opinion?
>>
>> Mirek
>>
>>
>>
>>
>>
>> Bruno Marchal wrote:
>>> Hi Mirek,
>>>
>>>
>>> On 01 Sep 2009, at 12:25, Mirek Dobsicek wrote:
>>>
>>>
>>>> I am puzzled by one thing. Is the Axiom of dependent choice (DC)
>>>> assumed
>>>> implicitly somewhere here or is it obvious that there is no need for
>>>> it
>>>> (so far)?
>>> I don't see where I would have use it, and I don't think I will use
>>> it. Cantor's theorem can be done in ZF without any form of choice
>>> axioms.  I think.
>>>
>>> Well, I may use the (full) axiom of choice by assuming that all
>>> cardinals are comparable, but I don't think I will use this above  
>>> some
>>> illustrations.
>>>
>>> If you suspect I am using it, don't hesitate to tell me. But so far I
>>> don't think I have use it.
>>>
>>> Bruno
>>>

--~--~---------~--~----~------------~-------~--~----~
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 02 Sep 2009, at 17:16, Mirek Dobsicek wrote:

>
> Bruno Marchal wrote:
>> Ouh la la ... Mirek,
>>
>> You may be right, but I am not sure. You may verify if this was not  
>> in
>> a intuitionist context. Without the excluded middle principle, you  
>> may
>> have to use countable choice in some situation where classical logic
>> does not, but I am not sure.
>
> Please see
> http://en.wikipedia.org/wiki/Countable_set
> the sketch of proof that the union of countably many countable sets is
> countable is in the second half of the article. I don't think it has
> anything to do with the law of excluded middle.

I was thinking about the equivalence of the definitions of infinite  
set (self-injection, versus injection of omega), which, I think are  
inequivalent without excluded middle, but perhaps non equivalent with  
absence of choice, I don't know)


>
> Similar reasoning is described here
> http://at.yorku.ca/cgi-bin/bbqa?forum=ask_a_topologist_2008;task=show_msg;msg=1545.0001

I am not sure ... I may think about this later ...

>
>
>> My opinion on choice axioms is that there are obviously true, and  
>> this
>> despite I am not a set realist.
>
> OK, thanks.
>
>> I am glad, nevertheless that ZF and ZFC have exactly the same
>> arithmetical provability power, so all proof in ZFC of an  
>> arithmetical
>> theorem can be done without C, in ZF. This can be seen through the  
>> use
>> of Gödel's constructible models.
>
> I am sorry, but I have no idea what might an "arithmetical provability
> power" refer to. Just give me a hint ...

By arithmetical provability power, I mean the set of first order  
arithmetical sentences provable in the theory, or by a machine.
I will say, for example,  that the power of Robinson Arithmetic is  
smaller than the power of Peano Aritmetic, *because* the set of  
arithmetical theorems of Robinson Ar. is included in the set of  
theorems of Peano Ar. Let us write this by RA < PA. OK?
Typically, RA < PA < ZF = ZFC < ZF + k  (k = "there exists a  
inaccessible cardinal").
The amazing thing is ZF = ZFC (in this sense!). Any proof of a theorem  
of arithmetic using the axiom of choice, can be done without it.

>
>> I use set theory informally at the metalevel, and I will not address
>> such questions. As I said, I use Cantor theorem for minimal purpose,
>> and as a simple example of diagonalization.
>
> OK. Fair enough.
>
>> I am far more puzzled by indeterminacy axioms, and even a bit
>> frightened by infinite game theory .... I have no intuitive clues in
>> such fields.
>
> Do you have some links please? Just to check it and write down few new
> key words.

This is not too bad, imo, (I should have use "determinacy", it is a  
better key word):

http://en.wikipedia.org/wiki/Determinacy

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 31 Aug 2009, at 19:31, Bruno Marchal wrote:

>
> Next: I will do some antic mathematic, and prove the irrationality  
> of the square root of two, for many reasons, including some thought  
> about what is a proof. And then I will prove Cantor theorem. Then I  
> will define what is a computable function. I will explain why Cantor  
> "reasoning" seems to prove, in that context, the impossibility of  
> the existence of universal machine, and why actually Cantor  
> "reasoning" will just make them paying the big price for their  
> existence.
>
> Any question, any comment?  I guess that I am too quick for some,  
> too slow for others.
>
> Don't forget the exercise: show that there is always a bijection  
> between A+ and N.
> (A+ = set of finite strings on the alphabet A). This is important  
> and will be used later.

I illustrate the solution on a simple alphabet.

An alphabet is just any finite set. Let us take A = {a, b, c}.
A+ is the set of words made with the letters taken in A. A "word" is  
any finite sequence of letters.

To build the bijection from N to A+, the idea consists in enumerating  
the words having 0 letters (the empty word), then 1 letter, then 2  
letters, then 3 letters, and so on. For each n there is a finite  
numbers of words of length n, and those can be ordered alphabetically,  
by using some order on the alphabet. In our case we will decide that a  
 > b, and b> c (a > b should be read "a is before b").

So we can send 0 on the empty word. Let us note the empty word as *.

0 ------> *

then we treat the words having length 1:

1 ------>  a
2 ------>  b
3 ------>  c

then the words having length 2:

4 -------> aa
5 ------>  ab
6 ------>  ac

7 ------>  ba
8 ------>  bb
9 ------>  bc

10 ------> ca
11 ------> cb
12 ------> cc

Then the words having lenght 3. There will be a finite number of such  
words, which can be ranged alphabetically,

etc.

Do you see that this gives a bijection from N = {0, 1, 2, 3 ...} to A+  
= {*, a, b, c, aa, ab, ac, ba, bb, bc, ...}

It is one-one: no two identical words will appears in the enumeration.
It is onto: all words will appear soon or later in the enumeration.

I will call such an enumeration, or order, on A+, the lexicographic  
order.

Its mathematical representation is of course the set of couples:

{(0, *), (1, a), (2, b), (3, c), (4, aa), ...}

OK? No question?

Next, I suggest we do some antic mathematics. It will, I think, be  
helpful to study a simple  "impossibility" theorem, before studying  
Cantor theorems, and then the many impossibilities generated by the  
existence of universal machines. It is also good to solidify our  
notion of 'real numbers', which does play some role in the  
computability general issue.


Here are some preparation. I let you think about relationship between  
the following propositions. I recall that: the square root of X  is  Y  
means that Y^2 = X. (It is the 'inverse function of the power 2  
function). The square root of 9 is 3, for example, because 3^2 = 3*3 =  
9. OK?

- There exists incommensurable length  (finite length segment of line  
with no common integral unity)
- the Diophantine equation x^2 = 2(y^2) has no solution  (Diophantine  
means that x and y are supposed to be integers).
- the square root of 2 is irrational (= is not the ratio of integers)
- The square root of 2 has an infinite and never periodic decimal.
- If we want to measure by numbers any arbitrary segment of line, we  
need irrational numbers

Take it easy, explanation will follow. This antic math interlude will  
not presuppose the 'modern math' we have seen so far.

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]

Bruno,
           Just to let you know that while I can't do the exercises, I am
following as best I can. I think I understand that powersets of sets lead to
ladders of larger and larger infinities and hope your exposition of how this
results in the existence of universal machines will be equally clear. Best
wishes,
                                                                             
                                        marty a.


----- Original Message -----
From: "Bruno Marchal" <marchal@...>
To: <everything-list@...>
Sent: Tuesday, September 08, 2009 4:43 AM
Subject: Re: The seven step series

>
>
> On 31 Aug 2009, at 19:31, Bruno Marchal wrote:
>>
>>
>> Any question, any comment?  I guess that I am too quick for some,
>> too slow for others.
>>
> 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 me Marty,
I wish you the best,

Bruno


On 08 Sep 2009, at 14:17, m.a. wrote:

>
> Bruno,
>           Just to let you know that while I can't do the exercises,  
> I am
> following as best I can. I think I understand that powersets of sets  
> lead to
> ladders of larger and larger infinities and hope your exposition of  
> how this
> results in the existence of universal machines will be equally  
> clear. Best
> wishes,
>
>                                        marty a.
>
>
> ----- Original Message -----
> From: "Bruno Marchal" <marchal@...>
> To: <everything-list@...>
> Sent: Tuesday, September 08, 2009 4:43 AM
> Subject: Re: The seven step series
>
>
>>
>>
>> On 31 Aug 2009, at 19:31, Bruno Marchal wrote:
>>>
>>>
>>> Any question, any comment?  I guess that I am too quick for some,
>>> too slow for others.
>>>
>> 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]

This is the last post before we proof Cantor theorem. It is an "antic interlude". We are about 2000 years back in time.

The square root of 2.

It is a number x such that x^2 = 2. It is obviously smaller than 2 and bigger than 1. OK? It cannot be a natural number. But could it be a fraction?

The square root of two is the length of the diagonal of a square with side one unity.

Do you see that? I can't draw, so you have to imagine a square. You may draw it. And then draw or imagine the square which sides the diagonal (of you square unity). Draw it with its diagonals and you will see, in your mind or on the paper that the second square is made of four times the half of your square unity: meaning that the square which sides the diagonal has an area twice the area of the square unity. But this means that if you call d the length of the diagonal of the square unity, you have, by the law of the area of square, d^2 = 2. OK?

So the length of the diagonal d = square root of 2. It is a 'natural' length occurring in geometry (and quantum mechanics!).

The function or operation "taking the square root of two" is the inverse operation of taking the square.

(In term of the couples defining the function as set, it means that if (x, y) belongs-to "taking the square root of two" then (y, x) belongs-to "taking the square of").

Now, please continue to imagine the diagonal, and try to evaluate its length. Is is not clearly less than two unities, and clearly more than one? Is it 3/2 i.e. 1.5? Well, 1.5 should give two when squared, but (1.5)^2 = 2,25. That's too much! Is 1,4?

Oh, 1.4 gives 1.96, not too bad, it is slightly more, may be 1.41? 1.41^2 gives 1,9881, we get closer and closer, but will such a search ends up with the best approximation? This would mean we can divide the side of the square unity in a finite number of smaller unities, and find a sufficiently little unity which could measure the diagonal exactly. It would mean d is equal to p * 1/q, where q is the number of divisions of the side of the square unity. If we find such a fraction the diagonal and the sided would be said commensurable.

 

Is there such a fraction?

It is not 3/2, we know already. Is it 17/12 (= 1,416666666666...)? (1712)^2 = 2,0069444444....). Close but wrong.

Is it 99/70? (= 1,414285714...) (99/70)^2 = 2,000204082...). Very close, but still wrong!

...

is it 12477253282759/8822750406821 ? My pocket computer says that the square of that fraction is 2. Ah, but this is due to its incompetence in handling too big numbers and too little numbers! It is still wrong!

How could we know if that search will end, or not end?

Sometimes, we can know thing in advance. Why, because things obeys laws, apparently.

Which laws of numbers makes the problem decidable?

Here is one:

- a number is even if and only if the square of that number is even, similarly

- a number is odd if and only if the square of that number is odd.

Taking the square of an integer leaves invariant the parity (even/odd) of the number.

Why? suppose n is odd. There will exist a k (belonging to {0, 1, 2, 3, ...} such that n = 2k+1. OK? So n^2 = (2k+1)^2 = 4k^2 + 4k + 1, OK? and this is odd. OK. And this is enough to show that if n^2 is even, then n is even. OK?

And why does this answer the question.

Let us reason 'by absurdo".

Suppose that there are number p and q such (p/q)^2 = 2. And let us suppose we have already use the Euclid algorithm to reduce that fraction; so that p and q have no common factor. 

 p^2 / q^2 = 2. OK? Then p^2 = 2q^2 (our 'Diophantine equation). OK?

Then p^2 is even. OK? (because it is equal to 2 * an integer).

Then p is even. OK? (by the law above).

This means p is equal to some 2*k (definition of even number). OK?

But p^2 = 2q^2 (see above), and substituting p by 2k, we get 4k^2 = 2q^2, and thus, dividing both sides by 2, we get that 2k^2 = q^2.

So q^2 is even. OK?

So q is even. (again by the law above). OK?

So both p and q are even, but this means they have a common factor (indeed, 2), and this is absurd, given that the fraction has been reduced before.

So p and q does not exist, and now we know that our search for a finite or periodic decimal, or for a fraction, will never end.

The diophantine equation x^2 = 2y^2 has no solution in the integers, and the number sqrt(2) = square root of two is not the ratio of two integers/ Such a number will be said irrational. If we want associate a number to each possible length of line segment, we have to expand the rational number (the reduced fraction, the periodic decimal) with the irrational number.

The numerical value of the sqrt(2) can only be given through some approximation, like

sqrt(2) =  1,414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 376 948 073 176 679 737 990 732 478...

OK?

I have to go now.

Please ask any question.

Does the "beginners" see that (2k+1)^2 = 4k^2 + 4k + 1? This comes from the 'remarkable product (a+b)^2 = a^2 + 2ab + b^2. Could you prove this geometrically (in your head or with a drawing)? Hint: search the area of a rectangle which sides (a+b).

In proof by 'reduction ad absurdo', sometimes Brent says this proofs only the result OR the fact that an error occur in the proof. Please comment.

I have not the time to give easy exercise, so I give one which is not so easy. try to use the fundamental theorem of arithmetic (saying that all natural numbers have a unique decomposition into prime factor to generalize this result: if n is not a square number (like 1, 4, 9, 16, 25, ...) then sqrt(n) is irrational. Guess who proves this theorem originally? Theaetetus! (well I read that somewhere).

This ends the antic interlude.

Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets.

After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc.

Bruno

On 08 Sep 2009, at 10:43, Bruno Marchal wrote:

On 31 Aug 2009, at 19:31, Bruno Marchal wrote:

Next: I will do some antic mathematic, and prove the irrationality  

of the square root of two, for many reasons, including some thought  

about what is a proof. And then I will prove Cantor theorem. Then I  

will define what is a computable function. I will explain why Cantor  

"reasoning" seems to prove, in that context, the impossibility of  

the existence of universal machine, and why actually Cantor  

"reasoning" will just make them paying the big price for their  

existence.

Any question, any comment?  I guess that I am too quick for some,  

too slow for others.

Don't forget the exercise: show that there is always a bijection  

between A+ and N.

(A+ = set of finite strings on the alphabet A). This is important  

and will be used later.

I illustrate the solution on a simple alphabet.

An alphabet is just any finite set. Let us take A = {a, b, c}.
A+ is the set of words made with the letters taken in A. A "word" is  
any finite sequence of letters.

To build the bijection from N to A+, the idea consists in enumerating  
the words having 0 letters (the empty word), then 1 letter, then 2  
letters, then 3 letters, and so on. For each n there is a finite  
numbers of words of length n, and those can be ordered alphabetically,  
by using some order on the alphabet. In our case we will decide that a  

b, and b> c (a > b should be read "a is before b").

So we can send 0 on the empty word. Let us note the empty word as *.

0 ------> *

then we treat the words having length 1:

1 ------>  a
2 ------>  b
3 ------>  c

then the words having length 2:

4 -------> aa
5 ------>  ab
6 ------>  ac

7 ------>  ba
8 ------>  bb
9 ------>  bc

10 ------> ca
11 ------> cb
12 ------> cc

Then the words having lenght 3. There will be a finite number of such  
words, which can be ranged alphabetically,

etc.

Do you see that this gives a bijection from N = {0, 1, 2, 3 ...} to A+  
= {*, a, b, c, aa, ab, ac, ba, bb, bc, ...}

It is one-one: no two identical words will appears in the enumeration.
It is onto: all words will appear soon or later in the enumeration.

I will call such an enumeration, or order, on A+, the lexicographic  
order.

Its mathematical representation is of course the set of couples:

{(0, *), (1, a), (2, b), (3, c), (4, aa), ...}

OK? No question?

Next, I suggest we do some antic mathematics. It will, I think, be  
helpful to study a simple  "impossibility" theorem, before studying  
Cantor theorems, and then the many impossibilities generated by the  
existence of universal machines. It is also good to solidify our  
notion of 'real numbers', which does play some role in the  
computability general issue.


Here are some preparation. I let you think about relationship between  
the following propositions. I recall that: the square root of X  is  Y  
means that Y^2 = X. (It is the 'inverse function of the power 2  
function). The square root of 9 is 3, for example, because 3^2 = 3*3 =  
9. OK?

- There exists incommensurable length  (finite length segment of line  
with no common integral unity)
- the Diophantine equation x^2 = 2(y^2) has no solution  (Diophantine  
means that x and y are supposed to be integers).
- the square root of 2 is irrational (= is not the ratio of integers)
- The square root of 2 has an infinite and never periodic decimal.
- If we want to measure by numbers any arbitrary segment of line, we  
need irrational numbers

Take it easy, explanation will follow. This antic math interlude will  
not presuppose the 'modern math' we have seen so far.

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,

I want to add something.

I said recently to John that the excluded middle principle should be seen as a tolerance-of-ignorance principle. Actually this will play an important role later, and it justifies the "arithmetical realism": what it is, and why it is important.

Let me illustrate this on the following problem. You have to prove the existence of two irrational numbers x and y such that x^y is rational. We don't ask that x is different from y..

This is not obvious. If x is not a fraction, and y is not a fraction, how could we hope that x^y gives a fraction?

Yet a very simple proof shows that there exists such a couple of irrational numbers.

Do you agree that a number x is either rational, or is not rational? 

If you answer yes, you are arithmetical realist. You believe that either there exist integers p and q such that x is equal to p/q, or that such integers don't exist.

We already know that sqrt(2) is irrational. That was the peurpose of the preceding post. OK?

Now, let us consider S = sqrt(2) ^ sqrt(2).

By arithmetical realism, either S is rational or it is not rational. OK?

But if S is rational, then our problem is solved.  x = y = sqrt(2) are not rational, and x^y is rational.

But if S is not rational, then our problem is solved too. Indeed is S is not rational then S^sqrt(2) is a solution. Indeed S^sqrt(2) = [sqrt(2) ^ sqrt(2)]^sqrt(2) = sqrt(2) ^[sqrt(2) * sqrt(2)] = sqrt(2) ^ 2 = 2; which is rational(*).

So by admitting that either sqrt(2) ^ sqrt(2) is rational or is not rational, we know that either sqrt(2) ^ sqrt(2) is our solution of 

[sqrt(2) ^ sqrt(2)]^sqrt(2 is our solution.

So we know that a solution exists(**).

We may feel uneasy here, because although we know there is a solution, we remain unable to provide one. But we were not asked to provide a solution. We are asked if a solution exist. And we know that either S or S^sqrt(2) is a solution. We know that the solution belongs to the set {S, S^sqrt(2)}, although we don't know which one among S and S^sqrt(2) is the solution.

It is like a crime inquest which concludes that the murderer is either Arthur or Penelope, but is incapable to know which one.

Such a proof is called non constructive. It proves that something exists, yet does not provide the existing object. All what the proof provides is a set, and a proof that what we are searching for is in the set. It is in that sense that such a proof provides incomplete information. The non constructive reasoning tolerates some amount of ignorance.

Non constructive reasoning is usually accepted by most mathematicians, and even by enginers, but not by intuitionists who ask always for constructive existence proof. 

Actually in theoretical artificial intelligence, and in mathematical theology not only such non constructive proofs abound, but in many case it can be proved that there are no better existence proof. That is we can prove that the proof is necessarily not constructive. It is that phenomenon which makes eventually comp a vaccine against reductionism. We can prove the existence of very 'clever' machine, but then we can prove that nobody can recognize as such, such a machine.

This is not the case for the present problem. It can be shown that S  (sqrt(2)^sqrt(2)) is irrational, and this provides a constructive solution. The proof that S is irrational is not elementary at all.

Such a phenomenon will already appears in the post on Kleene's theorem. 

Bruno

(*) We have used the laws of exponentiation: (a^b)^c = a^(b*c).

(**) That proof is sometimes attributed to Jarden.

On 09 Sep 2009, at 09:21, Bruno Marchal wrote:

This is the last post before we proof Cantor theorem. It is an "antic interlude". We are about 2000 years back in time.

The square root of 2.

It is a number x such that x^2 = 2. It is obviously smaller than 2 and bigger than 1. OK? It cannot be a natural number. But could it be a fraction?

The square root of two is the length of the diagonal of a square with side one unity.

Do you see that? I can't draw, so you have to imagine a square. You may draw it. And then draw or imagine the square which sides the diagonal (of you square unity). Draw it with its diagonals and you will see, in your mind or on the paper that the second square is made of four times the half of your square unity: meaning that the square which sides the diagonal has an area twice the area of the square unity. But this means that if you call d the length of the diagonal of the square unity, you have, by the law of the area of square, d^2 = 2. OK?

So the length of the diagonal d = square root of 2. It is a 'natural' length occurring in geometry (and quantum mechanics!).

The function or operation "taking the square root of two" is the inverse operation of taking the square.

(In term of the couples defining the function as set, it means that if (x, y) belongs-to "taking the square root of two" then (y, x) belongs-to "taking the square of").

Now, please continue to imagine the diagonal, and try to evaluate its length. Is is not clearly less than two unities, and clearly more than one? Is it 3/2 i.e. 1.5? Well, 1.5 should give two when squared, but (1.5)^2 = 2,25. That's too much! Is 1,4?

Oh, 1.4 gives 1.96, not too bad, it is slightly more, may be 1.41? 1.41^2 gives 1,9881, we get closer and closer, but will such a search ends up with the best approximation? This would mean we can divide the side of the square unity in a finite number of smaller unities, and find a sufficiently little unity which could measure the diagonal exactly. It would mean d is equal to p * 1/q, where q is the number of divisions of the side of the square unity. If we find such a fraction the diagonal and the sided would be said commensurable.

 

Is there such a fraction?

It is not 3/2, we know already. Is it 17/12 (= 1,416666666666...)? (1712)^2 = 2,0069444444....). Close but wrong.

Is it 99/70? (= 1,414285714...) (99/70)^2 = 2,000204082...). Very close, but still wrong!

...

is it 12477253282759/8822750406821 ? My pocket computer says that the square of that fraction is 2. Ah, but this is due to its incompetence in handling too big numbers and too little numbers! It is still wrong!

How could we know if that search will end, or not end?

Sometimes, we can know thing in advance. Why, because things obeys laws, apparently.

Which laws of numbers makes the problem decidable?

Here is one:

- a number is even if and only if the square of that number is even, similarly

- a number is odd if and only if the square of that number is odd.

Taking the square of an integer leaves invariant the parity (even/odd) of the number.

Why? suppose n is odd. There will exist a k (belonging to {0, 1, 2, 3, ...} such that n = 2k+1. OK? So n^2 = (2k+1)^2 = 4k^2 + 4k + 1, OK? and this is odd. OK. And this is enough to show that if n^2 is even, then n is even. OK?

And why does this answer the question.

Let us reason 'by absurdo".

Suppose that there are number p and q such (p/q)^2 = 2. And let us suppose we have already use the Euclid algorithm to reduce that fraction; so that p and q have no common factor. 

 p^2 / q^2 = 2. OK? Then p^2 = 2q^2 (our 'Diophantine equation). OK?

Then p^2 is even. OK? (because it is equal to 2 * an integer).

Then p is even. OK? (by the law above).

This means p is equal to some 2*k (definition of even number). OK?

But p^2 = 2q^2 (see above), and substituting p by 2k, we get 4k^2 = 2q^2, and thus, dividing both sides by 2, we get that 2k^2 = q^2.

So q^2 is even. OK?

So q is even. (again by the law above). OK?

So both p and q are even, but this means they have a common factor (indeed, 2), and this is absurd, given that the fraction has been reduced before.

So p and q does not exist, and now we know that our search for a finite or periodic decimal, or for a fraction, will never end.

The diophantine equation x^2 = 2y^2 has no solution in the integers, and the number sqrt(2) = square root of two is not the ratio of two integers/ Such a number will be said irrational. If we want associate a number to each possible length of line segment, we have to expand the rational number (the reduced fraction, the periodic decimal) with the irrational number.

The numerical value of the sqrt(2) can only be given through some approximation, like

sqrt(2) =  1,414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 376 948 073 176 679 737 990 732 478...

OK?

I have to go now.

Please ask any question.

Does the "beginners" see that (2k+1)^2 = 4k^2 + 4k + 1? This comes from the 'remarkable product (a+b)^2 = a^2 + 2ab + b^2. Could you prove this geometrically (in your head or with a drawing)? Hint: search the area of a rectangle which sides (a+b).

In proof by 'reduction ad absurdo', sometimes Brent says this proofs only the result OR the fact that an error occur in the proof. Please comment.

I have not the time to give easy exercise, so I give one which is not so easy. try to use the fundamental theorem of arithmetic (saying that all natural numbers have a unique decomposition into prime factor to generalize this result: if n is not a square number (like 1, 4, 9, 16, 25, ...) then sqrt(n) is irrational. Guess who proves this theorem originally? Theaetetus! (well I read that somewhere).

This ends the antic interlude.

Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets.

After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc.

Bruno

On 08 Sep 2009, at 10:43, Bruno Marchal wrote:

On 31 Aug 2009, at 19:31, Bruno Marchal wrote:

Next: I will do some antic mathematic, and prove the irrationality  

of the square root of two, for many reasons, including some thought  

about what is a proof. And then I will prove Cantor theorem. Then I  

will define what is a computable function. I will explain why Cantor  

"reasoning" seems to prove, in that context, the impossibility of  

the existence of universal machine, and why actually Cantor  

"reasoning" will just make them paying the big price for their  

existence.

Any question, any comment?  I guess that I am too quick for some,  

too slow for others.

Don't forget the exercise: show that there is always a bijection  

between A+ and N.

(A+ = set of finite strings on the alphabet A). This is important  

and will be used later.

I illustrate the solution on a simple alphabet.

An alphabet is just any finite set. Let us take A = {a, b, c}.
A+ is the set of words made with the letters taken in A. A "word" is  
any finite sequence of letters.

To build the bijection from N to A+, the idea consists in enumerating  
the words having 0 letters (the empty word), then 1 letter, then 2  
letters, then 3 letters, and so on. For each n there is a finite  
numbers of words of length n, and those can be ordered alphabetically,  
by using some order on the alphabet. In our case we will decide that a  

b, and b> c (a > b should be read "a is before b").

So we can send 0 on the empty word. Let us note the empty word as *.

0 ------> *

then we treat the words having length 1:

1 ------>  a
2 ------>  b
3 ------>  c

then the words having length 2:

4 -------> aa
5 ------>  ab
6 ------>  ac

7 ------>  ba
8 ------>  bb
9 ------>  bc

10 ------> ca
11 ------> cb
12 ------> cc

Then the words having lenght 3. There will be a finite number of such  
words, which can be ranged alphabetically,

etc.

Do you see that this gives a bijection from N = {0, 1, 2, 3 ...} to A+  
= {*, a, b, c, aa, ab, ac, ba, bb, bc, ...}

It is one-one: no two identical words will appears in the enumeration.
It is onto: all words will appear soon or later in the enumeration.

I will call such an enumeration, or order, on A+, the lexicographic  
order.

Its mathematical representation is of course the set of couples:

{(0, *), (1, a), (2, b), (3, c), (4, aa), ...}

OK? No question?

Next, I suggest we do some antic mathematics. It will, I think, be  
helpful to study a simple  "impossibility" theorem, before studying  
Cantor theorems, and then the many impossibilities generated by the  
existence of universal machines. It is also good to solidify our  
notion of 'real numbers', which does play some role in the  
computability general issue.


Here are some preparation. I let you think about relationship between  
the following propositions. I recall that: the square root of X  is  Y  
means that Y^2 = X. (It is the 'inverse function of the power 2  
function). The square root of 9 is 3, for example, because 3^2 = 3*3 =  
9. OK?

- There exists incommensurable length  (finite length segment of line  
with no common integral unity)
- the Diophantine equation x^2 = 2(y^2) has no solution  (Diophantine  
means that x and y are supposed to be integers).
- the square root of 2 is irrational (= is not the ratio of integers)
- The square root of 2 has an infinite and never periodic decimal.
- If we want to measure by numbers any arbitrary segment of line, we  
need irrational numbers

Take it easy, explanation will follow. This antic math interlude will  
not presuppose the 'modern math' we have seen so far.

Bruno







http://iridia.ulb.ac.be/~marchal/

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]

On 09 Sep 2009, at 09:21, Bruno Marchal wrote:

Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets.

After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc.

CANTOR'S FIRST RESULT

There is NO bijection between N and N^N  (N^N is the set of functions from N to N. N = (0, 1, 2,  ...}

Proof

1) preliminaries

Like for the irrationality of the square root of 2, we will proceed by a reduction to an absurdity.

First note that there are many obvious injection (= one-one function) from N to N^N. For example the function which sends the number n on the constant function from N to N which send all numbers to n:

0 ======>  {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0) ....}

1 ======>  {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) ....}

2  ======> {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) ....}

3 ...

...

Such correspondence is one-one: two different numbers are send to two different functions from N to N. OK?

With Cantor, inspired by what happens in the case of finite sets,  I will say that the cardinal of A is little or equal (≤) than the cardinal of B, when A and B are infinite sets, when there is a one-one function, also called injection, from A to B.

The injection described in the diagram above shows that the cardinal of N is little or equal than the cardinal of N^N.

 I will say that the cardinal of A is equal to the cardinal of B when there is a bijection between the two sets. 

I will also use the canonical bijection between the set of functions from N to N  and the set of infinite sequences of numbers, to write any function from N to N, as a sequence of numbers. This will make the things more readable.

The diagram above becomes:

0 ======> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1 ======> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

2 ======> 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

etc.

OK?

We can do that because we have all in mind the canonical order of the natural numbers: 0, 1, 2, 3, .... so that the sequence of numbers can be seen a short way to describe a function from N to N.

2) the proof

Let us do the Cantor's reduction to the absurd.

Suppose there is a bijection from N to N^N.  It will have some shape like:

0 =====> 34,  6,  678,  0,  6, 77,  8,  9, 39,  67009, ... 

1 =====>   0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ...

2 =====>   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...

3 =====>   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

4 =====>  1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ...

5 =====>  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ...

...

May be you recognize some functions in the correspondence. The first two functions seems arbitrary. The third one seems to be the power of two, the fourth one is the constant function sending all numbers on 2, the fifth one seems to be the factorial functions, the sixth one seems to be an arbitrary function from N to {0, 1}.  From such finite set of data we can never be sure, given that the "..." could in this context mean practically anything.

BUT, if there is a bijection between N and N^N, the correspondence is well defined, at least in Platonia, or in the mind of God. This means that each line must be thought as representing *some*, perhaps unknown, precise function. In particular, all numbers, including the double infinity of numbers that we have not represented, are well defined, perhaps unknown by us, numbers.

But then, Cantor reasons, if the whole diagram above makes some sense, it is easy to conceive a NEW function, which can be shown not belonging to the diagram. That is there will be a function from N to N which is not represented at any line of the above diagram.

Indeed the following sequence will play that role:

35,  678, 5, 3, 7, 1, ...

Do you see where it comes from? It comes from the diagonal elements, from up-left to down-right, with one added to them:

34+1, 677+1, 4+1, 2+1, 6+1, 0+1, ...

Why does such sequence not belong to the diagram? Because it differs from the first sequence for the first output. Indeed the first output at the first line is 34, and the new function outputs 35. It differs from the second sequence at the second outputs. Indeed the second output of the second sequence is 677, and the second output of the new sequence is 678, etc. So, by construction, the new function differs from all the sequence in the list above. We proceed diagonally to be sure that by changing a function, we don't come back on some distinction already introduced.

All the function being well defined, in Platonia, or in God's eyes (or in the eye of some omniscient being), automatically the new sequence is well defined too, and cannot belong to the sequence. Thus we get a contradiction. If the correspondence above is a bijection, then if fails as being a bijection.

This reasoning did not depend on the choice of the supposed bijection. All possible bijections will fail, because for each one, their very existence makes them failed to be a bijection, because again their very existence entails the existence of the "diagonal sequence", which by construction differs from each line of the correspondence. Indeed, you should see that they differ at the intersection of the diagonal and the line.  End of the proof.

OK?

3) Miscellaneous remarks, vocabulary.

When Cantor discovered this, he was in shock. He said the famous sentence: "I see it, but I don't believe it". His technic is know as the diagonalization (with a "z" or a "s" according to americans or english respective common uses). 

Is that proof 100% convincing?

I let you judge by yourself. If you say yes, it means you could be realist on the notion of set. Torgny Tholerus has already send to the list, some month ago, an argument which can throw some doubt about such a reasoning. But I want to avoid such premature discussion. Why?

Because I don't want you to redo the whole big set of discoveries, and mathematical constructions which have been inspired by Cantor's proof, and focus instead on what will become the 'discovery of the universal machine'. 

I let you know that this proof, that is Cantor's reasoning showing that there is no bijection between N and N^N, *can* be done without change in the context of formal axiomatic set theory (like Zermelo Fraenkel set theory). Such impossibility theorem is thus well accepted by classical mathematicians. Now, the discovery of the universal machine will come from a very similar reasoning, in a different context, and Torgny Tholerus' remark, for those who remembers it, cannot be applied, even without formal set theory. 

The biggest objection here would be that Cantor's proof invoke the name of God. Cantor will take that objection very seriously and he will literally ask the advice of the pope (!) to proceed. The formalization of set theory can hide a little bit that invocation, but eventually our diagonalization in the comp frame, will not invoke God or any omniscient being. We will of course come back on this.

Accepting Cantor's proof, we know that the cardinal of N^N is bigger than the cardinal of N. So there are infinities 'bigger' than other infinities.

Definition: we will say that a set S is enumerable if S is finite or if there is a bijection between S and N. We will say that an *infinite* set S is non enumerable if there is NO bijection between S and N. We can sum up Cantor's result by:

   N^N is non enumerable.

Exercise (using 2 for the set {0, 1})

1) Does this prove that 2^N is not enumerable?

2) In case you answer "no" to the first question, can you prove that 2^N is not enumerable?

OK? 

I let you think and ask question if necessary.

Next post: I will do again that very proof, but in a way which is somehow clearer, by using better notations (yet a bit more abstract, so that it is clearer only for those who are not afraid by math notations). I don't want to mix the two difficulties (new concept/new notations), in a first approach. In some sequel, I will give you the proof of what is known as Cantor's theorem: that the cardinal of a powerset 2^A is always bigger than the cardinal of the set A. But this is not needed for our computationalist purpose, so I will not insist on that. From this we get a ladder of bigger and bigger infinities.

A last remark for Mirek, and those who remember what I said about the ordinals (which I have illustrated with the growing functions, some years ago). Mirek, to ensure that cardinals are ordinals, I would need the axiom of choice. But I will never use that, some I will not try to put the cardinals among the ordinals. 

Best,

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 will introduce notation for functions, and prove again Cantor theorem, without making any diagram.

I will lazily write the diagram

0 =====> 34,  6,  678,  0,  6, 77,  8,  9, 39,  67009, ... 

1 =====>   0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ...

2 =====>   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...

3 =====>   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

4 =====>  1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ...

5 =====>  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ...

...

in the following way

0 =====> f_0

1 =====> f_1

2 =====> f_2

3 =====> f_3

4 =====> f_4

5 =====> f_5

....

Here the label "f_1" plays the role of a name for the function {(0, 34), (1, 6), (2, 678), (3, 0), ...}. Indeed it plays the role of the name of the function which is the image by the bijection, which we were supposing the existence. 

To say that f_1 send 0 to 34, or 1 to 6, ...  is usually written by either

f_0: 0 --> 34,  f_0 : 1 --> 6, ...

or by f_0(0) = 34, f_0(1) = 6, ... 

More generally if f is a name for a function, to say that (x, y) belongs to f, we write very often f(x) = y, or y = f(x).

For example we say that factorial(5) = 120.

Now, because I am even more lazy, instead of writing

0 =====> f_0

1 =====> f_1

2 =====> f_2

3 =====> f_3

4 =====> f_4

5 =====> f_5

....

I will write:

i =====> f_i

which is much shorter. I could even write just f_i.  the index i is supposed to vary from 0 to infinity (excluded). I mean that i belongs to {0, 1, 2, ...}, or just that it is natural number.

So with that notation, I could begin the proof by saying this: Let us assume that there is a bijection B:  i ==> f_i between N and N^N. OK? This is the "absurd hypothesis", that is the one we want to show leading to a contradiction. I call that bijection B to fix the idea.

Now the proof continues. Let us consider the function from N to N which is defined by g(n) = f_n(n) + 1.

Do you recognize g? if n varies from 0 to infinity, with the f_i given by the diagram above, f_n(n) describes the diagonal

34 677 4, 2, 6, 0, ...

And f_n(n) + 1, which is g(n), describes 

35 678, 5, 3, 7, 1, ...

It is the function which is supposed not be in the range of the supposed bijection.

Not only this can satisfy my lazy mood, but more importantly, it is easier to show now more clearly the contradiction.

Indeed, suppose that g is in the range of the bijection. This means there is some number k which is send on g by the bijection. This means that there is some k such that g is equal to f_k. OK?

But if g = f_k, it follows that g(n) = f_k(n) for any n. Right? But then if g is applied to k, its own image under the bijection, we have that g(k) = f_k(k). 

But by definition of g, g(n) = f_n(n) + 1. So g(k) = f_k(k) + 1.

 It follows that f_k(k) = f_(k) + 1. OK? This follows by the Leibniz rule (two quantities equal to a third one are equal with each other), applied on the two preceding line.

Now, each f_i is a function from N to N, so each f_i(n) are well defined number (if the bijection exists), so we can substract f_(k) on both side of the equality f_k(k) = f_(k) + 1, so we get 0 = 1. Contradiction. Such a bijection cannot exist.

Again, this makes N^N non enumerable. If you consider an enumeration (bijection from N to a set) f_i, it will means its corresponding diagonal g function.

OK? Take your time to compare with the last post, and to understand what happens.

Training exercise: prove, using that notation, that 2^N is non enumerable. Hint: use a slightly different g.

Bruno

-----------------

On 14 Sep 2009, at 16:40, Bruno Marchal wrote:

On 09 Sep 2009, at 09:21, Bruno Marchal wrote:

Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets.

After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc.

CANTOR'S FIRST RESULT

There is NO bijection between N and N^N  (N^N is the set of functions from N to N. N = (0, 1, 2,  ...}

Proof

1) preliminaries

Like for the irrationality of the square root of 2, we will proceed by a reduction to an absurdity.

First note that there are many obvious injection (= one-one function) from N to N^N. For example the function which sends the number n on the constant function from N to N which send all numbers to n:

0 ======>  {(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0) ....}

1 ======>  {(0, 1), (1, 1), (2, 1), (3, 1), (4, 1), (5, 1), (6, 1) ....}

2  ======> {(0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (5, 2), (6, 2) ....}

3 ...

...

Such correspondence is one-one: two different numbers are send to two different functions from N to N. OK?

With Cantor, inspired by what happens in the case of finite sets,  I will say that the cardinal of A is little or equal (≤) than the cardinal of B, when A and B are infinite sets, when there is a one-one function, also called injection, from A to B.

The injection described in the diagram above shows that the cardinal of N is little or equal than the cardinal of N^N.

 I will say that the cardinal of A is equal to the cardinal of B when there is a bijection between the two sets. 

I will also use the canonical bijection between the set of functions from N to N  and the set of infinite sequences of numbers, to write any function from N to N, as a sequence of numbers. This will make the things more readable.

The diagram above becomes:

0 ======> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...

1 ======> 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

2 ======> 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

etc.

OK?

We can do that because we have all in mind the canonical order of the natural numbers: 0, 1, 2, 3, .... so that the sequence of numbers can be seen a short way to describe a function from N to N.

2) the proof

Let us do the Cantor's reduction to the absurd.

Suppose there is a bijection from N to N^N.  It will have some shape like:

0 =====> 34,  6,  678,  0,  6, 77,  8,  9, 39,  67009, ... 

1 =====>   0, 677, 901, 1, 67, 8, 768765, 56, 9, 9, ...

2 =====>   1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, ...

3 =====>   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, ...

4 =====>  1, 1, 2, 3, 6, 24, 120, 720, 5040, 40320, ...

5 =====>  0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, ...

...

May be you recognize some functions in the correspondence. The first two functions seems arbitrary. The third one seems to be the power of two, the fourth one is the constant function sending all numbers on 2, the fifth one seems to be the factorial functions, the sixth one seems to be an arbitrary function from N to {0, 1}.  From such finite set of data we can never be sure, given that the "..." could in this context mean practically anything.

BUT, if there is a bijection between N and N^N, the correspondence is well defined, at least in Platonia, or in the mind of God. This means that each line must be thought as representing *some*, perhaps unknown, precise function. In particular, all numbers, including the double infinity of numbers that we have not represented, are well defined, perhaps unknown by us, numbers.

But then, Cantor reasons, if the whole diagram above makes some sense, it is easy to conceive a NEW function, which can be shown not belonging to the diagram. That is there will be a function from N to N which is not represented at any line of the above diagram.

Indeed the following sequence will play that role:

35,  678, 5, 3, 7, 1, ...

Do you see where it comes from? It comes from the diagonal elements, from up-left to down-right, with one added to them:

34+1, 677+1, 4+1, 2+1, 6+1, 0+1, ...

<snip>

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]

I give the solution.

On 15 Sep 2009, at 16:30, Bruno Marchal wrote:

OK? Take your time to compare with the last post, and to understand what happens.

Training exercise: prove, using that notation, that 2^N is non enumerable. Hint: use a slightly different g.

2^N is non enumerable.

2^N is the set of functions from N to {0, 1}, and I will again note or identify a function from N to {0, 1} with an infinite sequence of 1 and 0. For example, the function {(0, 0), (1, 1), (2, 0), (3, 1), (4, 0), (5, 1), ...} is identified with the sequence 010101010...

OK?

I reason "by absurdum",    ... again with the two notations.

Suppose that 2^N *is* enumerable, then there is a bijection from N to 2^N, which is something like

0 ====  000110100111011010011100 ...

1 ====  110110010000011110101111...

2 ====  000000000000000001000000...

3 ====  101010101010101010101000...

4 ====  111111111110000000111110...

5 ====  110011000010100101001100...

6 ====  000000000000000000000000...

7 ====  111000111000111000111111...

8 ====  000000001110000011010000...

9 ====  111111111111111111110001...

...

If the bijection exists, all the "1" and "0" are well defined in the infinite diagram, and the diagonal sequence is well defined too.

So the diagonal sequence,  made up from the diagonal sequence where all 0 are changed into 1 and vice versa, is well defined too. It is

1011001...    (print it, and use a rule to verify!)

OK?

Suc a sequence cannot appears in the enumeration. Indeed, if it appears in the diagram, it appears at some line, let us say the kth line. But at the intersection of the diagonal and the kth line, there will be a problem. By the construction of the diagonal, the kth element of the kth sequence has to be simultaneously equal to 0 and 1. Contradiction.

OK? 

So 2^N is non enumerable.

OK?

I do the proof with the "usual" notation:

Suppose f_n is an enumeration of the functions from N to {0, 1}. Let g be the function which send n on 1 - f_n(n).

g is a function from N to 2 (because both 1 - 1, and 1 - 0 gives 0 or 1). We write g(n) = 1 - f_n(n).

g is a function from N to 2, yet cannot belong to the enumeration f_i.

Why?

Suppose g is in the enumeration f_n. It means there is a number k such that g = f_k. Thus for all n, g(n) = f_k(n).

In particular g(k) = f_k(k). But by definition, for all n g(n) = 1 - f_n(n). In particular g(k) = 1 - f_k(k). So we have that g(k) is equal to both f_k(k) and 1 - f_k(k). And f_k is a function from N to {0, 1}, so we get either 0 = 1 (if f_k(k) = 0), and 1 = 0 if f_k(k) = 1. Contradiction.

We can say it is the same proof than the proof that N^N is non enumerable. The only change is in the diagonal function g.

Yesterday it was g(n) = f_n(n) + 1, and today it is g(n) = 1 - f_n(n). This comes from the fact that we want g to belong to N^N and 2^N respectively.

OK?

*****************

If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion.

We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N.

We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N.

The question is: is there a bijection from N to N^N-comp ?

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

[John Mikes]

Bruno,

 I loved your post on the square root of "2"!

(I also laughed at it, to stay at the puns).

 

You went out of your way and did not save efforts to prove how inadequate and wrong (y)our number system is. (ha ha).

 

Statement: if square-rooting is right (allegedly, and admittedly) then THERE IS such a 'quantity' (call it number and by this definition it must be natural) we consider as the square root of '2'.

You gave the plastic elemenary rule, how to get to it. Thankyou. Accepted.

 

I believe the '1' and the sophistication of Pythagoras. (provided that

< 1^2 = 1 >  which is also 'funny')  a n d :

If it is not part of your series of - what you call: - natural numbers, then YOUR series is wrong. We need another system (if we really need it).

 

Your math pupil

John, the 'commonsenser'.

On Wed, Sep 9, 2009 at 3:21 AM, Bruno Marchal <marchal@...> wrote:

This is the last post before we proof Cantor theorem. It is an "antic interlude". We are about 2000 years back in time.

The square root of 2.

It is a number x such that x^2 = 2. It is obviously smaller than 2 and bigger than 1. OK? It cannot be a natural number. But could it be a fraction?

The square root of two is the length of the diagonal of a square with side one unity.

Do you see that? I can't draw, so you have to imagine a square. You may draw it. And then draw or imagine the square which sides the diagonal (of you square unity). Draw it with its diagonals and you will see, in your mind or on the paper that the second square is made of four times the half of your square unity: meaning that the square which sides the diagonal has an area twice the area of the square unity. But this means that if you call d the length of the diagonal of the square unity, you have, by the law of the area of square, d^2 = 2. OK?

So the length of the diagonal d = square root of 2. It is a 'natural' length occurring in geometry (and quantum mechanics!).

The function or operation "taking the square root of two" is the inverse operation of taking the square.

(In term of the couples defining the function as set, it means that if (x, y) belongs-to "taking the square root of two" then (y, x) belongs-to "taking the square of").

Now, please continue to imagine the diagonal, and try to evaluate its length. Is is not clearly less than two unities, and clearly more than one? Is it 3/2 i.e. 1.5? Well, 1.5 should give two when squared, but (1.5)^2 = 2,25. That's too much! Is 1,4?

Oh, 1.4 gives 1.96, not too bad, it is slightly more, may be 1.41? 1.41^2 gives 1,9881, we get closer and closer, but will such a search ends up with the best approximation? This would mean we can divide the side of the square unity in a finite number of smaller unities, and find a sufficiently little unity which could measure the diagonal exactly. It would mean d is equal to p * 1/q, where q is the number of divisions of the side of the square unity. If we find such a fraction the diagonal and the sided would be said commensurable.

 

Is there such a fraction?

It is not 3/2, we know already. Is it 17/12 (= 1,416666666666...)? (1712)^2 = 2,0069444444....). Close but wrong.

Is it 99/70? (= 1,414285714...) (99/70)^2 = 2,000204082...). Very close, but still wrong!

...

is it 12477253282759/8822750406821 ? My pocket computer says that the square of that fraction is 2. Ah, but this is due to its incompetence in handling too big numbers and too little numbers! It is still wrong!

How could we know if that search will end, or not end?

Sometimes, we can know thing in advance. Why, because things obeys laws, apparently.

Which laws of numbers makes the problem decidable?

Here is one:

- a number is even if and only if the square of that number is even, similarly

- a number is odd if and only if the square of that number is odd.

Taking the square of an integer leaves invariant the parity (even/odd) of the number.

Why? suppose n is odd. There will exist a k (belonging to {0, 1, 2, 3, ...} such that n = 2k+1. OK? So n^2 = (2k+1)^2 = 4k^2 + 4k + 1, OK? and this is odd. OK. And this is enough to show that if n^2 is even, then n is even. OK?

And why does this answer the question.

Let us reason 'by absurdo".

Suppose that there are number p and q such (p/q)^2 = 2. And let us suppose we have already use the Euclid algorithm to reduce that fraction; so that p and q have no common factor. 

 p^2 / q^2 = 2. OK? Then p^2 = 2q^2 (our 'Diophantine equation). OK?

Then p^2 is even. OK? (because it is equal to 2 * an integer).

Then p is even. OK? (by the law above).

This means p is equal to some 2*k (definition of even number). OK?

But p^2 = 2q^2 (see above), and substituting p by 2k, we get 4k^2 = 2q^2, and thus, dividing both sides by 2, we get that 2k^2 = q^2.

So q^2 is even. OK?

So q is even. (again by the law above). OK?

So both p and q are even, but this means they have a common factor (indeed, 2), and this is absurd, given that the fraction has been reduced before.

So p and q does not exist, and now we know that our search for a finite or periodic decimal, or for a fraction, will never end.

The diophantine equation x^2 = 2y^2 has no solution in the integers, and the number sqrt(2) = square root of two is not the ratio of two integers/ Such a number will be said irrational. If we want associate a number to each possible length of line segment, we have to expand the rational number (the reduced fraction, the periodic decimal) with the irrational number.

The numerical value of the sqrt(2) can only be given through some approximation, like

sqrt(2) =  1,414 213 562 373 095 048 801 688 724 209 698 078 569 671 875 376 948 073 176 679 737 990 732 478...

OK?

I have to go now.

Please ask any question.

Does the "beginners" see that (2k+1)^2 = 4k^2 + 4k + 1? This comes from the 'remarkable product (a+b)^2 = a^2 + 2ab + b^2. Could you prove this geometrically (in your head or with a drawing)? Hint: search the area of a rectangle which sides (a+b).

In proof by 'reduction ad absurdo', sometimes Brent says this proofs only the result OR the fact that an error occur in the proof. Please comment.

I have not the time to give easy exercise, so I give one which is not so easy. try to use the fundamental theorem of arithmetic (saying that all natural numbers have a unique decomposition into prime factor to generalize this result: if n is not a square number (like 1, 4, 9, 16, 25, ...) then sqrt(n) is irrational. Guess who proves this theorem originally? Theaetetus! (well I read that somewhere).

This ends the antic interlude.

Next post: Cantor theorem(s). There is NO bijection between N and N^N. I will perhaps show that there is no bijection between N and {0, 1}^N. The proof can easily be adapted to show that there is no bijection between N and many sets.

After Cantor theorem, we will be able to tackle Kleene theorem and the 'mathematical discovery of the mathematical universal machine', needed to grasp the mathematical notion of computation, implementation, etc.

Bruno

On 08 Sep 2009, at 10:43, Bruno Marchal wrote:

On 31 Aug 2009, at 19:31, Bruno Marchal wrote:

Next: I will do some antic mathematic, and prove the irrationality  

of the square root of two, for many reasons, including some thought  

about what is a proof. And then I will prove Cantor theorem. Then I  

will define what is a computable function. I will explain why Cantor  

"reasoning" seems to prove, in that context, the impossibility of  

the existence of universal machine, and why actually Cantor  

"reasoning" will just make them paying the big price for their  

existence.

Any question, any comment?  I guess that I am too quick for some,  

too slow for others.

Don't forget the exercise: show that there is always a bijection  

between A+ and N.

(A+ = set of finite strings on the alphabet A). This is important  

and will be used later.

I illustrate the solution on a simple alphabet.

An alphabet is just any finite set. Let us take A = {a, b, c}.
A+ is the set of words made with the letters taken in A. A "word" is  
any finite sequence of letters.

To build the bijection from N to A+, the idea consists in enumerating  
the words having 0 letters (the empty word), then 1 letter, then 2  
letters, then 3 letters, and so on. For each n there is a finite  
numbers of words of length n, and those can be ordered alphabetically,  
by using some order on the alphabet. In our case we will decide that a  

b, and b> c (a > b should be read "a is before b").

So we can send 0 on the empty word. Let us note the empty word as *.

0 ------> *

then we treat the words having length 1:

1 ------>  a
2 ------>  b
3 ------>  c

then the words having length 2:

4 -------> aa
5 ------>  ab
6 ------>  ac

7 ------>  ba
8 ------>  bb
9 ------>  bc

10 ------> ca
11 ------> cb
12 ------> cc

Then the words having lenght 3. There will be a finite number of such  
words, which can be ranged alphabetically,

etc.

Do you see that this gives a bijection from N = {0, 1, 2, 3 ...} to A+  
= {*, a, b, c, aa, ab, ac, ba, bb, bc, ...}

It is one-one: no two identical words will appears in the enumeration.
It is onto: all words will appear soon or later in the enumeration.

I will call such an enumeration, or order, on A+, the lexicographic  
order.

Its mathematical representation is of course the set of couples:

{(0, *), (1, a), (2, b), (3, c), (4, aa), ...}

OK? No question?

Next, I suggest we do some antic mathematics. It will, I think, be  
helpful to study a simple  "impossibility" theorem, before studying  
Cantor theorems, and then the many impossibilities generated by the  
existence of universal machines. It is also good to solidify our  
notion of 'real numbers', which does play some role in the  
computability general issue.


Here are some preparation. I let you think about relationship between  
the following propositions. I recall that: the square root of X  is  Y  
means that Y^2 = X. (It is the 'inverse function of the power 2  
function). The square root of 9 is 3, for example, because 3^2 = 3*3 =  
9. OK?

- There exists incommensurable length  (finite length segment of line  
with no common integral unity)
- the Diophantine equation x^2 = 2(y^2) has no solution  (Diophantine  
means that x and y are supposed to be integers).
- the square root of 2 is irrational (= is not the ratio of integers)
- The square root of 2 has an infinite and never periodic decimal.
- If we want to measure by numbers any arbitrary segment of line, we  
need irrational numbers

Take it easy, explanation will follow. This antic math interlude will  
not presuppose the 'modern math' we have seen so far.

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 John,

On 17 Sep 2009, at 15:14, John Mikes wrote:

 

You went out of your way and did not save efforts to prove how inadequate and wrong (y)our number system is. (ha ha).

Wrong ?

 

Statement: if square-rooting is right (allegedly, and admittedly)

Well, it is certainly right if we want that to measure by a number length of the diagonal of the square unity.

then THERE IS such a 'quantity' (call it number and by this definition it must be natural)

It cannot be natural number. It has to be strictly bigger than 1, and strictly bigger than 2. But there was some hope that it could be the ratio of two natural number, so that it can live in arithmetic with addition and multiplication.

we consider as the square root of '2'.

You gave the plastic elemenary rule, how to get to it. Thankyou. Accepted.

 

I believe the '1' and the sophistication of Pythagoras. (provided that

< 1^2 = 1 >  which is also 'funny')  a n d :

If it is not part of your series of - what you call: - natural numbers, then YOUR series is wrong.

You could as well told something like "My cave is at the level -2 (minus two) of the building ...

We need another system (if we really need it).

That is why N (the set of natiral numbers, alias positive integers) has been extended into Z, all the integers, itself included in Q (he ratio). The my point was that Q was still not enough to define the length of the diagonal, we need the real numbers, which are more difficult to define in the structure (N, +, *).

From a logical point of view, N, Z, and Q are roughly equivalent. The real numbers are not, most are not definable in the structure N. yet, and we will see this (probably), most real numbers that we encounter in math and physics can still be defined in the structure (N,+,*). It is an open problem in math and physics if there is anything we cannot define in (N,+,*), and indeed it is an indirect consequence of COMP that we can. This probably why formal set theory is studied only by logicians.

Of course Riemann and number theorists, and knot theorists, are used to escape from the (N, +, *) structure all the time, and that is why we use analysis (based on the real numbers). But we have not yet find a theorem which *needs* to escape the structure (N, +, *), except those found by logicians to just provide examples. In the mechanical theory of mind, we have to escape the structure (N, +, *). Indeed the first person notion needs even more than Cantor paradise, from its point of view, and that is why and how the epistemology of comp is necessarily far bigger than its ontology. I may come back on this, but it asks for more model theory and logic to address the question technically.

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 16 Sep 2009, at 18:12, Bruno Marchal wrote:

If it is OK, in the next post we begin to address the computability issue. I give you an anticipative exercise or subject reflection. This is a deep exercise. Its solution leads to the notion of universal function and universal number/machine. More exactly it leads to an evaluation of the price we have to pay if we want to believe in that notion.

We have seen that the set N^N is non enumerable. This means it is a *huge* infinite set, compared to N.

We could argue that there are too much functions in that set. Most usual functions that we encounter in real life, both in math and physics, seem to share the property that they are computable. This means that we can write some rules or recipe for computing them, or that, may be, we can build some mechanical device capable of computing them. The natural functions we met were the exponential f(n) = 2^n, or the factorial(n), or similars. It seems that we can explain to each other how to compute them, and you already known that we can build machines computing them indeed. So, we could decide, if only to avoid those big infinities, to restrict ourself on the computable functions. Let us define N^N-comp to be the set of computable functions from N to N.

The question is: is there a bijection from N to N^N-comp ?

This is a tricky question. 

I give you an argument that there is a bijection between N and N^N-comp. Followed by an argument that there is no bijection between N and N^N-comp.

Which one is wrong?

1) A "proof" that N^N-comp is enumerable.

I said that a function from N to N, is computable (and thus in N^N-comp), if there is a recipe explaining how to compute it.

But this means that there has to be a language in which we can describe or encode that explanation. A language is a set of finite expressions build from some finite alphabet. But we have seen that the set of finite expressions build on an alphabet (which is always a finite set) is enumerable. Those expressions, corresponding to the explanation describing the recipe for a computable function, will constitute a subset of the set of all expressions, and is thus enumerable. So N^N-comp is enumerable.

2) A "proof" that N^N-comp is NOT enumerable.

Suppose N^N-comp is enumerable, and let f_n be such an enumeration, with n in {0, 1, 2, ...}. Consider the diagonal function g defined by g(n) = f_n(n) + 1. All f_n are computable, and surely "+ 1" is computable, so g is a computable function. But then g has to belong to f_n, which enumerates the computable functions. So there is a k such that g = f_k. But then g(k) = f_k(k) = f_k(k) + 1. But f_k is a computable function from N to N, so f_k(k) is a number, which I can subtract on both side, so 0 = 1. So N^N^comp is not enumerable.

Well, there is a problem, isn't it? N^N-comp cannot be both enumerable and non enumerable. So one of those proofs has to be wrong. Which one?

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

[John Mikes]

Dear Bruno,

 

it is not very convincing when you dissect my sentences and interject assuring remarks on statements to come later in the sentence, negating such remarks  in advance, on a different basis.  

 

I argued that - upon what you (and the rest of the multimillion mathematicians past and present) live with  - the applied nomenclature is incomplete. It is not a counter-argument that "it is used by many" or "for so many purposes". Of course it is in use, that was my point.

I am not basing my position on opinions from "within" the argued position.

(May the "-2 level" point to a 'total senselessness' of my opinion? I did not understand it, nor did I the (N + *) structure, which therefore I find irrelevant in the question what "I" raised. (I, not Rieman, Cantor, etc.).

 

There is the idea of including 'quantities' in our worldview (excuse my naive reference, but you illustrated earlier "2" as "II" and "3" as "III" etc. and THIS in my mind means sort of a quantity) and such 'system' would be qualitatively

infinite if we try to include quantities from all directions (math is the level of handling such quantities that 'came up' in the past - gradually - and we may expect more to come, new discoveries, extending the qualitative inventory)

although in your words 'everything' can be expressed by (many many?) of your natural numbers (except  square root 2?) - what is exactly my point.

 

I did not want to open a scientific argument - I am no match for you, or any other 'mathematically educated' person. I scribbled a 'qualitative' idea of thinking in 'wider' terms than the defined 'natural numbers' in a worldview of a (qualitative) "totality" - what I pursue, but do not understand in my sci.fic agnosticism.

 

I am sorry if I bored you with my remark.

 

John M

 

On Thu, Sep 17, 2009 at 10:01 AM, Bruno Marchal <marchal@...> wrote:

Hi John,

On 17 Sep 2009, at 15:14, John Mikes wrote:

 

You went out of your way and did not save efforts to prove how inadequate and wrong (y)our number system is. (ha ha).

Wrong ?

 

Statement: if square-rooting is right (allegedly, and admittedly)

Well, it is certainly right if we want that to measure by a number length of the diagonal of the square unity.

then THERE IS such a 'quantity' (call it number and by this definition it must be natural)

It cannot be natural number. It has to be strictly bigger than 1, and strictly bigger than 2. But there was some hope that it could be the ratio of two natural number, so that it can live in arithmetic with addition and multiplication.

we consider as the square root of '2'.

You gave the plastic elemenary rule, how to get to it. Thankyou. Accepted.

 

I believe the '1' and the sophistication of Pythagoras. (provided that

< 1^2 = 1 >  which is also 'funny')  a n d :

If it is not part of your series of - what you call: - natural numbers, then YOUR series is wrong.

You could as well told something like "My cave is at the level -2 (minus two) of the building ...

We need another system (if we really need it).

That is why N (the set of natiral numbers, alias positive integers) has been extended into Z, all the integers, itself included in Q (he ratio). The my point was that Q was still not enough to define the length of the diagonal, we need the real numbers, which are more difficult to define in the structure (N, +, *).

From a logical point of view, N, Z, and Q are roughly equivalent. The real numbers are not, most are not definable in the structure N. yet, and we will see this (probably), most real numbers that we encounter in math and physics can still be defined in the structure (N,+,*). It is an open problem in math and physics if there is anything we cannot define in (N,+,*), and indeed it is an indirect consequence of COMP that we can. This probably why formal set theory is studied only by logicians.

Of course Riemann and number theorists, and knot theorists, are used to escape from the (N, +, *) structure all the time, and that is why we use analysis (based on the real numbers). But we have not yet find a theorem which *needs* to escape the structure (N, +, *), except those found by logicians to just provide examples. In the mechanical theory of mind, we have to escape the structure (N, +, *). Indeed the first person notion needs even more than Cantor paradise, from its point of view, and that is why and how the epistemology of comp is necessarily far bigger than its ontology. I may come back on this, but it asks for more model theory and logic to address the question technically.

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 17 Sep 2009, at 18:17, John Mikes wrote:

> Dear Bruno,
>
> it is not very convincing when you dissect my sentences and  
> interject assuring remarks on statements to come later in the  
> sentence, negating such remarks  in advance, on a different basis.
>
> I argued that - upon what you (and the rest of the multimillion  
> mathematicians past and present) live with  - the applied  
> nomenclature is incomplete. It is not a counter-argument that "it is  
> used by many" or "for so many purposes". Of course it is in use,  
> that was my point.
> I am not basing my position on opinions from "within" the argued  
> position.
> (May the "-2 level" point to a 'total senselessness' of my opinion?  
> I did not understand it, nor did I the (N + *) structure, which  
> therefore I find irrelevant in the question what "I" raised. (I, not  
> Rieman, Cantor, etc.).
>
> There is the idea of including 'quantities' in our worldview (excuse  
> my naive reference, but you illustrated earlier "2" as "II" and "3"  
> as "III" etc. and THIS in my mind means sort of a quantity) and such  
> 'system' would be qualitatively
> infinite if we try to include quantities from all directions (math  
> is the level of handling such quantities that 'came up' in the past  
> - gradually - and we may expect more to come, new discoveries,  
> extending the qualitative inventory)
> although in your words 'everything' can be expressed by (many many?)  
> of your natural numbers (except  square root 2?) - what is exactly  
> my point.
>
> I did not want to open a scientific argument - I am no match for  
> you, or any other 'mathematically educated' person. I scribbled a  
> 'qualitative' idea of thinking in 'wider' terms than the defined  
> 'natural numbers' in a worldview of a (qualitative) "totality" -  
> what I pursue, but do not understand in my sci.fic agnosticism.
>
> I am sorry if I bored you with my remark.

I apologize if I gave that impression, but I try sometimes to be not  
too much long in the mails, and being short can have given that  
impression. Sorry. My point was just that there is a sense where  
natural numbers are not enough in math, and that is why mathematicians  
have extended the set N. N, then Z, then Q, then R, then the complex  
numbers, then the quaternions, octonions, etc.
But, once we assume comp, N is "ontologically" enough, all other sort  
of numbers do necessarily appear as unavoidable epistemological  
constructions, if only to understand the (additive-multiplicative)  
behavior of the natural numbers, a bit like Riemann use complex  
numbers to provide information on the prime (natural) numbers.

Without digging a bit more on the technical issue, I can hardly say  
more than my usual: there is only natural number, together with the  
additive and multiplicative law. This, assuming comp, already defines  
a "matrix" of number's dreams, and those cannot avoid the internal  
phenomenological appearance of richer structures, like the "other"  
numbers, and indeed like the whole physical appearances.

Does this help you a little bit?

Best,

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