Reading, Writing, and Proving

Frontmatter

Chapter 1. The How, When, and Why of Mathematics

Abstract

What is mathematics? Many people think of mathematics (incorrectly) as addition, subtraction, multiplication, and division of numbers. Those with more mathematical training may think of it as dealing with algorithms. But most professional mathematicians think of it as much more than that. While we certainly hope that our students will perform algorithms correctly, what we really want is for them to understand three things: how you do something, why it works, and when it works. The problems we present to you in this book concentrate on these three goals. If this is the first time you have been asked to prove theorems, you may find this to be quite a challenge. Not only will you be learning how to solve the problem, you will also be learning how to write up the solution. The necessary definitions and background to understand a problem, as well as a general plan of attack, will always be presented in the text. It’s up to you to spend the time reading, trying various approaches, rereading, and reapproaching. You will probably be spending more time on fewer exercises than you ever have before. While you are now beyond the stage of being given steps to follow and practice, there are general rules that can assist you in your transition to doing higher mathematics. Many people have written about this subject before. The classic text on how to approach a problem is a wonderful book called How to Solve It by George Pólya, [84].

Ulrich Daepp, Pamela Gorkin

Chapter 2. Logically Speaking

Abstract

Suppose your friend tells you that Mr. Hamburger is German or Swiss. You happen to know that Mr. Hamburger is not Swiss. Using your powers of reasoning, you decide that Mr. Hamburger is German. Note that this argument can be generalized, because it doesn’t really depend on Mr. Hamburger being Swiss or German. If your friend said that “A or B is true” and you happened to know that “B is not true,” you would conclude that “A is true.” This is an example of a valid argument. Now suppose your friend tells you that Mr. French eats only pickles on Wednesday, and only chocolate on Monday. You know that Mr. French is eating chocolate that day. Now what can you say? While you may conclude that Mr. French has odd eating habits, you would not have used a logically valid argument to do so. In this example, there is really only one thing you can conclude.We’ll return to this at the end of this chapter.

Ulrich Daepp, Pamela Gorkin

Chapter 3. Introducing the Contrapositive and Converse

Abstract

In the last chapter (see Theorem 2.7) we saw that two statement forms, P and Q, that have the same truth table are equivalent. This was also expressed by showing that the equivalence, P↔Q, is a tautology. When you are confronted with a mathematical statement that you need to prove, you will often find it helpful to paraphrase it. You will use tautologies to do so, since you don’t want to change the truth value of your statement. Some useful tautologies appeared in Theorem 2.9. More appear below and throughout this chapter.

Ulrich Daepp, Pamela Gorkin

Chapter 4. Set Notation and Quantifiers

Abstract

Consider the sentence “The equation x ²+2x = 15 has a unique solution.” Thus far, we’ve approached such things intuitively. It’s time now to tackle this head on. Is it true? False? It depends on which x we have in mind, of course.We turn to a rigorous way to make our sentence x ² +2x = 15 into a statement. But before we get to the heart of this chapter, it will be useful to have notation for the things with which we frequently work.

Ulrich Daepp, Pamela Gorkin

Chapter 5. Proof Techniques

Abstract

In this chapter, we introduce you to some of the most common proof techniques. The three methods we will examine in this section are: direct proof (just get started and keep going), proof by contradiction (show that the negation of the statement you wish to prove implies the impossible), and proof in cases (which may be used when conditions dictate that different situations occur).

Ulrich Daepp, Pamela Gorkin

Chapter 6. Sets

Abstract

In Chapter 4 we introduced the terms set and element of a set. In order to have some flexibility and to avoid the slightly awkward phrase set of sets, we will use the word collection as a synonym for set. In particular, we will usually speak of a collection of sets, which is just a set of sets. Just as you worked with points and lines in geometry without having a rigorous definition of those terms, we will ask you to use your intuition as you work with the terms set and element. It’s important to note that you will need to exercise care when you use these words. Mathematics describes very carefully and exactly what you can do with sets and when you can use the words element of a set. In particular, the construction of “the set of all sets” is forbidden, as this would lead to contradictions. In order to get around such contradictions, mathematicians have developed axioms. These are listed in the Appendix as the Zermelo–Fraenkel system together with the axiom of choice (ZFC, for short). At this point, we will introduce our subject in a less formal way, leaving a more axiomatic treatment for a later course in set theory.

