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 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/
>
>
>
>
> >
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 - 17:06:02 PDT