Showing posts with label easy proofs. Show all posts
Showing posts with label easy proofs. Show all posts

Tuesday, 5 July 2011

Proving 0.999999… = 1

I always knew there were people who disputed or disbelieved this fact. It did in no way worry me, because for every fact there are people who disbelieve it. There is even a man out there who claims that (–1)·(–1)=–1.

But then I came across conversations on the discussion forums of the popular xkcd webcomic (about which I wrote in this article), and that did worry me. After all, the adherents of this comic are all (assumedly) scientifically educated or at least interested—or they could not appreciate the comic fully. So those educated people were discussing the matter as well, without reaching a concensus. So I concluded that it must be a point worth clearing up once and for all, and hence this article.

On some website of jokes in a section titled “You know you are mathematician if …” I read that you could recognize mathematicians by their interest in the question whether 0.999999… was 1 or not. This made me angry; in fact you can much rather recognize non-mathematicians by it. Mathematicians don’t ponder the question because they know the answer, and it is boringly simple; they certainly do not discuss it with their peers. If they ever talk about it, it is in order to explain it to non-mathematicians who have doubts. And this, by the way, is exactly why I am doing it here.

So I will now make a note of the observation that the argument usually brought forth against 0.999999… being 1 is this:

1 is a normal number, whereas 0.999999… is not a number in the usual sense, but a process.

and I will adress this in detail below.

There is a Wikipedia article on the topic, but I ran over the page and think it does not adress the arguments commonly brought up against 0.999999… being 1. It simply takes the things for granted that are disputed by people. I thought I could do better. If, for all that, you still feel that your objection was not adressed by my article, please leave a comment, and I will try to clarify that point!

Decimal literals

First let’s look at a finite decimal literal. We find what it means is a (finite) sum of fractions, e.g.

0.234 =
2
10
+
3
100
+
4
1000

Now a nonending literal like 0.999999… is therefore an infinite sum, which in mathematics is called a series. They can be written with the “Σ” symbol:

0.999999… =
9
10
+
9
100
+
9
1000
+
9
10000
+ … =
Σ
i = 1
9
10i

And that is the point where the objection from above comes in. Summing up infinitely many numbers is a thing that simply cannot be done, because, indeed, it is a process that would never end. And all of mathematics only deals with operations that end at one point. So the argument is really to the point.

But notations as the ones above are used all the time in mathematics. How can we mathematicians use them if they are impossible? Simple: We mathematicians are a lazy lot, and we use infinite sums simply as a convenient shorthand notation for a quite different thing. In fact, all of mathematicians is a tower of shorthands of shorthands of shorthands of shorthands. If a mathematician sees that infinite sum he/she knows that it is just a shorthand for

Σ
i = 1
9
10i
 = 
lim
N → ∞
N
Σ
i = 1
9
10i

which is the limit of the sequence of the finite sums, all of which can be easily calculated. This gives us

0.999999… = lim (0.9, 0.99, 0.999, 0.9999, …)

This is the actual, precise meaning of a literal like 0.999999…, which you probably already knew. But what is a limit actually? It is the issue all the question hinges on. You may not have learned this at school. I will show you now.

Limits of sequences

I think we have a fuzzy intuitive notion of a limit. If people are asked to describe it without mathematics they will say thinks like “it is the point where the sequence goes when the indices become infinite.” It is very much like the popular phrase that is fed to school kids about how parallel lines “meet at infinity”. It is a convenient way of visualizing the thing (in a fuzzy way), but if you think about it with any degree of stringency, you get into trouble, because it is simply wrong. You cannot track a sequence up to infinity, because it is a never-ending process. Also infinity is not a place nor a number. Parallel lines do not meet at infinity because there is no such place. They do not meet at all. Likewise the sequence 0.9, 0.99, 0.999, 0.9999, … never reaches 1.

No, limits are a mathematically precisely defined concept. For a sequence a1, a2, a3, a4, … we call a number a the limit of the sequence if and only if

ε > 0:  Nε ∈ ℕ:  n > Nε: |aan| < ε

This is of course mathematical notation, which you might not understand, but I just could not resist putting it here because it is so beautiful. What it means in plain English is this:

A sequence is called converging to a number (which is then called the limit of that sequence), if any arbitrarily small vicinity of the limit is eventually entered by the sequence and never left any more.

With “vicinity” we mean an interval of real numbers containing the limit, but where the limit is not one of the borders. Usually we make these intervals symmetric, namely (if a is the limit) [aε, a+ε], which is the interval of all numbers whose distance from a is at most ε.

So there has to be a sequence index n, where the sequence element an has a distance from a less than ε and all subsequent elements do so too. For example the sequence

1, 0.1, 5, 0.01, 0.001, 5, 0.0001, 0.00001, 5, …

