Exercise session 1 — Solutions

Authors:

Yannick Forster

Théo Winterhalter

Files:

Try to solve the following exercises by using the tactics shown in class:

intro, apply, destruct, split, left, right, exfalso, simpl, reflexivity,
f_equal, induction, assumption.

When a lemma ends with the keyword Admitted, it means the lemma is accepted and can be used without a proof. When solving exercises, replace Admitted with Qed once you have completed the proofs.

There are more exercises than what can be done in the exercise session during the lecture. Proving is like programming: You will have to practice at home. It is fine not to do all the exercises, but you should feel like you could do the exercises. We will help you with this assessment at the start of every lecture.

We will begin with the exercises you have seen already.

Set Default Goal Selector "!".

Exercise: Implication

P: Prop

P -> P
P: Prop

P -> P
P: Prop
h: P

P
apply h. Qed.

Exercise: Conjunction

P, Q: Prop

P /\ Q -> Q /\ P
P, Q: Prop

P /\ Q -> Q /\ P
P, Q: Prop
h: P /\ Q

Q /\ P
P, Q: Prop
hP: P
hQ: Q

Q /\ P
P, Q: Prop
hP: P
hQ: Q

Q
P, Q: Prop
hP: P
hQ: Q
P
P, Q: Prop
hP: P
hQ: Q

Q
apply hQ.
P, Q: Prop
hP: P
hQ: Q

P
apply hP. Qed.

Exercise: Disjunction

P, Q: Prop

P \/ Q -> Q \/ P
P, Q: Prop

P \/ Q -> Q \/ P
P, Q: Prop
h: P \/ Q

Q \/ P
P, Q: Prop
hP: P

Q \/ P
P, Q: Prop
hQ: Q
Q \/ P
P, Q: Prop
hP: P

Q \/ P
P, Q: Prop
hP: P

P
apply hP.
P, Q: Prop
hQ: Q

Q \/ P
P, Q: Prop
hQ: Q

Q
apply hQ. Qed.

Exercise: Truth


True
split. Qed.

Exercise: Ex falso

P: Prop

False -> P
P: Prop

False -> P
P: Prop
h: False

P
destruct h. Qed.

Exercise: Negation

~ A (negation) is a notation for A -> False below.


~ False

~ False
h: False

False
apply h. Qed.

Exercise: Propositional logic

Now some new exercises about propositional logic.

P, Q, R: Prop

(P -> Q) -> (Q -> R) -> P -> R
P, Q, R: Prop

(P -> Q) -> (Q -> R) -> P -> R
P, Q, R: Prop
hPQ: P -> Q

(Q -> R) -> P -> R
P, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R

P -> R
P, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R
hP: P

R
P, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R
hP: P

Q
P, Q, R: Prop
hPQ: P -> Q
hQR: Q -> R
hP: P

P
apply hP. Qed.
P: Prop

P -> ~ ~ P
P: Prop

P -> ~ ~ P
P: Prop
hP: P

~ ~ P
P: Prop
hP: P
hnP: ~ P

False
P: Prop
hP: P
hnP: ~ P

P
apply hP. Qed.

For this one, note that if you already separated a case distinction with dashes (-) then you can use + at the next level. The following level is marked with *.

P, Q, R: Prop

(P \/ Q) /\ R -> P /\ R \/ Q /\ R
P, Q, R: Prop

(P \/ Q) /\ R -> P /\ R \/ Q /\ R
P, Q, R: Prop
h: (P \/ Q) /\ R

P /\ R \/ Q /\ R
P, Q, R: Prop
hPQ: P \/ Q
hR: R

P /\ R \/ Q /\ R
P, Q, R: Prop
hP: P
hR: R

P /\ R \/ Q /\ R
P, Q, R: Prop
hQ: Q
hR: R
P /\ R \/ Q /\ R
P, Q, R: Prop
hP: P
hR: R

P /\ R \/ Q /\ R
P, Q, R: Prop
hP: P
hR: R

P /\ R
P, Q, R: Prop
hP: P
hR: R

P
P, Q, R: Prop
hP: P
hR: R
R
P, Q, R: Prop
hP: P
hR: R

P
apply hP.
P, Q, R: Prop
hP: P
hR: R

R
apply hR.
P, Q, R: Prop
hQ: Q
hR: R

P /\ R \/ Q /\ R
P, Q, R: Prop
hQ: Q
hR: R

Q /\ R
P, Q, R: Prop
hQ: Q
hR: R

Q
P, Q, R: Prop
hQ: Q
hR: R
R
P, Q, R: Prop
hQ: Q
hR: R

Q
apply hQ.
P, Q, R: Prop
hQ: Q
hR: R

R
apply hR. Qed.
P: Prop

