And and Or
After finishing this section, you will be able to prove propositions involving "and" (∧) and "or" (∨). There is only one rule: whether it appears in the goal or in a hypothesis, the approach differs.
| In the goal (you need to prove it) | In a hypothesis (you have it in hand) | |
|---|---|---|
| p ∧ q | constructor: prove p and q separately | h.left, h.right: take out one half |
| p ∨ q | left or right: pick one side to prove | rcases h with hp | hq: both cases must be discussed |
How to type the symbols: in VS Code or the online version, type \and to get ∧, \or to get ∨, and \to to get →.
What you'll be able to do after this section
- Prove an "and": prove both sides
- Use an "and": take out the half you need
- Prove an "or": pick the correct side
- Use an "or": split into cases
Step 1: And
To prove p ∧ q, you must prove both p and q. constructor splits one goal into two:
example (p q : Prop) (hp : p) (hq : q) : p ∧ q := by
constructor
· exact hp
· exact hqThe · at the start of a line means "now focus on proving this one small goal". Type \. to get it.
Conversely, when you have h : p ∧ q in hand, h.left is a proof of p, and h.right is a proof of q:
example (p q : Prop) (h : p ∧ q) : q := by
exact h.rightOn the course entry page, you proved "it is windy and rainy" in plain language. Now prove it as a theorem that holds for any p and q — walk through it yourself:
theorem and_swap' (p q : Prop) : p ∧ q → q ∧ p := by
intro h
constructor
exact h.right
exact h.left
Write it as code:
theorem and_swap' (p q : Prop) : p ∧ q → q ∧ p := by
intro h
constructor
· exact h.right
· exact h.left- I know that for an "and" in the goal I use
constructor, and for an "and" in a hypothesis I use.leftand.right
Step 2: Or
To prove p ∨ q, proving one side is enough. Use left or right to indicate which side you pick:
example (p q : Prop) (hp : p) : p ∨ q := by
left
exact hpPicking the wrong side means you can't finish the proof. You only have p in hand, but you picked the right side:
example (p q : Prop) (hp : p) : p ∨ q := by
right
exact hpType mismatch
hp
has type
p
but is expected to have type
qWhen you have h : p ∨ q in hand, the situation is different: you don't know which side holds, so you must handle both cases. rcases h with hp | hq splits the proof into two branches, one with hp : p, the other with hq : q.
- I know that for an "or" in the goal I pick one side, and for an "or" in a hypothesis I must discuss both sides
Hands-on: swap the two sides of an "or"
Given "p or q", prove "q or p". Notice that after splitting into cases, the two branches pick exactly opposite sides.
theorem or_swap' (p q : Prop) : p ∨ q → q ∨ p := by
intro h
rcases h with hp | hq
right
exact hp
left
exact hq
Write it as code:
theorem or_swap' (p q : Prop) : p ∨ q → q ∨ p := by
intro h
rcases h with hp | hq
· right
exact hp
· left
exact hqQuiz timeYou have h : p ∧ q, and the goal is p ∨ q. Which of the following works?
Checkpoint
- I can write out from memory the two-row, two-column table at the top of this page
- I finished the proof of
or_swap'in the exercise - I know that
·is used to focus on one small goal - I can type
∧,∨,→
Didn't work?
After constructor there are two goals and I don't know which one I'm proving. Look at the topmost one in the goal state; case left or case right indicates which half it is. Use · to work through them one at a time.
The rcases line reports a syntax error. The vertical bar in the middle is the | key on the keyboard, and the names on either side are up to you.
Next section
Up to here, every step has been derived by your own hand. Next section covers a few tactics that can do the work for you: rewriting, simplification, and automatic arithmetic.