Skip to content

Tactics

A proof written after by is a sequence of tactics, each of which changes the goal, what is left to prove, until nothing is left. Put your cursor after any tactic and the infoview shows the goal at that point. This page lists the tactics this course uses, each with a small example that Lean checks.

Finishing a goal

rfl: both sides are the same once worked out.

example : 2 + 3 = 5 := by rfl

decide: Lean works out whether the statement is true, which needs it to be about finitely many cases (every player in Fin 2, say).

example : ∀ p : Fin 2, other p ≠ p := by decide

exact: here is the proof, exactly. Often a theorem applied to arguments.

example (a b : Nat) : a ≤ a + b := by exact Nat.le_add_right a b

constructor: for a goal A and B (or A if and only if B), make one goal for each part.

example : 1 < 2 ∧ 2 < 3 := by
  constructor
  · decide
  · decide

left / right: for a goal A or B, choose which side to prove.

example : 1 = 2 ∨ 2 = 2 := by
  right
  rfl

omega: solves arithmetic over whole numbers: +, -, <, ≤, multiplying by a constant, % and / by a constant. It uses the hypotheses in sight.

example (a b : Nat) (h : a < b) : a + 1 ≤ b := by omega

Changing the goal

intro: for a goal for every x, … or if A then …, take the x (or the assumption A) and name it.

example : ∀ n : Nat, n + 0 = n := by
  intro n
  rfl

rw: rewrite with an equation: replace its left side by its right side in the goal. rw [← e] rewrites right to left. It tries rfl afterwards.

example (a b : Nat) (same : a = b) : a + 1 = b + 1 := by
  rw [same]

subst: given a hypothesis x = e (or e = x) about a variable, replace the variable everywhere and drop the hypothesis.

example (a b : Nat) (same : a = b) (h : a > 3) : b > 3 := by
  subst same
  exact h

unfold: replace a definition's name with its body.

example (h : Hand) : h.size = h.down.length + h.up.length := by
  unfold Hand.size
  rfl

show: restate the goal in a form Lean agrees is the same, usually to make the next step clearer.

example (n : Nat) : n + 0 = n := by
  show n = n
  rfl

Simplifying

simp: simplify the goal using a large library of rewriting facts, plus any you list in brackets (simp [step, finished]). It often finishes the goal by itself. simp at h simplifies a hypothesis instead.

example (xs : List Nat) : (xs ++ []).length = xs.length := by simp

simp only [...]: simplify with only the facts listed, nothing from the library. Slower to write than simp, but it does exactly what it says, so a proof doesn't change when the library does. ↓reduceIte in such a list settles an if whose condition is known.

example (h : Hand) : (recycle h).size = h.size := by
  simp only [recycle]
  split <;> simp_all [Hand.size]

simp_all: simplify the goal and every hypothesis, using each to simplify the others.

example (a b : Nat) (h1 : a = 2) (h2 : b = a + 1) : b = 3 := by simp_all

simpa using e: simplify both the goal and e, then use e to finish.

example (xs : List Nat) (h : (xs ++ []).length = 3) : xs.length = 3 := by
  simpa using h

Splitting into cases

split: split on the if or match in the goal, one goal per branch. Each new goal starts with ·.

example (h : Hand) : (recycle h).up = [] ∨ recycle h = h := by
  unfold recycle
  split
  · exact .inl rfl
  · exact .inr rfl

split at h: the same, for an if or match in a hypothesis.

example (n : Nat) (h : (if n = 0 then 1 else 2) = 2) : n ≠ 0 := by
  split at h
  · simp at h
  · assumption

rename_i: give names to the hypotheses a tactic left unnamed (shown with a ✝ in the infoview), such as the condition split assumed.

example (n : Nat) : (if n = 0 then 1 else n) ≥ 1 := by
  split
  · decide
  · rename_i nonzero
    omega

match: split on the possible values of something.

example (p : Fin 2) : other (other p) = p := by
  match p with
  | 0 => rfl
  | 1 => rfl

cases … with: split on the constructors of a value, naming what each carries. On a hypothesis that no constructor can match (say 0 = 1), it leaves no cases at all, which finishes the goal.

example (o : Option Nat) : o.getD 0 ≥ 0 := by
  cases o with
  | none => decide
  | some n => simp
example (p : Fin 2) (h : p = 0) (h' : p = 1) : False := by
  subst h
  cases h'

by_cases: split on whether a statement is true, naming it in each case.

example (n : Nat) : n % 2 = 0 ∨ n % 2 = 1 := by
  by_cases even : n % 2 = 0
  · exact .inl even
  · exact .inr (by omega)

induction: prove something for every list (or number) from the empty case and the step case, with the fact for the shorter list available as the induction hypothesis.

example (xs : List Nat) : (xs.map id).length = xs.length := by
  induction xs with
  | nil => rfl
  | cons x rest ih => simp

Facts in and out

have: prove a fact on the way and name it.

example (a : Nat) (h : a > 3) : a ≠ 0 := by
  have positive : a > 0 := by omega
  omega

obtain: take a fact apart: the witness and property of an ∃, the two halves of an ∧, or the cases of an ∨.

example (n : Nat) (h : ∃ k, n = 2 * k) : n % 2 = 0 := by
  obtain ⟨k, twice⟩ := h
  omega

rcases: like obtain, with patterns; rfl as a pattern substitutes the equation it matches.

example (n : Nat) (h : ∃ k, n = k + 1) : n ≠ 0 := by
  rcases h with ⟨k, rfl⟩
  omega

refine: give the shape of the proof, with ?_ for the holes, each of which becomes a goal.

example : 1 < 2 ∧ 2 < 3 := by
  refine ⟨?_, ?_⟩
  · decide
  · decide

Combining tactics

t <;> u: run t, then u on every goal t made.

example : 1 < 2 ∧ 2 < 3 := by
  constructor <;> decide

↔, .mp and .mpr: if and only if. Prove it with constructor, one direction each; use a proof h of A ↔ B as h.mp (from A to B) or h.mpr (back).

example (n : Nat) : n + 1 = 1 ↔ n = 0 := by
  constructor
  · intro h; omega
  · intro h; rw [h]

Not in this project's proofs

sorry and admit stand in for a missing proof, and native_decide trusts compiled code instead of Lean's checker. All three are explained in What you have to trust; make proofs refuses every one of them.