P /\ ~ P -> False
P: Prop

P /\ ~ P -> False
P: Prop
h: P /\ ~ P

False
P: Prop
hP: P
hnP: ~ P

False
P: Prop
hP: P
hnP: ~ P

P
apply hP. Qed.
P, Q: Prop

P \/ ~ P -> ((P -> Q) -> P) -> P
P, Q: Prop

P \/ ~ P -> ((P -> Q) -> P) -> P
P, Q: Prop
lem: P \/ ~ P

((P -> Q) -> P) -> P
P, Q: Prop
lem: P \/ ~ P
h: (P -> Q) -> P

P
P, Q: Prop
hP: P
h: (P -> Q) -> P

P
P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
P
P, Q: Prop
hP: P
h: (P -> Q) -> P

P
apply hP.
P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P

P
P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P

P -> Q
P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
hP: P

Q
P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
hP: P

False
P, Q: Prop
hnP: ~ P
h: (P -> Q) -> P
hP: P

P
apply hP. Qed.
P: Prop

P \/ ~ P -> ~ ~ P -> P
P: Prop

P \/ ~ P -> ~ ~ P -> P
P: Prop
lem: P \/ ~ P

~ ~ P -> P
P: Prop
lem: P \/ ~ P
hnnP: ~ ~ P

P
P: Prop
hP: P
hnnP: ~ ~ P

P
P: Prop
hnP: ~ P
hnnP: ~ ~ P
P
P: Prop
hP: P
hnnP: ~ ~ P

P
assumption.
P: Prop
hnP: ~ P
hnnP: ~ ~ P

P
P: Prop
hnP: ~ P
hnnP: ~ ~ P

False
P: Prop
hnP: ~ P
hnnP: ~ ~ P

~ P
apply hnP. Qed.

To introduce several variables at once, you can use the intros tactic.

P, Q: Prop

(P -> Q) -> ~ ~ P -> ~ ~ Q
P, Q: Prop

(P -> Q) -> ~ ~ P -> ~ ~ Q
P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P

~ ~ Q
P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q

False
P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q

~ P
P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q
hP: P

False
P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q
hP: P

Q
P, Q: Prop
hPQ: P -> Q
hnnP: ~ ~ P
hnQ: ~ Q
hP: P

P
apply hP. Qed.

Exercise: Booleans

Let us switch to Booleans again.

andb is conjunction, orb is disjunction, negb is negation. Both andb and orb look at the first Boolean before simplifying.

b1, b2, b3: bool

(b1 && (b2 || b3))%bool = (b1 && b2 || b1 && b3)%bool
b1, b2, b3: bool

(b1 && (b2 || b3))%bool = (b1 && b2 || b1 && b3)%bool
b2, b3: bool

(true && (b2 || b3))%bool = (true && b2 || true && b3)%bool
b2, b3: bool
(false && (b2 || b3))%bool = (false && b2 || false && b3)%bool
b2, b3: bool

(true && (b2 || b3))%bool = (true && b2 || true && b3)%bool
b2, b3: bool

(b2 || b3)%bool = (b2 || b3)%bool
reflexivity.
b2, b3: bool

(false && (b2 || b3))%bool = (false && b2 || false && b3)%bool
b2, b3: bool

false = false
reflexivity. Qed.
b1, b2: bool

negb (b1 && b2) = (negb b1 || negb b2)%bool
b1, b2: bool

negb (b1 && b2) = (negb b1 || negb b2)%bool
b2: bool

negb (true && b2) = (negb true || negb b2)%bool
b2: bool
negb (false && b2) = (negb false || negb b2)%bool
b2: bool

negb (true && b2) = (negb true || negb b2)%bool
b2: bool

negb b2 = negb b2
reflexivity.
b2: bool

negb (false && b2) = (negb false || negb b2)%bool
b2: bool

true = true
reflexivity. Qed.

Exercise: Computation

Let us switch to natural numbers.


12 + 3 = 15

12 + 3 = 15

15 = 15
reflexivity. Qed.

Exercise: Addition

Let us make a lemma out of the n + 0 = n property.

You can then apply this lemma by using apply n_plus_0 like for hypotheses!

n: nat

n + 0 = n
n: nat

n + 0 = n

0 + 0 = 0
n: nat
IHn: n + 0 = n
S n + 0 = S n

0 + 0 = 0

0 = 0
reflexivity.
n: nat
IHn: n + 0 = n

S n + 0 = S n
n: nat
IHn: n + 0 = n

S (n + 0) = S n
n: nat
IHn: n + 0 = n

n + 0 = n
assumption. Qed.
n: nat

n + n = 2 * n
n: nat

n + n = 2 * n
n: nat

n + n = n + (n + 0)
n: nat

