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