Introductory Lessons in Real Analysis

C. Sormani

Harvard, Real Analysis 112

“The objective of mathematicians is to discover and communicate certain truths. Mathematics is the language of mathematicians, and a proof is a method of communicating a mathematical truth to another person who already ’speaks’ the language. A remarkable property of the language of mathematics is its precision. Properly presented a proof will contain no ambiguity: there will be no doubt as to its correctness.” - Solow How to Read and Do Proofs

In this course we will be studying Real Analysis, a course in which we learn the truths behind calculus. We will be studying the real line, functions on the real line and general metric spaces. We will also be learning how to provide rigorous proofs of these truths. Every theorem presented must be learned on three levels. The statement should be understood and memorized. The proof should be thoroughly dissected and should be presentable in a convincing manner. The implications of the theorem should be felt so strongly that they can be used to prove further theorems and lemmas. You will also be asked to prove results that are not taught in class. This requires a deep understanding of previous theorems and definitions and an ability to select those theorems which will be most useful for your purpose. It will also require an understanding of what it means to provide a proof and a mastering of the various techniques used to form a valid proof.

This handout is provided to ease the process of learning to write proofs. Some of you will have already learned to write proofs and may be frustrated by the simplicity of the first few sections. Please do all the problems anyway and do them in complete detail with justifications at every step even if they seem trivial. After the first few weeks, the theorems you will be proving will become much more complex and some of the more trivial justifications may be left out. However, it is important to get into the habit of being able to justify every step in every proof you write. If you cannot justify a step, then you have not proven that step and, in fact, the statement made may be wrong.

It is also important that you read this handout because it provides a more constructive development of the Real numbers which Marsden leaves out.

Some of you may have some difficulty with the problems in this handout. You should first attempt to imitate the sample proofs given in each section. Don’t expect the proof to be obvious. Most importantly, try to do all of them on your own and be prepared to spend a lot of time on this project. Even if you find the proofs in the first section easy the second section may take you some time. If you have written a proof and are unsure of its accuracy come to my office hours and show them to me. The problems are going to get much harder in the next few weeks. It is important to overcome any difficulties you may have immediately.

The proofs of theorems given below will contain comments in italics. These comments are not necessary parts of the theorems but point out what is going on and how far we have proceeded in the proofs. Most mathematicians include comments in the proofs of their theorems and they are considered necessary if the proof lasts many pages. It is recommended that you include comments in the proofs of your theorems but that you include them in parenthesis or script to indicate that they are not part of the proof itself.

Sections:

1. Set Theory and Simple Proofs

2. Complements and Contradictions

3. Mappings

4. Ordered Fields

5. Equivalence Relations and Classes

6. Denumerability and the Rationals

7. Sequences in the Rationals and Convergence

8. Cauchy Sequences in the Rationals

9. Construction of the Real Line

10. Decimal Expansions and the Nondenumerable Interval

This handout replaces Chapter 1 of Marsden except for sections 1.3 and 1.5 which must be read on your own.

1 Set Theory and Simple Proofs

1

We begin with some definitions. Mathematically, definitions are statements that everyone agrees upon. They may establish notation, such as ∩, or a classification, such as which numbers are even. In the proof of a theorem, definitions are regularly used to justify a statement or step.

Definition: A set is a collection of objects or points called elements. If x is an element in S we denote this by x ∈ S.

Examples of sets include the prime numbers, {1, 2, 3} and intervals in the real line.

Definition: A subset,A, of a set , S, is a set whose elements are elements of S. We denote this by A ⊂ S.

This definition can also be written as follows: A ⊂ S if for all points x ∈ A, x ∈ S. In fact the symbol ∀ often replaces the phrase “for all” making the statements even more concise and illegible to the noninitiated.

Definition: The union, A ∪ B, of two sets A and B is the set of all elements contained in A or in B.

1This material is contained in Marsden, Prerequisites

The word “or” used in this definition is the inclusive “or”. If an element is contained in A or in B then it might be contained in both sets.

In mathematics, the word “or” has a a special meaning quite different from the way that it is used in English. When we make a pair of statements and link them together with the word “or” then the whole combined statement is true even if only one of the parts was true. For example:

{1, 2, 3} ⊂ {1, 2} or {1, 2} ⊂ {1, 2, 3}

is a true statement because the second half of the statement is true. While it may seem silly to write statements like this, it is not always obvious which of the two statements is true. On the other hand, the word “and” in mathematics requires that both facts must be true. In particular:

{1, 2, 3} ⊂ {1, 2} and {1, 2} ⊂ {1, 2, 3}

is a false statement because the first part of the statement is false.

Definition: The intersection, A ∩ B, of two sets A and B is the set of all elements contained in both A and in B.

For example: {1, 2, 3} ∩ {1, 3, 5} = {1, 3} but {1, 2, 3} ∪ {1, 3, 5} = {1, 2, 3, 5}. We can also draw pictures illustrating these sets and their unions and intersections. These pictures are often useful in helping gain an intuitive feeling for what you wish to prove and how to go about constructing a proof.

We will now state our first theorem and then follow it by a proof. Compare the theorem to the diagram above.

Theorem I: A ∩ B ⊂ A ∪ B.

Proof: Show that all points x ∈ A ∩ B are contained in A ∪ B.

1. If x ∈ A ∩ B then x is contained in both A and B by the definition of intersection.

2. In particular x ∈ A. So x ∈ A ∪ B by the definition of union.

□

Notice the format of the proof. It begins with a short remark stating how we plan to prove the theorem. Here, we take a point in the set and show it must be contained in the other set. Notice that we have divided the proof into separate statements, each of which is justified by a definition. In the future, steps will often be justified by previously proven theorems. The steps need not be numbered but the enumeration is useful when referring back to a proof. This exact same proof can be written in shorthand as follows:

x ∈ A ∩ B ⟹ x ∈ A ⟹ x ∈ A ∪ B

where ⟹ means “implies that”. This notation is not used in publications but can be useful when sketching a proof before writing it up in an acceptable format. It is also useful to check that every ⟹ has been justified by a definition or previously proven theorem. Note that there is more than one way to prove this theorem. For example, we could have written:

x ∈ A ∩ B ⟹ x ∈ B ⟹ x ∈ A ∪ B.

This theorem is a little too obvious, so we will now turn to a slightly more involved theorem which can also be proven by a simple series of implications.

Theorem II: If A ⊂ B then (A ∩ C) ⊂ (B ∩ C).

Proof: Given A ⊂ B. Show that if x ∈ A ∩ C then x ∈ B ∩ C.

1. Let x ∈ A ∩ C. So x ∈ A and x ∈ C by the definition of intersection.

2. Since A ⊂ B (by the hypothesis) and x ∈ A, then x ∈ B by the definiton of subset.

3. By step 1, we know that x ∈ C and by step 2 x ∈ B, so x ∈ C ∩B by the definition of intersection.

□

□ symbolizes the end of a proof.

Notice that in this proof we refer to the hypothesis. The hypothesis is the given part of the theorem. It does not come from a previous theorem or definition but is part of the statement of the current theorem. As a general rule the hypothesis of a theorem must be used somewhere inside the proof. More importantly the hypothesis can be used to prove the theorem. Notice also that we have referred to previous steps to justify later steps.

PROBLEM 1: Prove that If A ⊂ B then (A∩C) ⊂ (B∪C) in two different ways. First prove it directly from the definitions. Then prove it using the two previous theorems.

Earlier we introduced the ∀ symbol which means “for all”. There is another symbol, ∃, which means “there exists”. These are called quantifiers. A statement which uses these quantifiers might be:

For all numbers, there exists a larger number.

The proof of this statement could be of the form:

Given any number,n, there exists another number n + 1 and n + 1 > n. More symbolically, ∀n, ∃n + 1 > n.

Our only problem is that we have not defined the numbers. So how do we know if n + 1 is a number?

Definition: The set of natural numbers, N I , is smallest set that contains 1 and satisfies the following condition:

∗ ∀a, b ∈ N I , a + b ∈ N I .

In particular, 1 ∈ N I , 2 = 1 + 1 ∈ N I , 3 = 1 + 2 ∈ N I and so on. So N I = {1, 2, 3, 4....}. We must be careful when refering to a set as a infinitely long list of numbers because we cannot list every number in the set. Such lists are only used to get an intuitive feeling for a set. The official definition of the natural numbers or counting numbers is the definition given above not the list {1, 2, 3, 4...}. Note by the way that N I is the smallest set which satisfies both condition * and the condition that it contains 1. By “smallest” we mean that it contains no unnecessary elements. The set {0} ∪ N I also satisfies condition * but is bigger than necessary.

Another useful way to define a set involves the “there exists” quantifier, ∃. Here we use this quantifier to define the even numbers, denoted by E_{1}.

Definition: We say x is an element of E_{1} if there exists n ∈ N I such that x = 2n. Another way to state the exact same definition is to write:

{2n : n ∈ N I }.

To get an intuitive feel for the set we can write:

E_{1} = {2(1), 2(2), 2(3), 2(4)...} = {2, 4, 6, 8...}.

Definition: Let E_{2} be the smallest set which contains 2 and satisfies

∗ ∀a, b ∈ E_{2}, a + b ∈ E_{2}.

Note that this is the same condition used to define the natural numbers except that now 1 need not be an element of the set. To get an intuitive feel for E_{2} we can write:

E_{2} = {2, 2 + 2, 2 + 2 + 2, 2 + 2 + 2 + 2...} = {2, 4, 6, 8...}.

It appears that E_{1} might be the same set as E_{2} but we need a rigorous proof to justify that these two definitions are equivalent. We can use the lists of elements to help us think of a proof much as we used the diagrams to help prove the previous theorems, but the lists themselves do not entail a proof, since they only contain the first few elements in each set and we can never check the sets element by element.

Theorem: E_{1} = E_{2}.

Proof: We will break this theorem into two steps: I. Show E_{1} ⊂ E_{2}. II. Show E_{2} ⊂ E_{1}.

I. Given x ∈ E_{1}, show x ∈ E_{2}.

1. Given x ∈ E_{1}, there exists n ∈ N I such that x = 2n by the definition of E_{1}.

2. x = 2n = 2+2+....+2 n times because n is a natural number (defn of multiplication).

3. Therefore x ∈ E_{2} since E_{2} contains all sums of 2 by definition.

At this point we interrupt our proof to remark on the fact that in step 2 it was crucial that n be a natural number. Had n been a fraction this would not hold. Nor would it hold if n were negative.

II. We will not prove that E_{2} ⊂ E_{1} by taking an element in E_{2}. It is not convenient to do so because we have no simple description of the particular elements in E_{2}. Instead, we will show that E_{1} contains E_{2} by showing that is satisfies the conditions used to describe E_{2}: that it contains 2 and satisfies *.

1. 2 = 2(1) ∈ E_{1} by the definition of E_{1} and the fact that 1 ∈ N I .

2. Given any a, b ∈ E_{1} there exists n, m ∈ N I such that a = 2n and b = 2m by the definition of E_{1}.

3. So a + b = 2n + 2m = 2(n + m) ∈ E_{1} because n + m ∈ N I by property * of the definition of N I .

4. By steps 1 and 3 we know that E_{1} satisfies all the conditions used to define E_{2} except that it need not be the smallest such set. Thus E_{1} ⊃ E_{2}.

□

This section has been carefully contrived to contain only the most simple proofs consisting of a sequence of statements each of which implies the next and which are not too hard to think of. All of the following theorems can be proven in a similar manner. Begin with a diagram or a list of a few elements to get an intuitive feeling for why the statement is true. Then write an aim or plan, and then proceed to attempt the proof. Always keep in mind what conclusion you are trying to reach and only list facts that you can justify. After acheiving a proof, write it over neatly filling in all the justifications.

PROBLEM 2: Use the following definition and the definition of N I to prove the next two theorems.

Definition: The Cartesian product, A × B, of two sets is the set of ordered pairs, (a, b), where a ∈ A and b ∈ B.

A × B = {(a, b) : a ∈ A, b ∈ B}.

For example,

{1, 2, 0} × {0, 1} = {(1, 0), (1, 1), (2, 0), (2, 1), (0, 0), (0, 1)}.

We say that two elements (a_{1}, b_{1}), and (a_{2}, b_{2}) are equal or the same if and only if a_{1} = a_{2} and b_{1} = b_{2}. So (1, 0) is not equal to (0, 1).

Theorem: N I × 1 ⊂ N I × N I .

Theorem: (A × B) ∩ (C × B) = (A ∩ C) × B.

PROBLEM 3: Give an example of some sets, A, B, C and D demonstrating that the following statement is FALSE:

(A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D).

To prove that a statement is true you need to provide a proof consisting of a logical sequence of justified steps. To prove that a statement is false you need only provide a counterexample. In the future you will be given statements and you will be asked to first ascertain their validity and then prove it. If you decide a statement is false, the proof “only” consists of a counterexample. Sometimes counter examples are very hard to come by.

Thus far we have mostly dealt with proofs involving intersections and the “and” conjunction. We have a few facts which are true at the same time and can use any of them to proceed with the proof. Many proofs, however, deal with various possibilities or cases. They involve the “or” conjunction and only one of a few facts may be true. The theorem must be proven no matter which of the facts is true and so it is divided into cases and the conclusion of the theorem is proven for each case. The following theorem has such a proof.

Theorem: (A × B) ∪ (C × B) = (A ∪ C) × B.

Proof: 1. Show (A×B)∪(C×B) ⊂ (A∪C)×B. 2. Show (A×B)∪(C×B) ⊃ (A∪C)×B.

1. Given x ∈ (A × B) ∪ (C × B). Then, by the definition of union, x ∈ A × B or x ∈ C × D. We split this into two cases: I. x ∈ A × B. II. x ∈ C × B.

Case I: If x ∈ A × B then there exists a ∈ A and b ∈ B such that x = (a, b), by the definition of the Cartesian Product.

Since a ∈ A, then a ∈ A ∪ C by the definition of union.

Thus x = (a, b) ∈ (A ∪ C) × B by the definition of the Cartesian product. We are done with the first case.

Case II: If x ∈ C × B then there exists c ∈ C and d ∈ B such that x = (c, ds), by the definition of the Cartesian Product.

Since c ∈ C, then c ∈ A ∪ C by the definition of union.

Thus x = (c, d) ∈ (A ∪ C) × B by the definition of the Cartesian product. We are done with the second case.

We have proven that (A × B) ∪ (C × B) ⊂ (A ∪ C) × B but we are not done with the theorem.

2. Let x ∈ (A ∪ C) × B. Then there exists p ∈ A ∪ C and q ∈ B such that x = (p, q), by the definition of Cartesian product.

Since p ∈ A ∪ C we know that p ∈ A or p ∈ C, by the defintion of union, and so we divide it into two cases:

Case I: If p ∈ A, then (p, q) ∈ A × B by the defn of Cartesian product. So x ∈ (A × B) ∪ (C × B) by the definition of union.

Case II: If p ∈ C, then (p, q) ∈ C × B by the defn of Cartesian product. So x ∈ (A × B) ∪ (C × B) by the definition of union.

We have proven that (A ∪ B) × C ⊂ (A × C) ∪ (B × C).

□

When proofs involve cases as well as steps they often become somewhat long and it is easy to forget to include all the cases. For this reason it is often useful to sketch an outline of a proof before writing out the proof itself. Below we state a theorem and provide an outline of its proof.

Theorem: (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C).

Outline of the Proof:

1. Show (A ∩ C) ∪ (B ∩ C) ⊂ (A ∪ B) ∩ C. If x ∈ (A ∩ C) ∪ (B ∩ C) then x ∈ A ∩ C or x ∈ B ∩ C.

Case I: Show x ∈ A ∩ C implies x ∈ (A ∪ B) ∩ C.

Case II: Show x ∈ B ∩ C implies x ∈ (A ∪ B) ∩ C.

2. Show (A ∪ B) ∩ C ⊂ (A ∩ C) ∪ (B ∩ C). If x ∈ (A ∪ B) ∩ C then x ∈ A ∪ B and x ∈ C. So x is in A or B, and it is definately in C.

Case I: Given x ∈ A and x ∈ C. Show (A ∩ C) ∪ (B ∩ C).

Case II: Given x ∈ B and x ∈ C. Show (A ∩ C) ∪ (B ∩ C).

End of the Outline.

Notice that in the second step, when we split it into two cases we keep the fact that x ∈ C in both cases. This fact is definately true and may be needed to complete both cases.

This is like knowing you have a striped sock which is either black or white or both and hoping to demonstrate that it is dirty. So you split arguement into two cases: A striped sock with black stripes or a striped sock with white stripes. In both cases you retain the fact that they are striped. If you find white chalk on the black stiped socks, they are dirty and the first case is proven. If you find soot on the white striped socks then they are dirty and the second case is proven. It does not matter that the black and white striped socks are included in both cases.

PROBLEM 4: Complete the proof of the above theorem following the outline.

Note, by the way, that the above outline is correct. Sometimes you will make an outline of a proof but fail to prove one of the steps. Then you will have to rework the outline. The purpose of the outline is to insure that all cases and steps have been included.

PROBLEM 5: Write an outline of a possible proof for the following theorem.

Theorem: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

2 Complements and Contradictions

In this section we introduce the Proof by Contradiction, one of the most powerful techniques used in proving theorems at all levels of mathematics. It is also used in everyday language and reasoning. “Everyone in the Student Center is a student.” “Why?” “Well, suppose one of them wasn’t a student. Then, when he entered the building he would not have been able to produce his ID and he would not have been allowed to proceed. Thus he could not be in the room. But there he is!” Of course, one would have to justify that only student ID’s provide one with access to the building and that the guards are responsible.

The first step of a proof by contradiction always consists of an assumption which is the opposite of what you are trying to prove. For example if we want to conclude that x ∈ A then we assume that x is not in A, x ∉ A. We then proceed with the theorem as usual using previously proven theorems and definitions as well as our assumption. The aim, however, is no longer to reach the conclusion but just to reach a pair of statements that contradict one another.

We begin with a lemma (or small theorem) that can be proven in this manner.

Lemma: If x ∉ B then x ∉ B ∩ A.

Proof:

1. Assume, to the contrary, that x ∈ B ∩ A. (the opposite of our conclusion)

2. Then x ∈ B by the definition of intersection.

3. But the hypothesis states that x ∉ B. This contradicts our assumption, thus our assumption is false and x ∉ B ∩ A.

□

We could also write: If x were in B ∩ A then x would be in B, but it isn’t; so x must have been in B ∩ A. This use of the subjunctive is helpful when giving a short quick proof by contradiction of a statement within a theorem. However, if the whole theorem is one long proof by contradiction, it is best to stick to the rigid formalism used above.

Definition: The complement of the set B relative to the set A, A \ B, is the set of elements of A which are not contained in B. A \ B is sometimes pronounced “A not B”.

This can also be written as x ∈ A \ B if and only if x ∈ A and x ∉ B. The following

lemma is useful when studying complements of sets. It is obvious if you think about it and draw the picture. We will give a short proof by contradiction.

Lemma: x ∉ A ∪ B implies that x ∉ A and that x ∉ B.

The idea is that if x is not in A ∪ B then x is not in A nor is it in B. So both facts x ∉ A and x ∉ B are true. It is important to be careful with the use of the words “and” and “or”. We now prove the lemma by contradiction.

Proof: We wish to begin with an assumption that the conclusion is false.

1. Assume, to the contrary, that it is not true that (x ∉ A and x ∉ B).

2. Thus x ∈ A or x ∈ B. (If it is not true that a sock is not red and not yellow then the sock is red or yellow (possibly both).)

3. Thus x ∈ A ∪ B by the definition of union.

4. However the hypothesis states that x ∉ A ∪ B, so we have contradicted our assumption. Thus it is true that (x ∉ A and x ∉ B).

□

It is important to understand this proof by contradiction. Notice how in step 2 the “and” is negated and becomes an “or”. The same thing happens in reverse, if it is not true that a sock is red or yellow then the sock is neither red nor yellow. That is, the sock is not red and the sock is not yellow. Learning how to correctly negate a statement is an important part of proving.

One way to negate a statement is to think about simple examples like the striped socks. Another, more rigorous approach is to use truth tables. We will not study truth tables in this course, but they are discussed in Sylow’s book and are usually taught in courses on proving or logic.

PROBLEM 1: Negate the following statements:

Example) x ∉ A. Answer: It is not true that x ∉ A means x ∈ A.

1) x ∉ A and x ∈ B.

2) x ∈ A or x ∉ B.

3) x ∉ A ∪ B.

4) x ∈ A ∩ B.

5) x ∈ A ∪ B.

The following theorem is not proved by contradiction but uses the same concepts of negation.

Theorem: B \ (A_{1} ∪ A_{2}) = (B \ A_{1}) ∩ (B \ A_{2}).

Proof: 1. Show (B \ A_{1}) ∩ (B \ A_{2}) ⊂ B \ (A_{1} ∪ A_{2}). 2. Show B (A_{1} ∪ A_{2}) ⊂ (B \ A_{1}) ∩ (B \ A_{2}).

1. Let x ∈ (B \ A_{1}) ∩ (B \ A_{2}). The x ∈ B \ A_{1} and x ∈ B \ A_{2} by the defn of intersection. So (x ∈ B and x ∉ A_{1}) and (x ∈ B and x ∉ A_{2}). We have used the parenthesis to surround pairs of statements resulting from single statements. Since all four facts are true, we have x ∈ B and x ∉ A_{1} and x ∉ A_{2}.

At this point we want to check what conclusion we wish to draw. We want to show that x ∈ B \ (A_{1} ∪ A_{2}). This is true if we show x ∈ B and x ∉ A_{1} ∪ A_{2}.

Since x ∉ A_{1} and x ∉ A_{2}, we know that x ∉ A_{1} ∪ A_{2} by the above lemma. Since we know x ∈ B, then x ∈ B \ (A_{1} ∪ A_{2}) by the definition of complement.

2. Let x ∈ B \ (A_{1} ∪ A_{2}). Then x ∈ B and x ∉ A_{1} ∪ A_{2} by the definition of complement. Since x is not in A_{1} nor A_{2}, we know x ∉ A_{1} and x ∉ A_{2}. Since x ∈ B and x ∉ A_{1}, x ∈ B \ A_{1} by defn of compl. Since x ∈ B and x ∉ A_{2}, x ∈ B \ A_{2} by defn of compl. Since both of the above statements are true, x ∈ (B \ A_{1}) ∩ (B \ A_{2}) by the defn of intersection.

□

This proof has been written out almost as long as possible. Later on in the semester, proofs should be written more concisely. However, it is safer to write a longer proof than an incorrect one.

A shorter version of this proof can be written with the phrase, “if and only if”. This phrase means that first statement implies the second and that the second statement implies the first. In a definition the “if and only if” is implicit. For example: x ∈ A ∪ B if and only ifX ∈ A or x ∈ B. Also x ∈ A and x ∈ B if and only if x ∈ A ∩ B. To prove that two sets,A and B are equal we need only prove that: x ∈ A if and only if x ∈ B. We use iff as a shorthand for “if and only if”.

A Shorter Proof:

1. x ∈ B \ (A_{1} ∪ A_{2}) if and only if x ∈ B and x ∉ A_{1} ∪ A_{2} by the defintion of complement.

2. This is true iff x ∈ B and (x ∉ A_{1} and x ∉ A_{2}) by the lemma (which only demonstrated that 1 implies 2) and by an extra lemma which we will add after the proof.

3. x ∈ B and x ∉ A_{1} and x ∉ A_{2} if and only if x ∈ B \ A_{1} and x ∈ B \ A_{2} by the definition of complement.Notice how we need “ands” throughout to state this.

4. This last statement is true iff x ∈ (B \ A_{1}) ∩ (B \ A_{2}).

□

The Extra Lemma: x ∉ A_{1} and x ∉ A_{2} implies that x ∉ A_{1} ∪ A_{2}.

Proof: Assume, to the contrary, that x ∈ A_{1} ∪ A_{2}. By the defn of union, x ∈ A_{1} or x ∈ A_{2}. Case I: x ∈ A_{1} contradicts the first hypothesis that x ∉ A_{1}. Case II: x ∈ A_{2} contradicts the second hypothesis that x ∉ A_{2}.

□

.

We have added this almost obvious extra lemma to emphasize the importance of being careful when using the “if and only if”. We must check both directions and provide a justification for both directions. Definitions are a natural justification for an iff. Previously proven theorems, however, are rarely true in both directions and often more than one theorem or lemma is needed to justify an iff.

PROBLEM 2: Prove that the following lemma and draw the appropriate picture.

Lemma: A \ (A ∩ B) = A \ B.

We will use this lemma to prove the next theorem. It is important to become comfortable with sets to the extent that you can picture which statements are true before being asked to prove them. Often you will be able to prove one statement and need to prove another, a diagram can help you decide if the first statement might imply the second one before continuing with the proof.

Theorem: (A \ B) ∪ (B \ A) = (A ∪ B) \ (A ∩ B).

Proof: 1. Show ⊂. 2. Show ⊃.

1. Let x ∈ (A \ B) ∪ (B \ A). By the defn of union, x ∈ A \ B or x ∈ B \ A.

Case I. Show x ∈ A \ B implies x ∈ (A ∪ B) \ (A ∩ B). If x ∈ A \ B then x ∈ A and x ∉ B by the defn of complement. Since x ∈ A, we know x ∈ A ∪ B by the definition of union. Since x ∉ B, then x ∉ B ∩ A by the first lemma of this section. So x ∈ A ∪ B and x ∉ A ∩ B. Thus, by the defn of complement, x ∈ (A ∪ B) \ (A ∩ B).

Case II. We must show that x ∈ B \ A implies that x ∈ (A ∪ B) \ (A ∩ B). However, we have just proven this in Case I with the symbols B and A reversed. So this is true.

2. Let x ∈ (A ∪ B) \ (A ∩ B). By the defn of complement x ∈ A ∪ B and x ∉ A ∩ B.

So (x ∈ A or x ∈ B) and x ∉ A ∩ B. It is important that we have parenthesis here. It means that x is in A or B and, in either case, it is definately not in A ∩ B. So we have two cases: I. x ∈ A and x ∉ A ∩ B or II. x ∈ B and x ∉ A ∩ B.

Case I. x ∈ A and x ∉ A ∩ B implies that x ∈ A \ (A ∩ B) by the definition of complement. So, by the lemma you have proven, we know x ∈ A \ B. By the definition of union, therefore x ∈ (A \ B) ∪ (B \ A) as we hoped to prove.

Case II. This is identical to Case I when we exchange B and A.

□

PROBLEM 3: Prove the following lemmas by contradiction and use them to prove the following theorem. Draw a picture corresponding to the theorem.

Lemma: If x ∉ A ∩ B then x ∉ A or x ∉ B.

Lemma: If (x ∉ A or x ∉ B) then x ∉ A ∩ B.

Theorem: B \ (A_{1} ∩ A_{2}) = (B \ A_{1}) ∪ (B \ A_{2}).

Finally it is important to be able to negate statements involving “for all” and “there exists”.

“All socks in the drawer are black” is negated by “There exists a sock in the drawer which is not black”.

Sometimes these sentences involve more than one quantifier: Examine the sentence: “For all left socks in the drawer there exists a matching right sock in the drawer.” Note that this does not mean that all the socks have been paired off. There could be two black left socks and only one black right sock. The statement is still true. Pick out any left sock, then you can find a right sock to match it. Now if we were to negate this statement we would say: “There exists a left sock inthe drawer such that none of the right socks in the drawer match it.” This is the same as saying “There exists a left sock in the drawer such that for all right socks in the drawer that right sock won’t match the left sock”.

Thus we can see that: For all x there exists y_{x} such that we have blah blah blah. is negated by: There exists x such that for all y we don’t have blah blah blah.

PROBLEM 4: Negate the following statements:

1. For all x ∈ A ⊂ N I there exists y ∈ B ⊂ N I such that x + y = 10.

2. There exists n ∈ N such that for all x ∈ A ⊂ N I , x < n.

3 Mappings

In this section, you will review the basic definitions related to mappings and practice proof by contradiction. You will also practice writing precise definitions. Fill in all the definitions by refering to pages 4-6 of Marsden, Elementary Classical Analysis.

Definition: A function or map, f : S ⟶ T consists of two sets S and T and a rule which assigns to each element s ∈ S a specific element t ∈ T denoted by f(s). One often writes s ⟼ f(s).

Fill in the following definitions. Be careful to change the names of the sets, S and T, to A and B. In a definition, the name of the set is not important, but the defintion must be consistant with itself.

Definition: The domain of f : A ⟶ B is

Definition: The range of f : A ⟶ B is

Definition: Given a map f : A ⟶ B the set, Graph(f), is

PROBLEM 1: Prove the following theorem.

