MAST20026 Real Analysis

1. Proof and Mathematical Logic

Logic and Notation

1. Write the following statements as a conditional statement in the form. p ⇒ q.

(a) “A monkey is happy only if he is eating a banana.”

(b) “A snake will not bite you provided you don’t step on its tail.”

(c) “A donkey laughs whenever he sees a mule.”

(d) “Happiness is a necessary condition for Wealth.”

(e) “Happiness is a sufficient condition for Wealth.”

2. Indicate whether each statement is True or False.

(a) Jupiter is a planet and Neptune is a moon.

(b) Jupiter is a planet or Neptune is a moon.

(c) Elvis was a woman or Cleopatra was a man.

(d) TikTok is a social media app, or Lord of the Rings was written by J.R.R. Tolkien.

(e) If the capital of Egypt is Cairo, then apples can be used to make cider.

(f) If Napolean was born in Zimbabwe, then the eigenstates of the quantum harmonic oscillator are proportional to Hermite polynomials.

(g) If the dodo is extinct, then pigs can fly!

(h) It is not the case that if Luke Skywalker was a Jedi, then his father was not Darth Vader.

3. Translate the following into mathematical notation.

(a) Six is not prime or eleven is not prime.

(b) The square of 10 is 50 and the cube of 5 is 12.

(c) If 7 is an integer then 6 is not an integer.

(d) If both 2 and 5 are prime then 2 × 5 is not prime.

Which of these are true, which are false, and which are neither?

4. Construct truth tables for the following statements.

(a) (p ∧ q) ∨ (∼ p ∧ ∼ q)

(b) [∼ q ∧ (p ⇒ q)] ⇒ ∼ p

(c) [(p ∨ q) ∧ r] ⇒ (p ∧ r)

Which of the statements above is logically equivalent to a connective we have studied? Which of the statements above is a tautology?

5. Translate the following into mathematical notation

(a) All rational numbers are larger than 6.

(b) There is a real number solution to x 2 + 3x − 7 = 0.

(c) There is a natural number whose cube is 8.

Which of these are true, which are false, and which are neither?

6. Translate the following mathematical statements into English.

(a) (∀a ∈ Q) a + 0 = a

(b) (∀x ∈ R) x2 > 1

7. The following two statements look similar, but say very different things. Which is true, and which is false?

(a) (∃b ∈ Z) [(∀a ∈ Z) a + b = 0]

(b) (∀a ∈ Z) [(∃b ∈ Z) a + b = 0]

8. Find the negation of

(a) (∀x ∈ R) x 2 = 10

(b) (∃y ∈ N) y < 0

(c) (∃a ∈ N) [(∀x ∈ R) ax = 4]

(d) (∀y ∈ Q) [(∃x ∈ R) x/y = 30]

9. Verify the following:

(a) p ∧ q ≡ q ∧ p

(b) ∼ (p =⇒ q) ≡ (p ∧ ∼ q)

What can you conclude about (i) p ∧ q ⇐⇒ q ∧ p and (ii) ∼ (p =⇒ q) ⇐⇒ (p ∧ ∼ q)?

Counter Examples

10. Use a counterexample to show that the following statements are false.

(a) If the product of two integers is even then both of those integers are even.

(b) For all real numbers, if x 2 = y 2 then x = y.

(c) Let a ∈ Z. If a divided by 7 gives remainder of 4, then 5a divided by 7 gives remainder of 4.

Direct Proofs

11. Prove the following results for the integers.

(a) The product of an even integer with an odd integer is even.

(b) The sum of an even integer and an odd integer is odd.

(c) The cube of an odd integer is odd.

(d) Let a ∈ Z. If a divided by 7 gives remainder of 4, then 15a divided by 7 gives remainder of 4.

(e) If k is odd, then k 2 − 1 is divisible by 4.

Domains

12. For each equation below, list the sets of numbers (N, Z, Q, R) in which there exists a solution.

(a) x 2 − 8 = 0

(b) x + 8 = 0

(c) 4x = 8

(d) x 2 + 8 = 0

(e) 3x + 8 = 0

(f) 0x = 8

Contrapositive

13. Prove the following theorems using the contrapositive.

(a) Let n ∈ Z. Prove that if n 4 is even, then n is even.

(b) Let n ∈ Z. Prove that if n 3 is odd, then n is odd.

(c) For all m, n ∈ Z, if mn is odd then m and n are odd.

Proof by Contradiction

14. Consider the following theorem:

Let p, q ∈ Z with p, q > 0. If pq = 1 then p = q = 1.

(a) Begin a proof by contradiction by assuming that at least one of p and q is not equal to 1.

(b) Starting with pq = 1, arrive at a contradiction.

15. Consider the following equation:

x2 − n2y2 = 1

where n ∈ N is fixed.

Show that it has no positive integer solutions for x, y using a proof by contradiction in the following steps.

