Isabelle/HOL — Interactive Theorem Proving

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

Isabelle/HOL is a powerful interactive theorem prover based on higher-order logic, widely used for Formal Verification of software, hardware, and mathematical theorems.

Learning Path

flowchart LR
  A["Theorem Proving"] --> B["Isabelle/HOL
Interactive Proving"]
  B --> C["Coq Proof Assistant"]
  B --> D["Industrial Formal Verification"]
  style B fill:#f90,color:#fff,stroke-width:2px

Prerequisites

Higher-order logic basics. Familiarity with Functional Programming (ML, Haskell).

What Is Isabelle/HOL?

Isabelle is a generic proof assistant. Its most popular instantiation is Isabelle/HOL (Higher-Order Logic). HOL extends first-order logic with function types, quantifiers over functions, and type variables.

Isabelle provides two proof styles: apply-style (tactic-based, like Coq) and Isar (structured, human-readable proofs).

Step-by-Step: First Isabelle Proof

Step 1: Define a Theory

theory FirstProof
imports Main
begin

theorem add_comm: "n + m = m + n"
  apply(induction n)
   apply(auto)
  done

end

Step 2: Understand Structured Isar Proofs

theorem add_comm_isar: "n + m = m + n"
proof (induction n)
  case 0
  show "0 + m = m + 0" by simp
next
  case (Suc n)
  assume IH: "n + m = m + n"
  show "Suc n + m = m + Suc n"
    by (simp add: IH)
qed

Step 3: Python Equivalent

def add(n, m):
    if n == 0:
        return m
    return 1 + add(n - 1, m)

def test_add_comm(n, m):
    return add(n, m) == add(m, n)

# Test for first 20 numbers
all_pass = all(test_add_comm(n, m) for n in range(20) for m in range(20))
print(f"Commutativity holds for n,m in 0..19: {all_pass}")

Expected output:

Commutativity holds for n,m in 0..19: True

Step-by-Step: Using Locales

Locales enable modular, parameterized reasoning.

Step 1: Define a Locale

locale semigroup =
  fixes f :: "'a => 'a => 'a"
  assumes assoc: "f (f x y) z = f x (f y z)"

locale monoid = semigroup +
  fixes e :: "'a"
  assumes left_neutral: "f e x = x"
    and right_neutral: "f x e = x"

Step 2: Instantiate the Locale

interpretation int_addition: monoid "(+)" "0"
  by standard auto

Step 3: Python Explanation

class Semigroup:
    def __init__(self, op):
        self.op = op

    def check_assoc(self, x, y, z):
        return self.op(self.op(x, y), z) == self.op(x, self.op(y, z))

class Monoid(Semigroup):
    def __init__(self, op, identity):
        super().__init__(op)
        self.identity = identity

    def check_left_neutral(self, x):
        return self.op(self.identity, x) == x

    def check_right_neutral(self, x):
        return self.op(x, self.identity) == x

int_add = Monoid(lambda a, b: a + b, 0)
print(f"Associative: {int_add.check_assoc(1, 2, 3)}")
print(f"Left neutral: {int_add.check_left_neutral(5)}")

Expected output:

Associative: True
Left neutral: True

Step-by-Step: Code Generation

Isabelle generates executable code from verified definitions:

fun fibonacci :: "nat => nat" where
  "fibonacci 0 = 0"
| "fibonacci (Suc 0) = 1"
| "fibonacci (Suc (Suc n)) = fibonacci n + fibonacci (Suc n)"

export_code fibonacci in Haskell

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 2) + fibonacci(n - 1)

print(f"fibonacci(10) = {fibonacci(10)}")

Expected output:

fibonacci(10) = 55

Common Errors

1. Forgetting done or qed

Every proof must end with a closing command. Isabelle will wait for closure indefinitely.

2. Wrong Case Name in Induction

In Isar proofs, use the case name as generated (0, Suc, etc.). Custom names require the case directive.

3. Using auto Too Aggressively

auto combines rewriting and simplification. It can diverge or produce unintended proofs. Use simpler tactics (simp, blast) first.

4. Non-Terminating Function Definitions

Isabelle accepts only terminating functions. Use fun (which attempts termination proof) or provide a termination measure with function.

5. Locale Import Conflicts

When using multiple locales, be aware of overlapping parameters. Use sublocale or subclass for proper inheritance.

Practice Questions

Q1: What is the difference between apply and proof in Isabelle?

apply starts a tactic-style proof. proof starts a structured Isar proof. Isar is more readable for complex proofs.

Q2: What are locales in Isabelle?

Locales are parameterized contexts that support modular reasoning and theory reuse.

Q3: How does Isabelle ensure logical consistency?

Isabelle uses the LCF approach: a small trusted kernel checks all proofs. Even sophisticated tactics produce kernel-verifiable proofs.

Q4: What is sledgehammer?

A tactic that calls external automated provers (E, SPASS, Vampire, Z3) and translates their results into Isabelle proofs.

Q5: What is the seL4 project?

A formally verified microkernel where all kernel code is proven correct in Isabelle/HOL, up to the ARM architecture model.

Challenge

Define a locale for a group (monoid with inverse). Instantiate it for integer addition and for boolean xor. Prove the group properties in Isabelle. Generate Haskell code for the boolean xor group.

FAQ

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