Theorem: Given two functions, f : A ⟶ B and g : A ⟶ B, if there is an element a ∈ A such that f(a) = g(a) then Graph(f) ∩ Graph(g) ⊃ {(a, g(a))}.

In analysis, mathematicians often study the properties of the intersections of graphs of two different functions. They study the smoothness of the intersections among other things. They also study the possibility of finding a way to turn an arbitrary surface into a curve. For example: given a sphere sitting in three dimensional space, is there a function f : R I × R I ⟶ R I such that Graph(f) is the sphere? The answer is: no. However, it is possible to find such a function defined on a subset of R I such that Graph(f) is a subset of the sphere. When we study the Inverse and Implicit Function Theorems we will learn when such functions exist.

Definition: The image, f(A), of a set A is

Definition: A map f : A ⟼ B is a surjection or is onto if

Definition: The preimage, f^{−1}(U), of a set U in the range of f is the set of elements in the domain of f that are mapped into U. If we let A be the domain of f then f^{−1}(U) = {a ∈ A : f(a) ∈ U}.

Note that f need not be invertible to define the preimage of a set. The map f : R I ⟶ R I , f(x) = x^{2} is not invertible. Note that f^{−1}([1, 4]) = [−2, −1] ∪ [1, 2].

Definition: The empty set, ∅, is the set that contains no elements.

Note that ∅ ⊂ N I and in fact ∅ ⊂ A for any set A. Note also that ∅ ≠ {0} since {0} contains 0.

Definition: Two sets A and B are disjoint if A ∩ B = ∅.

Theorem: Given f : A ⟶ B. If B_{1} and B_{2} are disjoint subsets of B then their preimages are disjoint as well.

Proof: Show f^{−1}(B_{1}) ∩ f^{−1}(B_{2}) = ∅. We will prove this by contradiction. In other words, we must show the intersection contains an element.

1. Assume, to the contrary, that there is an element, x ∈ f^{−1}(B_{1}) ∩ f^{−1}(B_{2}).

2. By the definition of intersection, x ∈ f^{−1}(B_{1}) and x ∈ f^{−1}(B_{2}).

3. By the definition of preimage, there exists b_{1} ∈ B_{1} such that b_{1} = f(x) and there exists b_{2} ∈ B_{2} such that b_{2} = f(x).

4. By the defintion of a function, we know that f(x) is an element in B so b_{1} = f(x) = b_{2} must be the same element.

5. By steps 3 and 4 we know b_{1} ∈ B_{1} and b_{1} = b_{2} ∈ B_{2} so, by the definition of intersection b_{1} ∈ B_{1} ∩ B_{2}.

6. This contradicts the hypothesis that B_{1} ∩ B_{2} = ∅.

□

PROBLEM 2: Fill in the definitions of Injection (One to One) and Bijection. Be sure to write the statement carefully, stating what f is and naming the sets involved.

Definition:

Definition:

PROBLEM 3: Prove the following theorem.

Theorem: If f : A ⟶ B is an injection and A_{1} and A_{2} are disjoint subsets of the domain, A, then f(A_{1}) and f(A_{2}) are disjoint.

PROBLEM 4: Prove that the following statement is FALSE by providing a counterexample. That is, find a map for which the statement is not true.

False Statement: Let f : A ⟶ B. If A_{1} and A_{2} are disjoint subsets of the domain, A, then f(A_{1}) and f(A_{2}) are disjoint.

PROBLEM 5: Prove the following theorem.

Theorem: Let f : A ⟶ B is a bijection and let A_{1} ⊂ A and A_{2} ⊂ A. If A_{1} ∩ A_{2} contains exactly one point, then f(A_{1}) ∩ f(A_{2}) contains exactly one point.

This theorem is a uniqueness theorem. It proves that there is a unique point contained in f(A_{1}) and in f(A_{2}). Later on in the course we will be proving other uniqueness thoerems. In analysis, uniqueness theorems are used to show that there are unique solutions to differential equations. If an equation doesn’t have a unique solution then often numerical approximations to the solution will give incorrect results. Thus it is important to be able to prove that the solution is unique before using a computer to solve the equation. We will discuss this later in the term when we learn the contraction mapping principle.

Fill in the definitions of restriction and extension.

Definition: (Restriction of f)

Definition: (Extension of f)

PROBLEM 6: Given f : A ⟶ B, C ⊂ A and D ⊂ B. Write a statement involving the quantifiers “for all” and “there exists” which is true iff D ≠ f(C). (Remember the definition of f(C) states that for all x ∈ f(C) there exists c ∈ C such that f(c) = x. Negate this statement.) Similarly, write a statement involving the quantifiers “for all” and “there exists” which is true iff C ≠ f^{−1}(D).

4 Ordered Fields

Read 25-31 of Marsden (The first half of 1.1). Here, an axiom is just part of a definition. For example the field axioms are the properties of a set which is a field. More generally, axioms are statements which are taken to be true. For example, in Euclidian geometry the Parallel Postulate is an axiom. However, in noneuclidean geometry this axiom is abandoned and it is no longer considered to be true that parallel lines exist.

PROBLEM 1: Show that N I does not satisfy the field axioms. That is find an axiom that it does not satisfy.

PROBLEM 2: Show that N I ∪ {0} also fails to satisfy the field axioms.

Definition: The set of integers, ZZ , is the smallest set including N I and {0} and such that all its elements, n, have negatives, −n.

The integers satisfy the addition axioms although we don’t have time to prove this here. They do not, however, have multiplicative inverses as is required in Axiom 8. Thus ZZ is not a field. We will soon define the rationals and the reals. Both of these sets are fields.

In Real Analysis, we will use the modulus or absolute value function regularly. It is essential to the definitions of limit, continuity and differentiation. One of its most important porperties is the following inequality:

|x + y| ≤ |x| + |y|.

PROBLEM 3: Prove the triangle inequality (1.1.5 iv.) using the axioms. This proof can be done by going through cases. First both x ≥ 0 and y ≥ 0, then x ≥ 0 and y < 0 and so on. Don’t leave any cases out! Use the axioms to justify your steps.

On both the real line and the general metric space, it is essential to study the distance function, d(x, y), between two points x and y. On the Real line, d(x, y) = |x − y|. This is a definition. In general distance functions must obey the triangle inequality:

d(x, y) ≤ d(x, z) + d(z, y).

PROBLEM 4: Verify that d(x, y) = |x − y| obeys the triangle inequality. Use the axioms and the inequality from problem 3 to justify your steps.

PROBLEM 5: Use the axioms and the properties of the absolute value to prove the following: If 0 ≤ x ≤ 2 and 0 ≤ y ≤ 2, then |x^{2} − y^{2}| ≤ 4|x − y|. Hint: Factor x^{2} − y^{2}.

Notice that in PROBLEM 5, you have proven that if |x − y| < δ then |x^{2} − y^{2}| < 4δ.

Thus we can make the following statement:

Given any ϵ, there exists δ = ϵ/4 such that if |x − y| < δ then |x^{2} − y^{2}| < ϵ for all x and y such that 0 ≤ x ≤ 2 and 0 ≤ y ≤ 2.

Later on in the course, we will be proving many statements of this form to prove the uniform continuity of various functions. Here we have proved the uniform continuity of f(x) = x^{2} on the interval [0, 1].

5 Equivalence Relations and Classes

The concept of equality can be extended to a more general concept called equivalence. Equivalence relations are often used to define new sets. In fact, we will use equivalence relations to define the Real line.

Definition An equivalence relation, ∼, is a relation between pairs of elements in a given set such that the following three properties hold:

i) Reflexive: a ∼ a.

ii) Symmetric: If a ∼ b then b ∼ a.

iii) Transitive: If a ∼ b and b ∼ c then a ∼ c.

Clearly = is an equivalence relation on N I and on ZZ .

Lemma: Given x, y ∈ ZZ . Let x ∼ y iff

\frac{x − y}{5} ∈ ZZ .

This is an equivalence relation.

Proof: Just check the three properties.

1. (a − a)/5 = 0 ∈ ZZ so a ∼ a.

2. If a ∼ b then (a − b)/5 ∈ ZZ . By the definition of ZZ , −(a − b)/5 ∈ ZZ so (b − a)/5 ∈ ZZ and b ∼ a.

3. If a ∼ b and b ∼ c than (a − b)/5 ∈ ZZ and (b − c)/5 ∈ ZZ . The sum of any two elements of ZZ is contained in ZZ , so

\frac{a − c}{5} = \frac{a − b}{5} + \frac{b − c}{5} ∈ ZZ .

Thus a ∼ c.

□

Definition: Given a set A and an equivalence relation, ∼. An equivalence class is a subset, B ⊂ A, such that the following properties hold:

1) Any pair of points b, p ∈ B must be equivalent b ∼ p.

2) If a point a ∈ A is equivalent to a point b ∈ B then a ∈ B.

Example: The set {5x : x ∈ ZZ } is an equivalence class of the equivalence relation defined above on ZZ .

Proof: Check the two properties.

1) Let b, p ∈ {5x : x ∈ ZZ }. Thus there exist x, y ∈ ZZ such that b = 5x and p = 5y. By the properties of ZZ and multiplication:

\frac{b − p}{5} = \frac{5x − 5y}{5} = x − y ∈ ZZ .

Thus b ∼ p by the definition of ∼. Note that (x − y)/5 need not be in ZZ .

2) Suppose a ∈ ZZ is equivalent to b ∈ {5x : x ∈ ZZ }. So (a − b)/5 ∈ ZZ . In particular, there exists z ∈ ZZ such that (a − b)/5 = z and in fact a = 5z + b.

Since b ∈ {5x : x ∈ ZZ } there exists y ∈ ZZ such that b = 5y. Thus a = 5z + 5y = 5(z + y). Since y and z are both in ZZ so is y + z by the properties of ZZ . Thus a ∈ {5x : x ∈ ZZ }.

□

PROBLEM 1: Show that {(5x + 1) : x ∈ ZZ } is also an equivalence class.

PROBLEM 2: Prove the following theorem:

Theorem: Let ∼ be an equivalence relation on A. If A_{1} and A_{2} are equivalence classes, then either A_{1} = A_{2} or A_{1} and A_{2} are disjoint.

By this theorem, we know that given any element a ∈ A it is contained in one and only one equivalence class. We denote that equivalence class by [a]. For example, 0 ∈ {5x : x ∈ ZZ } so [0] = {5x : x ∈ ZZ }.

Thus far all the sets we have defined have been sets of numbers. However if is possible to define sets of sets, that is, sets whose elements are sets. For example,

S = {∅, {0}, {1}, {0, 1}}

is the set of all subsets of {0, 1}.

Definition: Given an equivalence relation, ∼, on a set, A, the set of equivalence classes is the set including all equivalence classes of the given relation. It is denoted by A/ ∼.

There is a natural map from A to A/ ∼ defined by a ⟼ [a].

For example, we can define:

A_{0} = [0] = {5x : x ∈ ZZ }.
A_{1} = [1] = {5x + 1 : x ∈ ZZ }.
A_{2} = [2] = {5x + 2 : x ∈ ZZ }.
A_{3} = [3] = {5x + 3 : x ∈ ZZ }.
A_{4} = [4] = {5x + 4 : x ∈ ZZ }.

PROBLEM 3: Show that for all z ∈ ZZ , [z] = A_{z mod 5}. Then ZZ / ∼= {A_{0}, A_{1}, A_{2}, A_{3}, A_{4}} is the set of equivalence classes.

Sometimes we can define addition and multiplication on the set of equivalence classes. Usually this is done using the definition of multiplication and addition on the original set and then checking to see if it is well defined on the eqivalence classes.

We can try to define addition on ZZ / ∼ as follows:

[x] + [y] = [x + y].

In other words, A_{1} + A_{2} = A_{3} and A_{4} + A_{1} = [5] = [0] = A_{0}. To prove that this addition is well defined, we must show that [x + y] does not depend on our choice of x ∈ [x] and y ∈ [y]. That is we must show that if a ∈ [x] and b ∈ [y] then [a + b] = [x + y].

Proof: If a ∈ [x] then a ∼ x by the definition of the equivalence class [x]. Similarly, if b ∈ [y] then b ∼ y. We must show a + b ∼ x + y. Now

\frac{(a + b) − (x + y)}{5} = \frac{a − x}{5} + \frac{b − y}{5} ∈ ZZ

since (a − x)/5 ∈ ZZ and (b − y)/5 ∈ ZZ . Thus a + b ∼ x + y.

□

PROBLEM 4: Define multiplication on ZZ / ∼ and prove that it is well defined. Use the fact that if z_{1}, z_{2} ∈ ZZ then z_{1}z_{2} ∈ ZZ .

We now define another equivalence relation on ZZ .

Lemma: Let x, y ∈ ZZ . Let x ∼ y if there exists z ∈ ZZ such that 5z ≤ x < 5z + 5 and 5z ≤ y < 5z + 5. This is an equivalence relation.

PROBLEM 5: Prove this lemma. Be careful when proving the transitive property! a ∼ b implies that there exist x ∈ ZZ such that 5x ≤ a < 5x + 5 and 5x ≤ b < 5x + 5, while b ∼ c implies that there exist y ∈ ZZ such that 5y ≤ a < 5y+5 and 5y ≤ b < 5y+5. Why should x = y?

Note that 0 ∼ 1 ∼ 2 ∼ 3 ∼ 4 and 5 ∼ 6 ∼ 7 ∼ 8 ∼ 9 and so on. It is not hard to see that [0] = {0, 1, 2, 3, 4} and [5] = {5, 6, 7, 8, 9}. This equivalence relation groups bunches of nearby numbers.

PROBLEM 6: Show that ZZ / ∼ for this equivalence relation is {[5x] : x ∈ ZZ }. First show [5x] = [5y] iff x = y so we haven’t repeated any sets, then show ∀z ∈ ZZ , ∃a ∈ ZZ such that z ∈ [5a] to show that we’ve included all equivalence classes.

With this equivalence relation we cannot define addition like we did last time. That is, [x] + [y] = [x + y] is not well defined. In particular 1 ∼ 4 and 0 ∼ 3 but (1 + 0) = 1 is not equivalent to (4 + 3) = 7.

We will introduce more equivalence relations in the next few lessons.

6 Denumerability and the Rationals

Definition: A set A is finite if we can list all its elements {a_{1}, a_{2}...a_{n}} for some n ∈ N I . We say n is the cardinality of A.

Definition: A set is infinite if it is not finite or empty.

We would like to be able to compare sets which are infinite.

Definition: Two sets, A and B have the same cardinality if there is a bijection from A to B.