Ulrich Daepp, Pamela Gorkin

Chapter 7. Operations on Sets

Abstract

By an operation on sets we mean the construction of a new set from the given ones. As we saw in the last chapter, these new sets may be formed using unions, intersections, set differences, or complements of given sets. In this section, we will look at many important properties of operations on sets. We end the chapter with a summarizing list of identities. In the exercises and problems you will be given the opportunity to prove the most important ones and then commit them to memory, so you don’t have to re-prove them every time you need them.

Ulrich Daepp, Pamela Gorkin

Chapter 8. More on Operations on Sets

Abstract

Most of what we did in the last two chapters was concerned with operations on two sets. In Exercise 6.14 we defined unions and intersections of three sets. In general, we may have two or three sets, as many sets as there are integers, or even more sets than that. We’ll need a new definition and special notation. In this chapter, we will introduce the notation that will allow us to keep track of these sets. Unfortunately, a rigorous definition will have to wait until Chapter 14.

Ulrich Daepp, Pamela Gorkin

Chapter 9. The Power Set and the Cartesian Product

Abstract

Now that we know about sets, we can construct some new ones from old ones in even more ways than we did before. In this section we look closely at two special sets: the first is called the power set, and the second is called the Cartesian product of two sets.

Ulrich Daepp, Pamela Gorkin

Chapter 10. Relations

Abstract

In the last chapter we introduced relations. We will now look at three useful properties of relations. Recall that “S is a relation on a set X” is one way of saying that S is a subset of X ×X, and therefore the elements of S are ordered pairs, (x,y). Many authors write x ~ y rather than\((x,y)\, \in \,S.\) Sometimes we will write x ~y and other times we will write \((x,y)\, \in \,S,\) and this is exactly the same thing. So why do it? Because sometimes one notation is more convenient than the other. Use the next exercise to familiarize yourself with both notations.

Ulrich Daepp, Pamela Gorkin

Chapter 11. Partitions

Abstract

It is sometimes helpful to split a nonempty set into disjoint smaller pieces. For example, we might have reason to split the integers into positive integers, negative integers, and the set containing zero alone. We often split the real numbers into rational numbers and irrational numbers, or we might want to break ℝ² down into distinct vertical lines. All of these are examples of partitioning a space.

Ulrich Daepp, Pamela Gorkin

Chapter 12. Order in the Reals

Abstract

You’ve seen numbers ever since you’ve been in school, and you know a lot about them. It is possible to give them a careful mathematical foundation. In fact, it’s possible to construct the natural numbers (and you can do so in Project 29.3). Then, if you try to introduce operations like addition and subtraction, you’ll find that you are missing something: the negative numbers. So you look at the integers, and try again. Now, trying to introduce multiplication and division, you’ll find you are missing something again: multiplicative inverses. So you look at the rational numbers, and you’ll find you are missing something yet again. That brings you to the real numbers. Our ultimate goal will be to discuss what’s missing in ℚ, and to show you why ℝ has what’s missing. This is known as completeness of ℝ. In this and the next chapter, we’ll show you some wonderful applications of completeness.

Ulrich Daepp, Pamela Gorkin

Chapter 13. Consequences of the Completeness of ℝ

Abstract

We have now reached the point at which we can give rigorous proofs of two facts you have known for some time. We mention the second first; that is, we will conclude this chapter by showing that there is a nonempty bounded subset of ℚ that does not have a supremum in ℚ. As an exercise, you will show that there is also a nonempty bounded subset of ℚ that does not have an infimum in ℚ. In this sense, ℚ is not complete. Since ℝ is complete, there must be numbers in ℝ that are not in ℚ. We know what these numbers are, of course; they are the irrational numbers. Thus far we haven’t proven that a particular real number is irrational. But now we can! This will be the first fact that we prove. Here’s a rough outline: We will show that if a is a positive real number, then a has a positive square root; that is, there exists \(x\, \in \mathbb{R}^ +\) such that \(x^2 \, = \,a.\) But Theorem 5.2 told us that \(\sqrt 2\) is not rational. Thus, we know \(\sqrt 2\) exists and we know it is not rational. Therefore, we have a rigorous proof that \(\sqrt 2\) is irrational.

