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,


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  

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.



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to