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.
Theorems¶
theorem is def for proofs: it names a statement and its proof, so other
proofs can use it.
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:
unfold recyclereplacesrecycle hwith its definition, anif.splitsplits the goal in two: the case where theifis true, and the case where it's false. The dots·mark the proof of each case.- When the stack was empty, the new stack is the old face-up pile reversed.
simp_all [Hand.size]simplifies: it unfoldsHand.size, uses facts it knows (a reversed list has the same length; an empty list has length 0), and finishes the goal. - When it wasn't empty,
recyclegives back the hand unchanged, andrflfinishes.
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, namedfinished. Naming hypotheses after what they say makes proofs readable. - The conclusion, after the colon.
∃ reason, step s a act = .error reasonreads there is a reason such thatsteprefuses with it. (∃is there exists; type\ex.) - The proof.
stepchecks the phase before anything else, sosimp, told aboutstepand the hypothesisfinished, 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¶
- Prove that
other p ≠ pfor every player. (≠is not somethingrflcan prove. Trydecidein each case.) - Prove that if the first player's face-up pile is empty, there is no match.
Hint:
unfold State.isMatch, then use the hypothesis withrw. - Prove that a freshly dealt game is being played. Try
rflfirst: 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.