(a) Begin by assuming that there exists a positive integer solution.

(b) Factorized the left-hand side, and conclude that both factors are integers.

(c) Using the result of Question 14, conclude both factors equal 1.

(d) Attempt to solve the two equations you have just developed and arrive at a contradiction.

16. The Adventures of π-casso, the Mathematical Artist

Your friend π-casso has invited you over to see their new artwork. Before they unveil it, they tell you that it is a 3 × 3 grid of squares, each painted either red or blue. They go on to say that they used a special rule to paint it:

Every square has either 2 or 4 blue neighbours.

(a) Suppose that they tell you the centre square is red. Prove that the remaining squares are all blue using a contradiction argument. Hint: You will need to consider 2 cases.

(b) Suppose that they tell you the centre square is blue. Prove that at least one of the remaining squares is red using a contradiction argument.

(c) How many possible paintings are there that satisfy the special rule?

(d) Extension. Consider the paintings of 4 × 4 grids that use the same special rule. What are the possibilities?

More Proofs

17. Prove the following theorems by dividing into two or more cases.

(a) Let n ∈ Z. Prove that if n is not divisible by 3, then n 2 is not divisible by 3.

(b) For all m, n ∈ Z, if m and n are either both odd or both even then m + n is even.

Irrational numbers

18. Prove that the following are irrational:

(a) √3

(b) √15 + √5

(c) log2 7

Mathematical Induction

19. Prove by induction that each formula is true for every integer n ≥ 1.

Begin by rewriting these equations using summation notation.

20. Prove by induction that the following statements are true for every natural number n:

(a) 3 is a factor of n3 − n + 3;

(b) 9 is a factor of 10n+1 + 3 · 10n + 5;

(c) 4 is a factor of 5n − 1;

(d) x − y is a factor of xn − yn;

(e) 72n − 48n − 1 is divisible by 2304 (for all n ≥ 1).

21. Write the following inequalities in summation notation and then prove them for all n ∈ N, using summation notation throughout your proof. If you find this difficult, first try the proofs using more informal notation.

22. In each case try to find n0 ∈ N such that the inequality appears to hold true for n ≥ n0. If you think you have found such an n0, give a proof by induction that the inequality holds true for n ≥ n0. If you think that no such n0 exists, try to prove that it cannot exist.

(a) 1 + 2n ≤ 3n

(b) n! > 2 n

(c) n(n + 1) ≥ (2n − 1)2

(d) n! > 2n 3

23. If A is a square matrix and 1 is the identity matrix (of the same size), we define An by

A0 = 1 and An+1 = AnA for n = 0, 1, 2, . . . ,

which is a more precise and careful way of saying that

Prove by mathematical induction that for all natural numbers n

2. Set Theory

Sets

For questions 1 to 3, let A = {1, 2, 3, 4}, B = {1, 3, 5, 7} and C = {2, 3}.

1. Find the following sets:

(a) A ∪ B

(b) A ∩ B

(c) A ∪ C

(d) A ∩ C

(e) A ∪ B ∪ C

(f) A ∩ B ∩ C

2. Find the following sets:

(a) B × C

(b) A × {}

3. Which of the following statements are true?

(a) 3 ⊆ B

(b) {} ⊆ A

(c) 7 ∈ B ∪ C

(d) C ⊆ B

(e) C = B ∪ C

(f) C ∈ A

(g) (∀a ∈ A) a ≤ 4

(h) (∀b ∈ B)[(∃c ∈ C) b − c ≥ 0]

4. Let A, B and C be sets. Let U = A ∪ B ∪ C. Prove the following statements.

(Please write your proof using the definitions f =, ⊆, ∪, ∩, etc. from the lectures on set theory. Do not use set algebra.)

(a) A ⊆ [(A ∩ B) ∪ (A ∩ (U\B))]

(b) A ⊆ B =⇒ (C ∩ A) ⊆ (C ∩ B)

(c) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

(d) A ⊆ B if and only if A ∪ B ⊆ B

5. The Cantor Set

We are going to construct an unusual set made famous by Georg Cantor.

We begin with the set C0 = [0, 1]

(a) Draw this set on the real number line. What is its length?

(b) Construct C1 by removing the middle third of C0 as an open interval. In other words, remove (3/1, 3/2). Write C1 as the union of two intervals. Draw C1 on the real line, and determine its length.

(c) Construct C2 by removing the middle third of each segment in C1. C2 should have 4 segments. Write C2 as a union of 4 intervals. Draw it on the real line, and determine its length.

(d) By now you probably understand the pattern. Draw a few more: C3, C4, C5 etc.

(e) The Cantor Set C is what remains after you repeat this process ad infinitum. Find several points that are in the set. Find several points that aren’t in the set.

