Proofs — Exercises

Contents

1Vocabulary recap easy

Match each term with the right definition: axiom, conjecture, lemma, theorem, corollary, proof.

2Direct: sum of two odd integers is even easy

Prove that if $a, b$ are odd, then $a + b$ is even. Then verify in Python on a range.

3Direct: product of two rationals is rational easy

Write the direct proof, then check three random pairs of rationals in Python with fractions.Fraction.

4Contraposition: $n^2$ even $\Rightarrow n$ even medium

Prove by contraposition that for every $n \in \mathbb{Z}$, if $n^2$ is even then $n$ is even.

5Contraposition: $ab < 0 \Rightarrow a < 0 \vee b < 0$ medium

Prove by contraposition for $a, b \in \mathbb{R}$.

6Contradiction: $\sqrt{2}$ is irrational medium

Reproduce the classical proof in 4 steps. Verify the conclusion symbolically with SymPy.

7Contradiction: infinitely many primes (Euclid) hard

Reproduce Euclid's argument. Then write Python code that, for a list of "all" primes $L = [2, 3, 5, \dots, p_n]$, builds $q = 1 + \prod L$ and verifies that $q$ has a prime factor not in $L$ (for $n \leq 6$).

8Cases: $n^2 - 1$ is divisible by 3 when $3 \nmid n$ medium

Prove by cases and verify on a range.

9Cases: $n^2 \bmod 4 \in \{0, 1\}$ medium

Prove that for every $n \in \mathbb{Z}$, $n^2 \equiv 0$ or $1 \pmod 4$.

10Existence: find a SAT witness medium

Show that $(\neg x \vee y \vee z) \wedge (x \vee \neg y \vee z) \wedge (x \vee y \vee \neg z) \wedge (x \vee y \vee z)$ is satisfiable by exhibiting an assignment.

11Uniqueness: 2 is the only even prime medium

Show existence and uniqueness; back it up with a Python scan up to 10 000.

12Disprove a conjecture by counterexample hard

Someone claims: "For every $n \in \mathbb{N}$, $n^2 + n + 41$ is prime." Use Python to either confirm it or find the smallest counterexample.

Going further

• Prove (by contradiction) that $\sqrt{3} \notin \mathbb{Q}$. Generalize: $\sqrt{p}$ is irrational for any prime $p$.
• Prove by cases: for every $n \in \mathbb{Z}$, $n^3 - n$ is divisible by 6.
• Use sympy.logic.inference.satisfiable to check a 4-variable CNF and find all satisfying assignments via all_models=True.
• Look up "pigeonhole principle" — a non-constructive existence proof.

Open the main lesson for the matching theory.