Discrete Mathematics — MGU Mathematics Series

Part II: Proof, Induction, and Number Structures

Direct Proof · Contrapositive · Contradiction · Cases · Counterexamples

Chapter 4 of 14

MGU Mathematics Series · Discrete Mathematics · Library Textbook Edition

Chapter 4:
Methods of Proof

Direct proof, proof by contrapositive, proof by contradiction, proof by cases, counterexamples, existence and uniqueness proofs, and set identity proofs — the logical foundations of mathematical reasoning

■ Part II: Proof, Induction, and Number Structures ■

■ 14 Sections • Chapter 4 of 14 ■

Follows Chapter 3: Sets, Quantifiers, and Relations · Prepares students for Chapter 5: Mathematical Induction and Recursion

Chapter 4 — Purpose and Overview

Methods of Proof

This chapter teaches students how mathematical proof works. Proof is the mechanism by which mathematics moves from guessing to knowing. In earlier courses, students learned to calculate, simplify, solve, and check. Those skills remain essential. But discrete mathematics also requires a different kind of thinking: the ability to explain why a statement must be true for every possible case, not just for the examples you tested.

Chapter 4 introduces the major methods of mathematical proof used throughout this course and throughout mathematics generally. It covers direct proof, proof by contrapositive, proof by contradiction, proof by cases, counterexamples, existence proofs, and uniqueness proofs. It also teaches how to write proof clearly, what makes a proof correct, and what mistakes students commonly make when learning to write proofs for the first time.

All examples are drawn from integers, parity, divisibility, sets, algebraic inequalities, and logical statements — topics familiar from Algebra II and Chapters 1 through 3. No calculus is required.

Opening Question

Suppose someone claims: "If you multiply two odd integers together, the result is always odd." You could test several cases: \(3 \times 5 = 15\). Odd. \(7 \times 11 = 77\). Odd. \(1 \times 9 = 9\). Odd. Every case confirms the claim — but testing cases, even many cases, does not prove it is true for every pair of odd integers. To move from "this seems to always work" to "this must always work," you need a proof. This chapter explains how proofs are constructed, why they are necessary, and how to write them well.

14Sections

12Objectives

20Key Terms

15+Worked Proofs

Learning Objectives

1Explain what a mathematical proof is and why it is necessary.
2Distinguish between axioms, definitions, and theorems.
3Write a direct proof of a statement about integers, parity, or sets.
4Write a proof by contrapositive.
5Write a proof by contradiction.
6Organize a proof by cases when a statement depends on which case applies.
7Find and present a counterexample that disproves a universal claim.
8Write an existence proof that demonstrates at least one example satisfying a condition.
9Write a uniqueness proof that demonstrates exactly one object satisfies a condition.
10Prove simple set identities using element-chasing or algebraic laws.
11Identify common proof mistakes and explain how to correct them.
12Write proofs clearly in complete sentences with correct notation.

Chapter 4 — Contents

Sections at a Glance

4.1What a Proof IsProof vs. evidence; proof vs. intuition; proof vs. pattern recognition; structure of a proof; reading and writing proofs
4.2Definitions, Axioms, and TheoremsRole of definitions; even and odd integers; divisibility; axioms as starting points; theorems, lemmas, corollaries, conjectures
4.3Direct ProofAssuming \(P\), deriving \(Q\); algebraic manipulation; using definitions in symbolic form; worked examples on parity and divisibility
4.4Proof by ContrapositiveLogical equivalence of \(P \to Q\) and \(\neg Q \to \neg P\); when to use contrapositive; examples with squares and divisibility
4.5Proof by ContradictionAssuming the negation; deriving an impossibility; irrationality of \(\sqrt{2}\); no largest integer; structure and warnings
4.6Proof by CasesExhaustive cases; even/odd split; divisibility mod 4; labeling and completeness requirements
4.7CounterexamplesDisproving universal claims; one example suffices; finding and presenting counterexamples correctly
4.8Existence ProofsConstructive vs. non-constructive; explicit construction; the two-case irrational power example
4.9Uniqueness ProofsExistence plus uniqueness; assuming two solutions and deriving equality; additive identity; linear equations
4.10Proving Set IdentitiesElement-chasing method; mutual subset inclusion; De Morgan's Law; distributive law for sets
4.11Proving Statements About IntegersParity of squares; divisibility by 3; integer patterns; combined proof methods
4.12Writing Clear Mathematical ExplanationsComplete sentences; defining variables; stating the method; labeling cases; concluding clearly; what not to write
4.13Common Proof MistakesCircular reasoning; proving the converse; examples vs. proof; incomplete cases; undefined variables; confusing methods
4.14Preparing for InductionPreview of mathematical induction; connections to Chapter 5; readiness review; bridge to recursion and algorithms

Section 4.1

What a Proof Is

A proof is a complete, logically valid argument that shows a mathematical statement must be true. The key word is must. A proof does not show that something is probably true, or that it seems true in the cases you checked. A proof shows that, given the definitions and rules of mathematics, the statement cannot possibly be false.

Form of Reasoning	What It Does	Is It a Proof?
Evidence	Verifies specific cases: \(2+4=6\), \(4+8=12\), etc.	No — infinitely many cases remain unchecked
Intuition	Claims a statement "feels" true	No — intuition has failed many times in mathematics
Pattern recognition	Observes that a formula works for many values	No — patterns can break unexpectedly
Proof	Gives a general argument from definitions and logic covering all cases simultaneously	Yes

The Pattern That Broke

The expression \(n^2 + n + 11\) produces prime numbers for \(n = 1, 2, 3, \ldots, 9\). A student might conjecture it is always prime. But at \(n = 10\): \(100 + 10 + 11 = 121 = 11^2\). The pattern breaks at the first untested value. This is why no amount of examples can substitute for a general argument.

Every proof begins with what is given or assumed and ends with what is to be concluded. Between beginning and end, every step must follow from what came before — by applying a definition, invoking a previously proven result, or using a valid rule of logic. Reading a proof requires asking at each step: where does this come from? Writing a proof requires planning: what am I trying to prove, what am I allowed to assume, and which method fits?