n = n + 0
n: nat

n = n
reflexivity. Qed.
n, m: nat

n + S m = S n + m
n, m: nat

n + S m = S n + m
m: nat

0 + S m = 1 + m
n, m: nat
ih: n + S m = S n + m
S n + S m = S (S n) + m
m: nat

0 + S m = 1 + m
m: nat

S m = S m
reflexivity.
n, m: nat
ih: n + S m = S n + m

S n + S m = S (S n) + m
n, m: nat
ih: n + S m = S n + m

S (n + S m) = S (S (n + m))
n, m: nat
ih: n + S m = S n + m

n + S m = S (n + m)
apply ih. Qed.
n, m: nat

n + m = m + n
n, m: nat

n + m = m + n
m: nat

0 + m = m + 0
n, m: nat
IHn: n + m = m + n
S n + m = m + S n
m: nat

0 + m = m + 0
m: nat

m = m + 0
m: nat

m = m
reflexivity.
n, m: nat
IHn: n + m = m + n

S n + m = m + S n
n, m: nat
IHn: n + m = m + n

S (n + m) = m + S n
n, m: nat
IHn: n + m = m + n

S (n + m) = S m + n
n, m: nat
IHn: n + m = m + n

S (n + m) = S (m + n)
n, m: nat
IHn: n + m = m + n

n + m = m + n
assumption. Qed.

Show associativity of addition.

k, n, m: nat

k + n + m = k + (n + m)
k, n, m: nat

k + n + m = k + (n + m)
n, m: nat

0 + n + m = 0 + (n + m)
k, n, m: nat
IHk: k + n + m = k + (n + m)
S k + n + m = S k + (n + m)
n, m: nat

0 + n + m = 0 + (n + m)
n, m: nat

n + m = n + m
reflexivity.
k, n, m: nat
IHk: k + n + m = k + (n + m)

S k + n + m = S k + (n + m)
k, n, m: nat
IHk: k + n + m = k + (n + m)

S (k + n + m) = S (k + (n + m))
k, n, m: nat
IHk: k + n + m = k + (n + m)

k + n + m = k + (n + m)
assumption. Qed.

We can also show commutativity of multiplication. Try to come up with the lemmas yourself. Note that you can also use rewrite in the opposite direction by using:

rewrite <- n_plus_0

for instance. You can also use rewrite with hypotheses you have.

If you ever find yourself with x = y to prove, when you think you can prove y = x, you can also use the symmetry tactic.

Exercise: Minimum

Fill in the cases for the following function.

We use a placeholder REPLACE_ME that you need to replace.

Fixpoint min (n m : nat) :=
  match n, m with
  | 0, _ => 0
  | _, 0 => 0
  | S n, S m => S (min n m)
  end.

Exercise: Minimum (continued)


forall n m : nat, min n m = min m n

forall n m : nat, min n m = min m n
n: nat

forall m : nat, min n m = min m n

Hint: start the induction before introducing m. You can also use induction ... in.

  

forall m : nat, min 0 m = min m 0
n: nat
ih: forall m : nat, min n m = min m n
forall m : nat, min (S n) m = min m (S n)

forall m : nat, min 0 m = min m 0
m: nat

min 0 m = min m 0

min 0 0 = min 0 0
m: nat
min 0 (S m) = min (S m) 0

min 0 0 = min 0 0

0 = 0
reflexivity.
m: nat

min 0 (S m) = min (S m) 0
m: nat

0 = 0
reflexivity.
n: nat
ih: forall m : nat, min n m = min m n

forall m : nat, min (S n) m = min m (S n)
n: nat
ih: forall m : nat, min n m = min m n
m: nat

min (S n) m = min m (S n)
n: nat
ih: forall m : nat, min n m = min m n

min (S n) 0 = min 0 (S n)
n: nat
ih: forall m : nat, min n m = min m n
m: nat
min (S n) (S m) = min (S m) (S n)
n: nat
ih: forall m : nat, min n m = min m n

min (S n) 0 = min 0 (S n)
n: nat
ih: forall m : nat, min n m = min m n

0 = 0
reflexivity.
n: nat
ih: forall m : nat, min n m = min m n
m: nat

min (S n) (S m) = min (S m) (S n)
n: nat
ih: forall m : nat, min n m = min m n
m: nat

S (min n m) = S (min m n)
n: nat
ih: forall m : nat, min n m = min m n
m: nat

min n m = min m n
apply ih. Qed.

Exercise: Equivalence and forward reasoning (advanced)

If you have already used Rocq before or you are done with the exercises, give the advanced exercises a try. They hopefully teach you things you have not seen before.

If they are too hard, don't worry too much about it for the exam.

Section Advanced.

  Context (P Q R : Prop).

