The Art of Proof

Before You Get Started. You have used numbers like 1,2,3,34,101, etc., ever since you learned how to count. And a little later you also met numbers like 0,–11,–,40. You know that these numbers—they are called integers—come equipped with two operations, “plus” and “times.” You know some of the properties of these operations: for example, 3+5 = 5+3 and, more generally, m+n = n+m. Another example: 3 ∙ 5 ∙ 7 is the same whatever the order of multiplying, or, more abstractly, (k ∙ m) ∙ n = k ∙ (m ∙ n). List seven similar examples of properties of the integers, things you know are correct. Are there some of these that can be derived from others? If so, does that make some features on your list more fundamental than others? In this chapter we organize information about the integers, making clear what follows from what.We begin by writing down a list of properties of the integers that your previous experience will tell you ought to be considered to be true, things you always believed anyway. We call these properties axioms. Axioms are statements that form the starting point of a mathematical discussion; items that are assumed (by an agreement between author and reader) without question or deeper analysis. Once the axioms are settled, we then explore how much can be logically deduced from them. A mathematical theory is rich if a great deal can be deduced from a few primitive (and intuitively acceptable) axioms. If you open a mathematics book in the library, you usually will not see a list of axioms on the first page, but they are present implicitly: the author is assuming knowledge of more basic mathematics that rests on axioms known to the reader. In short, we have to start somewhere. The axioms in one course may in fact be theorems in a deeper course whose axioms are more primitive. The list of axioms is simply a clearly stated starting point.

Before You Get Started. From previous mathematics, you are accustomed to the symbol <. If we write 7 < 9 you read it as “7 is less than 9,” and if we write m < n you read it as “m is less than n.” But what should, for example, “n greater than 0” mean? If you look back over what we have done so far, you will notice that we have not ordered the integers: even the statement 0 < 1 does not appear. Here we impose another axiom on Z to handle these questions. This axiom will specify which integers are to be considered positive. What should it mean for an integer to be positive? Try to come up with an axiomatic way to describe positive integers. And then think about how we could use positive integers to define the symbol <. Another question: Is Z an infinite set? And what does this mean? Without Axiom 2.1 below we have no answer. We deal with this in Chapter 13.

Before You Get Started. We have already used phrases like for all, there exists, and, or, if... then, etc. What exactly do these mean? How would the meaning of a statement such as Axiom 1.4 change if we switched the order of some of these phrases? We will also need to express the negations of mathematical statements. Think about what the negation of an and statement should look like; for example, what are the negations of the statements “John and Mary like cookies” or “there exist positive integers that are not prime”?

Before You Get Started. You have most likely seen sums of the form \(\sum\nolimits_{j = 1}^k {j = 1 + 2 + 3 + \cdots + k,}\) or products like \(k! = 1 \cdot 2 \cdot 3 \cdots k.\) In this chapter we will use the idea behind induction to define expressions like these. For example, we can define the sum 1+2+3+ ∙ ∙ ∙ +(k+1) by saying, if you know what 1+2+3+ ∙ ∙ ∙ +k means, add k+1 and the result will be 1+2+3+ ∙ ∙ ∙ +(k+1). Think about how this could be done; for example, how should one define 973685! rigorously, i.e., without using ∙ ∙ ∙ ? Find a formula for 1+2+3+ ∙ ∙ ∙ +k.

Before You Get Started. Just like the integers, the real numbers, which ought to include the integers but also numbers like \(\frac{1}{3}, - \sqrt {2},{\rm and}\ \pi,\) will be defined by a set of axioms. From what you know about real numbers, what should this set of axioms include? How should the axioms differ from those of Chapters 1 and 2? We start all over again. You have used the real numbers in calculus. You have pictured them as points on an x-axis or a y-axis. You have probably been told that there is a bijection between the set of points on the x-axis and the set of all real numbers. Even if this was not made explicit in your calculus course, it was implied when you gave a real-number label to an arbitrary point on the x-axis, or when you assumed that there is a point on the x-axis for every real number. Intuitively, you are familiar with many real numbers: examples are \( - \sqrt 2,\pi,{\rm and}\ 6e.\) You probably thought of the integers as examples of real numbers: you calibrated the x-axis by marking two points as “0” and “1”, thus defining one unit of length; and, with that calibration, you knew which point on the x-axis should get the label “7” and which should get the label “–4”. The exact relationship between the integers and the real numbers will require careful discussion in Chapter 9. We are now going to rebuild your knowledge of the real numbers. In the first stage, which is this chapter, we will define the real numbers by means of axioms, just as we did with the integers in Part I. And as we did with the set of integers Z, we will assume without proof that a set R satisfying our axioms exists.

We have now defined two number systems, Z and R. Intuitively, we think of the integers as a subset of the real numbers; however, nothing in our axioms tells us explicitly that Z can be viewed as a subset of R. In fact, at the moment we have no axiomatic reason to think that the integers we named 0 and 1 are the same as the real numbers we named 0 and 1. Just for now, we will be more careful and write 0 _Z and 1 _Z for these special members of Z, and 0 _R and 1 _R for the corresponding special members of R. Informally we are accustomed to identifying 0 _Z with 0 _R R and identifying 1 _Z with 1 _R . We will justify this here by giving an embedding of Z into R, that is, a function that maps each integer to the corresponding number in R. Before You Get Started. How could such an embedding function of Z into R be constructed? From what you know about functions, what properties will such a function have?

