Mathematical Logic and Proofs

Every theorem in this course — every "hence," every "it follows that" — rests on a small number of logical rules that this chapter makes explicit. So far you have manipulated numbers and sets; now the objects of study are statements themselves, and the question is not whether a statement is true, but what it means to know it is true, and how one true statement can be shown to force another. The informal argument in Chapter 1 that $\sqrt{2}$ is irrational already used this chapter's central tool — proof by contradiction — without naming it. Here it gets named, and three others besides.

This chapter has two halves. The first half, propositional logic, gives a precise vocabulary for combining and negating statements: connectives, truth tables, and the crucial distinction between a conditional statement and its converse, inverse and contrapositive. The second half turns that vocabulary into a toolkit of proof techniques — direct proof, contrapositive, contradiction, and counterexample — that every later chapter in this course will use without further comment. Have to hand: a willingness to be pedantic about the difference between "if" and "only if," since exam questions are built precisely on that distinction.

1. Propositions and Truth Values

A proposition is a statement that is unambiguously either true or false — never both, never neither. "$7$ is prime" is a proposition (true). "$x+3=10$" is not a proposition as it stands, because its truth depends on the unspecified value of $x$; such a statement is called an open sentence or predicate, and only becomes a proposition once $x$ is assigned a value or bound by a quantifier (Section 5). "Is $7$ prime?" and "Stop!" are not propositions at all — a question or a command carries no truth value.

Propositions versus opinions. "Mathematics is the most interesting subject" is not a proposition, however strongly held — it has no objectively determinable truth value. Every proposition in this course is a precise mathematical or logical claim.

2. Logical Connectives and Truth Tables

Propositions combine into compound statements using connectives. Each connective's meaning is defined completely by a truth table, listing the truth value of the compound statement for every combination of truth values of its parts. With $n$ basic propositions, a truth table needs $2^n$ rows, since each proposition independently takes one of two values.

Negation, $\neg p$ ("not $p$"), reverses the truth value of $p$:

Conjunction, $p \wedge q$ ("$p$ and $q$"), is true only when both $p$ and $q$ are true:

Disjunction, $p \vee q$ ("$p$ or $q$"), is true when at least one of $p, q$ is true (the inclusive or — true even when both are true):

Negating a conjunction or disjunction follows the same De Morgan pattern met for sets in Chapter 1 — and this is no coincidence, since $\wedge$ behaves exactly like $\cap$ and $\vee$ exactly like $\cup$:

where $\equiv$ denotes logical equivalence: two statements with identical truth tables, true and false in exactly the same cases.

Worked example — negating a compound claim. Negate "the triangle is isosceles and right-angled." Here $p =$ "isosceles," $q =$ "right-angled." The negation is $\neg p \vee \neg q$: "the triangle is not isosceles, or it is not right-angled" — not the common wrong guess "the triangle is not isosceles and not right-angled," which would be $\neg p \wedge \neg q$, a much stronger (and incorrect) claim.

3. The Conditional and Biconditional

The conditional, $p \Rightarrow q$ ("if $p$ then $q$," or "$p$ implies $q$"), is the connective most often misjudged. Its truth table:

The only way for $p \Rightarrow q$ to be false is for $p$ to be true and $q$ false. Whenever $p$ is false, the conditional is automatically true, regardless of $q$ — this is called vacuous truth. "If $5$ is even, then $5$ is prime" is a true statement, however strange that feels, precisely because its hypothesis is false.

In $p \Rightarrow q$, $p$ is called a sufficient condition for $q$ (knowing $p$ is enough to guarantee $q$), and $q$ is called a necessary condition for $p$ (if $q$ fails, $p$ cannot hold either). The phrase "$p$ only if $q$" means exactly $p \Rightarrow q$ — not $q \Rightarrow p$, a distinction that trips up almost every student the first time.

"If" versus "only if." "$p$ if $q$" means $q \Rightarrow p$. "$p$ only if $q$" means $p \Rightarrow q$. The two have opposite direction, despite differing by a single word.

The biconditional, $p \Leftrightarrow q$ ("$p$ if and only if $q$," abbreviated "iff"), asserts both directions at once: $p \Leftrightarrow q$ is true exactly when $p$ and $q$ have the same truth value.

Proving a biconditional therefore generally requires proving two conditionals, one in each direction — a common source of incomplete proofs when a student proves only one half.

4. Converse, Inverse and Contrapositive

Given a conditional $p \Rightarrow q$, three related statements can be formed, and distinguishing them precisely is one of the most heavily examined skills in this chapter:

• Converse: $q \Rightarrow p$ (swap the two parts).
• Inverse: $\neg p \Rightarrow \neg q$ (negate both parts, keep the order).
• Contrapositive: $\neg q \Rightarrow \neg p$ (swap and negate both parts).

Worked example — building all three. Let $p =$ "$x$ is a multiple of $8$," $q =$ "$x$ is even," so $p \Rightarrow q$ reads "if $x$ is a multiple of $8$, then $x$ is even" (true).

• Converse: "if $x$ is even, then $x$ is a multiple of $8$" — false ($x=2$ is even but not a multiple of $8$).
• Inverse: "if $x$ is not a multiple of $8$, then $x$ is not even" — false (same counterexample, $x=2$).
• Contrapositive: "if $x$ is not even, then $x$ is not a multiple of $8$" — true, and in fact must be true whenever the original statement is.

This last fact is a theorem, not a coincidence, provable by comparing truth tables directly:

A conditional and its contrapositive are always logically equivalent; a conditional and its converse (or inverse) are, in general, not. The converse and the inverse are themselves always equivalent to each other, since the inverse is simply the contrapositive of the converse.

5. Quantifiers

A predicate such as "$x^2 \geq 0$" becomes a proposition once a quantifier fixes how many values of $x$ it must hold for.

The universal quantifier, $\forall$ ("for all"), asserts the predicate holds for every element of a specified domain:

The existential quantifier, $\exists$ ("there exists"), asserts the predicate holds for at least one element:

Negating a quantified statement swaps the quantifier and negates the predicate — this is the logical analogue of De Morgan's laws, extended from two propositions to an entire domain:

In words: to show a "for all" claim is false, it is enough to exhibit one element where the predicate fails — a counterexample. To show a "there exists" claim is false, you must show the predicate fails for every element of the domain — a much stronger requirement.

Worked example — negating a quantified claim. Negate: "$\forall x \in \mathbb{Z},\ x^2 > x$." The negation is $\exists x \in \mathbb{Z} : x^2 \leq x$. Testing $x=1$: $1^2 = 1 \leq 1$, true — so the negation holds, meaning the original universal claim is false, refuted by the single counterexample $x=1$ (also $x=0$ works). Notice the original claim is in fact true for every integer except $0$ and $1$; a single exception anywhere in the domain is enough to falsify a universal statement entirely.

6. Direct Proof

A direct proof of $p \Rightarrow q$ assumes $p$ is true and, through a chain of valid logical steps, deduces that $q$ must also be true.

Worked example. Prove: if $n$ is an odd integer, then $n^2$ is odd. Assume $n$ is odd, so $n = 2k+1$ for some integer $k$. Then

which is of the form $2m+1$ with $m = 2k^2+2k \in \mathbb{Z}$, hence odd. This completes a direct proof: starting from the hypothesis, pure algebra reached the conclusion.

7. Proof by Contrapositive

Sometimes $p \Rightarrow q$ is awkward to prove directly, but its contrapositive $\neg q \Rightarrow \neg p$ is easy — and since the two are logically equivalent (Section 4), proving one proves the other.

Worked example. Prove: if $n^2$ is even, then $n$ is even. A direct proof would need to extract a factor of $2$ from inside a square root of $n^2$, which is clumsy. Instead prove the contrapositive: if $n$ is odd, then $n^2$ is odd — which is exactly the direct proof of Section 6. Since $\neg q \Rightarrow \neg p$ is proved, $p \Rightarrow q$ follows automatically.

8. Proof by Contradiction

A proof by contradiction assumes $\neg p$ (the negation of what is to be proved) and derives a logically impossible consequence — a statement of the form $r \wedge \neg r$ for some $r$, which can never be true. Since the assumption $\neg p$ led to an impossibility, $\neg p$ must be false, so $p$ is true.

