How is Mathematics Constructed?

In this discussion, I will cover prominent proof techniques and clarify how mathematical proofs are structured. Along the way, I will offer examples to illustrate the concepts and highlight the elegance inherent in mathematical reasoning.

When posed with the question of what mathematics encompasses, many pure mathematicians might respond that it revolves around proving theorems or acquiring knowledge. Yet, in my view, mathematics transcends these definitions. If I were to express my philosophical beliefs, I might say:

"Mathematics is a tool for some, an art for others, a universal language that describes nature, an adventurous journey into uncharted territories of natural truths, a shared cultural pursuit, and a relentless quest for truth and pure understanding."

Before diving into the specifics, it is crucial to establish some foundational concepts regarding mathematical truth and how these truths interrelate.

At its core, a mathematical proof relies on established truths, which can be categorized into two types: theorems—statements that have been proven true—and axioms, which are accepted as true without proof.

An axiom can be viewed as a fundamental building block of mathematics, as all other truths are derived from them. This recursive nature of definitions in mathematics is acceptable since ultimately, every theorem is rooted in axioms through a chain of dependencies.

Thus, all mathematical theorems are ultimately built upon axioms. We begin with these axioms and apply logic to derive the first generation of theorems, which in turn enable us to prove subsequent theorems.

I won't delve deeply into the intricate nature of proofs themselves, as this is a complex topic, and interestingly, understanding this complexity is not a prerequisite for proving statements.

Instead, I will equip you with the necessary tools to derive theorems independently.

Before we embark on our journey, we must familiarize ourselves with some nomenclature and assumptions regarding naming conventions. Not all proved statements hold the same significance; some are deemed more critical than others.

In mathematics, we reserve specific terms for important proved statements. A significant result is termed a theorem; a smaller result that aids in proving larger theorems is called a lemma; a result that easily follows from a theorem is known as a corollary; and a statement of some importance that may be referenced later is termed a proposition.

Next, we must revisit some fundamental logic principles.

Logic - The Foundation of Mathematics

Without delving into the complexities of first and second-order logic, I will summarize the logical symbols commonly encountered in mathematical proofs.

A statement, referred to as A, can only be true or false. While fuzzy logic allows for intermediate truth values, we will not explore that concept here.

The negation operator ¬ inverts a statement's truth value; if A is true, ¬A is false, and vice versa. Additionally, we have logical and (denoted as ?) and logical or (denoted as ?), which operate as expected.

Parentheses function in a standard manner. Notably, the implication arrow (=>) signifies "if A then B," indicating that if A is true, then B must also be true. This statement does not assert that A is true; rather, it is only false when A is true and B is false.

To illustrate the implication, consider the following example. Suppose Alice tells her daughter Rachel:

"if it doesn’t rain tomorrow, then we are going out shopping."

Here, A represents "it doesn’t rain tomorrow," and B represents "we are going out shopping." The statement A => B is only false if it does not rain, but they do not go shopping. If it rains, it does not imply that they won’t go shopping; the statement remains true regardless.

Many students initially struggle with these logical concepts as they often conflate social interpretations with strict mathematical definitions.

Furthermore, the equivalence arrow (?) indicates "A if and only if B," which can be succinctly expressed as "A iff B." This indicates that A is true precisely when B is true, and vice versa.

The Direct Proof

The direct proof is the most straightforward form of proof. It involves linking statements through implications derived from axioms and previously established theorems to the statement we aim to demonstrate.

For example, consider the following simple result:

Lemma 1 For every natural number n, if n is odd, then n² is odd.

Proof. Assume n is an odd number. Thus, we can express n as n = 2m + 1 for some non-negative integer m. Therefore, we have:

Since this last expression can also be written as 2k + 1 for some non-negative integer k, it demonstrates that n² must indeed be odd.

In mathematical literature, proofs are often concluded with a small square or the acronym Q.E.D., although the choice of symbol is left to the author.

Direct proofs are inherently simple; we transition from one end to the other until we achieve our goal. Given that implications are transitive, we can consolidate them to form the desired conclusion.

Proof by Contraposition

An implication can be validated through a direct proof, but an alternate method exists. Rather than proving the statement A => B directly, we can utilize the contrapositive statement ¬B => ¬A, which is sometimes simpler to prove.

Consider the statement:

"if it doesn’t float, then it sinks."