Section 4.2

Definitions, Axioms, and Theorems

Proof rests on a precise vocabulary. In mathematics, words like "even," "prime," and "divides" have exact definitions, and those definitions are the foundation of every proof that uses them. Before reasoning about any object, you must know what each term means — and you must use that meaning in symbolic form when you write.

Core Definitions Used Throughout This Chapter

Even integer: An integer \(n\) is even if there exists an integer \(k\) such that \(n = 2k\).

Odd integer: An integer \(n\) is odd if there exists an integer \(k\) such that \(n = 2k + 1\).

Divides: An integer \(a\) divides an integer \(b\), written \(a \mid b\), if there exists an integer \(k\) such that \(b = ak\).

Subset: A set \(A\) is a subset of \(B\), written \(A \subseteq B\), if every element of \(A\) is also an element of \(B\).

Theorems, Lemmas, Corollaries, and Conjectures

Term	Meaning
Axiom	A statement accepted as true without proof; the bedrock of a mathematical system
Theorem	A statement proven true; can be freely used in later proofs
Lemma	A smaller theorem proved primarily to support a larger result
Corollary	A theorem following so directly from another that only a short argument is needed
Conjecture	A statement believed true but not yet proven; becomes a theorem if proved, is refuted if a counterexample is found

Read the Structure of a Theorem

Most theorems are conditional statements of the form "if \(P\), then \(Q\)." This structure tells you what is assumed (\(P\)) and what must be shown (\(Q\)). Identifying which part is the hypothesis and which is the conclusion is the first step in choosing a proof method.

Section 4.3

Direct Proof

The most natural method of proof is direct proof. A direct proof of "if \(P\), then \(Q\)" begins by assuming that \(P\) is true and reasons step by step until \(Q\) is shown to be true. Each step must follow from the previous one by applying a definition, a known theorem, or a valid algebraic rule. Direct proof works best when the definitions involved give you an explicit algebraic form to manipulate.

Structure of Direct Proof

1. Assume \(P\) is true.

2. Apply definitions to convert \(P\) into usable symbolic form.

3. Perform algebraic steps, citing each justification.

4. Show that \(Q\) holds by the relevant definition or property.

5. Conclude: "Therefore, \(Q\)." Mark end of proof with \(\square\).

Example 4.3.1

The Sum of Two Even Integers Is Even

ClaimIf \(m\) and \(n\) are even integers, then \(m + n\) is even.
ThinkThe hypothesis gives two even integers. The definition of even gives me an algebraic form for each. I will add those forms and show the result matches the definition of even.
Proof Assume \(m\) and \(n\) are even integers. By the definition of even, there exist integers \(j\) and \(k\) such that \(m = 2j\) and \(n = 2k\). Adding:

\[m + n = 2j + 2k = 2(j + k).\]
Since \(j\) and \(k\) are integers, \(j + k\) is an integer. Let \(p = j + k\). Then \(m + n = 2p\), where \(p\) is an integer.
CheckThe conclusion \(m + n = 2p\) matches the definition of even exactly.

Conclusion: The sum of any two even integers is even.

Example 4.3.2

The Product of Two Odd Integers Is Odd

ClaimIf \(m\) and \(n\) are odd integers, then \(mn\) is odd.
ThinkWrite each odd integer in the form \(2k+1\) and multiply. Show the result has that form too.
Proof Assume \(m\) and \(n\) are odd. Then \(m = 2j + 1\) and \(n = 2k + 1\) for integers \(j\) and \(k\). Computing:

\[mn = (2j+1)(2k+1) = 4jk + 2j + 2k + 1 = 2(2jk + j + k) + 1.\]
Let \(p = 2jk + j + k\), an integer. Then \(mn = 2p + 1\), so \(mn\) is odd.
CheckThe result has the form \(2p+1\), matching the definition of odd.

Conclusion: The product of any two odd integers is odd.

Example 4.3.3

Divisibility Is Transitive

ClaimIf \(a \mid b\) and \(b \mid c\), then \(a \mid c\).
ThinkTwo divisibility facts. Write each using the definition and combine.
Proof Assume \(a \mid b\) and \(b \mid c\). Then \(b = aj\) and \(c = bk\) for integers \(j\) and \(k\). Substituting:

\[c = bk = (aj)k = a(jk).\]
Since \(jk\) is an integer, \(a \mid c\).
Check\(c = a(jk)\) is exactly the form required by the definition of divides.

Conclusion: Divisibility is transitive.

Student Warning — Use the Definition in Symbolic Form

The most common direct proof mistake is failing to write the definition out symbolically. Writing "since \(m\) is even, it is divisible by 2" is not enough — you need to write \(m = 2k\) before you can do anything algebraic with it. Always convert defined terms into their symbolic forms before reasoning.

Section 4.4

Proof by Contrapositive

Recall from Chapter 2 that a conditional statement \(P \rightarrow Q\) is logically equivalent to its contrapositive \(\neg Q \rightarrow \neg P\). Proving the contrapositive is exactly as valid as proving the original statement. Sometimes the direct approach is unclear, but assuming \(\neg Q\) gives you something definite to work with and working toward \(\neg P\) is more natural.

Structure of Proof by Contrapositive

To prove \(P \rightarrow Q\) by contrapositive:

1. State that you are proving the contrapositive: \(\neg Q \rightarrow \neg P\).

2. Assume \(\neg Q\) is true.

3. Reason until you conclude \(\neg P\) is true.

4. Conclude: since \(\neg Q \rightarrow \neg P\) holds, the original \(P \rightarrow Q\) holds.

Example 4.4.1

If \(n^2\) Is Even, Then \(n\) Is Even

