Monday, April 16, 2012

On the existence of root two

Mathematicians are fond of defining things into existence. "If you say it exists, then it exists". This infuriates philosophers, who see existence as something that has to be proved.  You can say that p, and it can thus be true that you say that p. But that does not entail p.

Nonetheless, mathematician (and Fields medal winner) Tim Gower has an entertaining dialogue on whether you can prove the existence of the square root of two.

I like the idea that for any non-rational number you can define an ever-decreasing interval that appears to converge on the number.  For example, take any finite decimal expansion of root 2.  This will be slightly lower than the fully expanded number. Then add 1 to the digit at the very right hand side.  This will give a number slightly higher than the fully expanded number. Thus for any finite expansion whatever, you can define an interval which contains root 2.  For example, the interval
[1.4142135623, 1.4142135624]
Furthermore, for any such interval you can find the next digit in the expansion, and define in interval which lies completely inside the first interval, and which also contains root 2. For example, we know that the next digit in the expansion above is 7.  Thus  the interval
[1.41421356237, 1.41421356238]
contains root 2, and lies inside the first interval.

Thus we can prove the existence of an infinite set of intervals each of which contains root 2, and each of which can be further subdivided into another such subinterval inside that, and so on and so on.  But does that prove the existence of root 2 itself, which is not an interval, and which is 'indivisible'?  That is precisely where I lost Gowers' argument (the bit right at the end, where the disputant appears to accept the idea that you can define something into existence).

[Added as an afterthought.  I have a paper somewhere by Bolzano, written in 1917, where he attempts to prove by logic the intermediate value theorem.  It is blatantly fallacious, although a part of it eventually turned into the Bolzano-Weierstrass theorem.  This must be connected in some way, but it's so long ago I've forgotten most of it.  Could we not say, for example, that there are two sequences implied in the example above, one of increasing numbers that approach root 2 'from below', and the other of decreasing numbers which approach if 'from below'? ]

45 comments:

William M. Connolley said...

I think there are two things that are confusing. The first is that, in the standard construction of the reals (and the rationals) they aren't the same thing as integers. Unlike, say, points measured on a line, where all the points are the same, just at different distances from the origin. Considering the rationals because they are easier than reals, the rationals are usually defined as equivalence classes of pairs (a,b), where (a, b) is thought of as a/b, and so (a, b) eq (c, d) iff ad = bc (we know how to do integer multiplication, of course). Then the-equivalence-class-of (a,1) corresponds to integers in the rational world. If you make those distinctions carefully then it complicates the discussion; but the dialogue you point to only alludes to this.

The second is more directly related to sqrt(2). So, we define (finite) decimal expansions, and we know how to multiply these together. And we can also rigourously define infinite expansions, and how to multiply those together. And so we have this expansion for sqrt(2).

* Since it is a (converging) decimal expanion, we know it corresponds to a real number (real in the sense of the reals, not in the sense of the real world).
* We can demonstrate that this number is not less than sqrt(2); and that it isn't greater than sqrt(2).
* And so it must be sqrt(2) (because of the ordering properties of the reals, which we know).

William M. Connolley said...

> Then the-equivalence-class-of (a,1) corresponds to integers in the rational world.

Sorry, I mean corresponds to the integer a.

Edward Ockham said...

Thanks

>>Since it is a (converging) decimal expanion, we know it corresponds to a real number

That is the key assumption, no? What is the minimum baggage we need in order to get that?

Edward Ockham said...

>>real in the sense of the reals, not in the sense of the real world

Annnoying isn't it.

Edward Ockham said...

Ah if this is correct (and of course no reason to assume so), it is Descartes - a philosopher - we have to thank for the term 'real number'.

William M. Connolley said...

>>Since it is a (converging) decimal expanion, we know it corresponds to a real number
> That is the key assumption, no?
Its key, yes. Its not really an assumption. More a definition.

I'm now struggling to remember my maths, but there are many ways of doing it. Suppose we *define* the real numbers as infinite sequences of decimals (and ignore the tedium that 0.999...=1, which doesn't make any fundamental difference), which we can do. Then then need to demonstrate that these things we've defined behave like numbers: ie, you can add, subtract, multiply, divide and order them. You can do all this (the value of a partial sum is sum-over-i(a_i * 10^-i), in the obvious way, and you can do arithmetic on the partial sums in the obvious way), taking care of your infinite sequence convergence. That I think is the minimum baggage.