If we frame this as A => B, the contrapositive becomes:

"if it doesn’t sink, then it floats."

Both statements are equivalent to:

"Either it floats or it sinks."

Let’s validate the following lemma using this approach:

Lemma 2 For every natural number n, if n² is even, then n is even.

Proof. By contraposition, we can demonstrate:

For every natural number n, if n is odd, then n² is odd.

By Lemma 1, this holds true, thus concluding our proof.

Proof by Contradiction

This method, known as reductio ad absurdum, involves three steps: 1. Assume the proposition A is false, i.e., ¬A is true. 2. Show that ¬A leads to two contradictory assertions, B ? ¬B. 3. Since B and ¬B cannot both be true, the assumption that A is false must be incorrect, thereby proving A must be true.

Let’s explore this technique with a historical example attributed to Hippasus, who, around 500 B.C., demonstrated that ?2 is irrational—a revelation that shocked the Pythagorean community, which believed all numbers were ratios of whole numbers.

Proposition 1 ?2 is an irrational number.

Proof (by contradiction). Assume ?2 is rational. Then we can express it as n/m, where n and m are coprime integers. Squaring both sides yields 2m² = n², indicating that n² is even. By Lemma 2, n must also be even, allowing us to express n as n = 2k for some integer k.

Substituting gives:

2m² = (2k)² = 4k², leading to m² = 2k², thus indicating m is even as well. This implies that both n and m are even, contradicting the assumption that they are coprime.

We have reached a contradiction; therefore, ?2 is irrational.

Let us now explore one of the most beautiful proofs in mathematics.

About 300 B.C., Euclid pondered the nature of prime numbers, laying the groundwork for modern mathematical reasoning. He aimed to prove the infinitude of primes, which cannot be confirmed through brute force counting. Instead, a logical proof is required.

Proposition 2 There are infinitely many prime numbers (Euclid).

Proof (by contradiction). Assume there are finitely many primes, say n primes. We can form their product, which is finite. Define a number q as follows:

At least one prime must divide q; however, it cannot be one of the n primes, as that would leave a remainder of 1. This leads to a contradiction, confirming the existence of infinitely many primes.

Proof by Induction

Induction, while not exclusive to mathematics, takes on a unique significance here. It addresses the question of how to prove a statement true for all natural numbers.

To illustrate, consider proving that 2^n > n² for all n > 4. Induction provides a structured solution:

1. Show that P(k) is true.
2. Show that P(m) => P(m+1).

By the principle of weak induction, we conclude our proof.

Let’s demonstrate this through a proposition.

Proposition 3 The sum of the first n odd numbers is a square, specifically:

1 + 3 + ... + (2n - 1) = n² for n ? 1.

Proof (by induction). The first odd number is 1, which equals 1². Assume for m that:

1 + 3 + 5 + ... + (2m - 1) = m².

To show that:

1 + 3 + 5 + ... + (2(m + 1) - 1) = (m + 1)².

Expanding gives:

1 + 3 + ... + (2m - 1) + (2m + 1) = m² + 2m + 1 = (m + 1)².

This completes our proof.

Moreover, there exists strong induction, which allows assumptions for a range of numbers rather than just one.

Proposition 4 Every integer n ? 2 can be uniquely expressed as a product of prime numbers.

Proof (by strong induction). The base case is true for 2. Assuming the statement holds for all integers up to m, we show it holds for m + 1, considering two cases: if m + 1 is prime or composite.

If it is prime, the statement is true. If composite, it has a smallest prime factor p, allowing us to express m + 1 uniquely as a product of primes.

Undecidability, Consistency, and Metamathematics

As previously mentioned, Kurt Gödel revealed profound insights into logical systems through his Incompleteness Theorems.

The first theorem states that any consistent formal system F capable of performing basic arithmetic is incomplete. This implies there exist statements within F that cannot be proven or disproven within that system.

The second theorem asserts that if F is consistent, it cannot prove its own consistency. This raises significant concerns about the reliability of mathematical systems.

Gödel's theorems have extensive implications, suggesting that regardless of the logical framework employed, there will always be unprovable truths. It also cautions against the assumption of consistency within our mathematical systems.

In conclusion, while mathematics aims for rigor and objectivity, it is essential to recognize its inherent limitations. The pursuit of knowledge is a journey fraught with both discoveries and the acknowledgment of what remains unknown.