Problems

1. True or False

   Which of the following are true?

   1. (∀x ∈ ℝ)(x² + x + 1 > 0)
   2. (∀x ∈ ℝ)[x² > 0 ∨ x² < 0 ]
   3. (∀x ∈ ℤ)(x² > x)
   4. (∀x ∈ ℝ)(∃y ∈ ℝ)(y = sin x)
   5. (∀x ∈ ℝ)(∃y ∈ ℝ)(y = tan x)
   6. (∃x ∈ ℝ)(∃y ∈ ℝ)(y = sin x)
   7. (∃x, y ∈ ℕ)(∃n > 2)(xⁿ + yⁿ = 1)
   8. (∃x ∈ ℝ)(∀a, b, c ∈ ℝ)(ax² + bx + c = 0)
   9. (∃x ∈ ℂ)(∀a, b, c ∈ ℝ)(ax² + bx + c = 0)
   10. 
   11. (∀ε > 0)(∃δ > 0)(|x − 2| < δ ⇒ |x² − 4| < ε)
2. Predicate Logic Form

   Write the following theorems in the language of predicate logic.

   1. A number is divisible by 4 if and only if its last two digits are divisible by four.
   2. A natural number is divisible by 2ⁿ if and only if its last n digits are divisible by 2ⁿ.
   3. There exists irrational numbers a, b such that a^b is rational.
   4. 
   5. For positive real numbers a, b, we have .
   6. If a, b are integers and b ≠ 0, then there exists unique integers q, r such that a = qb + r where 0 ≤ r < |b|.
   7. If p is a prime number that does not divide an integer a, then p divides a^p − a.
   8. The square of any natural number has each of its prime factor occurring an even number of times in its prime factorization.
   9. All prime numbers p greater than 2 are of the form either p = 2n + 1 or p = 2n + 3 for some natural number n.
   10. Every even number greater than 4 can be expressed as the sum of two prime numbers.
   11. Euler's Conjecture: There are no natural numbers a, b, c, d that satisfy a⁴ + b⁴ + c⁴ = d⁴.
3. Negation

   Negate the following propositions and tell whether the original statement or the negation is true. Let x and y be real variables.

   1. (∃x)(∀y)(xy < 1)
   2. (∀x)(∀y)(∃z)(xyz = 1)
   3. (∀x)(∀y)(∀z)(∃w)(x² + y² + z² + w² = 0)
   4. ∼(∃x)(∀y)(x < y)
   5. (∀x)(∃y)(xy < 1 ∧ xy > 1)
   6. (∃x)(∃y)(xy = 0 ∨ xy ≠ 0)
4. Counterexamples

   All the following statements are wrong. Prove them wrong by finding a counterexample.⁴

   1. All mathematicians make tons of money writing textbooks.
   2. For all positive integers n, n² + n + 41 is prime.⁵
   3. Every continuous function defined on the interval (0,1) has a maximum and minimum value.
   4. Every continuous function is differentiable.
   5. If the terms of an infinite series approach zero, then the series converges.
   6. The perimeter of a rectangle can never be an odd integer.
   7. (∀x ∈ ℝ)(∃y ∈ ℝ)(x = y²)
   8. Every even natural number is the sum of two primes.
   9. If m and n are positive integers such that m divides n² − 1, then m divides n − 1 or m divides n + 1.
   10. If {f_n : n = 1, 2, …} is a sequence of continuous functions defined on (0, 1) that converge to a function f, then f is continuous.
5. If and Only If Theorems

   State each of the following theorems in the language of predicate logic. Take the function f as a real‐valued function of a real variable.

   1. A function f is even if and only if for every real number x we have f(x) = f(−x).
   2. A function f is odd if and only if for every real number x we have f(x) = − f(−x).
   3. A function f is periodic if and only if there exists a real number p such that f(x) = f(x + p) for all real numbers x.
   4. A function is increasing if and only if for every real numbers x and y we have x ≤ y ⇒ f(x) ≤ f(y).
   5. A function f is continuous at x₀ if and only if for any ε > 0 there exists a δ > 0 such that |x − x₀| < δ ⇒ |f(x) − f(x₀)| < ε.
   6. A function f is uniformly continuous on a set E if and only if for any ε > 0 there exists a δ > 0 such that |f(x) − f(y)| < ε for any x, y in E that satisfy |x − y| < δ.
6. Hard or Easy?

   Prove that if there is a real number a ∈ ℝ that satisfies a³ + a + 1 = 0, then there is a real number b ∈ ℝ that satisfies b³ + b − 1 = 0. This problem is either very hard or very easy, depending how it is approached. It is your job to determine which is true.

7. Predicate Logic in Analysis

   The so‐called ε − δ proofs in analysis were originated by the German mathematician Karl Weierstrass in the 1800s and involve inequalities and universal and existential quantifiers. They often start with (∀ε > 0) followed by (∃δ > 0). The idea is that your adversary can pick ε > 0 as small as one pleases, but you have the advantage of picking the δ second. Of course, your choice of δ will most likely depend on ε.

   1. Show that for every real number ε > 0 there exists a real number δ > 0 such that 2δ < ε. In the language of predicate logic, prove (∀ε > 0)(∃δ > 0)(2δ < ε).
   2. For every real number ε > 0, there exists an integer N > 0 such that for n > N one has 1/n < ε. In the language of predicate logic, prove (∀ε > 0)(∃N > 0)(∀n > N)(1/n < ε).
   3. Show that for every real number ε > 0, there exists a real number δ > 0 such that if |x| < δ then x² < ε. In the language of predicate logic, prove (∀ε > 0)(∃δ > 0)(∀x ∈ ℝ)(|x| < δ ⇒ x² < ε)
   4. Show that for every positive integer M there is a positive integer N such that .

   In the language of predicate logic, this says

   
8. Doing Mathematics

   Textbooks sometimes lead one to believe that theorems appear out of thin air for mathematicians to prove. If this were so, mathematics would be a purely deductive science, but in fact “doing mathematics” and mathematical research is as much an inductive science as deductive. Table 1.35 below lists the number of divisors τ(n) of n for the first 24 natural numbers. Looking at the table, can you think of any question to ask about the number of divisors of a natural number? A couple of candidates are

   • Theorem 1: τ(n) is odd if and only if n is a square, like 4, 9, 16, …
   • Theorem 2: If m and n have no common factor, then τ(m)τ(n) = τ(mn).

   n	τ(n)	n	τ(n)
   1	1	13	2
   2	2	14	4
   3	2	15	4
   4	3	16	5
   5	2	17	2
   6	4	18	6
   7	2	19	2
   8	4	20	6
   9	3	21	4
   10	4	22	4
   11	2	23	2
   12	6	24	8

9. Casting Out 9s

   Show that a number d₁d₂d₃ is a multiple of 9 if and only if d₁ + d₂ + d₃ is a multiple of 9.

10. Internet Research

    There is a wealth of information related to topics introduced in this section just waiting for curious minds. Try aiming your search engine toward philosophy of intuitionism, Gottlob Frege, casting out nines, proofs in predicate logic, and proofs by pictures.