How to Prove It

Introduction

I’m rereading this book for the third time but hopefully writing down a guide will help make the information stick as “structured proving” is a very novel concept that I have not seen elsewhere and I have a lot of math books to go through so this article only goes through the first 3 chapters and the chapter on mathematical induction.

Sentential Logic

• Conjectures = guesses (becomes a Theorem once proven)
• Argument is valid if conclusion cannot be true unless all premises are true
• Tautologies are always true
• Contradictions are always false
• Truth sets are for statements containing variables (not truth values)
• A free variable stands for objects and different values change the truth value
• A bound variable is a letter used as convenience to help express an idea and can be replaced by another variable without changing the meaning
• For $P\implies Q$, the truth table is false at $P$ is true and $Q$ is false because no value of $x$ will lead to this conclusion. E.g. $x > 2 \implies x^2 > 4$
• To talk about $P \implies Q$, you can say “$P$ is a sufficient condition for $Q$” or “$Q$ is a necessary condition for $P$” or “$P$ only if $Q$”. For $Q \implies P$, you say “$P$ if $Q$”.
• To talk about $P \iff Q$, you say “$P$ if $Q$ and $P$ only if $Q$” or “$P$ iff $Q$” or “$P$ is necessary and sufficient condition for $Q$”

Quantifiers

• The universal quantifier distributes over conjunction $\land$ (does not work for existential quantifier)
• You can swap the same quantifier types which do not change the argument. $\exists y \exists x$ is the same as $\exists x \exists y$ (same for $\forall$). However, $\exists y \forall x$ is not the same as $\forall x \exists y$.
• $\exists! x P(x)$ means “exactly one $x$” or “unique $x$”
• can use subset of universe for consideration, $\forall x \in \mathbb{U} P(x)$.

Proofs

• Transforming problem into an easier one
• Assuming is not the same as asserting
• Givens: statements known or assumed to be true
• Goal: statement that remains to be proven
• Keep thought process (givens and goals) separate from proof (mathematical conclusions)
• Easier to prove a postive statement than a negative one

To prove a CONCLUSION of the form $P \implies Q$:

1. Assume $P$ is true and then prove $Q$. (transforms conclusion from $P \implies Q$ to $Q$)

Suppose P.
    [Proof of Q]
Therefore, P -> Q.

1. Assume $Q$ is false and prove that $P$ is false. (contrapositve)

Suppose Q is false.
    [Proof of !P]
Therefore, P -> Q.

To prove a GOAL of the form $\neg P$:

1. If possible, reexpress the goal in some other form (postive form) and then use one of the proof strategies for this other goal form. (using set theory definitions and logical laws)