ClaimLet \(n\) be an integer. If \(n^2\) is even, then \(n\) is even.
ThinkDirect proof is awkward: from \(n^2 = 2k\) it is not easy to conclude information about \(n\). The contrapositive is: if \(n\) is odd, then \(n^2\) is odd. That direction uses squaring an odd integer, which is straightforward.
Proof We prove the contrapositive: if \(n\) is not even, then \(n^2\) is not even.

Assume \(n\) is not even. Since every integer is either even or odd, \(n\) must be odd. Write \(n = 2k + 1\) for some integer \(k\). Then:

\[n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.\]
This has the form \(2p + 1\), so \(n^2\) is odd — that is, \(n^2\) is not even.
CheckThe contrapositive has been proved. Therefore the original statement holds.

Conclusion: If \(n^2\) is even, then \(n\) is even.

Example 4.4.2

If \(3 \nmid n^2\), Then \(3 \nmid n\)

ClaimLet \(n\) be an integer. If \(3\) does not divide \(n^2\), then \(3\) does not divide \(n\).
ThinkThe contrapositive is: if \(3 \mid n\), then \(3 \mid n^2\). That direction is an easy direct proof.
Proof We prove the contrapositive: if \(3 \mid n\), then \(3 \mid n^2\).

Assume \(3 \mid n\). Write \(n = 3k\) for some integer \(k\). Then:

\[n^2 = (3k)^2 = 9k^2 = 3(3k^2).\]
Since \(3k^2\) is an integer, \(3 \mid n^2\). The contrapositive holds.

Conclusion: If \(3\) does not divide \(n^2\), then \(3\) does not divide \(n\).

Student Warning — Contrapositive vs. Contradiction

These are different methods. In a contrapositive proof, you assume the negation of the conclusion and derive the negation of the hypothesis. In a contradiction proof, you assume the negation of the entire claim and derive a logical impossibility. Do not confuse them.

Section 4.5

Proof by Contradiction

In a proof by contradiction, you assume that the statement you want to prove is false, then show that this assumption leads to a logical impossibility. Since a false assumption forces a contradiction, the assumption must have been wrong — meaning the original statement must be true.

Contradiction is especially useful when the claim involves "no," "never," or "does not exist" — so its negation gives you something concrete to work with — or when there is no clear starting point for a direct argument, but assuming the opposite provides structure.

Structure of Proof by Contradiction

1. State: "Assume, for the sake of contradiction, that [negation of the claim]."

2. Reason from this assumption using valid logical steps.

3. Derive a contradiction: a statement that is logically impossible, or that contradicts a known fact or earlier assumption.

4. Conclude: since the assumption leads to a contradiction, it must be false. Therefore the original claim is true.

Example 4.5.1

\(\sqrt{2}\) Is Irrational

Claim\(\sqrt{2}\) cannot be written as a ratio of integers.
ThinkAssume it is rational, derive a contradiction about the fraction being in lowest terms.
Proof Assume, for the sake of contradiction, that \(\sqrt{2}\) is rational. Then there exist integers \(p\) and \(q\) with \(q \neq 0\) and \(\gcd(p,q) = 1\) (the fraction is in lowest terms) such that

\[\sqrt{2} = \frac{p}{q}.\]
Squaring both sides: \(2 = \frac{p^2}{q^2}\), so \(p^2 = 2q^2\). This means \(p^2\) is even. By Example 4.4.1, since \(p^2\) is even, \(p\) must be even. Write \(p = 2k\) for some integer \(k\).

Substituting: \((2k)^2 = 2q^2\), so \(4k^2 = 2q^2\), giving \(q^2 = 2k^2\). This means \(q^2\) is even, so \(q\) is even.

But now both \(p\) and \(q\) are even, meaning they share a common factor of 2. This contradicts our assumption that \(\gcd(p,q) = 1\).
CheckThe contradiction is explicit: assuming rationality in lowest terms forces both \(p\) and \(q\) to be even, which contradicts "lowest terms."

Conclusion: \(\sqrt{2}\) is irrational.

Example 4.5.2

There Is No Largest Integer

ClaimThere is no largest integer.
ThinkAssume one exists, then exhibit a larger integer, producing a contradiction.
Proof Assume, for the sake of contradiction, that there exists a largest integer \(N\), so \(N \geq n\) for every integer \(n\).

Consider \(N + 1\). Since \(N\) is an integer and 1 is an integer, \(N + 1\) is also an integer. But \(N + 1 > N\), contradicting the assumption that \(N\) is the largest integer.

Conclusion: No largest integer exists.

Student Warning — State the Assumption Explicitly

A proof by contradiction must begin with an explicit statement of what is being assumed for contradiction. Write: "Assume, for the sake of contradiction, that [negation of claim]." Without this setup, the reader cannot follow the logical structure. The contradiction at the end must also be genuine — a statement that truly cannot hold given what is known.

Section 4.6

Proof by Cases

Sometimes a single general argument cannot prove a statement because the situation naturally divides into distinct scenarios. Proof by cases divides the problem into an exhaustive collection of cases — cases that together cover every possibility — and proves the conclusion separately in each one.

The critical requirement is that the cases be exhaustive: together they must cover every possibility. Leaving out a case makes the proof incomplete even if every covered case is correctly handled.

Example 4.6.1

For Any Integer \(n\), the Expression \(n^2 + n\) Is Even

ClaimFor every integer \(n\), \(n^2 + n\) is even.
ThinkEvery integer is either even or odd. I will prove the claim in each case separately.
Case 1 \(n\) is even. Write \(n = 2k\). Then:

\[n^2 + n = 4k^2 + 2k = 2(2k^2 + k).\]
Since \(2k^2 + k\) is an integer, \(n^2 + n\) is even.
Case 2 \(n\) is odd. Write \(n = 2k + 1\). Then:

\[n^2 + n = 4k^2 + 4k + 1 + 2k + 1 = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1).\]
Since \(2k^2 + 3k + 1\) is an integer, \(n^2 + n\) is even.
CheckThe two cases (even and odd) are exhaustive — every integer falls into one of them.

Conclusion: \(n^2 + n\) is even for every integer \(n\).