We introduce a new notation P <-> Q meaning P is equivalent to Q.

It is essentially a notation for (P -> Q) /\ (Q -> P) so you can use the tactics split and destruct to prove it and use it.

Here is a trivial example to understand it.

  
P, Q, R: Prop

P <-> P
P, Q, R: Prop

P <-> P
P, Q, R: Prop

P -> P
P, Q, R: Prop
P -> P
P, Q, R: Prop

P -> P
P, Q, R: Prop
H: P

P
assumption.
P, Q, R: Prop

P -> P
P, Q, R: Prop
H: P

P
assumption. Qed.

And here is a new tactic that is going to be useful: assert.

When you write assert (h : P) you are telling Rocq that you want to prove P and that then you are going to use this as a hypothesis named h. This is sometimes called forward reasoning.

See how it works below.

  
P, Q, R: Prop

(Q -> P) /\ (R -> P) -> Q \/ R -> ~ ~ P
P, Q, R: Prop

(Q -> P) /\ (R -> P) -> Q \/ R -> ~ ~ P
P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R

~ ~ P
P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R

P
P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R
hP: P
~ ~ P
P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R

P
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
h2: Q \/ R

P
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hQ: Q

P
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hR: R
P
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hQ: Q

P
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hQ: Q

Q
apply hQ.
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hR: R

P
P, Q, R: Prop
hQP: Q -> P
hRP: R -> P
hR: R

R
apply hR.
P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R
hP: P

~ ~ P
P, Q, R: Prop
h1: (Q -> P) /\ (R -> P)
h2: Q \/ R
hP: P

P
apply hP. Qed.
P, Q, R: Prop

~ (P <-> ~ P)
P, Q, R: Prop

~ (P <-> ~ P)
P, Q, R: Prop
h: P <-> ~ P

False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P

False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P

P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P

P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P

~ P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

P
apply hP.
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

P
apply hP.
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

~ P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
hnP: ~ P
False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

~ P
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P

P
apply hP.
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
hnP: ~ P

False
P, Q, R: Prop
h1: P -> ~ P
h2: ~ P -> P
hP: P
hnP: ~ P

P
apply hP. Qed. End Advanced.

Exercise: Quantifying over propositions (advanced)

For even more advanced stuff we are going to use quantifiers on propositions too. It's basically the same as with natural numbers.

If you have some hypothesis of the form:

h : forall x, P x

then know that you can use specialize (h y) to obtain h : P y. See the following example.


(forall P : Prop, P) -> False

(forall P : Prop, P) -> False
h: forall P : Prop, P

False
h: False

False
assumption. Qed.

Note that it would work with apply directly in this case.


(forall P : Prop, P) -> False

(forall P : Prop, P) -> False
h: forall P : Prop, P

False
apply h. Qed.

Prove the converse now.


False -> forall P : Prop, P

False -> forall P : Prop, P
h: False

forall P : Prop, P
destruct h. Qed.

Exercise: Excluded middle (advanced)

Rocq is, at its basis, a system that has nothing but elimination and introduction rules for disjunctions:

\begin{equation*} \frac{P}{P \vee Q} \end{equation*}
\begin{equation*} \frac{Q}{P \vee Q} \end{equation*}
\begin{equation*} \frac{P \vee Q \qquad P \Longrightarrow R \qquad Q \Longrightarrow R}{R} \end{equation*}

In particular, these rules do not allow proving

\begin{equation*} P \vee \neg P \end{equation*}

In other words, Rocq implements intuitionistic logic. This allows

  • assuming classical laws of reasoning like the law of excluded middle and doing classical math

  • not assuming the law of excluded middle, thus being able to have interesting proofs of the form A -> LEM for a statement A.

We will prove A <-> LEM for two statements now:

Law of Excluded Middle

Definition theLEM := forall P, P \/ ~ P.

Double Negation Elimination

Definition theDNE := forall P, ~~ P -> P.

Peirce's law

Definition thePL := forall P Q : Prop, ((P -> Q) -> P) -> P.

We can now prove the other direction from before.


theLEM -> theDNE

theLEM -> theDNE

You can use unfold to replace a name by its definition.

  

(forall P : Prop, P \/ ~ P) -> forall P : Prop, ~ ~ P -> P
lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P

P
lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hP: P

P
lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hnP: ~ P
P
lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hP: P

P
assumption.
lem: forall P : Prop, P \/ ~ P
P: Prop
h: ~ ~ P
hnP: ~ P

P
contradiction. Qed.

theLEM -> thePL

theLEM -> thePL

(forall P : Prop, P \/ ~ P) -> forall P Q : Prop, ((P -> Q) -> P) -> P
lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P

P
lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hP: P