2. Assume $P$ is true and try to reach a contradiction. Once you have reached a contradiction, you can conclude that $P$ must be false. (Look at using given $\neg P$ #1 below)

Suppose P is true.
    [Proof of contradiction]
Thus, P is false.

To use a GIVEN of the form $\neg P$:

1. If you’re doing a proof by contradiction, try making $P$ your goal. If you can prove $P$, then the proof will be complete, because $P$ contradictions the given $\neg P$.

    [Proof of P]
Since we already know !P, this is a contradiction.

1. If possible, reexpress this given in some other form. (postive form)

To use a GIVEN of the form $P \implies Q$:

1. If you are also given $P$, or if you can prove that $P$ is true, then you can use this given to conclude that $Q$ is true. (modus ponens) Since it is equivalent to $\neg Q \implies \neg P$, if you can prove that $Q$ is false, you can use this given to conclude that $P$ is false. (modus tollens)

Since P and P -> Q, it follows that Q.
[Proof of same goal goes here. We just add Q to the givens.]

To prove a GOAL of the form $\forall x P(x)$:

1. Let $x$ stand for an arbitrary object and prove $P(x)$. The letter $x$ must be a new variable in the proof. If $x$ is already being used in the proof to stand for something, then you must choose an unused variable, say $y$, to stand for the arbitrary object, and prove $P(y)$.

Let x be arbitrary.
    [Proof of P(x) goes here.]
Since x was arbitrary, we can conclude that $\forall$ x P(x).

To prove a GOAL of the form $\exists x P(x)$:

1. Try to find a value of $x$ for which you think $P(x)$ will be true. Then start your proof with “Let $x=$ (the value you decided on)” and proceed to prove $P(x)$ for this value of $x$. Once again, $x$ should be a new variable. If the letter $x$ is already being used in the proof for some other purpose, then you should choose an unused variable, say $y$, and rewrite the goal in the equivalent form $\exists y P(y)$. Now proceed as before by starting your proof with “Let $y =$ (the value you decided on)” and prove $P(y)$.

Let x = (the value you decided on).
    [Proof of P(x) goes here.]
Thus, $\exists$ x P(x).

To use a GIVEN of the form $\exists x P(x)$:

1. Introduce a new variable $x_0$ into the proof to stand for an object for which $P(x_0)$ is true. This means that you can now assume that $P(x_0)$ is true. Logicians call this rule of inference existential instantiation.

To use a GIVEN of teh form $\forall x P(x)$:

1. You can plug in any value, say $a$, for $x$ and use this given to conclude that $P(a)$ is true. This rule is called universal instantiation. (may not be able to use this given until a likely value for $a$ pops up)

To prove a GOAL of the form $P \land Q$:

1. Prove $P$ and $Q$ separately.

[Proof of P goes here.]
[Proof of Q goes here.]

To use a GIVEN of the form $P \land Q$:

1. Treat this given as two separate givens: $P$, and $Q$.

To prove a GOAL of the form $P \iff Q$:

1. Prove $P \implies Q$ and $Q \implies P$ separately.

(->) [Proof of P -> Q].
(<-) [Proof of Q -> P].

• Can also use string of equivalences “$P$ iff $R$ iff $Q$” if both directions of the proof are the same but in reverse order.

To use a GIVEN of the form $P \iff Q$:

1. Treat this as two separate givens: $P \implies Q$, and $Q \implies P$.

To use a GIVEN of the form $P \lor Q$:

1. Break your proof into cases. For case 1, assume that $P$ is true and use this assumption to prove the goal. For case 2, assume $Q$ is true and give another proof of the goal.

Case 1. P is true.
    [Proof of goal goes here.]
Case 2. Q is true.
    [Proof of goal goes here.]
Since we know P $\lor$ Q, these cases cover all possibilities. Therefore the goal must be true.

1. If you are given $\neg P$, or you can prove that $P$ is false, then you can use this given to conclude that $Q$ is true. Similarly, if you are given $\neg Q$ or can prove that $Q$ is false, then you can conclude that $P$ is true.

• Cases must be exhaustive but not exclusive

To prove a GOAL of the form $P \lor Q$:

1. Break your proof into cases. In each case, either prove $P$ or prove $Q$.

2. If $P$ is true, then clearly the goal $P \lor Q$ is true, so you only need to worry about the case in which $P$ is false. You can complete the proof in this case by proving that $Q$ is true.

If P is true, then of course P $\lor$ Q is true. Now suppose P is false.
    [Proof of Q goes here.]
Thus, P $\lor$ Q is true.

• If one of the givens is a disjuntion, you can uses these as suggested cases.

To prove a GOAL of the form $\exists! xP(x)$:

1. Prove $\exists xP(x)$ and $\forall y \forall z ((P(y) \land P(z)) \implies y = z)$. The first of these goals shows that there exists an $x$ such that $P(x)$ is true, and the second shows that it is unique. The two parts of the proof are therefore sometimes labeled existence and uniqueness. Each part is proven using strategies discussed earlier.

Existence: [Proof $\exists$xP(x) goes here.]
Uniqueness: [Proof of $\forall y \forall z$ ((P(y) \land P(z)) -> y = z) goes here.]

1. Prove $\exists x (P(x) \land \forall y (P(y) \implies y = x))$, using strategies from previous sections.

To use a GIVEN of the form $\exists! xP(x)$:

1. Treat this as two given statements, $\exists xP(x)$ and $\forall y \forall z((P(y) \land P(z)) \implies y = z)$. To use the first statement you should probably choose a name, say $x_0$ to stand for some object such that $P(x_0)$ is true. The second tells you that if you ever come across two objects $y$ and $z$ such that $P(y)$ and $P(z)$ are both true, you can condlude that $y=z$.

Mathematical Induction, $\forall n \in \mathbb{N} P(n)$:

1. First prove P(0), and then prove $\forall n \in \mathbb{N}(P(n) \implies P(n+1))$. The first of these proofs is sometimes called the base case and the second the induction step.

Base case: [Proof of P(0) goes here.]
Induction step: [Proof of \forall n \in N (P(n) -> P(n+1)) goes here.]

1. (Strong Induction) Prove that $\forall n [(\forall k < n P(k)) \implies P(n)]$ where both $n$ and $k$ range over the natural numbers in this statement. Of course, the most direct way to prove this is to let $n$ be an arbitrary natural number, assume that $\forall k < n P(k)$, and then prove $P(n)$. No base case needed.

• For proving statements about natural numbers
• Use modus ponens for induction steps. We know $P(0)$ and $P(0) \implies P(1)$, so $P(1)$ is true etc.

  Laws

• DeMorgan’s Laws \(\neg (P \land Q) \quad\equiv\quad \neg P \lor \neg Q \\ \neg (P \lor Q) \quad\equiv\quad \neg P \land \neg Q\)

• Commutative Laws \(P \lor Q \quad\equiv\quad Q \lor P \\ P \land Q \quad\equiv\quad Q \land P\)

• Associative Laws \(P \lor (Q \lor R) \quad\equiv\quad (P \lor Q) \lor R \\ P \land (Q \land R) \quad\equiv\quad (P \land Q) \land R\)

• Idempotent Laws \(P \land P \quad\equiv\quad P \\ P \lor P \quad\equiv\quad P\)

• Distributive Laws \(P \lor (Q \land R) \quad\equiv\quad (P \lor Q) \land (P \lor R) \\ P \land (Q \lor R) \quad\equiv\quad (P \land Q) \lor (P \land R)\)

• Double Negation Laws \(\neg \neg P \quad\equiv\quad P\)

• Tautology Laws \(P \land T \quad\equiv\quad P \\ P \lor T \quad\equiv\quad T \\ \neg T \quad\equiv\quad F\)

• Contradiction Laws \(P \land F \quad\equiv\quad F \\ P \lor F \quad\equiv\quad P \\ \neg F \quad\equiv\quad T\)

• Conditional Law \(P \implies Q \quad\equiv\quad \neg P \lor Q\)

• Converse (not equivalent to $P \implies Q$) \(Q \implies P\)

• Contrapositive \(\neg Q \implies \neg P \quad\equiv\quad P \implies Q\)

• Quantifier Negation Laws \(\neg \exists x P(x) \quad\equiv\quad \forall x \neg P(x) \\ \neg \forall x P(x) \quad\equiv\quad \exists x \neg P(x)\)

• Set Theory \(A \cap B = \{x | x \in A \land x \in B\} \\ A \cup B = \{x | x \in A \lor x \in B\} \\ A \setminus B = \{x | x \in A \land x \notin B\}\)