Theorem Proving — Induction, Tactics and Proof Assistants

In this tutorial, you'll learn about Theorem Proving. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Theorem Proving uses axioms and inference rules to construct formal proofs of program correctness, providing the highest level of assurance for critical software.

Learning Path

flowchart LR
  A["First-Order Logic"] --> B["Theorem Proving
Induction & Tactics"]
  B --> C["Coq Proof Assistant"]
  B --> D["Isabelle/HOL"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Propositional and first-order logic. Basic Functional Programming concepts.

What Is Theorem Proving?

Theorem Proving constructs a chain of logical deductions from axioms to the desired theorem. Each step applies an inference rule. A proof assistant checks every step mechanically.

Unlike Model Checking (automatic but limited to finite state), Theorem Proving can handle infinite-state systems but requires human guidance.

Step-by-Step: Natural Deduction

Step 1: Write the Sequent

A sequent Γ ⊢ φ means "from assumptions Γ, conclude φ".

p → q, p ⊢ q     (modus ponens)

Step 2: Apply Inference Rules

def modus_ponens(assumptions, target):
    # assumptions: dict mapping statement names to formulas
    # Check if p → q and p are both in assumptions
    impl = assumptions.get("p_implies_q")
    ante = assumptions.get("p")
    if impl and ante:
        # Check impl is (ante -> something)
        if impl[0] == "->" and impl[1] == ante:
            print(f"Proved: {impl[2]}")
            return impl[2]
    return None

assumptions = {
    "p_implies_q": ("->", "p", "q"),
    "p": "p"
}
result = modus_ponens(assumptions, "q")

Expected output:

Proved: q

Step-by-Step: Structural Induction

Step 1: Define the Data Type

class Nat:
    def __init__(self, val=None):
        self.val = val  # None for zero, Nat for successor

    @staticmethod
    def zero():
        return Nat(None)

    def succ(self):
        return Nat(self)

def to_int(n):
    if n.val is None:
        return 0
    return 1 + to_int(n.val)

Step 2: State the Theorem

Prove that add(n, zero()) = n for all n.

Step 3: Base Case

def add(a, b):
    if a.val is None:
        return b
    return Nat.succ(add(a.val, b))

# Base case: add(zero, zero) = zero
base = add(Nat.zero(), Nat.zero())
print(f"Base case: add(0, 0) = {to_int(base)}")

Expected output:

Base case: add(0, 0) = 0

Step 4: Inductive Step

Assume the theorem holds for n (IH: add(n, 0) = n). Prove for succ(n):

# Inductive case: add(succ(n), 0) = succ(add(n, 0)) = succ(n)
def inductive_step(n_val):
    inner = add(n_val, Nat.zero())
    result = Nat.succ(inner)
    return to_int(result)

n_val = Nat.succ(Nat.succ(Nat.zero()))
print(f"add(succ(succ(0)), 0) = {inductive_step(n_val)}")

Expected output:

add(succ(succ(0)), 0) = 2

Proof Tactics

Tactics are commands that transform the proof state. Common tactics:

intros moves assumptions to the context. apply uses a hypothesis or lemma. induction starts a proof by induction. auto attempts automatic proof.

# Simulating tactic-based proof
class ProofState:
    def __init__(self, goal, assumptions=None):
        self.goal = goal
        self.assumptions = assumptions or []

    def intro(self, name):
        # Move antecedent to assumptions
        if self.goal[0] == "->":
            self.assumptions.append((name, self.goal[1]))
            self.goal = self.goal[2]
            print(f"Introduced {name}, new goal: {self.goal}")

    def apply(self, lemma):
        if lemma == self.goal:
            print(f"Goal proved by assumption")

ps = ProofState(("->", "p", "q"), assumptions=[("H", "p")])
ps.intro("H0")

Expected output:

Introduced H0, new goal: q

Common Errors

1. Induction on the Wrong Variable

When proving a property about multiple variables, choosing the wrong one for induction may make the inductive hypothesis too weak.

2. Missing Base Case

Every induction proof needs at least one base case. Skipping it leaves the proof incomplete.

3. Using the Inductive Hypothesis Incorrectly

The IH applies only to smaller structures. Applying it to a larger structure is circular reasoning.

4. Ignored Assumptions

Not all assumptions are valid. Using a false assumption can prove anything (principle of explosion).

5. Wrong Rule Application

Applying an inference rule whose premises are not satisfied. The proof checker catches this, but the proof attempt fails.

Practice Questions

Q1: What is the difference between induction and deduction?

Deduction proves specific from general. Induction proves general from specific patterns (in math: proving P(n) implies P(n+1) for all n).

Q2: What is a proof tactic?

A command that transforms the proof state, breaking a complex goal into simpler subgoals.

Q3: Why does CompCert use Theorem Proving?

CompCert proves that the compiled assembly code behaves exactly as specified by the source C semantics, eliminating an entire class of compiler bugs.

Q4: What is the principle of explosion?

From a contradiction, any statement can be proven. This is why consistency of the logic is essential.

Q5: Can Theorem Proving be fully automated?

No. While SMT solvers automate many subproblems, complex proofs require human insight and guidance.

Challenge

Prove by structural induction that length(append(xs, ys)) = length(xs) + length(ys) for all lists xs and ys. Define your own list data type in Python and write the proof outline.

FAQ

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro.