1.1: Propositions

Definition

A proposition is a statement (communication) that is either true or false.

For example, both of the following statements are propositions. The first is true, and the second is false.

Proposition 1.1.1. 2 + 3 = 5.

Proposition 1.1.2. 1 + 1 = 3.

Being true or false doesn’t sound like much of a limitation, but it does exclude statements such as “Wherefore art thou Romeo?” and “Give me an A!” It also excludes statements whose truth varies with circumstance such as, “It’s five o’clock,” or “the stock market will rise tomorrow.”

Unfortunately it is not always easy to decide if a proposition is true or false:

Proposition 1.1.3. For every nonnegative integer, \(n\), the value of \(n^2 + n + 41\) is prime.

(A prime is an integer greater than 1 that is not divisible by any other integer greater than 1. For example, 2, 3, 5, 7, 11, are the first five primes.) Let’s try some numerical experimentation to check this proposition. Let

\[\label{1.1.1} p(n) ::= n^2 + n + 41. ^1\]

We begin with \(p(0) = 41\), which is prime; then

\[\nonumber p(1) = 43, p(2) = 47, p(3) = 53, \ldots , p(20) = 461\]

are each prime. Hmmm, starts to look like a plausible claim. In fact we can keep checking through \(n = 39\) and confirm that \(p(39) = 1601\) is prime.

But \(p(40) = 40^2 + 40 + 41 = 41 \cdot 41\), which is not prime. So it’s not true that the expression is prime for all nonnegative integers. In fact, it’s not hard to show that no polynomial with integer coefficients can map all nonnegative numbers into prime numbers, unless it’s a constant (see Problem 1.17). But the real point of this example is to show that in general, you can’t check a claim about an infinite set by checking a finite set of its elements, no matter how large the finite set.

By the way, propositions like this about all numbers or all items of some kind are so common that there is a special notation for them. With this notation, Proposition 1.1.3 would be

\[\forall n \in \mathbb{N}, p(n) \text{ is prime.}\]

Here the symbol \(\forall\) is read “for all.” The symbol \(\mathbb{N}\) stands for the set of nonnegative integers: \(0, 1, 2, 3, \ldots \)(ask your instructor for the complete list). The symbol “\(\in\)” is read as “is a member of,” or “belongs to,” or simply as “is in.” The period after the \(\mathbb{N}\) is just a separator between phrases.

Here are two even more extreme examples:

Proposition 1.1.4. [Euler’s Conjecture] The equation

\[\nonumber a^4 + b^4 + c^4 = d^4\]

has no solution when \(a, b, c, d\) are positive integers.

Euler (pronounced “oiler”) conjectured this in 1769. But the proposition was proved false 218 years later by Noam Elkies at a liberal arts school up Mass Ave. The solution he found was \(a = 95800, b = 217519, c = 414560, d = 422481\).

In logical notation, Euler’s Conjecture could be written,

\[\nonumber \forall a \in \mathbb{Z}^+ \forall b \in \mathbb{Z}^+ \forall c \in \mathbb{Z}^+ \forall d \in \mathbb{Z}^+ . a^4 + b^4 + c^4 \neq d^4 .\]

Here, \(\mathbb{Z}^+\) is a symbol for the positive integers. Strings of \(\forall\)'s like this are usually abbreviated for easier reading:

\[ \nonumber \forall a, b, c, d \in \mathbb{Z}^+ . a^4 + b^4 + c^4 \neq d^4 .\]

Proposition 1.1.5. \(313(x^3 + y^3) = z^3\) has no solution when \(x, y, z \in \mathbb{Z}^+ .\)

This proposition is also false, but the smallest counterexample has more than 1000 digits!

It’s worth mentioning a couple of further famous propositions whose proofs were sought for centuries before finally being discovered:

Proposition 1.1.6 (Four Color Theorem). Every map can be colored with 4 colors so that adjacent² regions have different colors.

Several incorrect proofs of this theorem have been published, including one that stood for 10 years in the late 19th century before its mistake was found. A laborious proof was finally found in 1976 by mathematicians Appel and Haken, who used a complex computer program to categorize the four-colorable maps. The program left a few thousand maps uncategorized, which were checked by hand by Haken and his assistants—among them his 15-year-old daughter.

There was reason to doubt whether this was a legitimate proof: the proof was too big to be checked without a computer. No one could guarantee that the computer calculated correctly, nor was anyone enthusiastic about exerting the effort to recheck the four-colorings of thousands of maps that were done by hand. Two decades later a mostly intelligible proof of the Four Color Theorem was found, though a computer is still needed to check four-colorability of several hundred special maps.³

Proposition 1.1.7 (Fermat’s Last Theorem). There are no positive integers \(x, y,\) and \(z\) such that

\[\nonumber x^n + y^n = z^n\]

for some integer \(n>2\).

In a book he was reading around 1630, Fermat claimed to have a proof for this proposition, but not enough space in the margin to write it down. Over the years, the Theorem was proved to hold for all \(n\) up to 4,000,000, but we’ve seen that this shouldn’t necessarily inspire confidence that it holds for all \(n\). There is, after all, a clear resemblance between Fermat’s Last Theorem and Euler’s false Conjecture. Finally, in 1994, British mathematician Andrew Wiles gave a proof, after seven years of working in secrecy and isolation in his attic. His proof did not fit in any margin.⁴

Finally, let’s mention another simply stated proposition whose truth remains unknown.

Proposition 1.1.8 (Goldbach’s Conjecture). Every even integer greater than 2 is the sum of two primes.

Goldbach’s Conjecture dates back to 1742. It is known to hold for all numbers up to \(10^{18}\) but to this day, no one knows whether it’s true or false.

For a computer scientist, some of the most important things to prove are the correctness of programs and systems—whether a program or system does what it’s supposed to. Programs are notoriously buggy, and there’s a growing community of researchers and practitioners trying to find ways to prove program correctness. These efforts have been successful enough in the case of CPU chips that they are now routinely used by leading chip manufacturers to prove chip correctness and avoid mistakes like the notorious Intel division bug in the 1990’s. Developing mathematical methods to verify programs and systems remains an active research area. We’ll illustrate some of these methods in Chapter 5.

¹The symbol ::= means “equal by definition.” It’s always ok simply to write “=” instead of ::=, but reminding the reader that an equality holds by definition can be helpful.

²Two regions are adjacent only when they share a boundary segment of positive length. They are not considered to be adjacent if their boundaries meet only at a few points.

³The story of the proof of the Four Color Theorem is told in a well-reviewed popular (nontechnical) book: “Four Colors Suffice. How the Map Problem was Solved.” Robin Wilson. Princeton Univ. Press, 2003, 276pp. ISBN 0-691-11533-8.

⁴In fact, Wiles’ original proof was wrong, but he and several collaborators used his ideas to arrive at a correct proof a year later. This story is the subject of the popular book, Fermat’s Enigma by Simon Singh, Walker & Company, November, 1997.