(f) The Cantor Set is a simple example of a fractal. It exhibits self-similairty: meaning if you zoom in on sections, you see the overal shape repeating itself. Type “fractal cauliflower” into Google to see another example of a fractal.

Supremum and Infimum

6. Find the supremum and infinum of the set S (where S ⊆ R), if they exist, and if they do, state whether the supremum or infimum is an element of S. You do not need to prove your answer is correct.

(a) S = {x | x2 ≤ 9}

(b) S = {x | |x − 2| < 3}

(c) S = {x | |2x + 1| < 5}

(d) S = {x | |x − 2| < 3 ∧ |x + 1| < 1}

(e) S = {x | |x + 2| ≤ 2 ∨ |x| > 1}

(f) S = {x ∈ Q | x2 ≤ 7}

7. Let S ⊆ R and c ∈ R. Define c + S = {c + x | x ∈ S} and cS = {cx | x ∈ S}. If S is bounded above and below, prove the following:

(a) c + S and cS are both bounded above and below

(b) sup(c + S) = c + sup(S)

(c) sup(cS) = c sup(S) for c ≥ 0

(d) sup(cS) = c inf(S) for c ≤ 0

8. Let A ⊆ R. Prove that the supremum of A is unique if it exists.

Hint: A useful method for showing some quantity is unique is to assume there are two, and prove they must be equal. In this case, assume that A has two suprema, s1 and s2, and show that s1 = s2. If s1 ≤ s2 and s2 ≤ s1, then s1 = s2

Inequalities

This subject will involve heavy use of inequalities. The following exercises will help you practice and become comfortable manipulating them.

Recall the following:

The Triangle Inequality: For all a, b ∈ R we have |a + b| ≤ |a| + |b|.

9. Let a, b, c ∈ R and let a < b. Which of the following statements are always true? Which are sometimes true? Which are never true?

(a) a + 1 < b + 1

(b) a + c < b + c

(c) 5a < 5b

(d) ac < bc

(e) a/1 < b/1

(f) c + a/1 < c/1

(g) c < c + a

(h) −a < −b

10. Express the solutions to the following inequalities as intervals of R.

(a) |1 + 2x| ≤ 4

(b) |x + 2| ≥ 5

(c) |x − 5| < |x + 1|

(d) |x − 2| < 3 ∨ |x + 1| < 1

(e) |x − 2| < 3 ∧ |x + 1| < 1

11. Use the triangle inequality or other properties of inequalities to find a bound for |f| on the stated interval.

12. Prove that ∀a, b ∈ R that |a − b| ≥ ||a| − |b||.

13. Let a, b ∈ R. If 0 <  < min{|a|, |b|} show that

14. Let a, b ≥ 0, p > 1 and q = p/(p − 1). We will prove that

(a) Consider the cases where either a = 0 or b = 0: the inequality is trivially true for these.

(b) Treat a as a real variable and define

Show that f has a minimum at  using calculus techniques.

(c) Find the value of the function at this point, and conclude f(x) ≥ 0.

(d) Finish off the proof.

3. The Real Numbers

Proofs with the Real Number Axioms

1. Let x, y, z ∈ R. Using only the axioms of the real numbers, prove the following obvious results.

(a) If x + z = y + z, then x = y.

(b) 0x = 0

(c) −(−x) = x

(d) If xy = 0, then x = 0 or y = 0.

(e) If x < y and z < 0 then xz > yz.

(f) If x > 0, then 1/x > 0.

Properties of Number Sets

2. What property separates the following sets? In other words, what vital property does one set have that the other doesn’t?

(a) N and Z

(b) Z and Q

(c) Q and R

The Archimedean Principle

3. Give a proof of the following statement

(∀ > 0) [(∃n ∈ N) 1/n < ]

Existence of the square root of 2

4. Throughout the course we have talked about the number √2. However, we have never actually shown that it follows from the Axioms of the Real Numbers that square roots exist. In this question, we will prove that there exists a positive real number α such that α2 = 2.

Throughout this exercise, only use algebraic facts which readily follow from the Axioms of the Real Numbers. Be careful to not assume the existence of square roots.

(a) Let A = {x ∈ R : x2 ≤ 2}. Show A is bounded above in R. That is, select a specific real number β which is an upper bound for A. Then prove β is indeed an upper bound for A in R.

(b) Explain why the supremum α of the set A exists in R.

(c) Suppose that α2 < 2.

(i) Use the Archimedean Principle to show that there exists n ∈ N + such that (α + 1/n)2 < 2.

(ii) Using Part (c)(i), show that α is not an upper bound of A. (This of course contradicts Part (b)!)

(d) Suppose that α2 > 2.

(i) Use the Archimedean Principle to show that there exists n ∈ N + such that (α − 1/n)2 > 2.

(ii) Using Part (d)(i), show that α is not the least upper bound of A. (This again contradicts Part (b)!)

(e) Explain why α > 0 and α2 = 2.