A proposition is a statement that is either true or false. This definition sounds very general and is a little vague, but it does exclude sentences such as, “What’s a surjection, again?” and “Learn logarithms!”

Here are some examples of propositions.

Proposition 1. 2 + 3 = 5

This proposition happens to be true.

Proposition 2. ∀ n ∈ ℕ   n2 + n + 41 is a prime number 

This proposition is more complicated. The symbol ∀ is read “for all”, and the symbol ℕ stands for the set of natural numbers, {0, 1, 2, 3, . . .}. (There is some disagreement about whether 0 is a natural number; in this tutorial, it is.) So this proposition asserts that the final phrase is true for all natural numbers n. That phrase is actually a proposition in its own right: "n² + n + 41 is a prime number ".

In fact, this is a special kind of proposition called a predicate, which is a proposition whose truth depends on the value of one or more variables. This predicate is certainly true for many natural numbers n:

Symbol	n2 + n + 41	Prime or composite?
0	41	prime
1	43	prime
2	47	prime
3	53	prime
...	...	prime
20	461	prime
39	1601	prime

Experimental data like this can be useful in mathematics, but can also be misleading. In this case, when n = 40, we get n² + n + 41 = 40² + 40 + 41 = 41 * 41, which is not prime. So Proposition 2 is actually false!

Proposition 3. a4 + b4 + c4 = d4  has no solution when a, b, c, d ∈ ℕ+

Here ℕ⁺ denotes the positive natural numbers, { 1, 2, 3, ... }. In 1769, Euler conjectured that this proposition was true. But it was proven false 218 years later by Noam Elkies at the liberal arts school up Mass Ave. He found the solution a = 95800, b = 217519, c = 414560, d = 422481. We could write his assertion symbolically as follows:

∃ a, b, c, d ∈ ℕ+      a4 + b4 + c4 = d4

The ∃ symbol is read "there exists". So, in words, the expression above says that there exist positive natural numbers a, b, c, and d such that a⁴ + b⁴ + c⁴ = d⁴.

Proposition 4. 313(x3 + y3) = z3 has no solution when x, y, z ∈ ℕ+ 

This proposition is also false, but the smallest counterexample has more than 1000 digits. This counterexample could never have been found by a brute-force computer search!

The symbol ∀ ("for all") and ∃ ("there exists") are called quantifiers. A quantifier is always followed by a variable (and perhaps an indication of what values that variable can take on) and then a predicate that typically involves that variable. The predicate may itself involve more quantifiers. Here are a couple examples of statements involving quantifiers:

∃ x ∈ ℕ   x2 - x + 1 = 0
∀ y ∈ ℕ+   ∃ z ∈ ℕ  ez = y

The first statement asserts that the equation x² − x + 1 = 0 has a real solution, which is false. The second statement says that as z ranges over the real numbers, e^z takes on every positive, real value at least once.

Proposition 5. In every map, the regions can be colored with 4 colors so that adjacent regions have different colors. 

This proposition was conjectured by Guthrie in 1853. The proposition was “proved” in 1879 by Kempe. His argument relied on pictures and— as is often the case with pictureproofs— contained a subtle error, which Heawood found 11 years later. In 1977 Appel and Haken announced a proof that relied on a computer to check an enormous number of cases. However, many mathematicians remained unsatisfied because no human could hand-check the computer’s work and also because of doubts about other parts of the argument. In 1996, Robertson, Sanders, Seymour, and Thomas produced a rigorous proof that still relied on computers. Purported proofs of the Four Color Theorem continue to stream in.

Proposition 6. Every even integer greater than 2 is the sum of two primes. 

For example, 24 = 11 + 23 and 26 = 13 + 13. This is called the Goldbach Conjecture, after Christian Goldbach who first stated the proposition in 1742. Even today, no one knows whether the conjecture is true or false. Every integer ever checked is a sum of two primes, but just one exception would disprove the proposition.

Proposition 7. ∀ n ∈ ℕ  (n ≥ 2) ⇒ (n2 ≥ 4)

The symbol ℕ denotes the set of integers, { ..., -2, -1, 0, 1, 2, ... }. There is predicate nested inside this proposition: (n ≥ 2) ⇒ (n² ≥ 4)

This is an example of an implication , a proposition of the form P ⇒ Q. This expression is read "P implies Q" or "if P, then Q". The proposition correctly asserts that this particular implication is true for every integer n. In general, the implication P ⇒ Q is true when P is false or Q is true. Another way of saying how implication works is with a truth table:

P	Q	P ⇒ Q
T	T	T
T	F	F
F	T	T
F	F	T

In general, a truth table indicates whether a compound proposition is true or false for every possible truth setting of the constituent propositions. The second line of this table, for example, says that the implication P ⇒ Q is false when P is true and Q is false.

Just now we used variables (P and Q) to denote arbitrary propositions. We’ll often use such Boolean variables in place of specific propositions. These are variables that can take on only two possible values, true or false, just as the propositions they represent could be either true or false.

Here another example of an implication:

“If pigs fly, then you will understand the Chernoff Bound.”

This is no insult! It’s a true proposition, even if you’re planning to sleep like a baby through the entire Chernoff Bound lecture. The reason is that the first part of the implication (“pigs fly”) is false. And the last two lines of the truth table say that P ⇒ Q is always true when P is false. This might not be the way you interpret if-then statements in everyday speech, but it’s the accepted convention in mathematical discussions

Proposition 8. ∀ n ∈ ℕ  (n ≥ 2) ⇔ (n2 ≥ 4)

A proposition of the form P ⇔ Q is read “P if and only if Q”. (Sometimes “if and only if” is abbreviated “iff”.) This proposition is true provided P and Q are both true or both false. Put another way, P ⇔ Q is true provided P ⇒ Q and Q ⇒ P are both true. Here is a truth table that compares all these kinds of implication:

P	Q	P ⇒ Q	Q ⇒ P	P ⇔ Q
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

The predicate (n ≥ 2) ⇔ (n² ≥ 4) is true when n = 1 (because both sides are false) and true when n = 3 (because both sides are true) but false when n = -3 (because the left side is false, but the right side is true). Therefore, Proposition 8 as a whole is false.