It is easy to see that the positive integers, ZZ ^{+}, and the negative integers, ZZ ^{−}, have the same cardinality using the map x ⟼ −x.

Definition: If an infinite set has the same cardinality as the natural numbers N I then it is denumerable. That is, if there exists a bijection from N I to the set then it is denumerable.

Definition: If a set is finite or denumerable, then it is countable.

Lemma: If S is countable, then there exists a surjection f : N I ⟼ S.

Proof:

By the definition of countable and the hypothesis, S is finite or denumerable.

Case I: S is finite. Show there exists a surjection by constructing it. By the definition of finite, there exists n ∈ N I such that S = {s_{1}, s_{2}, ...s_{n}}. Define f : N I ⟼ S as follows f(j) = s_{j} for j = 1, 2, ...n and f(j) = s_{n} for j > n. The map f is a surjection because given any s_{i} ∈ S, s_{i} = f(i).

Case II: S is deumerable. By the definition of denumerable, there exists a bijection from N I to S. By the definition of bijection, a bijection is a surjection. Thus a surjection exists from N I to S.

□

Theorem I: There exists a surjection f : N I ⟼ S, iff S is countable.

The proof of this theorem is too long to include in here. However, copies are available for students who are interested. The proof involves induction and some advanced proving techniques. The idea of the proof is to construct either a bijection from {1, 2, ...n} to S for some n in which case it is finite or to construct a bijection from N I to S in which case it is denumerable. The way to do this is first to examine the surjection f and split it into two cases: I. There exists an N such that f(i) ∈ f({1, 2, ...N}) for all i ≥ N II. This is not true. In the first case, we then show that S is finite. In the second, we show it is denumerable. Note that is is not enough to say that there exists a surjection f : {1, 2, ...N} ⟼ S to say that S is finite. We must construct a bijection. To do so, we carefull elliminate redundancies in the function. For example if f(1) = a, f(2) = b, f(3) = a, f(4) = c then we define a new map g(1) = a, g(2) = b, and g(3) = c. This is not to hard to do in the first case. In the second case, we need to construct a bijection from N I which is a much more difficult task.

PROBLEM 1: Use Theorem I to prove the following lemma:

Composition Lemma: Given a countable set A and a surjection f : A ⟼ B, prove that B is countable.

Hint: Prove that if g : S ⟼ A is a surjection then f ∘ g is a surjection and use this fact.

Theorem II: If A and B are countable, then A ∪ B is countable.

Proof of Theorem II We want to show that there exists a surjection from N I onto A ∪ B and then use Theorem I.

1. Since A is countable, by Theorem I, there exists a surjection f : N I ⟶ A. Since B is countable, by the same theorem, there exists a surjection g : N I ⟶ B.

2. Define F : N I ⟶ A ∪ B. Let F (n) = f(n/2) for n even and let F (n) = g((n + 1)/2) for n odd.

3. Since f is a surjection, for all a ∈ A there exist n ∈ N I such that f(n) = a. So F (2n) = a and F maps onto A.

4. Similarly, g is a surjection so F maps onto B.

5. By steps 3 and 4 and the defn of union, F maps onto A ∪ B. Thus we have constructed a surjection F : N I ⟶ A ∪ B. So by Theorem I, A ∪ B is countable.

□

PROBLEM 2: Prove that if A, B and C are countable then A ∪ B ∪ C is countable.

Definition: A is the countable union of the sets A_{1}, A_{2}... if for all a ∈ A there exists an i such that a ∈ A_{i}. We denote this by:

A = ⋃_{i=1}^{∞} A_{i}

Definition: A is the countable intersection of the sets A_{1}, A_{2}... if for all a ∈ A we have a ∈ A_{i} for all i ∈ N I . We denote this by:

A = ⋂_{i=1}^{∞} A_{i}.

Theorem III: The countable union of countable sets is countable. That is, if A_{i} are countable, then S = ⋃_{i}^{∞} A_{i} is countable.

Proof: We want to construct a surjection F : N I ⟼ S and use Theorem I. 1. Since each A_{i} is countable, there exists a surjection,

f_{i} : N I ⟼ A_{i}.

So we can write:

A_{1} = {f_{1}(1), f_{1}(2), f_{1}(3), f_{1}(4), ...}
A_{2} = {f_{2}(1), f_{2}(2), f_{2}(3), f_{2}(4), ...}
A_{3} = {f_{3}(1), f_{3}(2), f_{3}(3), f_{3}(4), ...}
A_{4} = {f_{4}(1), f_{4}(2), f_{4}(3), f_{4}(4), ...}

and so on. We now construct F mapping onto all of these sets. The idea is to order the points in countable union of all these sets as follows:

{f_{1}(1), f_{1}(2), f_{2}(1), f_{1}(3), f_{2}(2), f_{3}(1), f_{1}(4), f_{2}(3), ...}.

Look at the sets I’ve listed above, and see how we are including the points in this list. 2. We now define F : N I ⟼ S iteratively as follows:

F (1) = f_{1}(1)

and