Example 4.6.2

The Square of Any Integer Is Congruent to 0 or 1 Modulo 4

ClaimFor any integer \(n\), either \(n^2 \equiv 0 \pmod{4}\) or \(n^2 \equiv 1 \pmod{4}\).
ThinkEvery integer is even or odd. If even, \(n^2 = 4k^2\). If odd, \(n^2 = 4(\ldots) + 1\).
Case 1 \(n\) is even. Write \(n = 2k\). Then \(n^2 = 4k^2 = 4 \cdot k^2\), so \(4 \mid n^2\), meaning \(n^2 \equiv 0 \pmod{4}\).
Case 2 \(n\) is odd. Write \(n = 2k + 1\). Then:

\[n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1.\]
So \(n^2 - 1 = 4(k^2 + k)\), meaning \(n^2 \equiv 1 \pmod{4}\).

Conclusion: For any integer \(n\), \(n^2 \equiv 0\) or \(n^2 \equiv 1 \pmod{4}\).

Student Warning — Cases Must Be Exhaustive

When using proof by cases, list the cases at the start and verify they cover every possibility. If you prove the even case but forget the odd case, the proof is invalid. Always ask: have I covered every possible situation?

Section 4.7

Counterexamples

Not every claim is true. When a universal statement ("for all \(x\), ...") is false, it can be disproved by a single counterexample — one specific instance where the hypothesis is satisfied but the conclusion fails. One counterexample is enough to make a universal claim definitively false.

To find a counterexample: look for cases that seem different from the ones that work. Try small numbers, negative numbers, zero, fractions, or extreme values. Think about what would have to be unusual for the claim to fail.

Example 4.7.1

Disproving a Claim About Primes

ClaimFor every positive integer \(n\), the expression \(n^2 + n + 11\) is prime.
ThinkTest values: \(n=1\) gives 13 (prime), \(n=2\) gives 17 (prime), \(n=3\) gives 23 (prime). Try \(n = 10\): \(100 + 10 + 11 = 121 = 11^2\). Not prime.
Counterex.Let \(n = 10\). Then \(n^2 + n + 11 = 121 = 11 \times 11\), which is not prime. The hypothesis (\(n\) is a positive integer) is satisfied; the conclusion (the value is prime) fails.

Conclusion: The claim is false.

Example 4.7.2

Disproving a Claim About Squares

ClaimIf \(a^2 = b^2\), then \(a = b\).
Counterex.Let \(a = 3\) and \(b = -3\). Then \(a^2 = 9\) and \(b^2 = 9\), so \(a^2 = b^2\). But \(3 \neq -3\), so \(a \neq b\).

Conclusion: The claim is false.

Student Warning — Verify Both Parts

A counterexample must satisfy the hypothesis and fail the conclusion. Verify both explicitly. Also: a counterexample disproves a universal statement, but it cannot disprove an existential statement ("there exists..."). To disprove "there exists \(x\) with \(P(x)\)," you must show \(P(x)\) is false for every \(x\).

Section 4.8

Existence Proofs

An existence proof establishes that at least one object satisfying a given condition exists. The logical form is: "There exists \(x\) such that \(P(x)\)." Existence proofs come in two kinds.

Constructive Existence Proofs

Example 4.8.1

There Exists an Even Prime Number (Constructive)

ProofThe number 2 is prime (its only divisors are 1 and 2) and even.

Example 4.8.2

There Exist Integers Satisfying \(3x + 7y = 1\) (Constructive)

ThinkFind one pair. Try \(x = -2\) and \(y = 1\): \(3(-2) + 7(1) = -6 + 7 = 1\). That works.
ProofLet \(x = -2\) and \(y = 1\). Then \(3(-2) + 7(1) = -6 + 7 = 1\). So integers \(x = -2\) and \(y = 1\) satisfy the equation.

Non-Constructive Existence Proofs

A non-constructive proof shows an object satisfying the condition must exist without explicitly naming it. These proofs often use contradiction or a case argument to rule out the possibility that no such object exists.

Example 4.8.3

Irrational Numbers Whose Power Is Rational (Non-Constructive)

ClaimThere exist irrational numbers \(a\) and \(b\) such that \(a^b\) is rational.
ThinkConsider \(c = \sqrt{2}^{\sqrt{2}}\). It is either rational or irrational. Both cases establish the claim.
Proof We know \(\sqrt{2}\) is irrational (Example 4.5.1). Let \(c = \sqrt{2}^{\sqrt{2}}\).

Case 1: If \(c\) is rational, then irrational numbers \(a = \sqrt{2}\) and \(b = \sqrt{2}\) satisfy \(a^b = c\), which is rational. Done.

Case 2: If \(c\) is irrational, let \(a = c = \sqrt{2}^{\sqrt{2}}\) and \(b = \sqrt{2}\). Then:

\[a^b = \left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\sqrt{2} \cdot \sqrt{2}} = \sqrt{2}^2 = 2.\]
The number 2 is rational. So irrational numbers \(a\) and \(b\) exist such that \(a^b\) is rational.
CheckIn both cases, the claim is satisfied. We do not need to know which case actually occurs.

Conclusion: Such irrational numbers exist.

Section 4.9

Uniqueness Proofs

A uniqueness proof establishes that exactly one object satisfies a given condition. The typical structure has two parts: first show existence, then show that any two satisfying objects must be the same. The standard strategy for uniqueness: assume two objects \(x\) and \(y\) both satisfy the condition, then prove \(x = y\).

Example 4.9.1

The Additive Identity Is Unique

ClaimThere is exactly one integer \(z\) such that \(n + z = n\) for every integer \(n\).
ExistenceThe integer \(z = 0\) satisfies \(n + 0 = n\) for every integer \(n\). So at least one such integer exists.
Uniqueness Suppose \(z\) and \(z'\) both satisfy the identity for all \(n\). Applying \(n + z = n\) with \(n = z'\):

