Implications, equivalence and proof structures (direct, cases, contradiction, contrapositive)

Conjectures, implications and 'if and only if'

A conjecture is a statement put forward to be proved or disproved. A single counter-example disproves a universal claim, but no finite list of supporting examples ever proves one — examples only build intuition or motivate a conjecture.

The conditional P ⟹ Q reads “if P then Q”: P is sufficient for Q, and Q is necessary for P. The biconditional P ⟺ Q (“P if and only if Q”) means both P ⟹ Q and Q ⟹ P hold, so P and Q are equivalent. To prove an “iff”, you must prove both directions.

Direct proof and proof by cases

A direct proof chains together implications from the hypothesis to the conclusion. Example: if n is odd then n² is odd. Write n = 2k+1, then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. ∎

A proof by cases splits the domain into exhaustive cases and proves the result in each. Example: n² + n is even for every integer n.

• Case n even: n = 2k, so n² + n = 2k(2k+1), even.
• Case n odd: n = 2k+1, so n² + n = (2k+1)(2k+2) = 2(2k+1)(k+1), even.

Every integer falls into one case, so the result holds for all n. ∎