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 02 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 00 letters (the empty word), then 01 letter, then 2
> letters, then 03 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:
>
> 04 -------> aa
> 05 ------> ab
> 06 ------> ac
>
> 07 ------> ba
> 08 ------> 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.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Wed Sep 09 2009 - 09:21:47 PDT