[Incidentally I think people would more usually use Dedekind cuts or equivalence classes of converging sequences as the definition, not decimals, because it is more elegant. But the key step is still the same - you can define the arithmetic on the partial sums, or cut members, and then the property of the putative real number falls out in the convergence.]

Edward Ockham said...

>>Its not really an assumption. More a definition.

Once again, this is a fundamental difference between philosophers and mathematicians. Philosophers (mostly) do not think you can conjure anything into existence by definition. Mathematicians may object "But that's how we do things", philosophers will reply "Then justify doing things that way, i.e. justify your assumption that a definition is an existential statement". I haven't seen this done.

>>Suppose we *define* the real numbers as infinite sequences of decimals

Then prove there are such things as real numbers, as you have defined them. Are there infinite sequences of decimals? Do such things exist?

>>That I think is the minimum baggage.

Well as long as you treat "there are such things as infinite sequences of decimals" as an assumption implicit in your definition "real numbers are infinite sequences of decimals".

William M. Connolley said...

> Philosophers (mostly) do not think you can conjure anything into existence by definition.

Neither do mathematicians. We don't think real numbers exist, in the real world. Whether they exist or not in maths-world isn't interesting, to most mathematicians.

> Then prove there are such things as real numbers, as you have defined them.

The question doesn't really mean anything.

> Are there infinite sequences of decimals? Do such things exist?

Yes, if you accept the axiom of infinity. No, otherwise.

>>That I think is the minimum baggage.
> Well as long as...

Oh, well there are other foundational axioms for set theory, you need those too. But most of them are "obvious".

David Brightly said...

>> Thus we can prove the existence of an infinite set of intervals each of which contains root 2, ... But does that prove the existence of root 2 itself, which is not an interval, and which is 'indivisible'? <<

An interval isn't just a pair of endpoints it's all the reals in between, so if one of them contains root 2 then surely root 2 exists? :-)

To understand Gowers's presentation it's best to put thoughts of continua and intervals to one side and think about how to do arithmetic with sequences of decimal fractions. Gowers shows how to extract the digits of root two, say, one by one, so we get a sequence of fractions
x(1)=1
x(2)=1.4
x(3)=1.41
x(4)=1.414
x(5)=1.4142
and so on with the property that, though the fractions are increasing, more and more leading digits become fixed as we go down the sequence. What he then has to show is that we can do addition and multiplication on these sequences. We define
(x+y)(n)=x(n)+(y(n)
(x * y)(n)=x(n)*y(n)
That is, the nth element of the sequence for x+y is just the sum of the nth elements of the two sequences x and y. It's a little tricky to show that the resulting sequences have the property that more and more digits become fixed as we go down the sequence. So sequences of this kind are closed under this definition of addition and multiplication. That the other required properties for an arithmetic field are present can also be shown.

We can think of these infinite sequences of rationals as proxies for our intuitive idea of real numbers. That the above x does proxy for root two can be seen by calculating
x*x(1)=1
x*x(2)=1.96
x*x(3)=1.9881
x*x(4)=1.999396
x*x(5)= 1.99996164
The string of 9s eventually (and ever after) gets as long as you care to ask. So this sequence does proxy for 2. Proof of existence by construction.

Interestingly, with Gowers's presentation you don't, I think, have to buy into actually infinite sequences of rationals. You can imagine the successive approximations being produced as and when needed to give the required accuracy. This can be programmed on computers where it's known as 'lazy' evaluation.

Edward Ockham said...

>>We don't think real numbers exist, in the real world.

So they exist, er, in some other world? Would this be in the sense (whatever that is) that Frodo exists in Tolkien's world? You have to be aware that this kind of thing sets philosophers frothing at the mouth and biting the carpet.

William M. Connolley said...

> So they exist, er, in some other world?

Most mathematicians don't really trouble themselves with that kind of question, it being rather, err, philosophical. Though when I say "most" I should add the disclaimer that I only did an undergraduate degree in same, and am hardly privy to the thinking of those at the top.

> this kind of thing sets philosophers frothing at the mouth and biting the carpet.

Whatever turns you on :-)