P
lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hnP: ~ P
P
lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hP: P

P
assumption.
lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hnP: ~ P

P
lem: forall P : Prop, P \/ ~ P
P, Q: Prop
h: (P -> Q) -> P
hnP: ~ P

P -> Q
contradiction. Qed.

theDNE -> theLEM

theDNE -> theLEM

(forall P : Prop, ~ ~ P -> P) -> forall P : Prop, P \/ ~ P
dns: forall P : Prop, ~ ~ P -> P
P: Prop

P \/ ~ P
dns: forall P : Prop, ~ ~ P -> P
P: Prop

~ ~ (P \/ ~ P)
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)

False
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)

~ P
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ P
False
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)

~ P
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hP: P

False
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hP: P

P \/ ~ P
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hP: P

P
assumption.
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ P

False
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ P

P \/ ~ P
dns: forall P : Prop, ~ ~ P -> P
P: Prop
hn: ~ (P \/ ~ P)
hnP: ~ P

~ P
assumption. Qed.

thePL -> theLEM

thePL -> theLEM

(forall P Q : Prop, ((P -> Q) -> P) -> P) -> theLEM
pl: forall P Q : Prop, ((P -> Q) -> P) -> P

theLEM
pl: forall P Q : Prop, ((P -> Q) -> P) -> P

theDNE
pl: forall P Q : Prop, ((P -> Q) -> P) -> P

forall P : Prop, ~ ~ P -> P
pl: forall P Q : Prop, ((P -> Q) -> P) -> P
P: Prop

~ ~ P -> P
P: Prop
pl: forall Q : Prop, ((P -> Q) -> P) -> P

~ ~ P -> P
P: Prop
pl: ((P -> False) -> P) -> P

~ ~ P -> P
P: Prop
pl: ((P -> False) -> P) -> P
hnnP: ~ ~ P

P
P: Prop
pl: ((P -> False) -> P) -> P
hnnP: ~ ~ P

(P -> False) -> P
P: Prop
pl: ((P -> False) -> P) -> P
hnnP: ~ ~ P
hnP: P -> False

P
contradiction. Qed.

Exercise: Advanced advanced exercise

  • Come up with more natural statements equivalent to LEM.

  • Come up with a statement S such that LEM -> S, you cannot prove S -> LEM, but S is also not provable without any assumptions in Rocq.

  • Found one? Great! Now find a statement S' such that S -> S', you cannot prove S' -> S, but S' is also not provable without any assumptions in Rocq.

  • If you force theDNE and theLEM to talk about the same proposition P, the implication theDNE -> theLEM doesn't work any more, why?

  • Can you come up with a hierarchy S_i of such statements such that S_0 is the strongest and they get subsequently weaker?

  • Can you come up with a hierarchy S_i of such statements such that S_0 is the weakest and they get subsequently stronger?

🗣️ Talk to us if you want to know more about the solution.

Exercise: Commuting forall and \/ (advanced)

An example of commuting forall and \/.


forall (P : nat -> Prop) (Q : Prop), Q \/ ~ Q -> (forall x : nat, P x \/ Q) -> (forall x : nat, P x) \/ Q

forall (P : nat -> Prop) (Q : Prop), Q \/ ~ Q -> (forall x : nat, P x \/ Q) -> (forall x : nat, P x) \/ Q
P: nat -> Prop
Q: Prop
lemQ: Q \/ ~ Q
h: forall x : nat, P x \/ Q

(forall x : nat, P x) \/ Q
P: nat -> Prop
Q: Prop
hQ: Q
h: forall x : nat, P x \/ Q

(forall x : nat, P x) \/ Q
P: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q
(forall x : nat, P x) \/ Q
P: nat -> Prop
Q: Prop
hQ: Q
h: forall x : nat, P x \/ Q

(forall x : nat, P x) \/ Q
P: nat -> Prop
Q: Prop
hQ: Q
h: forall x : nat, P x \/ Q

Q
assumption.
P: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q

(forall x : nat, P x) \/ Q
P: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q

forall x : nat, P x
P: nat -> Prop
Q: Prop
hnQ: ~ Q
h: forall x : nat, P x \/ Q
x: nat

P x
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
h: P x \/ Q

P x
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hPx: P x

P x
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: Q
P x
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hPx: P x

P x
assumption.
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: Q

P x
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: Q

False
P: nat -> Prop
Q: Prop
hnQ: ~ Q
x: nat
hQ: Q

Q
assumption. Qed.

Exercise: More classical reasoning


theLEM -> forall P Q : Prop, (~ Q -> P) -> P \/ Q

theLEM -> forall P Q : Prop, (~ Q -> P) -> P \/ Q
lem: theLEM
P, Q: Prop
h: ~ Q -> P