does not converge to zero because every third element is 5, and therefore for every distance smaller than 5 the sequence will break out of the vicinity around 0 at every third element.

So obviously not every sequence has a limit (i.e., is convergent), but if it has a limit, it has only one. There cannot be multiple different limits to one sequence, which is very easy to prove.

Note that this approach (which was invented by Cauchy in the early 19th century) works in a way backwards from the intuitive notion. We can not take a sequence, do the limiting process, and arrive at a limit number. Instead we have to start with a number we think is the limit number (by educated guessing, intuition or one of many tricks that exist for this purpose), and then merely test whether it satisfies the condition for a limit as stated above. This may sound like a frustrating state of affairs, but it cannot be done better.

Let’s consider a stupid illustrative example. Imagine a turtle that crawls towards a goal line. After one minute it arrives at a position one meter before the line. But the run has made it tired, so now it is getting slower and in the next minute it only manages half of the distance remaining, ending up at half a meter from the line. It’s getting more tired still, so after the third minute it is still a quarter of a meter from the line. After the fourth minute one eighth of a meter remains and so on.

Now the intuitive approach would be to ride the turtle, so to speak, and see where it will arrive. As we know by now, it won’t work, because it will never arrive anywhere but will crawl on without end.

The Cauchy method means that we guess where the turtle is going (the goal line), so we just position ourselves on that line and consider: For any small distance from the line, will the turtle eventually arrive there and not go back? The answer is of course yes; we can easily give a formula when it will pass any point with distance ε>0 from the goal line (it involves a logarithm). Also we know it will never overshoot the goal, so the limit is not somewhere beyond the line. So we have proven that the goal line is precisely the limit of the turtle’s movement.

I think I have said enough now about limits, and you understand the concept. But there is another thing I want to mention because it is fun (for me, at least).

Famous Argentine author Jorge Luis Borges once wrote an essay titled The Eternal Footrace, which deals with the famous ancient greek logical paradox of the race between Achilles and a turtle. (Invented by Zeno of Elea, for us it is not a paradox anymore. We have solved it, precisely by the application of Cauchy’s definition of a limit.) To quote from that essay:

One only needs to numeralize the speed of Achilles as one meter per second to give the time he needs as follows:

10 + 1 +
1
10
+
1
100
+
1
1000
+
1
10000
+ …

The final value of the sum of this infinte geometric progression is twelve (more exactly, eleven and a fifth; more exactly eleven and three twenty-fifths), but it will never be reached.

The funny thing is that Borges correctly identified the series as a geometric one, but totally failed to give the correct limit. He gave several values, as you saw, but admitted they were only approximations. I have no idea why he could not do it. The correct formula to derive the limit is taught in schools, and has been known for thousands of years. In this case the result is eleven and a ninth. Also you might have noticed how turtles seem to be important mathematical animals.

Wrapping things up

Now we can apply this definition to our sequence 0.9, 0.99, 0.999, 0.9999, …. I claim the limit is exactly one; let’s test if the Cauchy criterion holds.

As with the turtle example, the sequence will never overshoot 1; therefore the limit is certainly not larger than 1. Take for example a distance of 0.0001 from 1: it will be reached by the sequence with the fouth element and the following ones will not drop back down again. A distance of 0.0000000001 will be reached with the 10th element and so on. Generally a distance of ε>0 will be reached with the first element whose index is at least log(1/ε), where “log” is the common logarithm.

So that’s the proof and therefore

0.999999… = lim (0.9, 0.99, 0.999, 0.9999, …) = 1

What’s there to say more on the issue? I don’t know. You might be saying, “you claim a limit is that thing you described, but I say it is something else.” Well, that is exactly as if you said that “” is not a quarter note, but something else. I am sorry, but it is. It just is defined that way.

Mathematical expressions like “0.999999…” are just strokes on the paper (or screen) that were ascribed certain meanings to by mathematicians. And if you use these strictly defined meanings you arrive at 0.999999…=1 as shown. There’s no hidden notion there that transcends the definition. It’s just black strokes, and we define what they mean.

Now please note this: You may very well assign a different meaning to these penstrokes and symbols, which does not give you the value of 1. It is allowed , and mathematicians play with things all the time. There is no conspiracy or establishment or mainstream at work to keep you from it. The usual definition is in no way more true than any other (provided it is logically consistent!), just like baseball is not more true than softball. Just be aware that your results do not tell you anything about the results of people who are using a different definition. In addition, always clearly state your definitions, if they deviate from the usual, so others can see what you were doing. For example, the word “also” means “too” or “as well”, whereas in German “also” means “therefore”. Would you say the English word proves that German is wrong?

Monday, 24 January 2011

Proving 1 + 1 = 2