F (j) = \{ \begin{matrix}f_{1}(k + 1) & if F (j − 1) = f_{k}(1) \\ f_{i+1}(k − 1) & if F (j − 1) = f_{i}(k) for k > 1 \end{matrix}

Notice that F is well defined since every possible value for F (j − 1) has been included in our definition of F(j). In fact, F (1) = f_{1}(1), F (2) = f_{1}(2), F (3) = f_{2}(1), F (4) = f_{1}(3) and so on.

3. We can prove by induction that f_{m}(1) = F (1+2+3+4+...+m) = F (m(m+1)/2). Thus, using the definition of F, f_{1}(m + 1) = F (1 + m(m + 1)/2) and f_{2}(m) = F (2 + m(m + 1)/2), ... f_{i}(m + 2 − i) = F (i + m(m + 1)/2). We skip the proof of this step because not everyone in the class knows induction.

4. We now show that F is a surjection. We will show that given any s ∈ S, there exists an n ∈ N I such that s = F (n). Let s ∈ S. By the definition of S and countable union, there exists an A_{i} such that s ∈ A_{i}. By the definition of the surjection f_{i} in step 1, there exists a k ∈ N I such that s = f_{i}(k). Thus, by step 3 taking m = k − 2 + i,

s = f_{i}(k) = F (i + \frac{(k − 2 + i)(k − 2 + i + 1)}{2}) .

The idea is that eventually, using the definition of F sufficiently many times, we reach f_{i}(k).

□

EXTRA PROBLEM: If you know induction and would like to test your abilities, try to prove step 3.

PROBLEM 3: Prove that the Cartesian product, N I × N I is countable. Hint: Define a surjection using an idea similar to the process done in step two above.

We now turn to a discussion of the rationals. We say that two numbers, p, q ∈ ZZ , are relatively prime if they have no common factors. So 2 and 7 are relatively prime and −6 and 21 are not relatively prime. Note that −5 and −7 have a common factor, −1.

Definition: The rationals are defined as follows:

Q = \{\frac{p}{q} : p, q ∈ ZZ are relatively prime and q > 0.\} .

Here:

\frac{p_{1}}{q_{1}} = \frac{p_{2}}{q_{2}}  iff  p_{1} = p_{2} and q_{1} = q_{2}.

Theorem: The rationals are countable.

Here are two proofs of this theorem.

Proof:

1. Given a, b ∈ Q, let

Q ∩ [a, b] = {q ∈ Q : a ≤ q ≤ b}.

2. In the next few steps we prove that Q ∩ [0, 1] is countable by constructing a map which lists this set as follows:

\{1, \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{2}{4}...\}

Note that 1/2 = 2/4 but this is OK because we are constructing a surjection not a bijection.

3. Let F : N I ⟼ Q ∩ [0, 1] be defined iteratively as follows:

F (1) = 1 and F (2) = 0

F (j) = \{ \begin{matrix}\frac{1}{q} & if F (j − 1) = \frac{q−2}{q−1} \\ \frac{p}{q} & if F (j − 1) = \frac{p−1}{q} for p < q \end{matrix}

Notice that F is well defined since every possible value for F (j − 1) has been included in our definition of F(j). In fact, F (3) = 1/2, F (4) = 1/3, F (5) = 2/3, F (6) = 1/4 and so on.

4.We can prove by induction that F (1+1+(0+1+2+3+4+...+m)) = (m)/(m+1) for m ≥ 0. The idea is to group the terms:

0; 1; 1/2; 1/3, 2/3; 1/4, 2/4, 3/4; 1/5, 2/5...4/5; .... Thus (m)/(m + 1) = F (2 + m(m + 1)/2) if m ≥ 0. We skip the proof of this step because not everyone in the class knows induction. Furthermore, if p < m + 1, we know that using the definition of F p times gives us: p/(m + 2) = F (p + 2 + m(m + 1)/2) if p = 1, ..m + 1 and m ≥ 0.

5. We now show that F is a surjection. We will show that given any p/q ∈ Q ∩ [0, 1], there exists an n ∈ N I such that p/q = F (n). Let p/q ∈ Q ∩ [0, 1]. Then p/q ≥ 0 so p ≥ 0 and q > 0. Also p/q ≤ 1, so p/q = 1 or p < q.

Case I: If p/q = 1 then p/q = F (2) and we are done.

Case II: If p = 0, then p/q = F (1).

Case III: If q > p > 0, then p ≥ 1 and q > p so q ≥ 2. So if we take m = q −2 we have m ≥ 0 and by the last line of step 4 we know p/q = p/(m + 2) = F (p + 2 + m(m + 1)/2).

Thus F is a surjection and Q ∩ [0, 1] is countable.

6. Given any i ∈ ZZ , then Q ∩ [i, i + 1] is also countable because the map F_{i}(n) = F (n) + i maps N I onto this set.

7. We claim that

Q = ⋃_{i=0}^{∞} ( Q ∩ [i, i + 1]) ∪ ⋃_{i=0}^{∞} ( Q ∩ [−i − 1, −i]) .

It is obvious from the definition of Q ∩ [a, b] that

Q ⊃ ⋃_{i=0}^{∞} ( Q ∩ [i, i + 1]) ∪ ⋃_{i=0}^{∞} ( Q ∩ [−i − 1, −i]) .

On the other hand, for all p/q ∈ Q we have two cases p/q > 0 and p/q < 0. If p/q > 0 then p/q = i + r/q where r < q by division with a remainer. So p/q ∈ Q ∩ [i, i + 1]. If p/q < 0 then negate it and do division, so −p/q = i + r/q and p/q ∈ Q ∩ [−i − 1, −i]. Thus

Q ⊂ ⋃_{i=0}^{∞} ( Q ∩ [i, i + 1]) ∪ ⋃_{i=0}^{∞} ( Q ∩ [−i − 1, −i]) .

8. By Theorem III, the countable unions,

⋃_{i=0}^{∞} ( Q ∩ [i, i + 1])

and

⋃_{i=0}^{∞} ( Q ∩ [−i − 1, −i]) .

are both countable. By Theorem II, their union is countable. Thus Q is countable.

□

Another Proof: 1. For homework you have proven that N I × N I is countable.

2. First we prove that {r ∈ Q : r > 0} is countable. Let g_{+} : N I × N I ⟼ {r ∈ Q : r > 0} be defined as follows: g_{+}(a, b) = a/b. This map is clearly a surjection by the definition of Q given that we have limited ourselves to the strictly positive rationals. Thus by the Composition Lemma and step 1, {r ∈ Q : r > 0} is countable.

3. Simalarly {r ∈ Q : r < 0} is countable, using g_{−}(a, b) = −a/b.

4. {0} is clearly finite and therefore countable.

5. Since Q = {r ∈ Q : r > 0} ∪ {0} ∪ {r ∈ Q : r < 0} is a union of three countable sets, it is countable.

□

The fact that Q is countable indicates that, although Q is infinite, it is not as large as it might be. The fact is that there do exist sets which are not countable. The real line is not countable. We will prove this in Section 10.

In fact Q is missing a lot of lengths. For example, given a square whose sides have length 1, the diagonal is the square root of 2. But there is no such rational number!

Lemma: There is no rational number, r ∈ Q such that r^{2} = 2.

Proof:

1. Assume on the contrary that there exists r ∈ Q such that r^{2} = 2.

2. By the definition of Q there exist p, q ∈ ZZ relatively prime such that r = p/q. Thus, p^{2}/q^{2} = 2.

3. Thus p^{2} = 2q^{2}. Thus 2 divides p^{2}. Since 2 is prime it must be a prime factor of p, otherwise it could not be a factor of p^{2}. Thus p is a multiple of 2.

4. So there exists n ∈ N I such that p = 2n. Substituting this into p^{2} = 2q^{2}, we get 4n^{2} = 2q^{2} and so q^{2} = 2n^{2}. Since 2 is prime it must be a prime factor of q, otherwise it could not be a factor of q^{2}. Thus q is a multiple of 2.

5. p and q are relatively prime. So only one of them can be divisable by two. In other words, both of them cannot be even. This is a contradiction.

□

In fact we can use this exact same method to prove that there are no rational numbers whose squares are prime. Furthermore, any natural number which is divisable by a prime number p but not by p^{2} does not have a rational square root.

PROBLEM 4: Find the mistake in the following proof that 4 has no rational square root:

False Proof:

1. Assume on the contrary that there exists r ∈ Q such that r^{2} = 4.

2. By the definition of Q there exist p, q ∈ ZZ relatively prime such that r = p/q, so p^{2}/q^{2} = 4.

3. Thus p^{2} = 4q^{2}. Thus 4 divides p^{2}. Since 4 is prime it must be a prime factor of p, otherwise it could not be a factor of p^{2}. Thus p is a multiple of 4.

4. So there exists n ∈ N I such that p = 4n. Substituting this into p^{2} = 4q^{2}, we get 16n^{2} = 4q^{2} and so q^{2} = 4n^{2}. Since 4 is prime it must be a prime factor of q, otherwise it could not be a factor of q^{2}. Thus q is a multiple of 4.

5. p and q are relatively prime. So only one of them can be divisable by four. This is a contradiction.

PROBLEM 5: Prove the following lemma by contradiction.

Lemma: Let B be uncountable and C be countable. Then B \ C is uncountable.

Later we will prove that the reals are uncountable, and we have already proven that rationals are countable. This last lemma thus shows that the irrationals are uncountable as well. Later on in the course we will define the term “almost everywhere” and “almost every”. We will show that “almost every” real number is irrational. In analysis it is often useful enough to prove results “almost everywhere” without actually proving them everywhere. For example, we will show that if a function is 0 almost everywhere then its integral is 0.

7 Sequences in the Rationals and Convergence

In this section we will study sequences in the rationals. For those of you who have taken Calculus with proofs will have seen some of these definitions. It is essential to truely understand the definition of convergence as it will be used throughout the course. You must learn to prove that a sequence converges or diverges using information about the sequence, the triangle inequality, and the definition of convergence. The same techniques learned here for the rationals will carry over to the reals and later to Euclidean spaces and metric spaces in general.

Definition: A sequence is a bijection from N I to a set, or an ordered infinite set. It is denoted {a_{1}, a_{2}, a_{3}, ...} or {a_{i}}.

Some examples of sequences are a_{i} = i which is {1, 2, 3, ...} and a_{i} = i^{2} which is {1, 4, 9, 16, ...}. Recall from Calculus that there are some sequences which get closer and closer to certain limits. This is defined rigorously here.

Definition: Let x_{i} be a sequence of rational numbers. We say that x_{i} converges to a limit L if for any rational ε > 0, no matter how small, there exists an N_{ε} ∈ N I such that |x_{n} − L| < ε for all n ≥ N_{ε}. We denote this by

lim_{i→∞} x_{i} = x or x_{i} → x as i → ∞,

The idea is that the x_{i} are getting closer and closer to L. How close are they getting? As close as you wish, give me any tiny rational number ε > 0 and I can guarantee that eventually all the x_{i} are so close to L that |x_{i} − L| < ε. Eventually! What does that mean? It means there is some natural number N, and this number might be huge mind you, such that the whole end of the sequence starting at x_{N} is close to L. That is |x_{n} − L| < ε for all n ≥ N_{ε}.

See Definition 1.2.1 in Marsden and the explanation before and after it for another angle on the definition.

We now provide a sample of a proof that a specific sequence converges to a specific limit. Read the proof and make sure you understand how it relates to the definition. Afterwords we will explain how to think up such a proof on your own.

Lemma: The sequence, {1/i}, converges to 0.

Proof: 1. Given any ε, let N_{ε} = 1/ε + 1.

2. |x_{n} − L| = |1/n − 0| = 1/n by the definition of {x_{n}} and the limit L.

3. If n ≥ N_{ε}, then n > (N_{ε} − 1) ≥ 1/ε. Thus 1/n < ε.

4. So for all ε there exists N_{ϵ} (as defined in step 2) such that |x_{n} − L| = 1/n < ε for all n ≥ N_{ε}.

□

Lemma: The sequence {1/10^{n}} converges to 0.

Scratch: Before we prove this theorem we will figure out how to prove it. We want to show that |x_{n} − L| gets small. So first we compute |x_{n} − L|.

|x_{n} − L| = |\frac{1}{10^{n}} − 0| = \frac{1}{10^{n}} .

We want this to be less than ε fo some n sufficiently large. So we just solve to find out when it is smaller than ε:

|x_{n} − L| < ε if \frac{1}{10^{n}} < ε

which is true if

10^{n} > \frac{1}{ε}

which is true if

n > Log(1/ε).

So if n > Log(1/ε) then |x_{n} − L| < ε. Let N_{ε} be the next integer larger than Log(1/ε). Then if n ≥ N − ε, then n ≤ Log(1/ε) so |x_{n} − L| < ε. We can now write up the proof.

Proof: 1. Given any ε, let N_{ε} be the next integer larger than Log(1/ε).

2. By the definition of our sequence:

|x_{n} − L| = |\frac{1}{10^{n}} − 0| = \frac{1}{10^{n}} .

3. If n ≥ N_{ε}, then n > Log(1/ε). Thus 1/10^{n} < ε.

4. So for all ε there exists N_{ϵ} (as defined in step 2) such that |x_{n} − L| = 1/10^{n} < ε for all n ≥ N_{ε}.

□

PROBLEM 1: Prove that {n/(n + 1)} converges to 1. First follow the scratch above to come up with a good choice of N_{ε}. Then write up the proof in the four step format.

PROBLEM 2: Write out the first five terms of {x_{n}} where

x_{n} = ∑_{i=1}^{n} (\frac{1}{2})^{i} .

Guess what the limit is. Then prove that your limit is correct. In this case it may be a bit difficult for you to figure out what |x_{n} − L| is, but it does have an exact answer. Some of you may wish to prove the formula you get for |x_{n} − L| using induction. Others should remark, “I believe this formula holds but cannot prove it at this time” or should provide a reference.

It is important to notice that N_{ε} depends on ε and usually grows as ε goes to 0. It may also depend on L. After all, we are saying that the sequence converges to L.

Another kind of convergence theorem does not refer to any specific sequence. It tells general information that can be used later to prove the convergence of given sequences. Most of the convergence theorems given in this course are of this form.

READ: Read Lemma 1.2.2 in the Marsden. This is the Sandwich Lemma. Copy it into your notes along with the proof which can be found at the end of the Chapter 1 along with all the other proofs (page 80).

Lemma: Suppose x_{i} → x and y_{i} → y then x_{i}y_{i} → xy.

Proof:

1. Since x_{i} → x we have: (in shorthand)

∀r > 0, ∃N_{x,r} ∈ N I such that |x_{n} − x| < r ∀n ≥ N_{x,r}.

We have used r instead of ε because we will use ε later in the proof for the sequence x_{i}y_{i}. Note that N_{x,ε} depends on our sequence x_{i} and on r.

2. Since y_{i} → y we have: (in shorthand)

∀R > 0, ∃N_{y,R} ∈ N I such that |y_{n} − y| < R ∀n ≥ N_{y,R}.

We have been careful not to use the same name for the two N′s.

3. We wish to show that |x_{i}y_{i} − xy| gets small. So first we rewrite this formula:

|x_{i}y_{i} − xy| = |x_{i}y_{i} − x_{i}y + x_{i}y − xy| ≤ |x_{i}y_{i} − x_{i}y| + |x_{i}y − xy| by the triangle inequality. Furthermore

|x_{i}y_{i} − x_{i}y| + |x_{i}y − xy| = |x_{i}||y_{i} − y| + |x_{i} − x||y|

4. By steps 1 and 2 we know that for n ≥ max{N_{x,r}, N_{y,R}}, we have |x_{n} − x| < r and |y_{n} − y| < R. Thus, using step 3,

|x_{n}y_{n} − xy| ≤ |x_{n}|R + r|y|.

Now we must bound |x_{n}| from above so that our upper bound on |x_{n}y_{n} − xy| doesn’t depend on n.

5. By step 1, we know that for n as in step 4, |x_{n}−x| < r. In particular, |x_{n}| < |x|+r. Thus

|x_{n}y_{n} − xy| ≤ (|x| + r)R + r|y|.

We need this last part to be less than epsilon. Note that we have not yet assigned any values to R and r, they could be any positive rational.

6. Given any ε > 0, let r < ε/(2|y|) and let R < ε/(2(|x| + r)). Then if we let

N_{ε} = max{N_{x,r}, N_{y,R}}

for those particular values of r and R depending on ε and the limits x and y, we have:

|x_{n}y_{n} − xy| ≤ (|x| + r)R + r|y| < ε/2 + ε/2 = ε

for all n ≥ N_{ε}.

□

PROBLEM 3: Prove that if x_{i} → x and y_{i} → y then x_{i} + y_{i} converges to x + y. Follow the technique used above and don’t worry step 3 will be significantly easier.

PROBLEM 4: Prove that if x_{i} → x ≠ 0 then there exists an M ∈ N I such that |x_{i}| > |x|/2 for all i ≥ M. Then use this to prove that if x_{i} → x ≠ 0 then 1/x_{i} converges to 1/x. Note that if we only assume that x_{i} does not converge to 0 it need not be bounded away from 0 as in problem 4. {x_{i}} could be an alternating sequence like {0, 1, 0, 1, 0...} which does not converge at all.

For further references about the convergence of sequences, see the beginning of Anton’s text on Calculus or most other standard Calculus texts. There you should find more examples and problems.

READ Marsden p 80, 1.2.5 and 1.2.6. (1.2.7 if you wish) Note that reading section 1.2 itself will be misleading, because that section discusses the real number system and here we are working with the rationals, however, these particular theorems hold on the rationals. In the next section one of the major problems with studying the rationals will be discussed.

8 Cauchy Sequences of Rationals

In this section we will develop and define one of the most important concepts in this course, Cauchiness. This is a special property of sequences which may or may not have limits. However, any sequence which has a limit is Cauchy. We begin with a discussion of some sequences which don’t converge.

Lemma: {n} = {1, 2, 3...} does not converge to any limit.

Proof:

1. Assume, in the contrary, that there exists L such that {n} converges to L.

2. By the definition of convergence,

∀ε > 0, ∃N_{ε} ∈ N I such that |n − L| < ε ∀n ≥ N_{ε}.

3. In particular, we can take ε = 1/2. So there exists N_{1/2} such that |n − L| < 1/2 for all n ≥ N_{1/2}.

4. Now we can chose particular n ≥ N_{1/2}. Since N_{1/2} ≥ N_{1/2}, we know |N_{1/2} − L| < 1/2. Since N_{1/2} + 1 ≥ N_{1/2}, we know that |N_{1/2} + 1 − L| < 1/2.

5. By step 4 and the triangle inequality, we have:

|N_{1/2} + 1 − N_{1/2}| ≤ |N_{1/2} + 1 − L| + |L − N_{1/2}| < 1/2 + 1/2 = 1

but on the otherhand:

|N_{1/2} + 1 − N_{1/2}| = 1

so we have a contradiction.

□

Notice how the key idea in the contradiction is that the elements in the sequence did not get close to each other. If they aren’t clustered together then they cannot converge together to a spot. In particular, the sequence {1, 2, 3...} is always spaced apart by a distance of 1. Thus we can’t expect that all the points will eventually get within 1/2 of any limit. Here is another example:

Lemma: If a_{n} = ∑_{i=1}^{n}(1/i), then the limit, lim_{n→∞}a_{n} does not exist.

Proof:

1. Assume, on the contrary, that the limit, lim_{n→∞}a_{n} = L exists.

2. Then ∀ε, ∃N_{ε} such that |a_{n} − L| < ε ∀n ≥ N_{ε}. In particular, taking ε = 1/4, we know there exists N_{1/4} such that |a_{n} − L| < 1/4 ∀n ≥ N_{1/4}.

(This time |a_{n+1} − a_{n}| = 1/(n + 1) does get very small. We need to use the fact the existence of a limit crowds all the a_{n} for n ≥ N_{1/4} near L. We will look at a_{N} and a_{2N}.)

3. Thus, |a_{N} − L| < 1/4 and |a_{2N} − L| < 1/4 for N = N_{1/4} and, by the triangle inequality,

|a_{2N} − a_{N}| ≤ |a_{N} − L| + |a_{2N} − L| < 1/2.

4. But

a_{2N} − a_{N} = ∑_{i=1}^{2N} \frac{1}{i} − ∑_{i=1}^{N} \frac{1}{i}

= ∑_{i=N+1}^{2N} \frac{1}{i}

≥ ∑_{i=N+1}^{2N} \frac{1}{2N} = N \frac{1}{2N} = \frac{1}{2}.

This is a contradiction.

□

Like the last sequence, this sequence didn’t converge because it did not bunch up enough. Although the neighboring terms in the sequence become arbitrarily close, we could always find another term which was more than 1/2 away from a given term. This bunching up of all the terms near all the other terms in the end of a sequence is called Cauchiness. A sequence is Cauchy if the terms bunch. The last two sequences were not Cauchy.

Definition: A sequence, {a_{i}}, is Cauchy if for all ε > 0, no matter how small, there exists an N_{ε} ∈ N I such that

|a_{n} − a_{m}| < ε ∀ n, m ≥ N_{ε}.

This is the same as saying that given any tiny number, ε, I can find a chopping point, N such that the tail of the sequence, {a_{N}, a_{N+1}, a_{N+2}, ...}, is all bunched up within a space of size ε.

PROBLEM 1: Prove that a_{n} = ∑_{i=1}^{n}(1/i) is not a Cauchy sequence. Hint: Prove it by contradiction.

PROBLEM 2: Prove that {1/2^{n}} is a Cauchy sequence using the definition of Cauchy. That is, for each ε provide a N_{ε} such that the tail is bunched up. This is very similar to the proof that a sequence converges to a limit.

This definition does not refer to any limit or whether or not a sequence has a limit. We now prove that if a sequence has a limit, then it is Cauchy. The converse, however, is not true on the rationals.

Theorem: If a sequence converges, then it is Cauchy.

Proof: 1. Let {a_{n}} be a sequence which converges to some L ∈ Q. By the definition of convergence we know:

∀r > 0 ∃N_{r} ∈ N I such that |a_{n} − L| < r ∀n ≥ N_{r}.

2. Furthermore if m ≥ N_{r} we have |a_{m} − L| < r.

3. Thus by the triangle inequality, |a_{m} − a_{n}| < |a_{n} − L| + |a_{m} − L| < 2r.

4. Taking ε = 2r, we have |a_{m} − a_{n}| < ε for all m, n ≥ N_{ε/2}.

5. Thus

∀ε > 0 ∃N_{ε/2} ∈ N I such that |a_{n} − L| < ε ∀n ≥ N_{ε/2}.
□

Other kinds of sequences of rationals are also Cauchy. For example if you have a monotone increasing sequence, that is a_{i+1} ≥ a_{i}, and it is bounded above, a_{i} ≤ M, then the sequence is forced to crowd up somewhere below or at M itself. It cannot have terms which are spaced a fixed distance apart and thus a fixed distance larger and still remain bounded above.

Theorem: If {a_{i}} is a sequence of rational numbers which is monotone increasing,

a_{i+1} ≥ a_{i} ∀i ∈ N I ,

and bounded above by a bound M ∈ Q,

a_{i} ≤ M ∀i ∈ N I ,

then {a_{i}} is a Cauchy sequence.

Proof: 1. Assume, on the contrary, that {a_{i}} is not Cauchy. Then there exists an ε such that for all N ∈ N I there exist pairs n, m ≥ N such that |a_{n} − a_{m}| ≥ ε. (Notice how we negated the definition of Cauchy changing the for alls into there exists and visa versa.).

2. Using monotonicity and step 1, we know that for all N ∈ N I there exists n, m ≥ N and we can chose n > m such that a_{n} ≥ a_{m} + ε.

3. There exists k ∈ N I such that M < a_{1} + kε by division.

4. Now using step 2 with N = 1, we know there exists n_{1} ≥ m_{1} ≥ 1 such that

a_{n,1} ≥ ε + a_{m,1} ≥ ε + a_{1}.

5. Using step 2 with N = n_{1}, we know there exists n_{2} > m_{2} ≥ n_{1} such that

a_{n,2} ≥ ε + a_{m,2} ≥ ε + a_{n,1}

6. We now keep iterating this idea, supposing we have defined n_{j}, we now find n_{j+1} using step 2 for N = n_{j}. That is there exists n_{j+1}, m_{j+1} such that

a_{n,j+1} ≥ ε + a_{m,j+1} ≥ ε + a_{n,j}

by the monotonicity. We repeat this for j = 1, 2, ...k. Then

a_{n,k} ≥ ε + a_{n,k−1}
≥ ε + ε + a_{n,k−2} = 2ε + a_{n,k−2}
...
≥ kε + a_{n,1}
≥ kε + ε + a_{1} ≥ M + ε.

The last line follows from the definition of k.

7. However, a_{n,j+1} is an element in the sequence, so a_{n,j+1} cannot be larger than M. Contradiction.

□

Recall from the last section that if x_{i} → x then x_{i}^{2} → x^{2}. The following lemma has the strongest possible reverse statement.

Lemma: Let {x_{i}} be a sequence of positive rationals. Suppose that the sequence of squares, {x_{i}^{2}} converges to a rational limit L. Then {x_{i}} is Cauchy.

PROBLEM 3: Prove the lemma. Warning: The square root of L may not exist in the rationals. So you cannot use it to help you with the proof. However you can use the fact that given any L, there exists k ∈ N I such that k^{2} ≥ 2/L. Hint: seperate the problem into two cases L = 0 or L ≠ 0 and refer back to Problem 4 of the last section.

An Example of a Cauchy Sequence That Does Not Converge:

We now present a Cauchy sequence of rational numbers which do not converge to a rational limit. This sequence starts out as {1, 14/10, 141/100, ...} and its squares converge to the limit 2.

1. Let us call this sequence {r_{k}} for a moment. We are going to construct {r_{k}} such that r_{k}^{2} → 2. Suppose r_{k} itself had a rational limit, r, then by the last section r^{2} = 2, but we have also proven that 2 does not have a rational square root. Thus the limit r could not have existed. We now construct this sequence.

2. Let b_{0} = max{b ∈ N I : (b/1)^{2} < 2}. Clearly b_{0} = 1. Let b_{1} = max{b ∈ N I : (b/10)^{2} < 2}. Clearly b_{1} = 14. Let b_{2} = max{b ∈ N I : (b/10^{2})^{2} < 2}. So b_{2} = 141. Let b_{k} = max{b ∈ N I : (b/10^{k})^{2} < 2}. This can be found for each k.

3. We now wish to show that (b_{k}/10^{k})^{2} converges to 2. Since b_{k} is the largest natural number such that (b_{k}/10^{k})^{2} < 2, we know that ((b_{k} + 1)/10^{k})^{2} ≥ 2. Thus we have

(\frac{b_{k} + 1}{10^{k}})^{2} ≥ 2 ≥ (\frac{b_{k}}{10^{k}} )^{2}

so

(\frac{b_{k}^{2} + 2b_{k} + 1}{10^{2k}}) ≥ 2 ≥ (\frac{b_{k}}{10^{k}} )^{2}

and

(\frac{2b_{k} + 1}{10^{2k}}) ≥ 2 − (\frac{b_{k}}{10^{k}} )^{2} ≥ 0.

Clearly b_{k} < 2(10^{k}) since (b_{k}/10^{k})^{2} < 2, so

(\frac{4(10^{k}) + 1}{10^{2k}}) ≥ 2 − (\frac{b_{k}}{10^{k}} )^{2} ≥ 0.

The left hand side of this equation converges to 0 as k → ∞ so by the Squeeze Lemma, 2 − (b_{k}/10^{k})^{2} converges to 0 and so (b_{k}/10^{k})^{2} converges to 2.

4. Let r_{k} = (b_{k}/10^{k}). This is clearly rational, since b_{k} ∈ N I . Thus r_{k}^{2} converges to 2. By the above Lemma, {r_{k}} is Cauchy. By step 1, {r_{k}} does not have a limit.

□

So now we have presented the essential problem with attempting to do Calculus on the rationals. Sequences can get closer and closer to empty spots. We must fill in these empty spots if we hope to define continuity or differentiability. Thus we must define the real line. The real line will be the rationals with all the holes filled in.

Although a Cauchy sequence need not converge it must remain bounded. That is, a Cauchy sequence cannot approach infinity or negative infinity.

Lemma: The Boundedness of Cauchy Sequences

Given a Cauchy sequence {a_{i}}, there exists a bound A ∈ N I such that |a_{i}| ≤ A for all i ∈ N I .

Notice how the entire sequence is bounded, not just the end.

Proof:

We will construct a number A ∈ N I . It may not be the smallest possible bound, but that is not necessary.

1. Since {a_{i}} is Cauchy we know that for all ε including the number 1, there exists a number N such that

|a_{i} − a_{j}| < 1 ∀i, j ≥ N.

2. Let A = max{|a_{1}|, |a_{2}|, ...|a_{N}|} + 1. This maximum is defined because this is just a finite list of rational numbers, choose the biggest.

3. If i = 1, 2, ..N then |a_{i}| < A by the definition of A in step 2. If i > N then, by step 1 substituting j = N, we have |a_{i}−a_{N}| < 1. Thus |a_{i}| < |a_{N}|+1 ≤ A.

□

Cauchy sequences which don’t converge to rationals are eventually bounded away from 0 as well as infinity.

Lemma: If {a_{i}} is a Cauchy sequence which does not converge in the rationals then there exists a lower bound m > 0 and there exists a number N such that |a_{i}| ≥ m for all i ≥ N.

PROBLEM 4: Prove this lemma by contradiction. Be careful when you negate the conclusion.

9 Construction of the Real Line

In this section we construct the real line which is the completion of the rationals. That is, it includes all the rationals and limits for any sequence of rationals. In order to construct the real line we must describe its elements including those which are not included in the rationals. These “holes” which are missing from the rationals must be “pointed at” in some sense. The only way to “point” at them is to use a Cauchy sequence which bunches around the “hole”. We must be careful not to point at the same “hole” twice. That is, if two Cauchy sequences bunch together, then we want to consider them as pointing at the same “hole”. For this reason we want two Cauchy sequences to be equivalent if they bunch together.

Definition: Two Cauchy sequences {a_{i}} and {b_{i}} are said to be Cauchy equivalent if the following is true:

∀ε > 0 ∃N_{ε} ∈ N I such that |a_{i} − b_{j}| < ε ∀i, j ≥ N_{ε}.

In other words, two Cauchy sequences are Cauchy equivalent if their tails get closer and closer together. Given any ε > 0 there exists a cutoff N such that all the points {a_{N}, a_{N+1}, ...} ∪ {b_{N}, b_{N+1}, ...} are within a distance ε from each other.

So in particular, the two sequences {1, 1/2, 1/3, ...} and {1, 1/10, 1/100, ...} are Cauchy equivalent.

Lemma: Cauchy Equivalence is an equivalence relation on the set of Cauchy sequences of rational numbers.

Proof: We must check the three properties.

i) {a_{i}} ∼ {a_{i}} because

∀ε > 0 ∃N_{ε} ∈ N I such that |a_{i} − a_{j}| < ε ∀i, j ≥ N_{ε}.

by the Cauchiness of {a_{i}}.

ii) If {a_{i}} ∼ {b_{i}} then