P \/ Q
Q: Prop
lem: Q \/ ~ Q
P: Prop
h: ~ Q -> P

P \/ Q
Q: Prop
hQ: Q
P: Prop
h: ~ Q -> P

P \/ Q
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> P
P \/ Q
Q: Prop
hQ: Q
P: Prop
h: ~ Q -> P

P \/ Q
Q: Prop
hQ: Q
P: Prop
h: ~ Q -> P

Q
assumption.
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> P

P \/ Q
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> P

P
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> P

~ Q
assumption. Qed.

For the following do you need LEM for both directions?


theLEM -> forall P Q : Prop, (P -> Q) <-> ~ P \/ Q

theLEM -> forall P Q : Prop, (P -> Q) <-> ~ P \/ Q
lem: theLEM
P, Q: Prop

(P -> Q) <-> ~ P \/ Q
lem: theLEM
P, Q: Prop

(P -> Q) -> ~ P \/ Q
lem: theLEM
P, Q: Prop
~ P \/ Q -> P -> Q
lem: theLEM
P, Q: Prop

(P -> Q) -> ~ P \/ Q
lem: theLEM
P, Q: Prop
h: P -> Q

~ P \/ Q
P: Prop
lem: P \/ ~ P
Q: Prop
h: P -> Q

~ P \/ Q
P: Prop
H: P
Q: Prop
h: P -> Q

~ P \/ Q
P: Prop
H: ~ P
Q: Prop
h: P -> Q
~ P \/ Q
P: Prop
H: P
Q: Prop
h: P -> Q

~ P \/ Q
P: Prop
H: P
Q: Prop
h: P -> Q

Q
P: Prop
H: P
Q: Prop
h: P -> Q

P
assumption.
P: Prop
H: ~ P
Q: Prop
h: P -> Q

~ P \/ Q
P: Prop
H: ~ P
Q: Prop
h: P -> Q

~ P
assumption.
lem: theLEM
P, Q: Prop

~ P \/ Q -> P -> Q
lem: theLEM
P, Q: Prop
h: ~ P \/ Q
hP: P

Q
lem: theLEM
P, Q: Prop
hnP: ~ P
hP: P

Q
lem: theLEM
P, Q: Prop
hQ: Q
hP: P
Q
lem: theLEM
P, Q: Prop
hnP: ~ P
hP: P

Q
lem: theLEM
P, Q: Prop
hnP: ~ P
hP: P

False
lem: theLEM
P, Q: Prop
hnP: ~ P
hP: P

P
apply hP.
lem: theLEM
P, Q: Prop
hQ: Q
hP: P

Q
assumption. Qed.

theLEM -> forall P Q : Prop, (~ Q -> ~ P) -> P -> Q

theLEM -> forall P Q : Prop, (~ Q -> ~ P) -> P -> Q
lem: theLEM
P, Q: Prop
h: ~ Q -> ~ P
hP: P

Q
Q: Prop
lem: Q \/ ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P

Q
Q: Prop
hQ: Q
P: Prop
h: ~ Q -> ~ P
hP: P

Q
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P
Q
Q: Prop
hQ: Q
P: Prop
h: ~ Q -> ~ P
hP: P

Q
assumption.
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P

Q
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P

False
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P

~ Q
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P
P

Notice we get two goals! Because h : ~ Q -> P -> False.

    
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P

~ Q
assumption.
Q: Prop
hnQ: ~ Q
P: Prop
h: ~ Q -> ~ P
hP: P

P
assumption. Qed.

theLEM -> forall P Q : Prop, ((P -> Q) -> Q) -> (Q -> P) -> P

theLEM -> forall P Q : Prop, ((P -> Q) -> Q) -> (Q -> P) -> P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
lemP: P \/ ~ P

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hP: P

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hP: P

P
assumption.
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
lemQ: Q \/ ~ Q

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hQ: Q

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hQ: Q

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hQ: Q

Q
assumption.
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q

P
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q

False
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q

Q
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q

P -> Q
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
hP: P

Q
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
hP: P

False
lem: theLEM
P, Q: Prop
h: (P -> Q) -> Q
h': Q -> P
hnP: ~ P
hnQ: ~ Q
hP: P

P
apply hP. Qed.

Exercise: More natural numbers


forall n m k : nat, k * (n + m) = k * n + k * m

forall n m k : nat, k * (n + m) = k * n + k * m
n, m, k: nat

k * (n + m) = k * n + k * m
n, m: nat

0 * (n + m) = 0 * n + 0 * m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m
S k * (n + m) = S k * n + S k * m
n, m: nat

0 * (n + m) = 0 * n + 0 * m
n, m: nat

0 = 0
reflexivity.
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