Before You Get Started. You probably know that the sequence of real numbers \(\frac{{n - 1}}{n}\) converges to the real number 1 as n gets larger. What exactly does this mean? Can you guess a definition of “converges” that does not use words like “nearer and nearer to” or “approaches”? Think about the picture above. Each black triangle occupies \(\frac{{1}}{4}\) of the area of its “parent” triangle. If the area of the biggest triangle is 1, then the sum of the areas of all the black triangles should be thought of as \(\frac{1}{4} + \frac{1}{{4^2 }} + \frac{1}{{4^3 }} \cdots.\) You might remember from previous math courses that the sum of this series is \(\frac{{1}}{3}\). Can you see in the picture that the blackened area constitutes \(\frac{{1}}{3}\) of the total area of the biggest white triangle? (Look at the white-black-white horizontal rows of triangles.) This is an example of convergence.

Before You Get Started. What is a fraction? Is it a real number? Are all real numbers fractions? Have you seen fractions in this book up to now? What real number should the fraction \(\frac{1}{2}\) be?

Our goal in this chapter is to prove that every real number can be represented by a decimal and that every decimal represents a real number. Before You Get Started. In Chapter 7 we discussed base-ten representation of integers. In fact, all real numbers can be given base-ten representations: this is what you called “decimals” in grade school. Do you remember repeating and nonrepeating decimals? For example, the decimal expansion 0.1111... is supposed to represent the number \(\frac {1}{9}.\) Why is this a valid expression for \(\frac {1}{9}\) ? What is a decimal expansion of \(\frac{1}{8}\ {\rm or}\ \sqrt 2 ?\)

Before You Get Started. The goal of this chapter is to compare the sizes of infinite sets. It is perfectly sensible to say that the sets {1,2,4} and {2,3,5} have the same size (still you might think about how to define rigorously what it means for two finite sets to have equal size), but how do we compare the sizes of N and Z, of N and R _>0, of Q and R? We want to say more than just “they are all infinite”—how do they compare? Are they all of different sizes? More generally, how should we measure the size of infinite sets?

We have had several purposes in this book: To teach you to read mathematics by encouraging you to read your own mathematics: to know the difference between an incorrect argument and a correct argument. To teach you to do mathematics: to discover theorems and write down your own proofs, so that what you write down accurately reflects what you discovered and is free of mistakes. As time goes on, your style of writing mathematics will improve: watch how the writers of your textbooks write. Develop opinions about good and bad writing. To teach you to write mathematics so that it is communicated accurately and clearly to another qualified reader. To introduce you to the axiomatic method. This was explained in Chapter 1, but the point may not have been clear at the beginning. Please reread Chapter 1. To teach you induction, one of the most fundamental tools. To make you understand the real numbers and how the rational numbers are distributed in them. To put the whole mathematics curriculum from Sesame Street through calculus in perspective.

It is likely that your first calculus class included a discussion of continuity. Many students find the definition hard to understand, and in many calculus classes the fine details are skipped. One of the rewards of mastering the kind of mathematics discussed in this book is that items like \(\varepsilon - \delta\) the definition of continuity are suddenly revealed as quite easy.

In this chapter, we will explore some computational aspects of modular arithmetic, which we studied in Chapter 6. We will be concerned about how to compute certain numbers in a most efficient way. There is a whole field at work here, of which we barely scratch the surface, called computational complexity. For example, in Section 6.4 we introduced the concept of greatest common divisor (gcd). You might wonder how quickly one could compute the gcd of two, say, 1000-digit integers. As another example, we now discuss how to quickly compute a ^b modulo c for given positive integers a, b, and c.

One deficiency of the real numbers is that the equation \(x^2 = - 1\ {\rm has\ no\ solution}\ x \in {\rm \mathbf R}\) (Corollary 11.23). In this chapter, we will extend R to overcome this deficiency; the price that we will have to pay is that this extension does not have a useful ordering relation.

A group is a set G equipped with a binary operation, ∙, and a special element, \(1 \in G,\) satisfying the following axioms: (i) For all \(g,h,k \in G,(g \cdot h) \cdot k = g \cdot (h \cdot k).\) (ii) For each \(g \in G,g \cdot 1 = g.\) (iii) For each \(g \in G\ {\rm there\ exists}\ g^{ - 1} \in G\ {\rm such\ that}\ g \cdot g^{ - 1} = 1.\)

Assume \((a_n )_{n = 0}^\infty\) is a sequence of real numbers that is not explicitly defined by a formula, for example, a recursive sequence. One can sometimes get useful information about this sequence—identities, formulas, etc.— by embedding it in a generating function: \(A(x): = \sum\limits_{n - 0}^\infty {a_n x^n}.\) We use the convention that the members of the sequence are named by a lowercase letter and the corresponding generating function is named by its uppercase equivalent. We think of this series A(x) as a formal power series, in the sense that questions of convergence are ignored. So operations on formal power series have to be defined from scratch.

Recall from Chapter 13 that we write card A = card B if there is a bijection A → B. Then we say that A and B have the same cardinal number. We write card A ≤ card B if there is an injection A → B. In this latter case we say that the cardinal number of A is less than or equal to the cardinal number of B. Recall that card N ≤ card R but card N ≠ card R.

You have studied geometry in high school, a version of what was assembled from knowledge of the ancient Greeks (around 300 BCE) by the Greek-speaking textbook writer Euclid, who lived in Alexandria, Egypt.