Mathematics is the science where we always prove things. This has even entered into popular rhetorics: If we claim that some fact or other is “mathematically proven” it is the highest kind of authority. Usually this is sloppy phrasing or simply a lie, because sociological, psychological, political, even physical facts cannot be mathematically proven, because you can only mathematically prove mathematic statements, and they are not. Mostly they are, if at all, juristically proven (“true beyond a reasonable doubt”). But in our own sphere we mathematicians prove everything, and if we can’t we don’t assume that thing as true (be that painful as it may).

I have a few times explained this to students. Usually the consequence is that someone ask me how you can prove that 1 + 1 = 2, or something along that line. In these cases I have to admit I generally just answer that this is indeed possible to prove, but don’t show how. The reason is that it simply would take too long. But here in this medium I have all the time I need.

If you read this article (and others in the same vein, which are sure to come soon) you will know what lies at the heart of mathematics. This is the stuff they don’t teach at school and I promise, it won’t contain any of the stuff you learned to hate when you were 14. (Fractions, for example: A neat and immensely useful method, but how on earth could anybody like doing them? It’s the results and the proofs that give satisfaction, the nuts-and-bolts calculations is just work for performing monkeys.)

If you feel that despite this you cannot be interested just skip this article! Mathematics is just one of my topics in this blog.

We start by asking: what are 1 and 2 anyway, or to be more exact: what are numbers?

For quite some time mathematicians have been using a tool called the axiomatic method. This lies at the roots of all mathematics, and certainly deserves to be talked about in detail. But I want to keep this article as short as possible and so I am forced to defer this undertaking to some other time. But I promise I will make good for it soon!

The basic idea is this: We might think we all share a common notion of numbers (that is natural numbers, 1,2,3,4 etc.). But is it true? In prehistoric times people used to count “one–two–many…” (allegedly there is still a tribe in Brazil that does that), and I read somewhere that in Indo-European languages the words “nine” and “new” are etymologically related—because when nine was invented after centuries of people only knowing 1 to 8 it became the new number (about 5000 years ago).

So I think we certainly do not have an instinctive notion of numbers. We merely learn it at a young age because our world is filled with numbers.

Learning numbers that way resembles learning a game by watching other people play and trying for yourself until you are sure you are doing it right. The downside is that in this way you can never be sure you are doing it right. Maybe in the next match a situation might arise where you do not know what to do? Some special case you are not prepared for?

But mathematicians want to be sure. In this analogy, it would mean that we want to thoroughly read the rules of the game before we play.

So mathematicians (actually it was an Italian, Giuseppe Peano) wrote down a set of rules (or axioms) for natural numbers. They clearly state which (natural) numbers exist and some properties of them. Here are Peano’s axioms:

  1. There is a natural number, call it 1.
  2. For every natural number n there is a natural number n′ which is the successor of n.
  3. The successor of any natural number is not 1.
  4. If two natural numbers have the same successors, they are the same.
  5. If a set of natural numbers contains 1 and, for every number n in it also contains its successor n′, then that set is the set of all natural numbers.

Once we have these rules we will never give a thought to what natural numbers actually are. We don’t know and we don’t need to know. All we need to know is that we can use these rules freely. We have no idea what numbers are, but we know what they do. (If I write any more on this, it is bound to get philosophical and I am going to reserve that for some other occasion. Suffice to say that however you may look on the matter, if you accept these rules as true you are still with me—and we will not use anything other than these rules.)

Adding up

Now can define a few numbers and give them names:

  • 1 we already know.
  • 2 = 1′
  • 3 = 2′ = 1″

and so on …

Now we know what 1 and 2 are, what what do we mean by “+”?

The task at hand is to define addition using only the Peano rules of natural numbers. This is done by stating two simple laws of addition, which I am sure will concur with your “instinctive” notion of Addition. We state:

“+” is an operator between two natural numbers that satisfies the following laws:

  1. n + 1 = n′ for all natural numbers n.
  2. n + m′ = n′ + m for all natural numbers n and m.
Now what is 1 + 1? We simply use the first rule, setting n = 1 and get

1 + 1 = 1′ = 2.

That is a proof. If we consent that natural numbers satisfy the Peano rules and that addition satisfies the two rules stated above and 2 is the successor of 1 then 1 + 1 = 2 is mathematically proven.

Now that was disappointingly simple. Let’s try for something harder. What’s 2 + 2 (that is 1′ + 1′)?

This time we start with addition rule (2). We find 1′ + 1′ = 1″ + 1. After that we once again use rule (1) and obtain

2 + 2 = 1′ + 1′ = 1″ + 1 = 1′′′ = 4.

I think you will now have no problem calculating 5 + 9 or whatever takes your fancy.