S k * (n + m) = S k * n + S k * m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + m + k * (n + m) = n + k * n + (m + k * m)
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + m + (k * n + k * m) = n + k * n + (m + k * m)
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + m + k * n + k * m = n + k * n + (m + k * m)
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + k * n + (m + k * m) = n + m + k * n + k * m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + k * n + m + k * m = n + m + k * n + k * m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + k * n + m = n + m + k * n
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + m + k * n = n + k * n + m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

k * n + (n + m) = n + k * n + m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

k * n + n + m = n + k * n + m
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

k * n + n = n + k * n
n, m, k: nat
ihk: forall n m : nat, k * (n + m) = k * n + k * m

n + k * n = n + k * n
reflexivity. Qed.

If you thought this kind of proof is extremely annoying, rest assured, most would agree and in practice you don't have to do them by hand. We torture you so you understand better how things work.

In practice Rocq users will use the lia tactic to solve a lot of integer arithmetic problems.

From Stdlib Require Import Lia.


forall n m k : nat, k * (n + m) = k * n + k * m

forall n m k : nat, k * (n + m) = k * n + k * m
lia. Qed.

See? Much better. 😊

Exercise: Defining addition

As always, when you see REPLACE_ME, replace it with the relevant value. Again try to solve the exercises without looking at the live coding file. Even if it seems easy when you see us doing it, it might not be so easy to do on your own, so try to do it!

Exercises all start with an "Exercise" heading. When it is written before a lemma, just prove it. :)

Module define_nat.

Inductive types can be defined using the Inductive keyword

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

Define addition.

  Fixpoint add (n m : nat) {struct n} : nat :=
    match n with
    | O => m
    | S n => S (add n m)
    end.

Exercise: Subtraction

Define subtraction on natural numbers, truncating at 0. In other words, when n < m then sub n m = 0.

  Fixpoint sub (n m : nat) : nat :=
    match n, m with
    | O, _  => O
    | S n', O => n
    | S n', S m' => sub n' m'
    end.

Exercise: Addition with zero

Prove the following lemma. You will replace Admitted with Qed once it is done. What Admitted does should be obvious: it admits a lemma without proof or with a partial proof, it can be used in subsequent proofs as if it were proven.

  

forall n : nat, add n O = n

forall n : nat, add n O = n
n: nat

add n O = n

add O O = O
n: nat
ih: add n O = n
add (S n) O = S n

add O O = O
reflexivity.
n: nat
ih: add n O = n

add (S n) O = S n
n: nat
ih: add n O = n

S (add n O) = S n
n: nat
ih: add n O = n

S n = S n
reflexivity. Qed.

Exercise: Addition with successor

  

forall n m : nat, add n (S m) = S (add n m)

forall n m : nat, add n (S m) = S (add n m)
n, m: nat

add n (S m) = S (add n m)
m: nat

add O (S m) = S (add O m)
n, m: nat
ih: add n (S m) = S (add n m)
add (S n) (S m) = S (add (S n) m)
m: nat

add O (S m) = S (add O m)
reflexivity.
n, m: nat
ih: add n (S m) = S (add n m)

add (S n) (S m) = S (add (S n) m)
n, m: nat
ih: add n (S m) = S (add n m)

S (add n (S m)) = S (S (add n m))
n, m: nat
ih: add n (S m) = S (add n m)

S (S (add n m)) = S (S (add n m))
reflexivity. Qed.

Exercise: Addition and subtraction

With the following commands we declare notations for add and sub.

  Infix "+" := add.
  Infix "-" := sub.

  

forall n m : nat, n + m - m = n

forall n m : nat, n + m - m = n
n, m: nat

n + m - m = n
n: nat

n + O - O = n
n, m: nat
ih: n + m - m = n
n + S m - S m = n
n: nat

n + O - O = n
n: nat

n - O = n

O - O = O
n: nat
S n - O = S n
all: reflexivity.
n, m: nat
ih: n + m - m = n

n + S m - S m = n
n, m: nat
ih: n + m - m = n

S (n + m) - S m = n
n, m: nat
ih: n + m - m = n

n + m - m = n
assumption. Qed.

Note the proof can look nicer if we also prove n - O = n.

  

forall n : nat, n - O = n

forall n : nat, n - O = n
n: nat

n - O = n

O - O = O
n: nat
S n - O = S n
all: reflexivity. Qed.

forall n m : nat, n + m - m = n

forall n m : nat, n + m - m = n
n, m: nat

n + m - m = n
n: nat

n + O - O = n
n, m: nat
ih: n + m - m = n
n + S m - S m = n
n: nat

n + O - O = n
n: nat

n - O = n
apply sub_O.
n, m: nat
ih: n + m - m = n

n + S m - S m = n
n, m: nat
ih: n + m - m = n