\[z' + z = z'.\]
Applying \(n + z' = n\) with \(n = z\):

\[z + z' = z.\]
Since addition is commutative, \(z' + z = z + z'\). Therefore \(z' = z\).

Conclusion: The integer 0 is the unique additive identity.

Example 4.9.2

Uniqueness of a Linear Solution

ClaimThe equation \(5x = 15\) has exactly one integer solution.
ExistenceLet \(x = 3\). Then \(5(3) = 15\). ✓
UniquenessSuppose \(x\) and \(y\) are both solutions. Then \(5x = 15\) and \(5y = 15\). Subtracting: \(5(x - y) = 0\). Since \(5 \neq 0\), we get \(x - y = 0\), so \(x = y\).

Conclusion: The unique solution is \(x = 3\).

Section 4.10

Proving Set Identities

A set identity is a statement that two set expressions always describe the same set. To prove two sets \(S\) and \(T\) are equal, use the element-chasing method: show \(S \subseteq T\) (every element of \(S\) is in \(T\)) and \(T \subseteq S\) (every element of \(T\) is in \(S\)). Together these give \(S = T\). The strategy for each direction: "Let \(x\) be an arbitrary element of \(S\). Show that \(x \in T\)."

Key Translation Rule for Element-Chasing

Translate set membership into logic immediately: "\(x \in A \cap B\)" means "\(x \in A\) and \(x \in B\)." "\(x \in A \cup B\)" means "\(x \in A\) or \(x \in B\)." "\(x \in \overline{A}\)" means "\(x \notin A\)." Work with the logical statements; convert back to sets when done.

Example 4.10.1

De Morgan's Law for Sets: \(\overline{A \cup B} = \overline{A} \cap \overline{B}\)

ClaimFor any sets \(A\) and \(B\) in a universal set \(U\): \(\overline{A \cup B} = \overline{A} \cap \overline{B}\).
Part 1 Show \(\overline{A \cup B} \subseteq \overline{A} \cap \overline{B}\).

Let \(x \in \overline{A \cup B}\). Then \(x \notin A \cup B\), so \(x \notin A\) and \(x \notin B\). Therefore \(x \in \overline{A}\) and \(x \in \overline{B}\), so \(x \in \overline{A} \cap \overline{B}\).
Part 2 Show \(\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}\).

Let \(x \in \overline{A} \cap \overline{B}\). Then \(x \in \overline{A}\) and \(x \in \overline{B}\), so \(x \notin A\) and \(x \notin B\). Therefore \(x \notin A \cup B\), so \(x \in \overline{A \cup B}\).

Conclusion: \(\overline{A \cup B} = \overline{A} \cap \overline{B}\).

Example 4.10.2

Distributive Law: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)

Part 1 Let \(x \in A \cap (B \cup C)\). Then \(x \in A\) and \(x \in B \cup C\), so \(x \in A\) and (\(x \in B\) or \(x \in C\)).

If \(x \in B\): then \(x \in A \cap B \subseteq (A \cap B) \cup (A \cap C)\).
If \(x \in C\): then \(x \in A \cap C \subseteq (A \cap B) \cup (A \cap C)\).
Part 2 Let \(x \in (A \cap B) \cup (A \cap C)\). Then \(x \in A \cap B\) or \(x \in A \cap C\).

If \(x \in A \cap B\): then \(x \in A\) and \(x \in B\), so \(x \in B \cup C\), giving \(x \in A \cap (B \cup C)\).
If \(x \in A \cap C\): then \(x \in A\) and \(x \in C\), so \(x \in B \cup C\), giving \(x \in A \cap (B \cup C)\).

Conclusion: \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).

Section 4.11

Proving Statements About Integers

Example 4.11.1

\(n\) and \(n^2\) Always Have the Same Parity

Case 1\(n\) even. Write \(n = 2k\). Then \(n^2 = 4k^2 = 2(2k^2)\), even.
Case 2\(n\) odd. Write \(n = 2k+1\). Then \(n^2 = 4k^2 + 4k + 1 = 2(2k^2+2k) + 1\), odd.

Conclusion: \(n\) and \(n^2\) have the same parity for every integer \(n\).

Example 4.11.2

For Any Integer \(n\), Exactly One of \(n\), \(n+1\), \(n+2\) Is Divisible by 3

ThinkEvery integer has one of three forms mod 3: \(3k\), \(3k+1\), or \(3k+2\). Use three cases.
Case 1\(n = 3k\). Then \(3 \mid n\). And \(n+1 = 3k+1\), \(n+2 = 3k+2\) — neither divisible by 3.
Case 2\(n = 3k+1\). Then \(n+2 = 3(k+1)\), so \(3 \mid (n+2)\). Neither \(n\) nor \(n+1\) is divisible by 3.
Case 3\(n = 3k+2\). Then \(n+1 = 3(k+1)\), so \(3 \mid (n+1)\). Neither \(n\) nor \(n+2\) is divisible by 3.

Conclusion: Exactly one of \(n\), \(n+1\), \(n+2\) is divisible by 3.

Section 4.12

Writing Clear Mathematical Explanations

Mathematical proof requires not just correct logic, but clear communication. A proof with correct steps written so poorly that a reader cannot follow it is not a successful proof. Mathematical writing must be both logically sound and readable.

Principle	What to Do
Complete sentences	Mathematical symbols appear inside sentences. Write "Since \(n\) is even, we have \(n = 2k\)" — not just "\(n = 2k\)."
Define your variables	Every variable must be introduced. Write "let \(k\) be an integer such that \(n = 2k\)."
State the method	Announce: "We use direct proof" or "We prove the contrapositive."
Label cases	Write "Case 1: \(n\) is even" before each case block.
Orient the reader	Include sentences like "We now show that \(m + n\) is even."
Clear conclusion	Always end: "Therefore, \(m + n\) is even." Mark with \(\square\).

Example 4.12.1

Poor Writing vs. Well-Written Proof — Sum of Even and Odd Is Odd