∀ε > 0 ∃N_{ε} ∈ N I such that |a_{i} − b_{j}| < ε ∀i, j ≥ N_{ε}.

which implies that {b_{i}} ∼ {a_{i}} since |a_{i} − b_{j}| = |b_{j} − a_{i}|.

iii) If {a_{i}} ∼ {b_{i}} and {b_{i}} ∼ {c_{i}} then

∀ε > 0 ∃N_{1,ε} ∈ N I such that |a_{i} − b_{j}| < ε ∀i, j ≥ N_{1,ε}.

and

∃N_{2,ε} ∈ N I such that |b_{j} − c_{k}| < ε ∀j, k ≥ N_{2,ε}.

Let N = max{N_{1,ε/2}N_{2,ε/2}}. This guarantees that if i, j, k ≥ N_{ε}, then both of the above equations hold. Then

|a_{i} − c_{k}| ≤ |a_{i} − b_{N}| + |b_{N} − c_{k}| < ε/2 + ε/2 = ε ∀i, k ≥ N.

Thus

∀ε > 0 ∃N_{ε} ∈ N I such that |a_{i} − c_{k}| < ε ∀i, k ≥ N_{ε}

and {a_{i}} ∼ {c_{i}}.

□

Note that Cauchy equivalence is not an equivalence relation on the set of all sequences. If a sequence is not Cauchy then it is not equivalent to itself and property (i) fails.

The next lemma states that if a Cauchy sequence is bunched close to a converging sequence, then it also converges and to the same limit.

Lemma: If {a_{i}} converges to L ∈ Q and {a_{i}} ∼ {b_{j}}, then {b_{j}} has a limit and that limit is L.

Proof:

1. Since a_{i} converges to L we know that

∀ε > 0 ∃N_{1,ε} ∈ N I such that |a_{i} − L| < ε ∀i ≥ N_{1,ε}.

2. Since {a_{i}} ∼ {b_{j}}, we know that

∀ε > 0 ∃N_{2,ε} ∈ N I such that |a_{i} − b_{j}| < ε ∀i, j ≥ N_{2,ε}.

3. Let n_{ε} = max{N_{1,ε/2}N_{2,ε/2}}. Then

|b_{j} − L| ≤ |a_{i} − L| + |b_{j} − a_{i}| < ε ∀j ≥ N_{ε}.

So:

∀ε > 0 ∃N_{ε} ∈ N I such that |b_{j} − L| < ε ∀j ≥ N_{ε}.
□

Lemma: If {a_{i}} and {b_{i}} are converging sequences and they converge to the same limit, L ∈ Q, then they are Cauchy equivalent to each other.

PROBLEM 1: Prove this lemma. Write out what a_{i} → L means and what b_{j} → L means using different notation for N, then choose an appropriately large N_{ε} and use the triangle inequality.

Given these last two lemmas, we see that Cauchy equivalence classes of Cauchy sequences have very nice properties. For one thing, if one sequence in an equivalence class converges to a rational number, q, then so does every other sequence in that class, and no other sequences in any other equivalence class does. Furthermore, given a rational number q, we know there exists a Cauchy sequence converging to q, namely the constant sequence: {q, q, q, q, q, ...}. Thus there is an injection mapping the rationals to equivalence classes of Cauchy sequences:

q ↦ [{q, q, q, ...}] = the set of sequences converging to q.

This is not a surjection, as we know because there exists the Cauchy sequence constructed in the last section, which does not converge. We can consider the equivalence class of that Cauchy sequence to correspond to the square root of 2. Before we can do so rigorously, we must check the properties of multiplication on these equivalence classes.

One more important property of equivalent Cauchy sequences is that it doesn’t matter where the sequence starts:

PROBLEM 2: Prove that the sequences {a_{i}} = {a_{1}, a_{2}, a_{3}, ...} and {a_{i+k}} = {a_{k+1}, a_{k+2}, ...} are equivalent. (Note that this implies that if two sequences are identical eventually, then they are equivalent. They bunch up into the same place.)

Definition: The Real line, R I , is defined to be the set of Cauchy equivalence classes of Cauchy sequences of rational numbers.

We must now verify that the Real line obeys all the field axioms (listed on page 26 of Marsden). For now, we will denote elements of the real line by [{a_{i}}] as is usual with equivalence classes.

Theorem: The Real line is a field containing the rationals.

Proof:

I. Addition Axioms:

Let [{a_{i}}]+[{b_{i}}] be defined to be [{a_{i} +b_{i}}] which is the equivalence class containing the sequence {a_{1} + b_{1}, a_{2} + b_{2}, ...}.

This is well defined because if {a_{i}} ∼ {c_{i}} and {b_{i}} ∼ {d_{i}} then:

∀ε > 0 ∃N_{1,ε} ∈ N I such that |a_{i} − c_{j}| < ε ∀i, j ≥ N_{1,ε}.

and

∀ε > 0 ∃N_{2,ε} ∈ N I such that |b_{i} − d_{j}| < ε ∀i, j ≥ N_{2,ε}.

so taking N_{ε} ≥ max{N_{1,ε/2}, N_{2,ε/2}} we get

|a_{i} + b_{i} − (c_{j} + d_{j})| < ε ∀i, j ≥ N_{ε}.

So {a_{i} + b_{i}} ∼ {c_{i} + d_{i}}.

The four addition axioms then follow:

Axioms 1 and 2 hold since they are true termwise in the rationals.

Axiom 3 holds with the additive identity element, [{0}] = [{0, 0, 0, 0...}].

Axiom 4 holds with the additive inverses defined by −[{a_{i}}] = [{−a_{i}}].

We need only verify that the rationals add the same way as a subset of the reals. This is true since q, r ∈ Q correspond to [{q}] and [{r}] in the reals and q + r ∈ Q corespnds to [{q + r}] in the reals. Notice that this interacts fine with all four additive axioms.

I. Multiplication Axioms:

Let [{a_{i}}] × [{b_{i}}] be defined to be [{a_{i}b_{i}}], which is the equivalence class containing the sequence {a_{1}b_{1}, a_{2}b_{2}, ...}.

This is well defined because if {a_{i}} ∼ {c_{i}} and {b_{i}} ∼ {d_{i}} then:

∀ε > 0 ∃N_{1,ε} ∈ N I such that |a_{i} − c_{j}| < ε ∀i, j ≥ N_{1,ε}.

and

∀ε > 0 ∃N_{2,ε} ∈ N I such that |b_{i} − d_{j}| < ε ∀i, j ≥ N_{2,ε}.

Since {b_{i}} and {c_{i}} are Cauchy sequences they are bounded by natural numbers B and C, by the boundedness of Cauchy sequences lemma. So taking N_{ε} ≥ max{N_{1,ε/(2B)}, N_{2,ε/(2C)}} we get

|a_{i}b_{i} − c_{j}d_{j}| ≤ |a_{i}b_{i} − c_{j}b_{i}| + |c_{j}b_{i} − c_{j}d_{j}|
≤ |a_{i} − c_{j}||b_{i}| + |c_{j}||b_{i} − d_{j}|
≤ |a_{i} − c_{j}|B + C|b_{i} − d_{j}|
≤ ε.

Thus {a_{i}b_{i}} ∼ {c_{i}d_{i}} and multiplication is well defined.

The multiplicative axioms follow:

Axioms 5, 6 and 9 hold because they hold termwise.

Axiom 7 holds with the multiplicative identity defined as [{1, 1, 1, 1...}].

Axiom 8 holds: Given [{a_{i}}] ≠ [{0}], we know by Problem 4 of the last section that there exists m > 0 and N ∈ N I such that |a_{i}| ≥ m for i ≥ N. So the sequence {1/a_{N}, 1/a_{N+1}, ...} exists. We claim that [{1/a_{N}, 1/a_{N+1}, ...}] is a good multiplicative inverse for [{a_{i}}]. Using problem 2, we know that [{a_{i}}] = [{a_{N}, a_{N+1}, ...}]. Thus

[{a_{i}}] × [{1/a_{N}, 1/a_{N+1}, ...}] = [{a_{N}, a_{N+1}, ...}] × [{1/a_{N}, 1/a_{N+1}, ...}] = [{1}].

and visa versa.

Axiom 10 holds because [{1}] ≠ [{0}] since they represent different rational numbers. We need only verify that the rationals multiply the same way as a subset of the

reals. This is true since q, r ∈ Q correspond to [{q}] and [{r}] in the reals and qr ∈ Q corresponds to [{qr}] in the reals. Notice that this interacts fine with all multiplicative axioms.

□

So, with these axioms proven once and for all, we can treat the reals like a field as we are used to doing. We now need to define an inequality and prove the order axioms (Marsden, page 27). Note that we will have to define this ordering on the equivalence classes. We want to say that one class is larger than another if it bunches around a location which is larger than the other. Since we know that the sequences are Cauchy, we know that their tails fit in very small intervals. So we will say that one sequence is larger than another if there is a cutoff point such that the one sequence has a tail which is larger than the others termwise. For example:

[{1, 1/2, 1/3, 1/4, 1/5, ...}] < [{2/10, 22/100, 222/1000, 2222/10000, ...}]

because, after the ninth term, the first sequence has smaller terms:

1/9 < 222222222/1000000000 1/10 < 2222222222/10000000000 ...

In this case our two sequences have rational limits, 0 and 2/9 = .22222... and 0 < 2/9 so the ordering makes sense.

Definition: Let [{a_{i}}] > [{b_{i}}] if [{a_{i}}] ≠ [{b_{i}}] and there exists N ∈ N I such that a_{i} > b_{i} for all i ≥ N.

PROBLEM 3: i) Prove that this definition is well defined. ii) Give an example of a pair of equivalent real numbers, [{a_{i}}] = [{b_{i}}], such that there exists N ∈ N I such that a_{i} > b_{i} for all i ≥ N. This is why we must insist that [{a_{i}}] ≠ [{b_{i}}] in our definition.

Lemma: [{a_{i}}] ≥ [{b_{i}}] if [{a_{i}}] > [{b_{i}}] or [{a_{i}}] = [{b_{i}}]. This inequality allows us to say that the real line is an ordered field (page 27, Marsden).

Proof:

1. The strict inequality, >, is well defined by problem 3, thus the inequality, ≥, is well defined as well..

2. The inequality obeys reflexivity by the definition. (Axiom 11)

3. To prove Antisymmetry, Axiom 12, we must show that if [{a_{i}}] ≥ [{b_{i}}] and [{b_{i}}] ≥ [{a_{i}}] then [{a_{i}}] = [{b_{i}}].

Assume on the contrary that [{a_{i}}] ≠ [{b_{i}}]. First of all if [{a_{i}}] ≥ [{b_{i}}], then [{a_{i}}] = [{b_{i}}] or [{a_{i}}] > [{b_{i}}]. We assume they aren’t equal, so the second case must be true. The idea is that if you know a sock is red or blue and you know it is not blue, then it must be red. In the second case, [{a_{i}}] > [{b_{i}}], we know there exists N_{1} such that a_{i} > b_{i} for all i ≥ N_{1}. We also have the hypothesis that [{b_{i}}] ≥ [{a_{i}}], which implies [{a_{i}}] = [{b_{i}}] or [{a_{i}}] > [{b_{i}}]. We assumed that the first case cannot hold, thus [{a_{i}}] > [{b_{i}}]. So there exists N_{2} such that a_{i} > b_{i} for all i ≥ N_{2}. This is impossible. Our assumption has been contradicted, so [{a_{i}}] = [{b_{i}}].

4. To prove transitivity, Axiom 13, we must show that if [{a_{i}}] ≥ [{b_{i}}] and [{b_{i}}] ≥ [{c_{i}}] then [{a_{i}}] ≥ [{c_{i}}].

PROBLEM 4: Prove this. Warning, split ≥ into the > and = cases.

5. To prove linear ordering, Axiom 14, we must show that given any pair of equivalence classes [{x_{i}}] and [{y_{i}}] then either [{x_{i}}] ≥ [{y_{i}}] or [{y_{i}}] ≥ [{x_{i}}].

Given any [{x_{i}}] and [{y_{i}}], let us look at [{x_{i}−y_{i}}] and a particular Cauchy sequence {x_{i} − y_{i}}. There are three cases: I. Eventually all the terms are strictly positive. II. Eventually all the terms are strictly negative. III. No matter how far we go there are nonnegative and nonpositive terms.

Case I. ∃N_{I} ∈ N I such that x_{I} − y_{i} > 0 for all i ≥ N_{I}. Thus [{x_{i}}] > [{y_{i}}], so [{x_{i}}] ≥ [{y_{i}}]

Case II. ∃N_{II} ∈ N I such that x_{i} − y_{i} < 0 for all i ≥ N_{II}. Thus [{y_{i}}] > [{x_{i}}], so [{y_{i}}] ≥ [{x_{i}}].

Case III. No matter how far we go there are nonnegative and nonpositive terms. We will prove that any such Cauchy sequence {a_{i}} converges to 0. Cauchiness implies that ∀ε > 0 ∃N ∈ N I such that |a_{i} − a_{j}| < ε ∀i, j ≥ N. Now, no matter how far we go there are nonnegative terms, so given any N, there exists i_{N} ≥ N such that a_{i,N} ≥ 0. In particular

|a_{i,N} − a_{j}| < ε ∀j ≥ N

so

a_{j} > a_{i,N} − ε ≥ −ε ∀j ≥ N.

Also, no matter how far we go there are nonpositive terms, so given any N, there exists i_{N} ≥ N such that a_{i,N} ≤ 0. In particular

|a_{i,N} − a_{j}| < ε ∀j ≥ N

so

a_{j} < a_{i,N} + ε ≤ ε ∀j ≥ N.

Putting this together, we have

|a_{j}| < ε ∀j ≥ N.

Thus, for all ε > 0, there exists an N ∈ N I such that |a_{j}| < ε∀j ≥ N. So {a_{i}} converges to 0.

This means that our particular sequence {x_{i} − y_{i}} converges to 0. We will now show that {x_{i}} ∼ {y_{i}}.

Since {x_{i}} is Cauchy we know that

∀ε ∃N_{1,ε} ∈ N I such that |x_{i} − x_{j}| < ε ∀i, j ≥ N_{1,ε}.

Since {x_{i} − y_{i}} converges to 0 we know that

∀ε ∃N_{2,ε} ∈ N I such that |(x_{j} − y_{j}) − 0| < ε ∀j ≥ N_{2,ε}.

Putting this all together, given any ε > 0 there exists N_{ε} = max{N_{1,ε/2}, N_{2,ε/2}} such that

|x_{i} − y_{j}| ≤ |x_{i} − x_{j}| + |x_{j} − y_{j}| < ε/2 + ε/2

for all i, j ≥ N_{ε}. Thus they are equivalent. So [{x_{i}}] ≥ [{y_{i}}] and [{y_{i}}] ≥ [{x_{i}}]. 6. We now show that our inequality obeys axiom 15, compatibility with addition. PROBLEM 5: Prove this step. Don’t forget the cases > and =.

7. We now show that our inequality obeys axiom 16, compatibility with multiplication. If [{0}] ≤ [{x_{i}}] and [{0}] ≤ [{y_{i}}] then [{0}] ≤ [{x_{i}}] × [{y_{i}}].

PROBLEM 6: Prove this step. Don’t forget the cases > and =.

□

PROBLEM 7: During the proof of the above lemma it was irritating to break everything into the cases: > and =. Why couldn’t we just define ≥ in the first place? Demonstrate that the following definition does not obey one of the order axioms (reflexivity): [{a_{i}}] ≥ [{b_{i}}] if there exists N ∈ N I such that a_{i} ≥ b_{i} for all i ≥ N. Hint: Think about problem 3.

Now that we have proven that the reals are an ordered field we know that there is an absolute value, |[{x_{i}}]| which is defined to be [{x_{i}}] if [{x_{i}}] ≥ [{0}] and −[{x_{i}}] if [{x_{i}}] < [{0}]. Notice that the absolute value is another real number. It is an equivalence class of Cauchy sequences. We will now provide a formula which we can use to find the absolute value of a real number.

Absolute Value Lemma:

|[{x_{i}}]| = [{|x_{i}|}].

Proof: We break this into three cases: I. [{x_{i}}] > [{0}] II. [{x_{i}}] < [{0}]. II. [{x_{i}}] = [{0}].

1. Since [{x_{i}}] > [{0}] then |[{x_{i}}]| = [{x_{i}}] by the definition of the absolute value. Furthermore, ∃N ∈ N I such that x_{i} > 0 for all i ≥ N by the definition of the strict inequality. Thus x_{i} = |x_{i}| for all i ≥ N. So by problem 2, [{x_{i}}] = [{|x_{i}|}], and, combining this with the above equality, |[{x_{i}}]| = [{|x_{i}|}].

2. Since [{x_{i}}] < [{0}] then |[{x_{i}}]| = −[{x_{i}}] by the definition of the absolute value. Also −[{x_{i}}] = [{−x_{i}}] by the defn of −. Furthermore, ∃N ∈ N I such that x_{i} < 0 for all i ≥ N by the definition of the strict inequality. Thus −x_{i} = |x_{i}| for all i ≥ N. So by problem 2, [{−x_{i}}] = [{|x_{i}|}], and, combining this with the above equalities, |[{x_{i}}]| = [{|x_{i}|}].

3. Since [{x_{i}}] = [{0}], we have |[{x_{i}}]| = [{x_{i}}] by the definition of the absolute value. Also [{x_{i}}] = [{0}] implies that x_{i} → 0 and thus |x_{i}| → 0, so {x_{i}} ∼ {|x_{i}|}, so we have |[{x_{i}}]| = [{x_{i}}] = [{|x_{i}|}].

□

So we have finished proving that the real numbers are an ordered field and are related nicely to the rationals. All the theorems and definitions from the last section hold for the reals because they were based on the ordered field properties of the rationals. One thing to keep in mind is the ε in the definition of convergence is now thought of as a positive real number and thus should be thought of as an equivalence class of sequences as well. In short, the reals are at least as good a number system as the rationals. However, we have not shown that the reals have filled up all the holes.

Theorem: If a sequence of real numbers is Cauchy, then it converges to a real limit.

Proof: 1. Let {R_{i}} be a Cauchy sequence of real numbers. Note that each term, R_{i}, is a real number so it is an equivalence class of rational Cauchy sequences. That is, there exists a Cauchy sequence of rational numbers x_{j}^{i} such that

R_{i} = [{x_{1}^{i}, x_{2}^{i}, x_{3}^{i}...}] = [{x_{k}^{i}}].

Here x_{k}^{i} we are not taking an i^{th} power, but are refering to the i^{th} sequence.

We must find the limit, L, of this sequence R_{i}. Each R_{i} is being pointed at by a sequence {x_{k}^{i}}. So we need to construct a Cauchy sequence which points at their limit.

2. We know that {x_{k}^{i}} is Cauchy for all the sequences. So ∀ε > 0 ∃N_{i,ε} such that |x_{k}^{i} − x_{m}^{i}| < ε ∀ k, m ≥ N_{i,ε}. In particular, we can take ε = 1/i, then there exists n_{i} = N_{i,1/i} such that |x_{k}^{i} − x_{m}^{i}| < 1/i ∀ k, m ≥ n_{i}. Our special choice of n_{i} guarantees that the tail of each sequence {x_{n_{i}}^{i}, x_{n_{i}+1}^{i}, x_{n_{i}+2}^{i}, ...} is bunched into a space of size 1/i. So in some sense x_{n_{i}}^{i} is within a distance 1/i from the hole, R_{i}.

3. Let {y_{i}} = {x_{n_{i}}^{i}} = {x_{n_{1}}^{1}, x_{n_{2}}^{2}, ...}. This is a sequence made of terms from the other sequences, one term from each sequence. From step 2, we know that

|x_{k}^{i} − y_{i}| < 1/i ∀ k ≥ n_{i}.

Notice how each term in this sequence is within a distance 1/i from the hole R_{i} so that the R_{i} should converge to the same point that this sequence converges to.

4. We need to show that L = [{y_{i}}] is a real number.

Claim: {y_{i}} is Cauchy. Proof: We know that R_{i} is a Cauchy sequence. Thus for all r > 0 there exists M_{r} ∈ N I such that |R_{i} − R_{j}| < r for all i, j ≥ M_{r}. By the Absolute Value Lemma, we know that

r > |R_{i} − R_{j}| = [{|x_{k}^{i} − x_{k}^{j}|}] ∀i, j ≥ M_{r}.

Now, by the definition of >, and the fact that r is really the equiv class of the constant sequence [{r}], we know there exists N_{i,j}, which depends on the sequences i and j, such that

r > |x_{k}^{i} − x_{k}^{j}| ∀i, j ≥ M_{r} ∀k ≥ N_{i,j}.

On the other hand, from step 3, we have

|x_{k}^{i} − y_{i}| < 1/i ∀ k ≥ n_{i}.

and

|x_{k}^{j} − y_{j}| < 1/j ∀ k ≥ n_{j}.

So putting these three equations together we have

|y_{i} − y_{j}| ≤ |x_{k}^{i} − y_{i}| + |x_{k}^{i} − x_{k}^{j}| + |x_{k}^{j} − y_{j}|
< 1/i + 1/j + r ∀ k ≥ max{n_{i}, n_{j}, N_{i,j}} ∀i, j ≥ N_{ε}.

Since the dependence on k has disappeared, we have:

|y_{i} − y_{j}| < 1/i + 1/j + r ∀i, j ≥ M_{r}.

Thus, given any ε > 0 there exists N_{ε} = max{3/ε, M_{r}} where r = ε/3 such that

|y_{i} − y_{j}| < ε ∀i, j ≥ N_{ε}.

Thus {y_{i}} is Cauchy and its equivalence class, [{y_{i}}] is a real number.

5. Claim: R_{i} converges to L = [{y_{k}}]. The idea is that each y_{i} is close to R_{i} so the equivalence class [{y_{i}}] must be the limit of the R_{i}. Given ε > 0 we must find an N_{ε} such that

ε > |R_{i} − [{y_{k}}]| = |[{x_{k}^{i}}] − [{y_{k}}]| ∀i ≥ N_{ε}.

This means that we must show that the tails are less than epsilon apart. That is, we must show there exists M ∈ N I such that

ε > |x_{k}^{i} − y_{k}| ∀k ≥ M ∀i ≥ N_{ε}.

From step 2, we know that

|x_{k}^{i} − y_{i}| < 1/i ∀ k ≥ n_{i}

and from the last step we know that {y_{i}} is Cauchy so for all r > 0 there exists N_{r} such that

|y_{i} − y_{k}| < r ∀i, k ≥ N_{r}.

Thus, using the triangle inequality as usual, given any ε > 0 there exists N_{ε} = max{N_{r/2}, 2/ε} such that

|x_{k}^{i} − y_{k}| < ε ∀k ≥ n_{i} ∀i ≥ N_{ε}.

This is saying that the tails of these two sequences starting at n_{i} are less than epsilon. Thus:

|R_{i} − L| = |[{x_{k}^{i}}] − [{y_{k}}]| < ε ∀i ≥ N_{ε}

and we have proven the convergence of the R_{i}.

□

So we have proven that the set of real numbers is a complete ordered field. That is, it obeys all the expected properties of addition and multiplication and has an inequality with the usual properties. Furthermore, every Cauchy sequence converges. This last property is the completeness property. We will study it again in section 2.8, see definition 2.8.1 in Marsden. (Disregard definition 1.2.9 in Marsden).

The completeness of the reals implies one more important property of the real line, the Monotone Sequence Property. This property is taken as an axiom in Marsden. Here we will prove it.

Theorem: Any monotone increasing sequence of real numbers which is bounded above converges to a limit.

Proof: In the last section we proved that any monotone increasing sequence of rational numbers which is bounded above is Cauchy. The exact same proof, word for word, can be used to prove that any monotone increasing sequence of real numbers is Cauchy. We only need to use the ordered field properties.

We have just proven that any Cauchy sequence converges. Thus any monotone increasing sequence which is bounded above converges.

□

We have constructed a set of real numbers which obeys all the properties required by Marsden. In the future, we will rarely refer to the construction of the real line. Instead, we will refer to the properties of the real line as a complete ordered field.

READ sections 1.3 and 1.5

10 Decimal Expansions and the Nondenumerable Interval

In general, real numbers are refered to as decimal expansions of the form, .333333333... or 1.1415..... Through the act of long division it is easy to see that rational numbers have decimal expansions and that their expansions begin to repeat eventually (there are only finitely many different remainders before the process of division begins to repeat itself). We will now use our construction of the real line to prove that every real line can be mapped by a bijection to a special set of decimal expansions. We will then use these decimal expansions to prove that the unit interval is not countable.

First of all, we should examine what we mean by a decimal expansion. For example, .33333333...., is really the limit of a series. That is

.33333.... = lim_{n→∞} ∑_{i=1}^{n} \frac{3}{10^{i}} .

PROBLEM 1: Prove that \{a_{n}\} is Cauchy if a_{n} = ∑_{i=1}^{n} \frac{3}{10^{i}}.

Now since this is a Cauchy sequence it converges to a real number by the completeness of the reals.

Notice that in fact .3333333.... = 1/3. This can be seen using the following trick :

9(.33333...) = 10(.333....) − (.3333...)
= lim_{n→∞} 10a_{n} − lim_{n→∞} a_{n}
= lim_{n→∞}(3 + a_{n−1}) − lim_{n→∞} a_{n−1}
= lim_{n→∞}(3 + a_{n−1}) − a_{n−1} = 3.

PROBLEM 2: Justify these steps!

Before we define precisely what we mean by a decimal expansion, we will discuss one troublesome point. Notice that some decimals are finite, like 1/4 = .25. We will consider such expansions to have repeating 0’s. That is .25 = .2500000000...... Now what about .24999999....? It also refers to the real number 1/4.

PROBLEM 3: Prove that the sequence \{b_{i}\} where b_{n} = 2/10 + 4/100 + ∑_{i=3}^{n} \frac{9}{10^{i}} converges to 1/4.

To avoid these redundancies, we will define decimal expansions as infinite decimals which may end in repeating 0’s but not in repeating 9’s.

Definition: A decimal expansion is a sequence of the form:

\{∑_{i=1}^{n} \frac{b_{i}}{10^{i}} \}

such that b_{i} = 0, 1, 2...9 and such that there does not exist a number N such that b_{i} = 9 ∀i ≥ N. The decimal expansion is denoted by .b_{1}b_{2}b_{3}.....

PROBLEM 4: Prove that

∑_{i=m+1}^{n} \frac{b_{i}}{10^{i}} ≤ \frac{1}{10^{m}}

for any decimal expansion.

PROBLEM 5: Prove that all decimal expansions, \{∑_{i=1}^{n} \frac{b_{i}}{10^{i}} \}, are Cauchy sequences and therefore converge in R I . Hint use problem 4 and the defn of Cauchy.

Thus there is a map from the set of decimal expansions to the real line. We can consider every decimal expansion to be a real number.

Uniqueness of Decimal Expansions Theorem Given any pair of decimal expansions .b_{1}b_{2}b_{3}... and .c_{1}c_{2}c_{3}..., they converge to the same real number if and only if b_{i} = c_{i} for all i ∈ N I .

Proof: It is clear that if b_{i} = c_{i} for all i ∈ N I then the two sequences converge to the same point.

We must show that if they converge to the same point then b_{i} = c_{i} for all i ∈ N I . Assume on the contrary, that b_{i} ≠ c_{i} for some i. Let m ∈ N I be the first number such that b_{i} ≠ c_{i}. That is let b_{i} = c_{i} for i < m and b_{m} ≠ c_{m}. It is possible that m = 1.

Since b_{m} ≠ c_{m}, one of them must be larger than the other. So lets say b_{m} > c_{m}. Since they are natural numbers we have b_{m} ≥ c_{m} + 1. Thus

∑_{i=1}^{m} \frac{b_{i}}{10^{i}} ≥ ∑_{i=1}^{m} \frac{c_{i}}{10^{i}} + \frac{1}{10^{m}} .

So the sums are already 1/10^{i} apart. Can they come back together?

In problem 4, you demonstrated that:

∑_{i=m+1}^{n} \frac{b_{i}}{10^{i}} ≤ \frac{1}{10^{m}}

So we can use this fact to compare subsequent terms in our sequence, n ≥ m.

∑_{i=1}^{n} \frac{b_{i}}{10^{i}} ≥ ∑_{i=1}^{m} \frac{b_{i}}{10^{i}}
≥ ∑_{i=1}^{m} \frac{c_{i}}{10^{i}} + \frac{1}{10^{i}}
= ∑_{i=1}^{n} \frac{c_{i}}{10^{i}} − ∑_{i=m+1}^{n} \frac{c_{i}}{10^{i}} + \frac{1}{10^{m}}
≥ ∑_{i=1}^{n} \frac{c_{i}}{10^{i}} − \frac{1}{10^{m}} + \frac{1}{10^{m}}
= ∑_{i=1}^{n} \frac{c_{i}}{10^{i}} .

The first line follows from the fact that b_{i} ≥ 0. The second line uses the difference in the terms at m. The fourth line uses problem 4.

Now if we take limits as n approaches infinity throughout on this equation we get

lim_{n→∞} (∑_{i=1}^{n} \frac{b_{i}}{10^{i}} ) ≥ lim_{n→∞} (∑_{i=1}^{m} \frac{b_{i}}{10^{i}} )
≥ lim_{n→∞} (∑_{i=1}^{m} \frac{c_{i}}{10^{i}} ) + \frac{1}{10^{m}}

= lim_{n→∞} (∑_{i=1}^{n} \frac{c_{i}}{10^{i}} − ∑_{i=m+1}^{n} \frac{c_{i}}{10^{i}} ) + \frac{1}{10^{m}}

≥ lim_{n→∞} ∑_{i=1}^{n} \frac{c_{i}}{10^{i}} − \frac{1}{10^{m}} + \frac{1}{10^{m}}
≥ lim_{n→∞} ∑_{i=1}^{n} \frac{c_{i}}{10^{i}} .

By our hypothesis, the first and last lines of this equation must be equal. This forces all the other lines to be equal as well. In particular, the fourth line must be an equality,

lim_{n→∞} (∑_{i=1}^{n} \frac{c_{i}}{10^{i}} − ∑_{i=m+1}^{n} \frac{c_{i}}{10^{i}} ) + \frac{1}{10^{m}} = lim_{n→∞} ∑_{i=1}^{n} \frac{c_{i}}{10^{i}} − \frac{1}{10^{m}} + \frac{1}{10^{m}}

which implies that

lim_{n→∞} ∑_{i=m+1}^{n} \frac{c_{i}}{10^{i}} = \frac{1}{10^{m}} .

Now we know that c_{i} cannot be equal to 9 for every i ≥ m otherwise it would not be a decimal expansion. So we know there exists k ≥ m such that c_{i} ≤ 9 for i ≠ k and c_{k} ≤ 8. Then

lim_{n→∞} ∑_{i=m+1}^{n} \frac{c_{i}}{10^{i}} ≤ lim_{n→∞} ∑_{i=m+1}^{n} \frac{9}{10^{i}} + \frac{8 − 9}{10^{k}}
≤ lim_{n→∞} \frac{1}{10^{m}} + \frac{8 − 9}{10^{k}}
< lim_{n→∞} \frac{1}{10^{m}} .

In the first line we replaced each of the b_{i} with a 9 except b_{k} so we adjusted the equation f0r the k^{th} term. In the second line we used problem 4 again.

This contradicts the fact that it must be an equality. Therefore our assumption was wrong and b_{i} = c_{i} for all i ∈ N I .

□

Theorem: All real numbers on the unit interval, (0, 1) ⊂ R I , have unique decimal expansions.

Proof: 1. Given any real number, r, it is the equivalence class of Cauchy sequences of rational numbers. In particular any sequence in the class converges to r. So there exists a sequence of rational numbers q_{i} converging to r. Since r < 1, eventually the q_{i} < 1 and since r > 0 eventually the q_{i} > 0. So we can cut off the beginning of the sequence of q_{i} and saythat r is the limit of a Cauchy sequence of rational numbers between 0 and 1.

2. Each q_{n} has a decimal expansion using long division:

q_{n} = .a_{n,1}a_{n,2}a_{n,3}.... = ∑_{i=1}^{∞} \frac{a_{n,i}}{10^{i}} .

3. Since q_{n} → r by the definition of limit we know that for all ε > 0 including ε = 1/10^{m} there exists N_{m} such that |q_{n} − r| < 1/10^{m} for all n ≥ N_{m}. Notice also, from Problem 4, that

|q_{n} − ∑_{i=1}^{m} \frac{a_{n,i}}{10^{i}} | ≤ \frac{1}{10^{m}}

as well, so

|r − ∑_{i=1}^{m} \frac{a_{n,i}}{10^{i}} | ≤ \frac{2}{10^{m}} ∀n ≥ N_{m}.

So we have some sums that converge to r but we need a decimal expansion. 4. Using the last equation twice and the traingle inequality, we have

| ∑_{i=1}^{m} \frac{a_{n,i}}{10^{i}} − ∑_{i=1}^{m} \frac{a_{k,i}}{10^{i}} | ≤ \frac{4}{10^{m}} ∀n, k ≥ N_{m}.

Using the same ideas as in the uniqueness proof, if these two sums are so close the terms must match. That is, a_{n,i} = a_{k,i} for i < m and ∀n, k ≥ N_{m}.. PROBLEM 6: Prove this step.

5. Let a_{i} = a_{N_{i+1},i}. So a_{i} = a_{n,i} ∀n, k ≥ N_{i+1}. We claim that

lim_{n→∞} ∑_{i=1}^{n} \frac{a_{i}}{10^{i}} = r.

In step 3 we proved that for all m ∈ N I there exists N_{m} such that

|r − ∑_{i=1}^{m} \frac{a_{n,i}}{10^{i}} | ≤ \frac{2}{10^{m}} ∀n ≥ N_{m}

If we take n ≥ max{N_{1}, N_{2}, ...N_{m}, N_{m+1}} then we can replace the a_{n,i} with a_{i} and

|r − ∑_{i=1}^{m} \frac{a_{i}}{10^{i}} | ≤ \frac{2}{10^{m}} .

So for all ε > 0 take m large enough that 2/10^{m} < ε and let N_{ε} = m. Then

|r − ∑_{i=1}^{m} \frac{a_{i}}{10^{i}} | < ε ∀n ≥ N_{ε}.

so r = .a_{1}a_{2}a_{3}...... 6. Uniqueness follows from the previous theorem.

□

PROBLEM 6: Prove that any real number, r > 0, can be written as a unique sum n + d where d is a decimal expansion and n ∈ N I . The negative reals can be represented as sums of the form −(n + d) with n and d as above. Finally 0 = 0.00000000....

We will now use these decimal expansions to prove that the unit interval is not countable.

Theorem: The unit interval, [0, 1] ⊂ R I , is not countable.

Proof: 1. Assume on the contrary that the unit interval is countable. So there exists a surjection, s : N I ⟼ [0, 1]. Let s(n) = s_{n}.

2. s_{n} is a real number so it corresponds to a unique decimal expansion.

s_{n} = .a_{n,1}a_{n,2}a_{n,3}.... = ∑_{i=1}^{∞} \frac{a_{n,i}}{10^{i}}

by the previous theorem.

3. Let x = .b_{1}b_{2}b_{3}.... where b_{i} = 1 if a_{i,i} ≠ 1 and b_{i} = 2 if a_{i,i} = 1. The key point is that b_{i} ≠ a_{i,i}. Clearly x is a real number in the unit interval because it has a decimal expansion.

4. Claim: x ≠ s_{k} for any k ∈ N I contradicting the fact that s is a surjection. Proof: Suppose x = s_{k}. Then, by the uniqueness of decimal expansions, b_{i} = a_{k,i} for all i ∈ N I . However, b_{k} ≠ a_{k.k} by step 3. So we have a contradiction, x ≠ s_{k} for all k ∈ N I .

□