S (n + m) - S m = n
n, m: nat
ih: n + m - m = n

n + m - m = n
assumption. Qed. End define_nat.

Exercise: Equality of natural numbers

Define a Boolean predicate deciding equality of natural numbers.

Fixpoint eq_nat (x y : nat) : bool :=
  match x, y with
  | 0, 0 => true
  | 0, S _ => false
  | S _, 0 => false
  | S x', S y' => eq_nat x' y'
  end.

Exercise: Specification of equality


forall n m : nat, eq_nat n m = true <-> n = m

forall n m : nat, eq_nat n m = true <-> n = m
n, m: nat

eq_nat n m = true <-> n = m
m: nat

eq_nat 0 m = true <-> 0 = m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
eq_nat (S n) m = true <-> S n = m
m: nat

eq_nat 0 m = true <-> 0 = m

eq_nat 0 0 = true <-> 0 = 0
m: nat
eq_nat 0 (S m) = true <-> 0 = S m

eq_nat 0 0 = true <-> 0 = 0

true = true <-> 0 = 0

true = true -> 0 = 0

0 = 0 -> true = true
all: reflexivity.
m: nat

eq_nat 0 (S m) = true <-> 0 = S m
m: nat

false = true <-> 0 = S m
m: nat

false = true -> 0 = S m
m: nat
0 = S m -> false = true
all: discriminate.
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat (S n) m = true <-> S n = m
n: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat (S n) 0 = true <-> S n = 0
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
eq_nat (S n) (S m) = true <-> S n = S m
n: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat (S n) 0 = true <-> S n = 0
n: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

false = true <-> S n = 0
n: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

false = true -> S n = 0
n: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
S n = 0 -> false = true
all: discriminate.
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat (S n) (S m) = true <-> S n = S m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat n m = true <-> S n = S m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat n m = true -> S n = S m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
S n = S m -> eq_nat n m = true
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

eq_nat n m = true -> S n = S m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: eq_nat n m = true

S n = S m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: eq_nat n m = true

n = m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: eq_nat n m = true

eq_nat n m = true
assumption.
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m

S n = S m -> eq_nat n m = true
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: S n = S m

eq_nat n m = true
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: S n = S m

n = m
n, m: nat
ih: forall m : nat, eq_nat n m = true <-> n = m
h: S n = S m
H0: n = m

m = m
reflexivity. Qed.

Exercise: Currying

Definition cur {X Y Z} (f : X * Y -> Z) : X -> Y -> Z :=
  fun x y => f (x, y).

Exercise: Uncurrying

Definition car {X Y Z} (f : X -> Y -> Z) : X * Y -> Z :=
  fun p =>
    match p with
    | (x, y) => f x y
    end.

Note, we can take a shortcut because there is only one constructor so we have a so-called "irrefutable pattern".

Definition car' {X Y Z} (f : X -> Y -> Z) : X * Y -> Z :=
  fun '(x,y) => f x y.

We could also use fst and snd.

Definition car'' {X Y Z} (f : X -> Y -> Z) : X * Y -> Z :=
  fun p => f (fst p) (snd p).

Exercise: Uncurrying after currying


forall (X Y Z : Type) (f : X * Y -> Z) (p : X * Y), car (cur f) p = f p

forall (X Y Z : Type) (f : X * Y -> Z) (p : X * Y), car (cur f) p = f p
X, Y, Z: Type
f: X * Y -> Z
p: X * Y

car (cur f) p = f p
X, Y, Z: Type
f: X * Y -> Z
x: X
y: Y

car (cur f) (x, y) = f (x, y)
reflexivity. Qed.

Exercise: Currying after uncurrying


forall (X Y Z : Type) (f : X -> Y -> Z) (x : X) (y : Y), cur (car f) x y = f x y

forall (X Y Z : Type) (f : X -> Y -> Z) (x : X) (y : Y), cur (car f) x y = f x y

No intros needed, reflexivity does it for us.

  reflexivity.
Qed.

Exercise: Swap

Definition swap {X Y} (p : X * Y) : Y * X :=

Irrefutable patterns also work with let.

  let '(x, y) := p in
  (y, x).

Exercise: Swap is involutive


forall (X Y : Type) (p : X * Y), swap (swap p) = p

forall (X Y : Type) (p : X * Y), swap (swap p) = p
X, Y: Type
p: X * Y

swap (swap p) = p
X, Y: Type
x: X
y: Y

swap (swap (x, y)) = (x, y)
reflexivity. Qed.

Exercise: True is not false

Prove true <> false without the tactics inversion or discriminate.


true <> false

true <> false
e: true = false

False
e: true = false

if true then False else True
e: true = false

True
constructor. Qed.