1. The sum of two odd integers is even
2. √2 is irrational
3. 1 + 2 + 3 + …+ n = n(n+1)/2
4. 1 + 1 = 2
5. 1 = 0.999…
6. There are infinitely many primes

Proof that the sum of two odd integers is even

Definitions

• An integer is even if it’s two times some integer.
• An integer is odd if it’s two times some integer + 1.

Proof

1. Let x and y be two odd integers.
2. Then, x = 2a + 1, for some integer a.
   • Definition of odd integer
3. And y = 2b + 1, for some integer b.
   • Definition odd integer
4. So x + y = 2a + 1 + 2b + 1.
5. Thus, x + y = 2a + 2b + 2.
   • Rearranging line 4
6. And so x + y = 2(a + b + 1).
   • Factoring line 5
7. Thus x + y = two times some integer (a + b + 1) and is therefore even.
   • Definition of even integer.

Proof that √2 is irrational

Preliminaries

• A rational number is a number that can be expressed as a fraction c/d where c and d are integers and d ≠ 0.
• An integer is even if it’s two times some integer
• An integer is odd if it’s two times some integer + 1
• The square of an odd integer is odd.
  • Suppose m is odd. We want to prove that m² is odd.
  • m = 2c + 1, for some integer c.
    • Definition of odd
  • m² = (2c + 1)(2c + 1)
  • m² = 1 + 4c + 4c²
  • m² = 1 + 2(2c + 2c²)
  • m² = 1 + even number
  • m² is odd.

Proof

• Suppose for a reductio ad absurdum proof that there are integers c and d such that √2 = c/d.
• Let a/b = c/d in lowest terms.
• Thus, √2 = a/b, for some integers a and b.
• Proof that a is even:
  • √2 = a/b
  • 2 = a²/b²
  • a² = 2 b²
  • So a² is even
    • Definition of even
  • So a is even
    • If a were odd then a² would be odd
• Proof that b is even:
  • a² = 2b²
    • from above
  • a = 2k, for some integer k
    • since a is even
  • (2k)² = 2b²
  • 4k² = 2b²
  • 2k² = b²
  • So b² is even
    • Definition of even
  • So b is even
    • If b were odd then b² would be odd
• Since a and b are both even they have a common factor, 2. Therefore, a/b is not in lowest terms, contradicting the assumption above.

Proof that 1 + 2 + 3 + … + n = n(n+1)/2

For Example

• 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
• (10 x 11)/2 = 55

Proof by Mathematical Induction

• Initial Step
  • For n = 1, 1 = 1(1+1)/2 = 1
• Inductive Step
  1. Let n be any positive integer
  2. Assume that 1 + 2 + 3 + … + n−1 = (n−1)n/2
     • The Inductive hypothesis
  3. We want to prove that:
     • 1 + 2 + 3 + … + n = n(n+1)/2
  4. 1 + 2 + 3 + …+ n−1 + n = (n−1)n/2 + n
     • Add n to both sides of the inductive hypothesis
  5. (n−1)n/2 + n = n(n+1)/2
     • The right side of line 4 = the right side of line 3
     • Expand[(n − 1) n/2 + n] = n/2 + n²/2
     • Expand[n (n + 1)/2] = n/2 + n²/2
  6. Therefore, 1 + 2 + 3 + … + n = n(n+1)/2

Proof that 1 + 1 = 2

Axioms

• Recursive Definition of Addition
  • (x)(x + 0 = x)
  • (x)(y)(x + Sy = S(x + y))
• Successor Function
  • Sx = the successor of x
  • So, S0 = 1 and S(S0) = 2

Proof

1. (x)(x + 0 = x)
   • Axiom
2. S0 + 0 = S0
   • Universal Specification on 1
3. (x)(y)(x + Sy = S(x + y))
   • Axiom
4. (y)(S0 + Sy = S(S0 + y))
   • Universal Specification on 3
5. S0 + S0 = S(S0 + 0)
   • Universal Specification on 4
6. S0 + S0 = S(S0)
   • Leibniz Law on 2 and 5
7. S0 = 1
   • Successor Function
8. S(S0) = 2
   • Successor Function
9. 1 + 1 = 2
   • Leibniz Law on 6, 7, 8

Proof that 1 = 0.999…

1. 3 x ⅓  = 1
   • Self-evident
2. ⅓ = 0.333…
   • Decimal expansion of ⅓.
3. 3 x 0.333…  = 1
   • From 1 and 2 by transitivity of equality
4. 3 x 0.333… = 0.999….
   • Self-evident
5. Therefore, 1 = 0.999….
   • From 3 and 4 by transitivity of equality

Proof by Euclid that there are infinitely many primes

Assumed Theorem

• Every integer greater than 1 has at least one prime divisor.
  • For example, 2|2, 3|3, 2|4, 5|5, 2|6, 7|7, 2|8, 3|9, 2|10, 11|11, 2|12, 13|13, 2|14, 3|15.
    • (n|m means n divides m)

Proof

• Suppose, for a reductio ad absurdum proof, that there are only finitely many primes. List them all:
  • p₁, p₂, p₃,…, p_n
    • Prime[Range[25]] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
• Define the number:
  • N = p₁ p₂ p_3… p_n + 1.
    • Times[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] + 1 =
      • 2305567963945518424753102147331756071
• Let p_i be anyone of the primes on the assumed list of all primes.
• Because p_i is one of the factors in the product p₁ p₂ p_3… p_n
  • p_i | p₁ p₂ p_3… p_n (i.e. p_i divides evenly into p₁ p₂ p_3… p_n)
• Therefore, dividing N by p_i leaves a remainder of 1.
  • QuotientRemainder[2305567963945518424753102147331756071, 29] =
    • {79502343584328221543210418873508830, 1}
  • QuotientRemainder[2305567963945518424753102147331756071, 97] =
    • {23768741896345550770650537601358310, 1}
• It’s therefore false that p_i | N.
• Since p_i was any prime on the assumed list of all primes, none of the primes on the list divides N. Since the list is assumed complete, N therefore has no prime divisors. But this contradicts the assumed theorem above that every integer greater than 1 has a prime divisor.
  • FactorInteger[2305567963945518424753102147331756071] =
    • {{2336993, 1}, {13848803, 1}, {71237436024091007473549, 1}}
    • PrimeQ[2336993] = True
• QED