Anthony said...

The square root of two? Try to show the existence of two, first.

David Brightly said...

>> Try to show the existence of two, first. <<

Point taken. But note that as we ascend the number tower:

complex numbers (engineering, physics)

reals (surveying, engineering)

rationals (dividing a cake)

integers (bank accounts)

natural numbers (fenceposts)

we move away from the familiar and well-grounded. The fear is that though the foundations might seem ok, the upper storeys, like rationalist philosophy, make a house of cards.

>> Mathematicians are fond of defining things into existence. "If you say it exists, then it exists". This infuriates philosophers, who see existence as something that has to be proved.<<

We don't define things into existence, as I'm sure Ed well knows. We are far too aware of the risks. Existence (or rather existents) have to be created. We take givens and assemble them into new combinations using notions like pair, tuple, sequence, function. Though they can be given a mathematical treatment, eg, pairs seen as sets, these combining ideas could just as well be seen as logical. And if existence has to be proved there is a question of what logic is appropriate. Do we allow ourselves 'Excluded Middle', for example. Once some class of entity has been constructed, the question turns to Does one or more of them have some particular property, eg does it square to two?

As Gowers says here:

Recall that to `construct' the real numbers means to give an example of a complete ordered field. For this purpose one is allowed to assume the existence of the rational numbers (themselves constructed from the positive integers, which can, if you want, be constructed from sets) and certain notions, such as that of an infinite sequence, which are not entirely unproblematic (for reasons discussed here ) but which are in a sense more elementary.

If you have bricks you can make a house. If you have the idea of bricks you can have the idea of a house.

Anthony said...

"reals (surveying, engineering)"

For what applications of surveying or engineering will rationals not suffice? When does an engineer/surveyer need to use pi, and not 314159265358979/100000000000000, or some other, more detailed, but rational, approximation?

Anthony said...

Moreover, and I think this is a yet unanswered scientific, and not philosophical question, what is actually happening in nature?

When I cut a 1x1 square piece of paper along its diagonal, what is the actual length of the hypotenuse of the resulting triangle? Can the length of anything in reality ever actually be the square root of two? What would it mean for it to be so?

David Brightly said...

>> For what applications of surveying or engineering will rationals not suffice? <<

Sure. So-called 'floating point' numbers are essentially rationals with scale factors attached. And Q[i] would do just as well for electrical engineering and quantum mechanics calculations. I guess it's the completeness of the reals that's needed for the theoretical underpinnings of these disciplines, as they currently stand. My intention was merely to emphasise their distance from common familiarity.

Anthony said...

>> "As Gowers says here"

I'm sorry, but I basically stopped paying serious attention to that link after reading "About this last example, by the way, there can be no argument, since I am giving a definition. I can do this in whatever way I please, and it pleases me to stipulate that 1.999999... =2 and to make similar stipulations whenever I have an infinite string of nines."

There very well may be a good argument along these lines, but that wasn't it.

In fact, it's almost the beginnings of a disproof. 1.9999...=2? I can't come up with a way to accept that other than by fiat.

Anthony said...

>> I guess it's the completeness of the reals that's needed for the theoretical underpinnings of these disciplines, as they currently stand.

Okay, but at the atomic level, these theoretical underpinnings seem to be wrong.

David Brightly said...

>> Can the length of anything in reality ever actually be the square root of two? <<

No. (a) because we no longer picture material stuff as continuous at all scales, so that 'length' loses its sense in the very small, and (b) because some arbitrary unit of length will be involved, so there's no direct connection between even a classically-conceived physical length and any particular real number.

But is this a relevant question? For a mathematical entity to exist, must it be 'instantiated', as it were, in the physical? That would leave a lot of reals with 'nowhere to be'. Almost all of them, in fact.

David Brightly said...

>> but I basically stopped paying serious attention to that link <<

That's a shame. Gowers sounds perhaps a bit imperious here, I suspect for lack of space, but I'll try to justify him.

Do you perhaps think of things like '1.99999' as names for things in the world? If so, that would make maths into an empirical science, and I can see why you would object to Gowers stipulating that 1.9999...=2.0... It just might not be the case. Rather, you have to think of 1.99999... as the sequence [1, 1.9, 1.99, 1.999,...] and I'll use the trailing ellipsis notation to denote such sequences. Now, we don't normally talk about 'adding', 'comparing', etc such things. Gowers is telling us how he is going to apply these words to these sequences. He tells us what he means by 'addition' of sequences, and so on. He also says what he means by the '=' relation between two sequences and the '<' relation. He just stipulates that 1.999...=2.0... but he can show that this is consistent with <. For 2.0... < 1.999...+ε for any sequence ε you like (try it---we have only positive sequences at this stage). So, in this respect at least, 1.999... and 2.0... behave just like our pre-Gowers notion of the real number 2. Adding anything you like to either of them gives something bigger than the other. What he is showing is that his sequences, if you will allow him them in the first place, plus his use of 'addition', '<', etc, on them, behave just like the reals as we currently conceive them. The two structures are isomorphic, as we portentously like to say.

David Brightly said...

>> Okay, but at the atomic level, these theoretical underpinnings seem to be wrong. <<

Yes, I have some sympathy with this. What on earth do we mean when we say that the quantum state of some system is represented by a ray in some Hilbert space over the complex numbers? How can the latter mathematical gobbledegook relate to the actual world? One answer is that it offers a calculus for predicting what happens in the real world that seems to work very well indeed.

David Brightly said...

>> for any sequence ε you like <<

oops. any sequence ε other than 0.0..., the latter being [0, 0, 0, 0,...] of course.

Edward Ockham said...

>>Can the length of anything in reality ever actually be the square root of two?

Well yes. The distance between the ends of the hands of a clock whose hands are the same length, at precisely 9 o'clock. You object that the hands cannot be exactly the same length. I reply, take any parts of the hands which are equidistant from the centre.

The distance between the tips is then a multiple of root 2.

David Brightly said...

Ed, every real is a multiple of root 2. We might say the ratio of the distance between the tips and the common length of the hands is root 2, but that's a ratio, not a length.

Edward Ockham said...

>>every real is a multiple of root 2

Oh yes silly me. You know what I meant. The ratio.

Anthony said...

>> "For a mathematical entity to exist, must it be 'instantiated', as it were, in the physical? "

I'd remove the word "mathematical" from that sentence.

>> "That would leave a lot of reals with 'nowhere to be'. Almost all of them, in fact."

That's exactly what I'm questioning. I don't know enough about math to answer the question, but it seems to me that once we go beyond the "countably infinite" into the "uncountably infinite", we don't even have potential existence, let alone actual existence.

Interestingly, from what I know of math and physics, it seems that imaginary numbers have more of a claim to existence than real numbers. But, again, I could just be missing something that the notion of the reals are actually useful for.

Anthony said...

>> The [ratio of the] distance between the tips is then [a multiple of] root 2.

Only in euclidean geometry, which the real world most emphatically is not.

Anthony said...

Besides, how do you know it's exactly root 2? How do you know it's not root 2 rounded to the nearest planck length, or sub planck length?

You could say that we inductively assume it's true, because we don't have any reason not to...but we do have reasons to doubt that standard euclidean geometry and physics work on the scale of the extremely small.

Anthony said...

"So, in this respect at least, 1.999... and 2.0... behave just like our pre-Gowers notion of the real number 2."

You seem to be presenting an argument for 1.999...=2. Had Gowers done that, I wouldn't have "basically stopped paying serious attention" (I may or may not have been able to follow the argument, but I would have given it a try).

But Gowers doesn't present an argument. Nor does he say that the proof is merely too big to fit within the margins, so he is omitting it for space considerations. He says "there can be no argument, since I am giving a definition".

David Brightly said...

>> That's exactly what I'm questioning. <<

We are getting into the deep waters of what's meant by 'mathematical existence'. I doubt that a philosophy of mathematics would want to tie itself as strongly to the physical as you seem to be suggesting.* Would physical space not being Euclidean and three dimensional vitiate in any way the theory of linear programming (optimising economic allocation problems) which works in Euclidean space of arbitrary dimension?

*Though in the paper that Belette recommended Newstead tells us that Aristotle's Phil of math is very much 'abstraction from the natural world'. How far can abstraction go?


>> He says "there can be no argument, since I am giving a definition". <<

And that's right. Let's use bold type for sequence talk and italic type for real number talk. Gowers is defining the relations < and = between sequences in such a way that there is a mapping between sequences and reals that preserves the relations, that is

a < b iff a < b
a = b iff a = b

when sequence a maps to real a, etc. True statements about sequences and their slightly weird ordering relations correspond with true statements about reals and their usual ordering relations. That's what I mean by saying that the sequences 'stand proxy' for real numbers. The structure of the bold entities and their relations 'fits on to' (is isomorphic with) the structure of italic entities and their relations. Where Gowers is maybe a bit quick is in proving that this correspondence works. But it does.

Anthony said...

It's unclear to me what "mathematical existence" means if it doesn't mean "existence". If mathematical axioms are arbitrary, and one just defines entities into existence, then there's no point in discussing whether or not anything "mathematically exists". You just define it to exist, and it exists.

It's also unclear to me what "a philosophy of mathematics" is if it is not a branch of philosophy. And philosophy is a study of the actual, not a study of the imaginary.

Finally, you say "Where Gowers is maybe a bit quick is in proving that this correspondence works." The problem that I was addressing was with his claim that he didn't have to prove anything.

As for whether or not 1.999...=2, I accept that if 1.999... exists, then 1.999... equals 2. On the other hand, the fact that the existence of reals implies the existence of 1.999... which implies that 1.999...=2, is a reason to question the existence of reals.

Anthony said...

FWIW, I reread the Gowers presentation, and I did find it to be a good (*) presentation that infinite decimals are in fact well-defined. It seems that he (and perhaps also you?) is saying that "[mathematical] existence" is tantamount to well-definedness. On the other hand, I am saying that existence requires more than just well-definedness. Call it a "tie to the physical world". Call it the application of the principle of parsimony. These two are, I believe, aspects of the same thing, and part of the meaning of "existence".

(*) I wouldn't call it a proof as it includes some missing details, but I found no reason to doubt that those details have been proven elsewhere.

Edward Ockham said...

>>Call it a "tie to the physical world".

That's quite unnecessary for "existence". It is a reasonable question to ask whether there are non-physical things (for example, are emotions physical or not)? Regardless of the answer, if the question makes sense at all, then 'existence' per se has no tie to the physical.

Anthony said...

>> It is a reasonable question to ask whether there are non-physical things (for example, are emotions physical or not)?

Surely emotions are "tied to the physical world", which I put in quotes because it was a phrase used by David. A better phrasing would probably be "perceived or abstracted from that which we perceive".

Anthony said...

Perhaps I misunderstood David. David, how would you define "physical", and how would you define "tied to the physical"?

Anthony said...

In any case, emotions exist, but emotions are not entities, they are phenomena. David was talking about the existence of entities (which he called "mathematical entities"), not phenomena. Though I suppose maybe by "mathematical entities" he is talking about phenomena, and not entities. We'll have to ask him.

David Brightly said...

Anthony, having reread Gowers do you now see that he is completely free to stipulate that = means anything he likes with respect to his sequences? It's important that you get this. Of course, he wants it to mean something that bears a strong resemblance to =, and lo, he finds that there is a way of doing it. What he ends up with is a somewhat more concrete realisation of the real numbers. So, if you don't buy into the existence of real numbers, but do buy rationals and infinite sequences, forget worries over reals and stick to Gowersian sequences. They do the same job. The whole exercise is a typical bit of mathematical construction work, not too far removed from the way (something that can do the job of) the integers can be built as equivalence classes of pairs of naturals. Can you see that it isn't 'defining something into existence'? It's making it out of other stuff. There's nothing axiomatic at all in Gowers's piece.

>> And philosophy is a study of the actual, not a study of the imaginary. <<

Could it also be the study of the possible?

Regarding 'well-definedness', this term has at least two usages I can think of. The first is in the avoidance of empty names in proofs. 'Let P be the point where lines AB and CD intersect' can get you into a lot of trouble if you don't at first show that AB and CD do intersect. Those amusing 'proofs' of geometrical and other impossibilities often rely on some name not being well-defined. Second is when you want to define some operation on equivalence classes by operating on arbitrary representatives. You have to show that the result class is independent of which representatives you choose, else your operation is not 'well-defined'. 'Well-definedness' is important but not the whole story.

Anthony said...

Also for David: What would be the use of irrational numbers in a linear programming application used for optimizing economic allocation problems?

What is being optimized, anyway? Presumably it is something which is somehow "tied to the physical world".

If you're talking about the notion of cardinal utility functions, then I reject that theory altogether.

If not, then where do the irrational numbers come into play, and what is their meaning with regard to thing which is being optimized?

Edward Ockham said...

>>but do buy rationals and infinite sequences

I think if we have bought the idea of an infinite sequence, i.e. that such sequences exist, then we have bought pretty much everything that was for sale, no?

Anthony said...

"Anthony, having reread Gowers do you now see that he is completely free to stipulate that = means anything he likes with respect to his sequences?"

He is free to stipulate whatever he wants. But that doesn't mean he is correct.

"What he ends up with is a somewhat more concrete realisation of the real numbers."

Not really. If anything he showed a somewhat more concrete realization of one type of real number - the square root of a rational number. If it were complete - and I argue it is not - then it would be a first step toward discussing real numbers in general. But only a first step, and not a particularly big one. There are only "countably many" square roots of rational numbers.

His argument of 1.999...=2, were it complete, didn't even go that far, as 1.999..., if is a number and it equals 2, is a natural number.

"So, if you don't buy into the existence of real numbers, but do buy rationals and infinite sequences, forget worries over reals and stick to Gowersian sequences."

It's the infinite sequences I have a problem with. An infinite procedure is, by definition, a procedure which can never be completed. A completed infinity is a contradiction in terms.

This doesn't mean that the square root of two does not exist. But it does mean that any construction of the square root of two which relies on an infinite sequence is not valid.

"Could [philosophy] also be the study of the possible?"

Yes, philosophy involves studying the possible, as well as the actual. But for something to be possible, there must be some evidence for it. "Possible" does not mean merely imaginable. Someone who claims that "anything is possible" is using an improper definition of "possible".

Edward Ockham said...

>> An infinite procedure is, by definition, a procedure which can never be completed

No, an infinite process is one that can never be completed in a finite number of steps. That is the essence of Cantor's original argument.

David Brightly said...

>> I think if we have bought the idea of an infinite sequence, i.e. that such sequences exist, then we have bought pretty much everything that was for sale, no? <<

I agree. If there is a stumbling block it's the infinite sequences.

>> He is free to stipulate whatever he wants. But that doesn't mean he is correct. <<

To be free to stipulate means just that one isn't bound by some notion of correctness.

>> If anything he showed a somewhat more concrete realization of one type of real number - the square root of a rational number <<

No, he does more. He outlines how to construct a complete ordered field---the article isn't a textbook---it's intended for mathematicians who can fill in the details---and shows how it contains an element that squares to 2.

>> What would be the use of irrational numbers in a linear programming application... <<

My rhetorical point was Should we deny ourselves, say, a 23 dimensional Euclidean space for theorising about the simplex algorithm in 23 variables because this 'space' is a spectacularly bad model for what we believe of physical space.

Edward Ockham said...

I have changed the period after which moderation is required to 10 days.

The number of comments on this post is now the maximum in the history of this blog. (The previous record was set by an Ayn Rand post, not surprisingly. So, philosophy of mathematics = Objectivism.

Anthony said...

>> >> An infinite procedure is, by definition, a procedure which can never be completed

>> No, an infinite process is one that can never be completed in a finite number of steps.

And what is a finite number of steps, but a number of steps which can be completely counted?

>> That is the essence of Cantor's original argument.

Which argument?

--

>> To be free to stipulate means just that one isn't bound by some notion of correctness.

I don't get it. Bound in what way?

If his definition isn't correct (e.g. if he defines "=" such that 1.999...=3), it won't lead to useful results.

>> He outlines how to construct a complete ordered field

You forgot the scare quotes around "construct". Gowers even includes them in his own use of the word, presumably because he realizes he isn't outlining how to actually construct anything.

Edward Ockham said...

>>And what is a finite number of steps, but a number of steps which can be completely counted?

>>>> That is the essence of Cantor's original argument.
>>Which argument?

I hope the latest post may answer this