The language of proof: implication, converse, contrapositive and proof by contradiction

Statements, implication and equivalence

A statement (proposition) is a sentence that is either true or false. The conditional P ⟹ Q (“if P then Q”) says P is sufficient for Q and Q is necessary for P. Keep the three symbols distinct:

• ⟹ implication — one direction only.
• ⟺ equivalence (P iff Q) — both P ⟹ Q and Q ⟹ P hold.
• = equality — a relation between two quantities, not between statements. Writing “x² = 4 = x = 2” is wrong; you mean x² = 4 ⟹ x = ±2.

The quantifiers are ∀ (“for all”) and ∃ (“there exists”). “∀ real x, x² ≥ 0” is a universal claim; “∃ real x such that x² = 2” is an existential one.

Converse, negation and contrapositive

From P ⟹ Q you can form three related statements:

• Converse: Q ⟹ P — a different statement; the converse of a true statement need not be true.
• Negation: not(P ⟹ Q), which is “P is true but Q is false”.
• Contrapositive: (not Q) ⟹ (not P) — logically equivalent to the original, so proving it proves P ⟹ Q.

Example: “if n² is even then n is even.” The contrapositive “if n is odd then n² is odd” is easier: n = 2k+1 gives n² = 4k²+4k+1 = 2(2k²+2k)+1, odd. ∎ The converse here (“if n is even then n² is even”) also happens to be true, but that is a separate proof — never assume it for free.