Chapter 2 Exercises

2.1 Introduction

2.2 Sets and Functions

Let be a function where S is either the set of rational numbers or the set of real numbers. The range of f is the set of all elements t in T such that t = f(s) for some s in S. Find the range of the following functions:
1. The identity function given by i(x) = x for all x in S.
2. The square function given by for all x in S.
3. The cube function given by for all x in S.
4. The function defined by .
5. The function defined by .
A function is said to be one-to-one (or injective) if f(x) = f(y) only happens when x = y. For each of the functions of the last exercise, either show that the function is one-to-one, or give an example showing that it is not.
Given a function , and a subset U of S, there is a function defined by g(x) = f(x) for all x in U. We say that the function g is the function induced on U by f. For each of the functions of the last exercise which were not one-to-one, find subsets U of S such that the function induces one-to-one functions on the set U.
A function is said to be onto or surjective if the range of f is the whole range space T. For each of the functions in the first problem, determine whether or not the function is onto.
A function which is both one-to-one and onto defines a function by g(y) = x if and only if f(x) = y. So, if the graph of the function contains (x, y), the graph of the function g contains (y, x).
1. For each of the functions in the first problem which are one-to-one and onto, determine the inverse function.
2. Each of the induced one-to-one functions defined in the third exercise can be considered to be functions mapping onto their range. Find the inverse functions.
A function where S and T are subsets of the set of real numbers is said to be increasing if f(x) < f(y) for all x and y in S with x < y. It is said to be decreasing if f(x) > f(y) for all x and y in S with x < y.
1. For each of the functions in the first exercise, determine whether the function is increasing, decreasing, or neither.
2. Do the same for each of the induced functions in the third exercise.
3. For each of the functions in the first exercise that are neither increasing nor decreasing, determine subsets U on which the induced function is increasing or decreasing.

2.3 Fields

Give complete proofs of all the assertions of Proposition 3.
Re-examine the rules in Chapter 1, section 1.1, 1.2, and 1.3. Identify any results there which you cannot prove for any field F.
Let n be a positive integer. We say that two integers a and b are congruent modulo n if a - b is evenly divisible by n; this is written .
1. Show that congruence modulo n satisfies the common properties of equality:
  1. (reflexivity)
  2. If , then (symmetry)
  3. If and , then (transitivity)
2. Show that congruence modulo n is compatible with addition and multiplication, i.e.
  1. If , then for every integer c, one has .
  2. If , then for every integer c, one has .
  3. If and a + c equiv a + c text{ (mod n)} a equiv b text{ (mod n)} c equiv d text{ (mod n)} then for every integer c, one has .
3. Congruence modulo n partitions the set of integers into n subsets, such that any two numbers in the same subset are congruent modulo. In particular, the numbers 0, 1, ..., n - 1 are all in different ones of these subsets. The subsets are called congruence classes modulo n. The above properties of compatibility of with addition and multiplication mean that we can define addition on the congruence classes by simply doing the operation on any of the integers in the congruence classes; which integer one chooses in the congruence class does not matter because the result will always be in the same congruence class. Verify that all the field axions except for the existence of inverses holds for the the set of congruence classes modulo n.
4. Show that if p is prime, then for any integer a, the product of a with any two different non-zero congruence classes modulo p cannot give the same congruence class. So, if we multiply a times all the the non-zero congruence classes, we get all the non-zero congruence classes back. In particular, one of these must be the congruence class containing 1. So, if p is a prime, then the congruence classes modulo p is a field.

2.4 Ordered Fields

Show that if p is a prime, then even though the congruence classes modulo p form a field, there is no way that it can be made into an ordered field.

2.5 The Natural Numbers and Induction

The factorial function is the product of all positive integers from 1 to n, i.e. . When n = 0, one defines 0! = 1. Give an inductive definition of assuming that you have not yet defined the product of n numbers.
For every pair of non-negative integers n and k with , the binomial coefficient is defined to be . Use induction to prove the identity:

This identity is the basis of Pascal 's Triangle.
The binomial theorem gives a formula for expanding any positive integer power of a binomial. Prove this theorem:
Binomial Theorem: Let n be a non-negative integer and a and b be real numbers. Then
Prove the following formulas by induction
Although it is easy enough to verify by induction that each of the previous formulas hold, it is not so obvious how one came up with the formula to verify in the first place. This exercise will give you an idea of how to do it.
1. If f(x) is a non-zero polynomial of degree d, show that is a polynomial of degree d - 1. (For the purposes of this result, it is convenient to define the degree of the zero polynomial to be -1.)
2. If f(x) = g(x) + h(x), show that .
3. Use the binomial theorem to calculate .
4. Suppose that for all , one knows a polynomial such that . The last problem gave us for i = 0, 1, 2, 3, and 4. Combine your work on this problem in order to show you how to calculate .
5. Test out your method by using your result to find a formula for .
Determine the flaw in the arguments:
1. Theorem: Let n be a natural number. Any set of at most n elements numbers contains at most one element.
  Corollary: There are no finite sets with more than one element.
  Proof of Theorem: Suppose the theorem is false. Let n be the smallest natural number for which it is false. Clearly since the theorem is true for n = 1. Let S be a set with no more than n elements for which the assertion is false. Since n is the smallest natural number for which the assertion is false, it is true for numbers less than n. So the set S must have exactly n elements. Let the elements of S be . Let be the set containing every element of S except for ; so its elements are
  
  Since each has less elements than S, the assertion must be true of . But then we have
  
  But since this is true for all choices of i, we have with a different choice, say j
  
  Since each of these leaves out only one of the , we see that the two sets of equalities together show that all the are equal. So, all the are all equal. But then the assertion is true of S, contradicting the choice of S.
2. Define for numbers a and b:
  
  Theorem: If a and b are two natural numbers with max(a, b) = n, then a = b.
  Proof: Prove the assertion by induction on n. The assertion for n = 1 is clearly true. Assume that the assertion is true for n and try to prove the assertion for n + 1. Let a and b be any two natural numbers such that max(a, b) = n + 1. Then c = a - 1 and d = b - 1 satisfy max(c, d) = n. But the assertion for n then implies that c = d. But then a = c + 1 = d + 1 = b. So, the assertion is proved for n + 1. By induction, the result is true for all natural numbers n.
  Corollary: Any two natural numbers are equal.

2.6 The Fundamental Theorem of Arithmetic

Let a, b, and c be natural numbers. Prove that if a and b are relatively prime and a divides bc, then a divides c.
Prove that the least common multiple of two natural numbers a and b is .
Prove that, if a natural number n is not divisible by any prime number less than or equal to , then n is a prime.
Here is another proof of Euclid's Theorem that there are infinitely many primes. The numbers for are called Fermat numbers. He stated that they were all prime, but that has since been proved false -- Euler was the first to factor . The Fermat numbers are important because Gauss proved that a regular n-gon can be constructed by straightedge and compass only if and only if n is of the form where p is either 4 or a prime of the form . The known Fermat primes are 3, 5, 17, 257, and 65537. In 1732, Euler found the factorization . In the intervening centuries, for k = 6,7,8,9,10,11,12,13,14,15,16,18,19,23,36,38,39,55,63, and 73 have been shown to be composite; no Fermat numbers beyond those originally known to be prime have been shown to be prime. In case you are interested, -- if you don't think this is a large number, calculate the number of truckloads of paper that would be required to write it out as a base 10 numeral.
1. Show by induction that
2. Use the last factorization to prove that evenly divides for all k > 0.
3. Prove that and are relatively prime for all k > 0.
4. Explain why this implies that Euclid's Theorem is true.
Pythagorean Triples: From the most ancient times, it has been known that a triangle with sides of length 3, 4, and 5 is a right triangle. Almost equally ancient is the knowledge that a triangle with sides of length 5, 12, and 13 is a right triangle. Of course, both of these are consequences of the converse of the Pythagorean Theorem and the computations

It is natural to ask if there are other right triangles whose sides have natural number lengths. This means, we want to solve

where a, b, and c are required to be natural numbers. Given a solution, (a, b, c) and any natural number r, it is trivial to verify that (ar, br, cr) is also a solution; also, if a and b have a common factor f, then (a/f, b/f, c/f) is also a solution. This makes it reasonable to define a solution (a, b, c) to be primitive if a and b are relatively prime. Then our problem is to find all primitive solutions.
1. Letting x = a/c and y = b/c, we see that (x, y) is a point on the unit circle with rational number coordinates. In the section on solving systems of simultaneous equations, one obtained a parametrization of all solutions of this equation. Verify that if one allows the parameter t to take on only rational solutions, then one obtains a parameterization of all the solutions which are rational numbers.
2. Determine conditions on t so that one has a parametrization of all positive rational solutions.
3. Let t = u/v where u and v are relatively prime natural numbers and v > u. Then substitute these into the parametrization to obtain
  
  Now, it is tempting, but not valid to conclude that the numerators and denominators on each side are equal. However, one can conclude that there is a positive rational number r such that
  
  Explain why this is the case.
