# Direct Proof and Counterexample

Mathematics I · Mathematical Language and Reasoning · https://tryals.app/learn/mathematics-i/direct-proof-and-counterexample

## Direct Proofs

A **proof** is a finite chain of logically valid steps establishing a statement from **axioms**, **definitions**, and **theorems**. A proof settles a claim for all cases permanently.

To run a **direct proof** of "if $p$ then $q$", **assume $p$** and derive $q$ through justified algebraic and logical steps.

| Concept | Meaning | Role in Proof |
| --- | --- | --- |
| **Axiom** | Accepted starting fact | Foundation |
| **Universal** | Claim for all $n$ | Requires **arbitrary** element |

Example: To prove "if $n$ is even, then $n^2$ is even," assume $n = 2k$. Then $n^2 = 4k^2 = 2(2k^2)$, which is even by definition.

## Refuting Claims

The mirror image is **disproof by counterexample**. To show a universal claim is false, exhibit a single instance where it fails.

To refute "every prime is odd," name **2**, a prime that is even. **A universal statement is proved by a general argument but disproved by a single example.**

| Method | Works for Universal? | Why? |
| --- | --- | --- |
| **Examples** | Only for disproof | One failure demolishes it |
| **General Arg** | Only for proof | Covers **arbitrary** elements |

> **Common pitfall:** trying to **prove a universal by examples**. Verifying a claim for several cases never establishes it for all cases.

## Practice questions

6 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. Checking that a claim about all integers holds for the first ten thousand cases is not a proof, while a single failing case is a complete refutation. Why is the evidence so lopsided?

A. Because ten thousand cases is too few, and a sufficiently large number of verified cases would constitute a proof.
B. Because mathematicians conventionally require symbolic arguments and do not accept numerical evidence of any kind.
C. Because a counterexample is easier to verify than a general argument, which is why it is given more weight.
D. Because verified cases leave infinitely many untested, and one falsifies.

**Answer:** D. Because verified cases leave infinitely many untested, and one falsifies.

**Why:** 'For all n' is a conjunction of infinitely many claims, so verifying finitely many leaves infinitely many untested however large the finite number; its negation needs one witness. The history is genuinely alarming: Pólya's conjecture holds below roughly 900 million and fails after, which is why no finite threshold could ever settle it.

Page: https://tryals.app/practice/mathematics-i/direct-proof-and-counterexample/checking-that-a-claim-about-all-integers-holds-for-the-first-ten

### 2. A claim that holds for the first one million integers is thereby proven for all integers.

**Answer:** False

**Why:** False. A million confirmations leave infinitely many cases untested. Polya's conjecture survived far beyond a million before failing, and Euler's polynomial gave 40 primes before breaking, evidence is not proof.

Page: https://tryals.app/practice/mathematics-i/direct-proof-and-counterexample/a-claim-that-holds-for-the-first-one-million-integers-is-thereby

### 3. Order the steps of a direct proof that the sum of two even integers is even.

**Answer:**

1. Assume m and n are even integers
2. Write m = 2a and n = 2b for some integers a and b
3. Add them: m + n = 2a + 2b = 2(a + b)
4. Note that a + b is an integer
5. Conclude m + n is even

**Why:** A direct proof runs hypothesis to conclusion: assume, unpack the definition into algebra, compute, check the result fits the definition again, conclude. Step 4 matters, 2(a+b) only proves evenness because a+b is itself an integer.

Page: https://tryals.app/practice/mathematics-i/direct-proof-and-counterexample/order-the-steps-of-a-direct-proof-that-the-sum-of-two-even-integers

### 4. Claim: 'every prime number is odd'. Select every value that is a genuine COUNTEREXAMPLE.

A. 2
B. 15
C. 9
D. 17
E. 4

**Answer:** A. 2

**Why:** Only 2 works: it is prime (satisfying the hypothesis) and even (failing the conclusion). 9 and 15 are odd but not prime, 4 is even but not prime, neither type touches the claim. A counterexample must sit inside the claim's scope.

Page: https://tryals.app/practice/mathematics-i/direct-proof-and-counterexample/claim-every-prime-number-is-odd-select-every-value-that-is-a

### 5. Sort each claim by what it would take to settle it.

**Answer:**

- Settled by one example: Some even number is prime, There is an integer between 3 and 5
- Settled by one counterexample: Every prime is odd
- Needs a general proof: The sum of two odd numbers is even

**Why:** Existential claims (p1, p4) need one witness. A false universal (p2) needs one counterexample. But a true universal (p3) covers infinitely many cases, so no finite pile of examples proves it, only a general argument does.

Page: https://tryals.app/practice/mathematics-i/direct-proof-and-counterexample/sort-each-claim-by-what-it-would-take-to-settle-it

### 6. Every even number above 2 checked so far is the sum of two primes, verified past 4 × 10¹⁸. Why is Goldbach's conjecture still a conjecture?

A. Because mathematicians have not yet agreed on the definition of a prime
B. Because no finite verification touches an infinite domain
C. Because it has been proved for even numbers only, not for odd ones
D. Because the computations may contain errors at that scale

**Answer:** B. Because no finite verification touches an infinite domain

**Why:** Four quintillion is a rounding error against infinity, and the history is a warning: Pólya's conjecture survived to around 900 million and Skewes' number shows a crossover far past any feasible search. Verification builds confidence and never converts a universal claim, which is the whole reason proof exists.

Page: https://tryals.app/practice/mathematics-i/direct-proof-and-counterexample/every-even-number-above-2-checked-so-far-is-the-sum-of-two-primes