This is exactly the structure used in Chapter 1 to prove $\sqrt{2}$ irrational: assume $\sqrt{2}$ is rational ($\neg p$), derive that the numerator and denominator of its lowest-terms fraction are both even ($r \wedge \neg r$, since "lowest terms" and "both even" cannot coexist), conclude $\sqrt{2}$ is irrational ($p$).

When to reach for contradiction. Proof by contradiction is most useful exactly when the conclusion is a negative statement ("$\sqrt{2}$ is not rational," "there is no largest prime") — negating it produces a positive, workable assumption to reason from.

Worked example — infinitude of primes (Euclid). Prove there is no largest prime number. Assume, for contradiction, that there are only finitely many primes, $p_1, p_2, \ldots, p_n$. Consider

$N$ is not divisible by any $p_i$ (dividing $N$ by $p_i$ always leaves remainder $1$), so either $N$ itself is prime, or it has a prime factor not in the original list. Either way, a prime exists outside $\{p_1,\ldots,p_n\}$, contradicting the assumption that the list was complete. Hence there are infinitely many primes.

9. Counterexamples and Proof by Exhaustion

To disprove a universal claim, a single counterexample suffices — Section 5 already showed this. No general argument is needed, only one explicit instance where the predicate fails.

Worked example. Disprove: "every prime number is odd." The counterexample $p=2$ (prime, but even) suffices to falsify the universal claim entirely.

Proof by exhaustion (or proof by cases) proves a claim by checking every possible case separately, used when the domain splits naturally into a small, finite number of possibilities (e.g. checking a claim about integers separately for the cases "even" and "odd"). It is a direct proof repeated once per case, not a distinct logical mechanism.

10. Common Exam Pitfalls

• Confusing the converse with the contrapositive. Only the contrapositive is guaranteed logically equivalent to the original conditional; the converse generally is not and must be checked independently.
• Negating "and" as "and" instead of "or." $\neg(p \wedge q) \equiv \neg p \vee \neg q$ — the connective flips, exactly as with set complements in Chapter 1.
• Treating a false hypothesis as making the whole proof false. $p \Rightarrow q$ is vacuously true whenever $p$ is false — this is a feature of the definition, not an error.
• Proving only one direction of an "if and only if" statement. A biconditional needs both $p \Rightarrow q$ and $q \Rightarrow p$ established.
• Trying to disprove an existential ($\exists$) claim with a single counterexample. A single failing case only disproves a universal claim; an existential claim requires showing the predicate fails for every element of the domain.
• Misreading "only if." "$p$ only if $q$" is $p \Rightarrow q$, not $q \Rightarrow p$ — the two directions are easy to swap by mistake.

Summary

• A proposition has a definite truth value; an open sentence does not, until a value is substituted or a quantifier applied.
• Connectives: $\neg p$ (not), $p\wedge q$ (and, true only if both true), $p\vee q$ (or, true if at least one true). Logical De Morgan: $\neg(p\wedge q)\equiv \neg p\vee\neg q$ and $\neg(p\vee q)\equiv\neg p\wedge\neg q$.
• $p \Rightarrow q$ is false only when $p$ is true and $q$ is false; it is vacuously true whenever $p$ is false. $p \Leftrightarrow q \equiv (p\Rightarrow q)\wedge(q\Rightarrow p)$.
• Given $p \Rightarrow q$: converse $q\Rightarrow p$, inverse $\neg p\Rightarrow\neg q$, contrapositive $\neg q\Rightarrow\neg p$. Only the contrapositive is guaranteed equivalent to the original.
• $\neg(\forall x, P(x)) \equiv \exists x, \neg P(x)$ and $\neg(\exists x, P(x)) \equiv \forall x, \neg P(x)$. A universal claim is disproved by one counterexample; an existential claim requires ruling out every case.
• Proof techniques: direct proof (assume $p$, deduce $q$); proof by contrapositive (prove $\neg q\Rightarrow\neg p$ instead); proof by contradiction (assume $\neg p$, reach an impossibility $r\wedge\neg r$); disproof by counterexample; proof by exhaustion (check every case).