# Baby’s First Proof

Unlike many languages that you learn, in Coq, things are truly different. Much like your first functional language after using nothing but imperative languages, you have to re-evaluate things. Instead of just defining functions, you have to *prove* properties of them. So, let’s take a look at a few basic ways to do that.

## Simpl and Reflexivity

Here we have two basic “tactics” that we can use to prove simple properties. Suppose we have some function `addition`

. We’re all familiar with how this works; `2 + 2 = 4`

, right? Prove it:

```
Lemma two_plus_two:
2 + 2 = 4.
Proof.
Admitted.
```

First, what is this `Admitted.`

thing? Admitted basically tells Coq not to worry about it, and just assume it is true. This is the equivalent of your math professor telling you “don’t worry about it, Aristotle says it’s true, are you calling Aristotle a liar?” and if you let this make it into live code, you are a bad person. We must make this right!

```
Lemma two_plus_two:
2 + 2 = 4.
Proof.
simpl.
reflexivity.
Qed.
```

That’s better. This is a simple proof; we tell Coq to simplify the expression, then we tell Coq to verify that the left-hand-side is the same as the right-hand-side. One nice feature of Coq is that lets you step through these proofs to see exactly how the evaluation is proceeding. If you’re using Proof General, you can use the buttons `Next`

, `Goto`

, and `Undo`

to accomplish this. If you put the point at `Proof.`

and click `Goto`

, Coq will evaluate the buffer up to that point, and a window should appear at the bottom with the following:

```
1 subgoals, subgoal 1 (ID 2)
============================
2 + 2 = 4
```

This is telling you that Coq has 1 thing left to prove: ` 2 + 2 = 4`

. Click next, the bottom should change to:

```
1 subgoals, subgoal 1 (ID 2)
============================
4 = 4
```

Coq processed the `simpl`

tactic and now the thing it needs to prove is that `4 = 4`

. Obviously this is true, so if we click next…

`No more subgoals.`

…`reflexivity`

should succeed, and it does. If we click next one more time:

`two_plus_two is defined`

This says that this Lemma has been defined, and we can now refer to it in other proofs, much like we can call a function. Now, you may be wondering “do I really have to simplify `2 + 2`

?” No, you don’t, `reflexivity`

will simplify on it’s own, this typechecks just fine:

```
Lemma two_plus_two:
2 + 2 = 4.
Proof.
reflexivity.
Qed.
```

So, what’s the point of `simpl`

then? Let’s consider a more complicated proof.

## Induction

```
Lemma n_plus_zero_eq_n:
forall (n : nat), n + 0 = n.
```

This lemma state that for any n, n + 0 = n. This is the same as when you’d write `∀`

in some math. Other bits of new syntax is `n : nat`

, which means that n has the type nat. The idea here is that no matter what natural number n is, n + 0 = n. So how do we prove this? One might be tempted to try:

```
Lemma n_plus_zero_eq_n:
forall (n : nat), n + 0 = n.
Proof.
reflexivity.
Qed.
```

One would be wrong. What is Coq stupid? Clearly n + 0 = n, Aristotle told me so! Luckily for us, this is a pretty easy proof, we just need to be explicit about it. We can use induction to prove this. Let me show the whole proof, then we’ll walk through it step by step.

```
Lemma n_plus_zero_eq_n:
forall (n : nat), n + 0 = n.
Proof.
intros n.
induction n as [| n'].
{
reflexivity.
}
{
simpl.
rewrite -> IHn'.
reflexivity.
}
Qed.
```

Place the point at `Proof`

and you’ll see the starting goal:

```
1 subgoals, subgoal 1 (ID 6)
============================
forall n : nat, n + 0 = n
```

Click next and step over `intros n.`

```
1 subgoals, subgoal 1 (ID 7)
n : nat
============================
n + 0 = n
```

What happened here is `intros n`

introduces the variable n, and names it n. We could have done `intros theNumber`

and the bottom window would instead show:

```
1 subgoals, subgoal 1 (ID 7)
theNumber : nat
============================
theNumber + 0 = theNumber
```

The `intros`

tactic reads from left to right, so if we had some `Lemma foo : forall (n m : nat), [stuff]`

, we could do `intros nName mName.`

