Mathematical Proof and the Principles of Mathematics/Logic/Logical equivalence

There is a final logical connective we'll be covering.

Equivalence

Again, we 'define' this in terms of other connectives and verify that it matches the definition given earlier. In this case we take

($P$ implies $Q$) and ($Q$ implies $P$)

to be the definition of

$P$ iff $Q$.

This definition is where the 'if and only if' expression comes from, since

$Q$ implies $P$

can be phrased $P$ if $Q$ and

$P$ implies $Q$

can be phrased as $P$ only if $Q$.

So see that this matches the previous definition, notice that $P$ implies $Q$ is False when $P$ is True and $Q$ is False, meanwhile $Q$ implies $P$ is False when $Q$ is True and $P$ is False, so the expression ($P$ implies $Q$) and ($Q$ implies $P$) can only be true when $P$ and $Q$ are both True or both False.

By combining this definition with the other rules of inference we get the following:

From $P$ implies $Q$, $Q$ implies $P$ deduce $P$ iff $Q$.

If by making the assumption not $P$ one can derive $Q$, and if by making the assumption not $Q$ one can derive $P$ then deduce $P$ iff $Q$.

From $P$, $P$ iff $Q$ deduce $Q$.

From $Q$, $P$ iff $Q$ deduce $P$.

So you can use equivalence like implication except it goes in both directions, and to proof an equivalence is the same as proving an implication except you do it in both directions.

Example Proof #1

Prop 1: $P$ or $Q$ iff $Q$ or $P$

In this case we already have $P$ or $Q$ implies $Q$ or $P$ as Prop. 1 on the previous page. By switching the letters $Q$ with $P$ in the proposition we get $Q$ or $P$ implies $P$ or $Q$. So the proof is just a matter of putting these two previous results together.

Line	Statement	Justification
1	$P$ or $Q$ implies $Q$ or $P$	Prop. 1 from the previous page.
2	$Q$ or $P$ implies $P$ or $Q$	Also Prop. 1 from the previous page.
3	$Q$ or $P$ iff $P$ or $Q$	From 1 and 2

Example Proof #2

For a more complicated example, we'll need to use subproofs.

Prop 2: $P$ or $Q$ iff ($P$ implies $Q$) implies $Q$

We're proving two implications, one in each direction, so the structure of the proof looks like:

Line	Statement	Justification
1	$P$ or $Q$	Hypothesis
(something)
n	($P$ implies $Q$) implies $Q$	?
n+1	($P$ implies $Q$) implies $Q$	Hypothesis
(something)
n+p	$P$ or $Q$	?
n+p+1	$P$ or $Q$ iff ($P$ implies $Q$) implies $Q$	From 1 and n, n+1 and n+p

At this point we've broken the proof into parts which can be tackled separately. In the first case we need to prove an implication, but it seems easier to do the usual way. In the second case we need to prove disjunction and there are two ways of doing this. It looks like the easier way is to assume not $P$ and prove $Q$. Now that we have several ways of proving things it may be that some ways are simpler than others, but without enough experience to get a feel for it you may have to use trial and error to find the simplest way. Keep in mind though, that when you see a proof in a book or article, the author may have gone through quite a few failed attempts before finding a proof that worked, but you don't get to see the failures.

Filling in more of the structure we have:

Line	Statement	Justification
1	$P$ or $Q$	Hypothesis
2	$P$ implies $Q$	Hypothesis
(something)
n−1	$Q$	?
n	($P$ implies $Q$) implies $Q$	From 2 and n−1
n+1	($P$ implies $Q$) implies $Q$	Hypothesis
n+2	not $P$	Hypothesis
(something)
n+p−1	$Q$	?
n+p	$P$ or $Q$	From n+2 and n+p−1
n+p+1	$P$ or $Q$ iff ($P$ implies $Q$) implies $Q$	From 1 and n, n+1 and n+p

(To save space, we're constructing both halves of the proof at once; normally you'd do one at time though.)

In the first half we need to prove $Q$ and it appears that the best way to do this is using the method of contradiction. For the second half we already have enough results from previous pages to fill in the rest. As usual, we encourage you to try to fill in the rest yourself before looking at the final result. By different methods you may even find a simpler proof than the one given.

Line	Statement	Justification
1	$P$ or $Q$	Hypothesis
2	$P$ implies $Q$	Hypothesis
3	not $Q$	Hypothesis
4	$P$	From 1 and 3
5	not $P$	From 2 and 3
6	$False$	From 4 and 5
7	$Q$	From 3 and 6
8	($P$ implies $Q$) implies $Q$	From 2 and 7
9	($P$ implies $Q$) implies $Q$	Hypothesis
10	not $P$	Hypothesis
11	$P$ implies $Q$	Prop. 8 on the page on indirect proofs.
12	$Q$	From 9 and 11
13	$P$ or $Q$	From 10 and 12
14	$P$ or $Q$ iff ($P$ implies $Q$) implies $Q$	From 1 and 8, 9 and 13

In prose form it's a good idea to label the statements and clearly mark which implication is being being proved when so that the reader can easily follow the proof.

