## Proof by Contradiction: Knights and Liars

I am currently reading a local book about mathematical problem solving and I came across with a cute proof demonstrating proof by contradiction.  Actually, I heard a very similar problem ages ago, but I never really thought that it was mathematical and never really bothered to solve it.

Anyway, according to the authors, the problem was based on the lectures given by Oleg Goldberg (an International Math Olympiad gold medalist) at the IDEA MATH program, a weekend extracurricular training on problem solving [in Massachussettes?].  The problem and proof are as follows.

Problem

All natives of the Idea island are either knights or liars. Knights always tell the truth, and liars always lie.  A person says “I am a liar.” Prove that he is not an Idea native.

Note: The idea of putting the image below is to let you do the proof first before scrolling down.  So, no peeking please. » Read more

## More examples of proof by contradiction

We have had good discussions on mathematical proofs, so I am planning to create a mathematical proof series that will discuss the basics such as direct proof, indirect proof, and proof by mathematical induction.  But before I do that, let me continue with more examples of proof by contradiction.

Proof by contradiction, as we have discussed, is a proof strategy where you assume the opposite of a statement, and then find a contradiction somewhere in your proof. Finding a contradiction means that your assumption is false and therefore the statement is true. Below are several more examples of this proof strategy.

Example 2: $\sqrt{6}$ is irrational. The proof of this is basically the same as example 1, so it is left as an exercise.

Example 3: Proof that there are infinitely many primes.

Example 4: Knights and Liars

Example 5: $\sqrt{2} + \sqrt{3}$ is irrational. » Read more

## Is 0.999… really equal to 1?

Introduction

Yes it is. 0.999…  is equal to 1.

Before we begin our discussion, let me make a remark that the symbol “…” in the decimal 0.999… means that the there are infinitely many 9’s,  or putting it in plain language, the decimal number has no end.

For non-math persons, you will probably disagree with the equality, but there are many elementary proofs that could show it, some of which, I have shown below. A proof is a series of valid, logical and relevant arguments (see Introduction to Mathematical Proofs for details), that shows the truth or falsity of a statement.

Proof 1

$\frac{1}{3} = 0.333 \cdots$

$\frac{2}{3} = 0.666 \cdots$

$\frac{1}{3} + \frac{2}{3} = 0.333 \cdots + 0.666 \cdots$

$\frac{3}{3} =0.999 \cdots$

But $\frac{3}{3} = 1$, therefore $1 =0.999 \cdots$

Proof 2

$\frac{1}{9} = 0.111 \cdots$
Multiplying both sides by 9 we have

$1 = 0.999 \cdots$

Proof 3

Let $x = 0.999 \cdots$

$10x = 9.999 \cdots$

$10x - x = 9.999 \cdots - 0.9999 \cdots$

$9x = 9$

$x = 1$

Hence, $0.999 \cdots = 1$

Still in doubt?

Many will probably be reluctant in accepting the equality $1 = 0.999 \cdots$ because the representation is a bit counterintuitive.  The said equality requires the notion of the real number system, a good grasp of the concept of limits, and knowledge on infinitesimals or calculus in general.  If, for instance,you have already taken sequences (in calculus), you may think of the $0.999 \cdots$ as a sequence of real numbers $(0.9, 0.99, 0.999,\cdots)$. Note that the sequence gets closer and closer to 1, and therefore, its limit is 1.

Infinite Geometric Sequence

My final attempt to convince you that $0.999 \cdots$ is indeed equal to $1$ is by the infinite geometric sequence. For the sake of brevity, in the remaining part of this article, we will simply use the term “infinite sequence” to refer to an infinite geometric sequence.  We will use the concept of the sum of an infinite sequence, which is known as an infinite series, to show that $0.999 \cdots = 1$.

One example of an infinite series is $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots$.  If you add its  infinite number of terms, the answer is equal to 1. Again, this is counterintuitive.

How can addition of numbers with infinite number of terms have an exact (or a finite) answer?

There is a formula to get the sum of an infinite geometric sequence, but before we discuss the formula, let me give the geometric interpretation of the sum above. The sum $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \cdots$ can be represented geometrically using a 1 unit by 1 unit square as shown below. If we divide the square into two, then we will have two rectangles, each of which has area $\frac{1}{2}$ square units. Dividing the other half into two, then we have three rectangles with areas $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{4}$ square units. Dividing the one of the smaller rectangle into two, then we have four rectangles with areas $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{8}$. Again, dividing one of the smallest rectangle into two, we have five rectangles with areas $\frac{1}{2}$, $\frac{1}{4}$, $\frac{1}{8}$, $\frac{1}{16}$, and $\frac{1}{16}$ Since this process can go on forever, the sum of all the areas of all the rectangles will equal to 1, which is the area of the original square.

Now that we have seen that an infinite series can have a finite sum, we will now show that $0.999 \cdots$ can be expressed as a finite sum by expressing it as an infinite series. The number $0.999 \cdots$ can be expressed as an infinite series $0.9 + 0.09 + 0.009 + \cdots$. Converting it in fractional form, we have  $\frac{9}{10} + \frac{9}{100} + \frac{9}{1000} + \cdots$.

We have learned that the sum of the infinite series with first term $\displaystyle a_1$ and ratio $r$ is described by $\displaystyle\frac{a_1}{1-r}$. Applying the formula to our series above, we have

$\displaystyle\frac{\frac{9}{10}}{1-\frac{1}{10}} = 1$

Therefore, the sum our infinite series is 1.

Implication

This implication of the equality $0.999 \cdots =1$ means that any rational number that is a non-repeating decimal can be expressed as a repeating decimal. Since $0.999 \cdots =1$, it follows that $0.0999 \cdots =0.1, 0.00999 \cdots=0.01$ and so on. Hence, any decimal number maybe expressed as number + 0.00…01. For example, the decimal $4.7$, can be expressed as $4.6 + 0.1 = 4.6 + 0.0999 \cdots = 4.6999 \cdots$. The number $0.874$ can also be expressed as $0.873 + 0.001 = 0.873 + 0.000999 \cdots = 0.873999 \cdots$

Conclusion

Any of the four proofs above is actually sufficient to show that $0.999 \cdots = 1$.  Although this concept is quite hard to accept, we should remember that in mathematics, as long as the steps of operations or reasoning performed are valid and logical, the conclusion will be unquestionably valid.

There are many counterintuitive concepts in mathematics and the equality $0.999 \cdots = 1$ is only one of the many.  In my post, Counting the Uncountable: A Glimpse at the Infinite, we have also encountered one:   that the number of integers (negative, 0, positive) is equal to the number of counting numbers (positive integers) and we have shown it by one-to-one pairing. We have also shown that the number of counting numbers is the same as the number of rational numbers. Thus, we have shown that a subset can have the same element as the “supposed” bigger set.  I guess that is what makes mathematics unique; intuitively, some concepts do not make sense, but by valid and logical reasoning, they perfectly do.

Notes:

1. You can find discussions about 0.999… = 1 here and here.
2. There is another good post about it here and here.
Related Articles