, and it would read in n, and bind it to nName, and then read in m and bind it to mName. Click next and evaluate `induction n as [| n'].`

```
2 subgoals, subgoal 1 (ID 10)
============================
0 + 0 = 0
subgoal 2 (ID 13) is:
S n' + 0 = S n'
```

The `induction`

tactic implements the standard proof by induction, splitting our goal into two goals: the base case and the n + 1 case. Similarly to `intros`

, this will create subgoals starting with the first constructor of an ADT, and ending with the last.

## On Natural Numbers in Coq

Let us take a second to talk about how numbers are represented in Coq. Coq re-implements all types within itself, so `nat`

isn’t a machine integer, it’s an algebraic datatype of the form:

```
Inductive nat : Set :=
| O : nat
| S : nat -> nat.
```

`O`

is zero, `S O`

is one, and `S (S (S (O)))`

is three. There is a lot of syntax sugar in place that lets you write 49 instead of `S (S ( ... ( S O) ... ))`

, and that’s a good thing.

The point of all of this is that we can pattern match on `nat`

much like we can a list.

## More Induction

…anyways, all this brings us back to induction and this mysterious `as [| n'].`

What this is doing is binding names to all the fields of the ADT we are deconstructing. The `O`

constructor takes no parameters, so there is nothing to the left of the `|`

. The `S`

constructor takes a `nat`

, so we give it the name `n'`

. Click next and observe the bottom change:

```
1 focused subgoals (unfocused: 1)
, subgoal 1 (ID 10)
============================
0 + 0 = 0
```

The curly braces “focuses” the current subgoal, hiding all irrelevant information. Curly braces are optional, but I find them to be very helpful as the bottom window can become very cluttered in large proofs. Here we see the base case goal being to prove that 0 + 0 = 0. Obviously this is true, and we can have Coq verify this by `reflexivity.`

Click next until the next opening curly brace is evaluated. We see the next subgoal:

```
1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 13)
n' : nat
IHn' : n' + 0 = n'
============================
S n' + 0 = S n'
```

So, what do we have here? This is the n + 1 case; here the n’ in `S n'`

is the original n. A particularly bored reader may try to prove `forall (n : nat), S n = n + 1`

and I’ll leave that as an exercise. However, this follows from the definition of `nat`

.

Also of note here is `IHn'`

. `IH`

stands for induction hypothesis, and this is that n’ + 0 = n’. So, how do we proceed? Click next and observe how the subgoal changes:

```
1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 15)
n' : nat
IHn' : n' + 0 = n'
============================
S (n' + 0) = S n'
```

It brought the `+ 0`

inside the `S`

constructor. Notice that now there is `n' + 0`

on the left hand side. Click next and watch closely what happens:

```
1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 16)
n' : nat
IHn' : n' + 0 = n'
============================
S n' = S n'
```

Here we use the induction hypothesis to rewrite all occurrences of `n' + 0`

, which was the left hand side of the induction hypothesis as `n'`

, which was the right hand side of the induction hypothesis. This is what the `rewrite`

tactic does. Notice now that the subgoal is `S n' = S n'`

which `reflexivity`

will surely find to be true. So, what would happen if we had done `rewrite <- IHn'.`

?

```
1 focused subgoals (unfocused: 0)
, subgoal 1 (ID 16)
n' : nat
IHn' : n' + 0 = n'
============================
S (n' + 0 + 0) = S (n' + 0)
```

It rewrote all instances of `n'`

, which was the right hand side of the induction hypothesis with `n' + 0`

which was the left hand side of the induction hypothesis. Obviously, this isn’t what we want. I should note that you can undo this by rewriting to the right twice…

```
{
simpl.
rewrite <- IHn'.
rewrite -> IHn'.
rewrite -> IHn'.
reflexivity.
}
```

…and it will technically work. But don’t do this, it’s silly and there’s no room for silliness in a rigorous mathematical proof.

Personally, I have a hard time keeping it straight what the left and right rewrites do. I sometimes find myself just trying one, and then the other if I guessed wrong. Think of it like this: `rewrite -> foo`

rewrites the current goal, replacing all occurrences of the thing on the left hand side of the equation of `foo`

with the thing on the right hand side of the equation. It changes *from* the left *to* the right. And vice-versa for `rewrite <-`

, which changes *from* the right *to* the left.