Prop 2: $P$ or $Q$ iff ($P$ implies $Q$) implies $Q$

Proof: We first prove that $P$ or $Q$ implies (($P$ implies $Q$) implies $Q$). Assume $P$ or $Q$. Now assume $P$ implies $Q$. We need to proof $Q$, so suppose not $Q$. Then $P$ by the first assumption and not $P$ by the second assumption. This is a contradiction so we have $Q$. Therefore ($P$ implies $Q$) implies $Q$. From the original assumption $P$ or $Q$ it follows that ($P$ implies $Q$) implies $Q$, so we can conclude that $P$ or $Q$ implies (($P$ implies $Q$) implies $Q$).

Now we prove that (($P$ implies $Q$) implies $Q$) implies $P$ or $Q$. Assume ($P$ implies $Q$) implies $Q$. Now assume not $P$. Then $P$ implies $Q$ and therefore $Q$, so $P$ or $Q$.

Left for the reader

We've now covered nearly all of the commonly used rules of inference, so there is no shortage of statements that can be proved now. Some of the following are relatively trivial extensions of previous results, and some will require one or more subproofs, but it's up to you to figure out which is which.

Prop. 3: ($P$ or $Q$) or $R$ iff $P$ or ($Q$ or $R$)

Prop. 4: $P$ and $Q$ iff $Q$ and $R$

Prop. 5: ($P$ and $Q$) and $R$ iff $P$ and ($Q$ and $R$)

Prop. 6: ($P$ and $Q$) or $R$ iff ($P$ or $R$) and ($Q$ or $R$)

Prop. 7: ($P$ or $Q$) and $R$ iff ($P$ and $R$) or ($Q$ and $R$).

Prop. 8: ($P$ iff $Q$) implies ($Q$ iff $P$)

Prop. 9: ($P$ iff $Q$) and ($Q$ iff $R$) implies ($P$ iff $R$)

Prop. 10: $P$ implies $Q$ iff not $P$ or $Q$

Prop. 11: not ($P$ implies $Q$) iff $P$ and not $Q$

Prop. 11: not ($P$ or $Q$) iff not $P$ and not $Q$

Prop. 12: not ($P$ and $Q$) iff not $P$ or not $Q$

Prop. 13: ($P$ iff $Q$) implies ($P$ implies $R$ iff $Q$ implies $R$)

Prop. 14: ($P$ iff $Q$) implies ($R$ implies $P$ iff $R$ implies $Q$)

Prop. 15: $P$ iff not not $P$

Groups of equivalent statements

In some cases a theorem may state that a group of several statements are equivalent to each other. For example the statement of the theorem might be in the form:

Theorem: The following are equivalent:

1. Statement 1

2. Statement 2

3. Statement 3

4. Statement 4

This says Statement 1 iff Statement 2, Statement 1 iff Statement 3, ... Statement 3 iff Statement 4, with all 6 possible variations. The usual way to proof this type of theorem is to prove implications in a cycle. In this case you would prove,

P1: Statement 1 implies Statement 2

P2: Statement 2 implies Statement 3

P3: Statement 3 implies Statement 4

P4: Statement 4 implies Statement 1

This is very efficient since by proving just four implications you've in effect proven all 12 possible implications between two of the four statements. The reason this works is by repeated application of the following

Prop. 13: ($P$ implies $Q$) and ($Q$ implies $R$) implies ($P$ implies $R$)

Proof: (This is an easy application of previous results and is left as an exercise.)

As a further exercise, prove that

P1 and P2 and P3 and P4 implies (Statement 1 iff Statement 3)

Substitution

When two statements are logically equivalent they have the same truth value. So it seems reasonable to claim that if $P$ is equivalent to $Q$ and $E(P)$ is some expression involving $P$, then $E(P)$ is equivalent to $E(Q)$, where $E(Q)$ is obtained from $E(P)$ by replacing the statement $P$ by $Q$.

As an example of how this might be applied, we have from Prop. 15 above that $P$ is equivalent to not not $P$. It would be nice to conclude then that

not not $P$ implies $R$ or ($Q$ iff $S$)

is equivalent to

$P$ implies $R$ or ($Q$ iff $S$)

without going through a separate proof.

This is a valid conclusion, but the tools to justify it belong to the realm of mathematical logic and are outside the scope of this book. We can give proofs on a case by case basis though, and some examples serve to demonstrate how these proofs can be constructed. If the expression $E(P)$ involves only implication and the logical constant $False$, then we can apply repeatedly apply propositions 13 and 14 above.

For example, if $E(P)$ is

$Q$ implies ($P$ implies $R$)

then we can prove

$Q$ implies ($P$ implies $R$)

is equivalent to

$Q$ implies (not not $P$ implies $R$)

as follows:

not not $P$ iff $P$ (by Prop. 15)

not not $P$ implies $R$ iff $P$ implies $R$ (by Prop. 13)

$Q$ implies (not not $P$ implies $R$) iff $Q$ implies ($P$ implies $R$) (by Prop. 14)

For an expression involving other logical connectives we can use the definitions we gave in terms of implication to turn the expression into one of the previous type.