4. Since r is a positive rational number, it can be written as r = s/t where s and t are relatively prime natural numbers. Assume now that (a, b, c) is a primitive solution and a is odd.
  1. Show that t has no odd prime factor.
  2. Show that v and u cannot both be odd.
  3. Show that t is not even. So, t = 1 and r = s is a natural number.
  4. Show that s = 1.
5. One has shown that every primitive solution (a, b, c) with a odd can be expressed in the form
  
  where u and v are relatively prime natural numbers with v > u and exactly one of u and v is even. Now verify that every (a, b, c) of this form is a primitive solution with a odd.
6. Having completely solved this equation, it would be natural to ask for non-zero integer solutions of the equation
  
  where n is a positive integer larger than 2. The assertion that this equation has no solutions is called Fermat's Last Theorem. Although Fermat provided no proof of the assertion, one finds the following marginal note in his copy of Diophantus's Arithmetica:
  I have discovered a truly remarkable proof which this margin is too small to contain.
  This challenge has generated some of the most beautiful mathematics of the last three centuries, whole branches of mathematics have been created by some of the world's best mathematicians to address the question of whether or not Fermat's Last Theorem is true or false. This body of mathematics is vastly more important than the actual resolution of the original assertion. However, the theorem was finally proved in 1994 by Wiles.
Recall the equation which came up in the problem of bisecting the area of a trapezoid. Using the last problem as a model, determine all the natural number solutions of this equation.
The proofs of Corollaries 3 and 5 were based on the Euclidean Algorithm. Let's see if we can't derive similar results without the Euclidean Algorithm.
1. Let a and b be relatively prime integers. Show that the numbers all lie in distinct congruence classes modulo b. Explain why this means that ax + by = 1 has integer solutions.
2. Let a and b be arbitrary non-zero integers. Show that the equation ax + by = gcd(a, b) has integer solutions.
3. Show that if and are solutions of ax + by = gcd(a, b), then and for some integer r. Conversely, if is a solution and r is an integer, then as defined here are also solutions.
Let m and n be relatively prime natural numbers.
1. Show that every sufficiently large integer q is of the form q = mx + ny where x and y are non-negative intgers.
2. Find the greatest integer which cannot be so represented.
Let p be a prime and a be an integer not a multiple of p.
1. Prove that mod p.
2. Fermat's Theorem: Show that for any prime p and any integer a which is not a multiple of p, one has mod p.
3. Euler's Theorem: Show that for any non-zero integer n and and any a relatively prime to n, one has mod n where is the number of integers which are relatively prime to n.

2.7 Real Numbers

2.7.1 Infinite Decimals

Show that in an Archimedean ordered field, if an infinite decimal has a limit, then the limit is unique.
Show that if F is an Archimedean ordered field in which every infinite decimal in which every digit is even has a limit in F, then F is a field of real numbers.
Let F be the an ordered field, for example, you could take F to be the field of rational numbers or the field of real numbers. Recall that F(x) is the field of rational functions with coefficients in F. Its elements are elements of the form where p and q are polynomials and q is non-zero. The leading coefficient of the rational function is the quotient of the leading coefficient of p and the leading coefficient of q (or zero if p is zero). One can define an order on F(x) by

if the leading coefficient of the first rational function is less than the leading coefficient of the second rational function.
1. Show that this definition makes F(x) into an ordered field.
2. Show that F(x) is NOT Archimedean.
3. Do infinite decimals in F(x) have unique limits?

2.7.2 Decimal Expansions

For every real number a and positive integer n, determine the number of real roots of a.
Let a be a positive real number. Make a reasonable definition of where p and q are integers. Does this quantity always exist? If the function f defined by an increasing function of rational numbers?

2.7.3 Limits of Sequences

