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

Statements, implication and equivalence

A statement (proposition) is a sentence that is either true or false. Statements are joined by connectives:

• ∧ “and” (conjunction) — P ∧ Q is true only when both P and Q are true.
• ∨ “or” (disjunction) — P ∨ Q is true when at least one of P, Q is true (the inclusive ‘or’).
• ¬ (also written ∼) “not” (negation) — ¬P is true exactly when P is false.

The conditional P ⟹ Q (“if P then Q”) says P is sufficient for Q and Q is necessary for P. It is false only when P is true and Q is false. 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: ¬(P ⟹ Q), which is “P is true but Q is false”, i.e. P ∧ ¬Q.
• Contrapositive: ¬Q ⟹ ¬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.

Negating compound statements. The rules to know:

• Double negation: ¬(¬P) ≡ P.
• Negating ‘and’: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q — to deny that both hold, one of them must fail.
• Negating ‘or’: ¬(P ∨ Q) ≡ ¬P ∧ ¬Q — to deny that at least one holds, both must fail.
• Negating an implication: ¬(P ⟹ Q) ≡ P ∧ ¬Q — the negation is not another implication.
• Quantifiers swap: ¬(∀x, P(x)) ≡ ∃x such that ¬P(x), and ¬(∃x such that P(x)) ≡ ∀x, ¬P(x).

Worked negation. Negate: “∀ integers n, if n is odd then n² − 1 is divisible by 8.” Swap ∀ for ∃, then negate the implication with P ∧ ¬Q: “∃ an integer n such that n is odd and n² − 1 is not divisible by 8.” Proving this negation would need a single odd counterexample; since (2k+1)² − 1 = 4k(k+1) and k(k+1) is even, no such n exists, so the original statement is true.

Proof by contradiction and irrationality

In proof by contradiction you assume the statement is false, then derive an impossibility. The standard NESA results are irrationality proofs.

√2 is irrational: suppose √2 = a/b in lowest terms (so a, b share no common factor). Then 2b² = a², so a² is even, hence a is even, a = 2c. Then 2b² = 4c², i.e. b² = 2c², so b is even too — contradicting “lowest terms”. Therefore √2 is irrational. ∎

log₂ 5 is irrational: suppose log₂ 5 = p/q with positive integers p, q. Then 2^(p/q) = 5, so 2^p = 5^q. The left side is even (a power of 2) and the right side is odd (a power of 5) — impossible for positive p, q. Hence log₂ 5 is irrational. ∎