Ulrich Daepp, Pamela Gorkin

Chapter 14. Functions, Domain, and Range

Abstract

What is a function? You’ve probably gotten a definition of this somewhere along the way. We will state the definition of function in terms of relations, which is probably different than the way you have seen it stated.

Ulrich Daepp, Pamela Gorkin

Chapter 15. Functions, One-to-One, and Onto

Abstract

Functions can map elements from the domain to the codomain in many ways. A function may “hit” every element in the codomain, or it may “miss” some. It may assign more than one x to a y or it may assign exactly one x to each y. We will understand our function better if we know which of these things it does. Precise formulations of these ideas will be given in a moment. It’s a mouthful, though, and really requires practice.

Ulrich Daepp, Pamela Gorkin

Chapter 16. Inverses

Abstract

Given functions f : A \(\rightarrow\) B and g : C \(\rightarrow\) D with ran(f) \(\subseteq\) C, we can define a third function called the composite function from A to D. (We will usually call this the composition, rather than the composite function.) This composition is the function \(g\, \circ \,f:A\, \to \,D\,\text{defined}\,\text{by}\,\text{(}g\, \circ \,f\text{)(}x\text{)}\,\text{ = g(f(}x\text{))}\text{.}\)

Ulrich Daepp, Pamela Gorkin

Chapter 17. Images and Inverse Images

Abstract

In the last chapter, we looked at where points in the domain are mapped to under a function f and where points in the range come from under f. But sometimes we need to look at where f maps a whole set, or where an entire set comes from. So here are two definitions that are waiting to be understood.

Ulrich Daepp, Pamela Gorkin

Chapter 18. Mathematical Induction

Abstract

Suppose that you want to show something is true for all positive integers. You could start by checking that the statement is true for n=1, n=2, and so on, but you would have to stop somewhere. Even if you check lots and lots of integers, you can run into problems.

Ulrich Daepp, Pamela Gorkin

Chapter 19. Sequences

Abstract

We have all seen lists of numbers. For example, we’ve all worked with a list of positive even integers presented in increasing order, (2,4,6,8,...,2n,...), where n=1,2,3,4,.... The positive odd numbers (1,3,5,7,....,2n - 1,...) can also be presented in such a list, where n = 1,2,3,4,.... What we are interested in here is a precise definition of “infinite list.”

Ulrich Daepp, Pamela Gorkin

Chapter 20. Convergence of Sequences of Real Numbers

Abstract

As we saw in the last chapter, when we graph several terms of a sequence, certain behavior may appear. We may become convinced, for whatever reason, that the sequence is unbounded. Or, we may believe that the sequence is bounded and we may even notice the sequence moving toward a particular horizontal line. But how do we check that what we believe is happening really is happening?

Ulrich Daepp, Pamela Gorkin

Chapter 21. Equivalent Sets

Abstract

If you were asked how many people are in your class, you would do the natural thing and count them. Thinking about this carefully, we see that what you are doing is assigning each person in the room one and only one number. If we asked whether or not there are more people in this class than were in your high school geometry class, you could certainly answer that question by comparing the two numbers.

Ulrich Daepp, Pamela Gorkin

Chapter 22. Finite Sets and an Infinite Set

Abstract

We have proved that sets are finite, but we have not yet shown rigorously that a set is infinite. It is not as easy as you might think to do so, nor do we have an exact notion of what it means for a finite set “to have n elements.” Our proof of the former and the definition of the latter will depend on a principle known as the pigeonhole principle. The pigeonhole principle is something that is familiar to all of us. As a very simple example of this, recall a childhood birthday party in which you played musical chairs. In case you weren’t invited to any parties, we’ll remind you of the rules behind the game. Let’s say there were 10 children at the party. Someone, say the child’s father, would set up 9 chairs in a row. Someone else, say the child’s mother, would play a song on the piano stopping unexpectedly at some point. When the music ended, the 10 children would scramble for the 9 seats. If everyone sat down, two people would sit in the same chair. This game is our first example of the pigeonhole principle. Now we turn to a more elaborate one.

