Skip to content

First proofs

Tests check the cases you try. A proof covers every case at once: every deal, every state, every move. This chapter is about how to write one.

Statements are values too

2 + 2 == 4 is a computation: it works out to the Bool value true. 2 + 2 = 4, with one =, is a statement: a claim, which might be true or false, and which you can prove. Statements have their own type, Prop:

/-- info: true -/
#guard_msgs in
#eval 2 + 2 == 4

/-- info: 2 + 2 = 4 : Prop -/
#guard_msgs in
#check 2 + 2 = 4

To prove a statement is to give a value of that type. That sounds strange, but you've already done it: rfl is a proof that something equals itself, and Lean accepts it as a proof of 2 + 2 = 4 because both sides work out to the same thing.

example : 2 + 2 = 4 := rfl
example : deck.length = 52 := rfl

Theorems

theorem is def for proofs: it names a statement and its proof, so other proofs can use it.

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

Read the statement: for any player p, the other player's other player is p. After := by, the proof is written in tactics: instructions that build the proof step by step. Put your cursor at the end of each line and watch the infoview: it shows the goal, what is still to be proved. Before match, the goal is other (other p) = p. match p with splits it into one goal per player, and in each one other (other 0) works out to 0, so rfl closes it.

A theorem about the rules

Here is a real fact about Snap: turning your face-up pile over to make a new stack never changes how many cards you hold.

/-- Turning the face-up pile over never changes how many cards you hold. -/
theorem recycle_keeps_size (h : Hand) : (recycle h).size = h.size := by
  unfold recycle
  split
  · -- The stack was empty: the face-up pile, reversed, becomes the stack.
    simp_all [Hand.size]
  · -- The stack wasn't empty: nothing changes.
    rfl

Step by step:

  1. unfold recycle replaces recycle h with its definition, an if.
  2. split splits the goal in two: the case where the if is true, and the case where it's false. The dots · mark the proof of each case.
  3. When the stack was empty, the new stack is the old face-up pile reversed. simp_all [Hand.size] simplifies: it unfolds Hand.size, uses facts it knows (a reversed list has the same length; an empty list has length 0), and finishes the goal.
  4. When it wasn't empty, recycle gives back the hand unchanged, and rfl finishes.

You will meet a dozen tactics in this course. The tactics reference lists them all, with examples from the project.

Reading the project's proofs

Snap's guarantees are in Proofs/Snap/Guarantees.lean. Each one opens with a plain-English headline. Here is the shortest:

/-- **A finished game accepts nothing.**

Once someone has won or the game is drawn, every action from every player is
rejected. -/
theorem finished_game_rejects_everything {w : Option (Fin 2)} (finished : s.phase = .finished w)
    (a : Nat) (act : Action) : ∃ reason, step s a act = .error reason := by
  -- `step` checks the phase before anything else.
  simp [step, finished]

The parts:

  • The hypotheses, between brackets before the colon. Each one names something the theorem assumes. (finished : s.phase = .finished w) is the assumption that the game is over, named finished. Naming hypotheses after what they say makes proofs readable.
  • The conclusion, after the colon. ∃ reason, step s a act = .error reason reads there is a reason such that step refuses with it. (∃ is there exists; type \ex.)
  • The proof. step checks the phase before anything else, so simp, told about step and the hypothesis finished, can work out that the answer is an error, whatever the player and move.

Two more, one about each kind of snap:

/-- **A valid snap is never penalised.**

When the top cards match, calling snap never leaves you with fewer cards. -/
theorem valid_snap_never_penalised (s : State) (p : Fin 2) (matched : s.isMatch = true) :
    (s.hand p).size ≤ ((snap s p).1.hand p).size := by
  -- The caller keeps everything they had and gains the other player's face-up pile.
  rw [caller_after_valid_snap s p matched]
  exact Nat.le_add_right _ _

rw [caller_after_valid_snap s p matched] rewrites: it uses an equation proved elsewhere to replace the left side with the right side in the goal. That lemma says what the caller holds after a valid snap:

/-- On a valid snap, the caller's face-up pile is gone and their stack gains
both piles. -/
theorem caller_after_valid_snap (s : State) (p : Fin 2) (matched : s.isMatch = true) :
    ((snap s p).1.hand p).size = (s.hand p).size + (s.hand (other p)).up.length := by
  match p with
  | 0 => simp [snap, matched, State.setHand, State.hand, Hand.size, other]; omega
  | 1 => simp [snap, matched, State.setHand, State.hand, Hand.size, other]; omega

so the goal becomes a ≤ a + b, which is a fact about numbers, and exact Nat.le_add_right _ _ supplies it. exact says this is exactly the proof. Nat.le_add_right is a theorem from Lean's library.

This is the pattern of every larger proof in the project: the guarantee is a short argument, and the mechanical facts it rests on are lemmas in Bookkeeping.lean, proved once.

Theorems are functions

A theorem with hypotheses is a function: give it proofs of its hypotheses, and it gives you a proof of its conclusion. So you can use a guarantee by calling it:

/-- A finished game refuses a flip by player 0. -/
example (s : State) (w : Option (Fin 2)) (over : s.phase = .finished w) :
    ∃ reason, step s 0 .flip = .error reason :=
  Proofs.Snap.finished_game_rejects_everything over 0 .flip

Exercises

  1. Prove that other p ≠ p for every player. (≠ is not something rfl can prove. Try decide in each case.)
  2. Prove that if the first player's face-up pile is empty, there is no match. Hint: unfold State.isMatch, then use the hypothesis with rw.
  3. Prove that a freshly dealt game is being played. Try rfl first: why does it work?
Solution
theorem other_differs (p : Fin 2) : other p ≠ p := by
  match p with
  | 0 => decide
  | 1 => decide

theorem nobody_snaps_an_empty_pile (s : State) (empty : s.hand0.up = []) : s.isMatch = false := by
  unfold State.isMatch
  rw [empty]

theorem fresh_games_are_playing (seed maxFlips : Nat) : (State.deal seed maxFlips).phase = .playing := rfl

The third works by rfl because deal sets no phase, so the field keeps its default, .playing, and Lean sees that by working out the definition.