Show that the infinite sum converges.
The harmonic series is the . The harmonic series does not converge. The idea of the proof is that the first term is clearly at least 1/2 as is the sum of the next 2 terms, the sum of the succeeding 4 terms, and the sum of the next 8 terms. Verify these assertions and see if you can show that the sum is eventually larger than any number.
Let F be an Archimedean ordered field in which every increasing bounded sequence of numbers converges to an element of F. Show that F is a field of real numbers.
Given any natural number b > 1, one can define a notion of infinite decimals to the base b. Basically, one restricts the digits to lie between 0 and b - 1 and interprets them using powers of b rather than powers of 10. Show that if infinite decimals to the base b converge in an ordered field F, then so do infinite decimals to the base 10 and conversely. In particular, we could have defined real numbers using any other base than 10 and the theory would be equivalent.
Recall that if S is a subset of a ordered field F and b is in F, then b is an upper bound of S if for all s in S. b is said to be a least upper bound of S if for every upper bound c of S. An ordered field is said to satisfy the least upper bound axiom if every subset S of F with at least one upper bound in F has a least upper bound in F.
1. Show that if F is an Archimedean ordered field which satisfies the least uppper bound axiom, then F is a field of real numbers.
2. Show that if F is a field of real numbers, then it satisfies the least upper bound axiom.
3. Make up a reasonable definitions for lower bound, greatest lower bound, and the greatest lower bound axiom. Prove results analogous to the last two parts of this exercise for these notions.
Let S be a subset of an ordered field F and b be an element of F. We say that b is a limit point of S if for any there is an s in S such that . A set S in F is said to be bounded if there is a natural number M > 0 such that |s| < M for all s in S.
1. Show that if F is an Archimedean ordered field in which every infinite bounded subset of F has a limit point in F, then F is a field of real numbers.
2. Show that if F is a field of real numbers, then every infinite bounded subset S of F has a limit point in F.

2.8 Complex Numbers

2.8.1 The Field of Complex Numbers

Show that the complex numbers form a field.
Prove Proposition 15.
Most of the arguments in this section work fine for other fields. Does the argument for Proposition 14 work when the field of real numbers is replaced by the field of rational numbers? What about Proposition 15?
Does the proof of Proposition 14 work when the field of real numbers is replaced by the field of complex numbers? If not, where does it break down?

2.8.2 Geometric Interpretation of Complex Operations

Show for every positive integer n that

The same sum with the sine function replaced with the cosine function is equal to zero.
The method used to calculate in Chapter 1 can also be used to calculate the area of a circle. Do this.
Use the same method to calculate the lateral surface area of a right circular cone. The formula is where r is the radius of the base and s is the distance from the vertex to any point on the edge of the base. The quantity s is called the slant height.
Use the result of the last exercise to show that the area of the frustrum of a right circular cone is where r is the average of the radius of the top and bottom of the frustrum and s is the slant height. If the frustrum is obtained by cutting the top off a cone, the slant height is the distance along a line from the vertex to the base, from the point of intersection with the top of the frustrum to the point of intersection with the base.
To calculate the surface area of a sphere, approximate a circle by taking a regular inscribed 2n-gon and spinning it about an axis. The figure consists of several frustra of cones stacked on each other. You calculate the total lateral area of these figures and then take the limit to find the area of the sphere. The result is Archimedes famous result that where r is the radius of the sphere.
Let . So, , , and 1 are the cube roots of unity. Let a, b, and c be complex numbers, which we also think of as being points in the complex plane. As such, the three numbers determine a triangle.
1. Suppose the three points a, b, and c are the vertices of an equilateral triangle traversed in counterclockwise order. Show that .
2. Conversely, if , then the three points a, b, and c are the vertices of an equilateral triangle traversed in counterclockwise order.
3. How does the result change if you traverse the points in clockwise order?
In the last section, for every positive real number a, one defined a function with domain the rational numbers . Can you extend this in a natural way to function defined for all real numbers?

2.8.3 Applications

2.8.3.1 Rotations and Translations

Already in Chapter 1, one noted that all first degree polynomials define lines. This exercise will classify all curves defined by second degree polynomials.
1. The equation for fixed values of s and p has either 0, 1, or 2 solutions. If and are solutions, then and , i.e. the problem is equivalent to finding numbers given their sum and product. To get a good graphical view of how the number of solutions varies with s and p, we will fix only one of the two parameters and graph the other as a function of x.
  1. Show that if s is fixed, then writing p as a function of x, gives the graph of a parabola which opens downward. In particular, for a given sum, one cannot find a pair of with a given product p unless p is sufficiently small. Find the coordinates of the vertex of the parabola and interpret it algebraically.
  2. Fix p and express s as a function of x. Graph the function and interpet the graph in terms similar to that of the last part. Find a rotation which shows that the graph is actually the graph of a conic section. What kind of conic section is it?
2. Show that by rotating through an appropriate angle, the general second degree polynomial equation:
  
  can be converted into a second degree polynomial in which the coefficient of xy is zero.
3. Show that by an appropriate translation, any second degree polynomial in which the coefficient of xy is zero can be converted into one of the form
4. Show that after an appropriate rotation and translation, any second degree polynomial equation can be converted into one of the following:
  1. An ellipse, hyperbola, or parabola
  2. Either one or two lines
  3. The empty set