PoorLet \(m\) be even and \(n\) be odd. \(m = 2k\), \(n = 2j+1\). \(m+n = 2k + 2j + 1\). Odd.
Well-written Let \(m\) be an even integer and \(n\) be an odd integer. We will show that \(m + n\) is odd.

By the definition of even, there exists an integer \(k\) such that \(m = 2k\). By the definition of odd, there exists an integer \(j\) such that \(n = 2j + 1\). Adding:

\[m + n = 2k + (2j + 1) = 2k + 2j + 1 = 2(k + j) + 1.\]
Since \(k + j\) is an integer, \(m + n = 2(k+j) + 1\) has the form \(2p + 1\) with \(p = k + j\). By the definition of odd, \(m + n\) is odd.

Both reach the same conclusion. The second is readable and verifiable at every step.

Section 4.13

Common Proof Mistakes

Mistake 1 — Circular Reasoning

"To show \(n^2\) is even, assume \(n\) is even. Then \(n^2\) is even because even numbers squared are even."

Error: The phrase "even numbers squared are even" is exactly what is being proven. Correction: Write \(n = 2k\), compute \(n^2 = 4k^2 = 2(2k^2)\), and cite the definition of even.

Mistake 2 — Proving the Converse Instead

Statement to prove: \(P \to Q\). Student proves: \(Q \to P\).

Error: The converse is a different statement and may be false. Correction: Write "assume \(P\)" at the top and "therefore \(Q\)" at the bottom. Check you are going the right direction.

Mistake 3 — Using Examples to Prove Universal Claims

"I checked \(n = 1, 2, 3, 4, 5\). The claim holds in each case. Therefore it is true for all \(n\)."

Error: Specific examples do not constitute a proof. Correction: Argue about an arbitrary element using definitions and algebra.

Mistake 4 — Incomplete Case Analysis

Proof by cases handles only the even case; the odd case is omitted.

Error: Even one missing case makes the proof invalid. Correction: List all cases before writing any of them. Verify the list is exhaustive.

Mistake 5 — Undefined or Reused Variables

"Write \(m = 2k\) and \(n = 2k\) for some integer \(k\)."

Error: Using the same \(k\) for two different integers implies \(m = n\). Correction: Use distinct variable names: \(m = 2j\) and \(n = 2k\).

Mistake 6 — Confusing Contrapositive and Contradiction

Student labels the proof "by contradiction" but proves \(\neg Q \to \neg P\) without deriving a contradiction.

Error: That is contrapositive, not contradiction. Correction: State the method clearly. Contradiction requires assuming \(\neg C\) and deriving an impossibility; contrapositive assumes \(\neg Q\) and derives \(\neg P\).

Mistake 7 — No Clear Conclusion

Proof ends mid-calculation without restating what was shown.

Correction: Always close with a sentence: "Therefore, [conclusion]." Place \(\square\) at the end.

Mistake 8 — Writing "It Is Obvious That"

"It is clear that \(n(n+1)\) is always even."

Error: Claiming something is obvious without justification is not a proof step. Correction: Provide the argument, even if brief.

Section 4.14

Preparing for Induction

Chapter 4 has introduced the major methods of proof: direct proof, proof by contrapositive, proof by contradiction, proof by cases, counterexamples, existence proofs, uniqueness proofs, and set proofs. These methods apply across all of discrete mathematics.

Chapter 5 introduces mathematical induction, a specialized proof method for statements indexed by whole numbers — statements of the form "for every positive integer \(n\), \(P(n)\) is true." Induction is the natural proof method when the claim involves patterns that build step by step: sums, sequences, divisibility patterns, and recursive structures.

To prepare for Chapter 5, review the proof methods in this chapter and practice writing proofs clearly. Pay particular attention to direct proof using algebraic manipulation, proof by cases (since induction proofs use base and inductive cases), and the definitions of even, odd, and divides.

Chapter 4 — Back Matter

Chapter Summary

Sec 4.1A proof is a logically valid general argument — not evidence, not intuition, not pattern recognition. Every step must follow from a definition, theorem, or valid rule of logic.
Sec 4.2Proof begins with definitions. Translate every defined term into its symbolic form before reasoning. Theorems are proven results; axioms are assumed starting points; conjectures are unproven claims.
Sec 4.3Direct proof: assume \(P\), use definitions to obtain a symbolic form, perform algebraic steps, show \(Q\) holds by definition. Most useful when definitions give explicit algebraic forms.
Sec 4.4Proof by contrapositive: prove \(\neg Q \to \neg P\) instead of \(P \to Q\), which is logically equivalent. Useful when the negation of the conclusion is easier to work with as an assumption.
Sec 4.5Proof by contradiction: assume \(\neg C\), reason until a logical impossibility appears. Best for "does not exist," irrationality, infinitude, and claims where the direct approach is unclear.
Sec 4.6Proof by cases: divide the problem into exhaustive mutually exclusive cases; prove the conclusion in each. Cases must cover every possibility. Label each case explicitly.
Sec 4.7Counterexamples: one specific instance where the hypothesis holds but the conclusion fails disproves a universal claim. Verify that both parts (hypothesis satisfied, conclusion fails) hold.
Sec 4.8Existence proofs show at least one satisfying object exists. Constructive proofs name it explicitly. Non-constructive proofs show it must exist without identifying it.
Sec 4.9Uniqueness proofs combine existence with the argument that any two satisfying objects must be equal. Assume \(x\) and \(y\) both satisfy the condition; derive \(x = y\).
Sec 4.10Set identity proofs use element-chasing: prove \(S \subseteq T\) and \(T \subseteq S\) by letting \(x\) be an arbitrary element of each and translating membership into logical statements.
Sec 4.11Integer proofs combine parity, divisibility, and case analysis. Many results about \(n^2\), \(n(n+1)\), divisibility by 3, and similar topics follow from definitions and algebraic manipulation.
Sec 4.12Clear proof writing requires complete sentences, defined variables, stated methods, labeled cases, reader orientation, and explicit conclusions. Good logical steps must also be written well.
Sec 4.13Eight common mistakes: circular reasoning; proving the converse; using examples for universals; incomplete cases; reused variables; confusing methods; no conclusion; writing "obviously."
Sec 4.14Mathematical induction (Chapter 5) is the next major proof method, suited to statements indexed by whole numbers. Every skill from Chapter 4 carries forward directly.

