Proof techniques

1. Name the three properties of an equivalence relation.
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

2. |{∅, {∅}}| = ?
   Stuck? Peek at 0.2.1 Sets

   • x ∈ A (element) vs X ⊆ A (subset). ∅ ⊆ every set. A = B ⇔ A ⊆ B and B ⊆ A.
   • A ∪ B, A ∩ B, A − B = A ∩ B̅, A̅ = U − A. De Morgan: (A∪B)̅ = A̅∩B̅, (A∩B)̅ = A̅∪B̅.
   • |A ∪ B| = |A| + |B| − |A ∩ B|. |A × B| = |A|·|B|. |P(A)| = 2^|A|.
   • |∅| = 0, |{∅}| = 1, P(∅) = {∅}.

   Read lesson 0.2.1

3. Which question needs unbounded memory: “contains x?” or “more x’s than y’s?”
   Stuck? Peek at 0.1.1 What “computation” means

   • Machine: reads a finite input symbol by symbol, changes mode, ends with yes (accept) / no (reject) — or may never end.
   • Decision problem: a question whose answer is yes or no for every input.
   • Machines differ by memory: finite modes → pile of plates → endless notebook → beyond all machines.
   • Finite memory works iff the fact you must carry stays bounded (even/odd, remainder, “seen x?”). Unbounded counts/comparisons break it.

   Read lesson 0.1.1

A friend claims: “I built a tiny machine with a fixed number of modes that checks whether brackets are balanced, for any length of code.” You suspect it’s impossible — but suspicion isn’t enough. You need an argument so airtight that it covers every machine anyone could ever build. That is a proof, and TOC questions on GATE regularly ask you to recognise which proof pattern is being used.

Statement: “If it rained, the road is wet.” Which of these says exactly the same thing? (a) If the road is wet, it rained. (b) If the road is not wet, it did not rain. (c) If it did not rain, the road is not wet.

Prediction check

Answer: (b). That is the contrapositive, always equivalent to the original. (a) is the converse and (c) is the inverse; both can be false (a tanker could have wet the road).

Implication

When P is false the implication is automatically true (“vacuously true”). P ⇔ Q (“if and only if”, iff) means both P ⇒ Q and Q ⇒ P.

Converse, inverse, contrapositive

• Converse: Q ⇒ P. Not equivalent.
• Inverse: not P ⇒ not Q. Not equivalent (it is the converse’s contrapositive).
• Contrapositive: not Q ⇒ not P. Always equivalent to P ⇒ Q.

Why it matters: a famous TOC theorem has the shape “if a language is handled by a finite-memory machine, then property X holds.” We use its contrapositive: “if property X fails, then no finite-memory machine handles it.” That is how we prove limits.

Direct proof

Assume P, chain true steps, arrive at Q. Example: “if n is even then n² is even”: n = 2k ⇒ n² = 4k² = 2(2k²), even. ∎

Proof by contradiction

To prove S: assume S is false, deduce something impossible, conclude S must be true.

Classic: there are infinitely many primes. Suppose only finitely many: p₁,…,pₖ. Let N = p₁·p₂···pₖ + 1. Dividing N by any pᵢ leaves remainder 1, so no pᵢ divides N; but N > 1 has some prime factor — a prime not in our “complete” list. Contradiction. ∎

Almost every “no machine can do this” proof in TOC is a proof by contradiction: suppose a machine exists… then something impossible follows.

Counterexample

To show a claim “for all x, …” is false, one example where it fails is enough. To show it is true, examples are never enough — you need a proof.

Mathematical induction

To prove a statement S(n) for all n ≥ 0:

1. Base case: prove S(0).
2. Inductive step: assume S(k) (the inductive hypothesis), prove S(k+1).

Like dominoes: the first falls, and each one knocks the next. Example: 1 + 2 + … + n = n(n+1)/2. Base n=1: 1 = 1·2/2 ✓. Step: (1+…+k) + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓. ∎

Strong induction assumes S(0),…,S(k) all hold to prove S(k+1). Later we will induct on the length of the input to prove a machine is correct: “after reading any k symbols the machine is in the right mode”.

Putting it together

• Only the contrapositive (¬Q ⇒ ¬P) is equivalent to P ⇒ Q; converse and inverse are traps.
• Impossibility proofs assume the machine exists, then reach a contradiction.
• Induction = base case + step; you will induct on input length to prove machines correct.

       P ⇒ Q  ≡  ¬Q ⇒ ¬P            (contrapositive — SAME meaning)
       Q ⇒ P  ≡  ¬P ⇒ ¬Q            (converse ≡ inverse — a DIFFERENT statement)

 Proof by contradiction            Induction (dominoes)
 ┌──────────────────────┐          S(0) ─► S(1) ─► S(2) ─► S(3) ─► ...
 │ assume NOT S         │           ▲       each arrow = "S(k) ⇒ S(k+1)"
 │      ⋮ valid steps   │         base
 │ reach impossibility  │
 │ ∴ S is true          │
 └──────────────────────┘

We now have the logic to prove limits. One counting fact powers the most famous limit proof in this subject: if you have more items than boxes, two items share a box. That’s the pigeonhole principle — next.

1. MCQ

   Which is logically equivalent to “If x is in A, then x is in B”?

   1. If x is in B, then x is in A
   2. If x is not in B, then x is not in A
   3. If x is not in A, then x is not in B
   4. x is in A and x is in B
2. MCQ

   P ⇒ Q is false exactly when:

   1. P false, Q false
   2. P false, Q true
   3. P true, Q false
   4. P true, Q true
3. MSQ

   Which arguments are valid?

   1. P ⇒ Q, P; therefore Q
   2. P ⇒ Q, ¬Q; therefore ¬P
   3. P ⇒ Q, Q; therefore P
   4. P ⇒ Q, ¬P; therefore ¬Q
4. NAT

   In an induction proof that S(n) holds for all n ≥ 3, what value of n does the base case check?

   Write your answer before opening the key.

5. MCQ

   A proof begins “Suppose such a machine exists with k modes…” and ends “…which is impossible.” Which technique is it?

   1. Direct proof
   2. Induction
   3. Contradiction
   4. Counterexample

• implication P ⇒ Q
• if and only if ⇔
• converse, inverse, contrapositive
• vacuous truth
• direct proof
• proof by contradiction
• counterexample
• mathematical induction (base case, inductive step, hypothesis)
• strong induction

1. Which statement is equivalent to P ⇒ Q?
   Reveal answer

   Its contrapositive ¬Q ⇒ ¬P.
2. When is P ⇒ Q false?
   Reveal answer

   Only when P is true and Q is false.
3. Two parts of an induction proof?
   Reveal answer

   Base case, and inductive step (assume S(k), prove S(k+1)).
4. From “P ⇒ Q” and “Q”, can you conclude P?
   Reveal answer

   No — that is the converse error.