Ulrich Daepp, Pamela Gorkin

Chapter 23. Countable and Uncountable Sets

Abstract

Having mastered finite sets, we now turn to understanding the infinite. We know that ℕ is infinite, and we know that ℚ is infinite (see Problem 22.8). Are they equivalent? In some sense, we can count ℕ and it may feel as though we cannot count ℚ—that is, as though we cannot list a first element, second element, third element, and so on. However, we shall see that ℚ and ℕ are, in fact, equivalent.

Ulrich Daepp, Pamela Gorkin

Chapter 24. The Cantor–Schröder–Bernstein Theorem

Abstract

Suppose we have two finite sets. We have developed enough machinery to tell when one set has more elements than another. But what about infinite sets? For example, we might consider \(\mathbb{N}\) and \(\mathbb{Z^+}\), and we may ask which one has more elements. Well, we have already developed mathematical concepts that convince us that these two sets have the same number of elements. In this chapter, we investigate the situation for general infinite sets.

Ulrich Daepp, Pamela Gorkin

Chapter 25. Metric Spaces

Abstract

There are many ways to measure distance in the spaces in which we live and work. For example, if you want the shortest distance between two geographical places (the distance “as the crow flies”), you follow the line segment joining them. But in real life this isn’t always possible. If you are driving your car through a city or across your campus, you need to go around solid objects and not through them. So how do we calculate distance in those cases? Measuring distance in a set X is a very small (but interesting) part of a branch of mathematics known as “point set topology,” and we will look at it in detail in this chapter. We will now often refer to the elements of X as points.

Ulrich Daepp, Pamela Gorkin

Chapter 26. Getting to Know Open and Closed Sets

Abstract

When we work in ℝ with the usual metric, we think of distance as measured by absolute value. Points are close when the absolute value of the difference is small.

Ulrich Daepp, Pamela Gorkin

Chapter 27. Modular Arithmetic

Abstract

You began your mathematical education adding, subtracting, multiplying, and dividing integers. From there you moved on to rational numbers, then to real numbers, and, perhaps, to complex numbers. But this is not the only kind of arithmetic mathematicians study. In fact, there’s a very different kind of arithmetic that you use every single day. The popular name for these calculations is clock arithmetic, and it is indeed based upon the clock.

Ulrich Daepp, Pamela Gorkin

Chapter 28. Fermat’s Little Theorem

Abstract

We begin this chapter with a fundamental result of number theory, discovered by Pierre de Fermat. Fermat lived from 1601 to 1665. Many of his contemporaries were “number-lovers” rather than number theorists, [108, p. 51], and one thing that interested them was perfect numbers (a number is perfect if it is the sum of all its proper divisors). Bernard Frénicle de Bessy, who was also a mathematician and physicist, first raised the question of whether there was a perfect number of 20 digits and, if not, what the next largest perfect number was. (See [29] and [30].) The answer to the question required determining whether certain large numbers were prime. As a consequence, the men began corresponding. In a letter to Frénicle, dated October 18, 1640, Fermat stated what is now known as Fermat’s theorem or Fermat’s little theorem (to distinguish it from Fermat’s last theorem), but he did not include a proof. In 1736, almost a century later, Leonhard Euler gave the first rigorous proof of the little theorem. Though this theorem is clearly theoretical in nature, it plays an important role in primality testing; that is, in deciding whether or not a certain number is prime. Fermat’s little theorem (in the form due to Euler) is also the mathematical heart of the widely used RSA code that we will describe later in this chapter. In fact, Fermat’s little theorem is not little at all.

Ulrich Daepp, Pamela Gorkin

Chapter 29. Projects

Abstract

It’s not easy to talk about mathematics to other people. In this section, we present some tips that we find helpful when we present a talk to undergraduates. Let’s say someone has just asked you to give a talk about mathematics to undergraduates.

Ulrich Daepp, Pamela Gorkin

Backmatter