Key Terms Review

proof

A logically valid argument establishing a mathematical statement as necessarily true, from definitions, axioms, and previously proven results.

axiom

A statement accepted as true without proof; the bedrock starting point of a mathematical system.

definition

An exact, unambiguous statement of a term's meaning. In proof, always convert defined terms into their symbolic form.

theorem

A statement that has been proven true. Once proven, it may be freely used in later proofs.

lemma

A smaller theorem proven primarily to support a larger result.

corollary

A theorem following so directly from another theorem that only a short argument is needed.

conjecture

A statement believed to be true but not yet proven. Becomes a theorem if proved; is refuted by a counterexample.

direct proof

Assume \(P\) and derive \(Q\) through a sequence of justified logical steps.

contrapositive

To prove \(P \to Q\), prove the equivalent statement \(\neg Q \to \neg P\).

contradiction

Assume the negation of the claim; derive a logical impossibility; conclude the claim must be true.

proof by cases

Divide the problem into exhaustive, mutually exclusive cases. Prove the conclusion in each case.

counterexample

A specific instance where a universal claim's hypothesis holds but its conclusion fails. One counterexample suffices to disprove the claim.

existence proof

Demonstrates that at least one object satisfying a given condition exists.

constructive proof

An existence proof that explicitly names the satisfying object.

non-constructive

An existence proof that shows the object must exist without identifying it.

uniqueness proof

Shows exactly one object satisfies a condition: prove existence, then show any two satisfying objects are equal.

parity

Whether an integer is even or odd. Even: \(n = 2k\). Odd: \(n = 2k+1\).

divides

\(a \mid b\) means \(b = ak\) for some integer \(k\). Read "a divides b."

element-chasing

Proof method for set equality: take an arbitrary element of each set and show it belongs to the other.

circular reasoning

Using the conclusion as a step in the argument that is supposed to establish it. A fatal error in proof.

Concept Review Questions

What is the difference between verifying a claim for several examples and proving a claim? Why is the distinction important?
Explain the relationship between a conditional statement and its contrapositive. Why are they logically equivalent?
What is the negation of the statement "there exists an integer \(n\) such that \(n^2 < 0\)"?
What does it mean to say a set of cases is "exhaustive"? Give an example of a non-exhaustive case split and explain why it is incomplete.
What is the difference between a constructive and a non-constructive existence proof?
Describe the two parts of a uniqueness proof and explain why both are necessary.
What is a counterexample? What does it prove, and what does it not prove?
Explain the element-chasing method for proving set equality.
What is the difference between proof by contrapositive and proof by contradiction?
Why is it not acceptable to write "it is obvious that..." without further justification in a proof?

Proof Strategy Practice

For each statement, identify which proof method (direct, contrapositive, contradiction, cases, or counterexample) would be most natural. Do not write the full proof — identify and briefly explain your choice.

If \(n\) is odd, then \(n^3\) is odd.
The product of two rational numbers is rational.
If \(n^2\) is divisible by 5, then \(n\) is divisible by 5.
For every integer \(n\), \(3 \mid (n^3 - n)\).
The claim "for every positive integer \(n\), \(n^2 - n + 41\) is prime." (Test \(n = 41\).)
There is no integer \(n\) such that \(n^2 = 2\).
There exist integers \(m\) and \(n\) with \(m > 1\) and \(n > 1\) such that \(m \cdot n = 100\).

Skill Practice — Writing Proofs

Part ADirect Proof

Prove: if \(m\) and \(n\) are odd, then \(m + n\) is even.
Prove: if \(a \mid b\) and \(a \mid c\), then \(a \mid (b + c)\).
Prove: if \(a \mid b\) and \(c\) is any integer, then \(a \mid (bc)\).
Prove: the product of any integer and an even integer is even.
Prove: if \(m\) is odd and \(n\) is even, then \(m + n\) is odd.

Part BProof by Contrapositive

Prove: if \(mn\) is even, then \(m\) is even or \(n\) is even.
Prove: if \(n^3\) is even, then \(n\) is even.
Prove: if \(m + n\) is odd, then exactly one of \(m\), \(n\) is odd.

Part CProof by Contradiction

Prove: there is no smallest positive rational number.
Prove: if \(a \mid b\) and \(a \mid (b + 1)\), then \(a = 1\) or \(a = -1\).
Prove: \(\sqrt{3}\) is irrational. (Model your proof on Example 4.5.1.)

Part DProof by Cases

Prove: for any integer \(n\), \(n^2 - n\) is even.
Prove: for any integer \(n\), \(n(n+1)(n+2)\) is divisible by 6. (Consider \(n \bmod 2\) and \(n \bmod 3\) separately.)
Prove: \(|ab| = |a| \cdot |b|\) for all real numbers, considering the four sign combinations.

Counterexample Practice

For each claim, determine whether it is true or false. If false, provide a specific counterexample and verify both parts.

For every positive integer \(n\), \(n^2 + n\) is divisible by 4.
For all integers \(a\) and \(b\), if \(a \mid b^2\) then \(a \mid b\).
For all integers \(m\) and \(n\), if \(mn\) is divisible by 4, then \(m\) is divisible by 4 or \(n\) is divisible by 4.
For all integers \(n > 1\), \(n^2 > 2n\).
The sum of two irrational numbers is always irrational.
If \(n\) is a positive integer, then \(n^2 + 3\) is never divisible by 4.

Set Proof Practice

