| Topics | Assignments | Coq | Proofs | Presentations | Sources |
Proofs reflect our creativity, but they mostly follow certain patterns and rules of the genre. Here we list some proof templates used in course assignments with examples.
| Name of a template | A Typical Example | Further Examples |
|---|---|---|
| Direct proof of an IF-THEN statement | Prove that for any odd integer
\(k\), the square
\(k^2\)
gives remainder 1, when divided by 8. (1) Translate: Odd \( k \) means \(k = 2n+1\) (2) Rewrite: \( (2n+1)^2 = 4n^2 + 4n + 1 = 4n(n+1)+1 \) (3) Sort cases: \( n \) even or odd. |
|
| Bidirectional proof of an IF-AND-ONLY-IF statement | Prove that a positive integer \(n\) has odd number of positive divisors (including 1 and \(n\) itself) if and only if \(n\) is a full square - can be expressed as \( k^2 \). | |
| Contrapositive proof of an IF-AND-ONLY-IF statement | Prove that for any prime number \(\ p \), the square root \(\ \sqrt{p} \) is irrational. | |
| Proving an identity by sorting cases | For any real number \(\ x \in \mathbb{R} \) its rounded value to the nearest tenth (rounding to one decimal place) is equal to \( \frac{1}{10} \lfloor 10x + 0.5 \rfloor \). | |
| Proving that a bijective function exists by construction | Prove that there is a function \(\ f : (-\pi;\pi) \rightarrow \mathbb{R} \) mapping interval \(\ (-\pi;\pi) \) to \(\ \mathbb{R} \) such that every real number \(\ y \) has exactly one \(\ x \) such that \(\ f(x)=y \). | |
| Disproving that a bijective function exists from the contrary. | Prove that it is impossible to enumerate all subsets of natural numbers with natural numbers. | |
| Prove that some set is infinite by contradiction. | Prove that there are infinitely many primes. |