Prove: for any sets \(A\) and \(B\), \(A \cap B \subseteq A\).
Prove: for any sets \(A\) and \(B\), \(A \subseteq A \cup B\).
Prove: \(\overline{A \cap B} = \overline{A} \cup \overline{B}\). (The second De Morgan's Law.)
Prove: for any sets \(A\), \(B\), \(C\): if \(A \subseteq B\) and \(B \subseteq C\), then \(A \subseteq C\).
Prove: \(A \cup (A \cap B) = A\) for any sets \(A\) and \(B\).

Error Analysis

Each proof below contains one or more errors. Identify the error and explain how to correct it.

Error 1 — Flawed Square Root Argument

Claim: If \(n^2\) is divisible by 4, then \(n\) is divisible by 4.

"Let \(n^2 = 4k\). Taking square roots: \(n = 2\sqrt{k}\). Therefore \(n\) is divisible by 2."

Identify two errors. (1) The conclusion says divisible by 4, not 2. (2) \(\sqrt{k}\) need not be an integer.

Error 2 — Proving the Converse

Claim: If \(2 \mid n\) and \(3 \mid n\), then \(6 \mid n\).

"Let \(6 \mid n\). Write \(n = 6k\). Then \(n = 2(3k)\), so \(2 \mid n\), and \(n = 3(2k)\), so \(3 \mid n\)."

The student proved the converse. The original claim still needs proof. What should the proof assume at the start?

Error 3 — Non-Distinct Counterexample

Claim: There exist distinct integers \(a\) and \(b\) such that \(a^2 = b^2\).

"Let \(a = 3\) and \(b = 3\). Then \(a^2 = b^2 = 9\)."

What is wrong? The claim requires \(a\) and \(b\) to be distinct. Provide a correct existence proof.

Error 4 — Wrong Direction

Claim: For every integer \(n\), if \(n\) is even then \(n + 1\) is odd.

"Suppose \(n+1\) is odd. Then \(n+1 = 2k+1\) for some integer \(k\), so \(n = 2k\), making \(n\) even."

The logic is valid — but the student proved the converse. What has actually been proven? How would you write a correct direct proof of the original claim?

Chapter 4 Checkpoint

Complete without assistance — assesses all key skills and concepts from Chapter 4

Part A — Concepts

State the definition of an even integer and an odd integer.
Explain why a proof is different from evidence. What can evidence never do?
What is the contrapositive of "If \(n\) is not divisible by 3, then \(n^2\) is not divisible by 9"?
In a proof by contradiction, what is assumed and what must be derived?
What two properties must a set of cases satisfy to make a proof by cases valid?

Part B — Proof Writing

Prove: if \(n\) is odd, then \(n^2 + n\) is even. (Direct proof or cases.)
Prove: if \(n^2\) is odd, then \(n\) is odd. (Contrapositive.)
Prove: for any integer \(n\), exactly one of \(n\), \(n+1\) is even. (Cases.)
Prove: \(A \setminus B \subseteq A\) for any sets \(A\) and \(B\). (Element-chasing.)
Prove: there exist integers \(m\) and \(n\) such that \(7m + 11n = 1\). (Find explicit values.)

Part C — Counterexamples

Provide a counterexample to: "For all integers \(n\), if \(2 \mid n^2\) then \(4 \mid n^2\)."
Provide a counterexample to: "The product of two irrational numbers is always irrational."

Part D — Error Analysis

A student writes: "Let \(m = 1\) and \(n = 3\). Then \(m + n = 4\), which is even." The student claims this proves the sum of two odd integers is even. Identify the error and state the correct conclusion.
A student proves "if \(n\) is divisible by 6, then \(n\) is divisible by 2 and 3" but labels it a proof of "if \(n\) is divisible by 2 and 3, then \(n\) is divisible by 6." What is the error?

Looking Ahead

Chapter 5: Mathematical Induction and Recursion

Chapter 4 gave you the tools of mathematical proof: direct proof, contrapositive, contradiction, cases, counterexamples, existence, uniqueness, and set proofs. Chapter 5 introduces mathematical induction — a proof method for statements indexed by whole numbers. Induction is the natural technique when a pattern repeats at every step: sums that grow by one term, divisibility patterns that hold for every integer, sequences defined by recursion. You will learn the base case, the inductive hypothesis, and the inductive step — and see how induction and recursion mirror each other. Every proof skill from Chapter 4 carries directly into Chapter 5 and beyond.

Bridge to Computer Science, Security, and Higher Mathematics

Proof is not an abstract exercise disconnected from computing. It sits at the foundation of every reliable system built with mathematics.

In algorithms, proving that an algorithm is correct means proving it produces the right output for every valid input — not just the inputs tested. The same techniques from this chapter — direct reasoning from definitions, proof by cases based on which branch an algorithm takes, proof by contradiction to show that an incorrect answer is impossible — appear throughout algorithm analysis and correctness verification.

In cybersecurity and cryptography, security proofs establish that breaking an encryption scheme is at least as hard as solving a mathematically intractable problem. These arguments use contradiction: if an adversary could break the cipher, they could solve the hard problem — which is assumed impossible.

In programming and software verification, formal verification tools check program correctness by encoding programs and their specifications as logical statements and checking whether the specification is provably satisfied. The logic of conditionals, conjunctions, and quantifiers from Chapter 2, and the proof methods of Chapter 4, are the vocabulary of these tools.

In higher mathematics — real analysis, abstract algebra, topology — proof is the primary activity. The habits developed here: working from definitions, choosing a method that fits the problem's structure, writing clearly, checking every step — are the habits that carry students into advanced mathematics and into any field that demands rigorous reasoning.

MGU Library Connection

Appendix F: Proof Strategy Guide — summary of all proof methods from this chapter in reference form
Appendix G: Induction Template Reference — preparation for Chapter 5
Chapter 5: Mathematical Induction and Recursion — the next major proof technique
Chapter 12: Algorithms and Complexity — applications of proof to algorithm correctness
MGU Cybersecurity and Cryptography Library — examples of security proofs built on contradiction and conditional reasoning
MGU Dictionary entries: proof, theorem, contrapositive, contradiction, counterexample, parity, divides, element-chasing

Chapter 4:Methods of Proof