Proof Technique: Equivalence

what we’re really saying is that if we know that proposition a is true, then we know that proposition b is also true. But because an implication is not generally logically equivalent to it’s converse, we can’t go the other way, meaning if we know that proposition b is true, we don’t necessarily know that proposition a is also true.

However, just because it is true in general does not mean there are never any instances where an implication is logically equivalent to it’s converse. Consider the statement

n is even ⟹ n + 1 is odd.

Clearly, the converse of this implication is also a logical implication as well:

n + 1 is odd ⟹ n is even.

Hence, whenever the proposition “n is even” is true, the proposition “n + 1 is odd” is also true. Likewise, when the proposition “n + 1 is odd” is true, then we also know that proposition “n is even” is also true. Thus these propositions are either simultaneously true, or simultaneously false. Hence, we can write

n is even ⟺ n + 1 is odd.

In this section, we demonstrate a technique for proving statements of the form

a ⟺ b.

The General Strategy

The proof technique for showing a logical equivalence is based on the fact that

(p ↔ q) ⟺ (p → q) ∧ (q → p).

Figure 2.13.1: Showing two statements to be logically equivalent involves showing two implications.

As hinted at in the introduction of this section, if we ever want to prove a statement of the form

a ⟺ b

what we need to do is provide a proof for

a ⟹ b

and a proof for

b ⟹ a.

Just as a reminder, when we want to try and provide a proof for the statement a ⟹ b, we assume that a is true, and then try to deduce the truth of b. When trying to provide a proof for the statement b ⟹ a, we assume the truth of b, and then try to deduce the truth of a.

Of course, any proof technique that was previously discussed (or will be discussed) can be used for a ⟹ b and b ⟹ a.

Another Result About Even and Odd Numbers

Theorem 2.13.1

n is even if and only if n² is even.

Proof

n is even ⟹ n² is even

Suppose n is an even integer. Then there exists some integer k such that

n = 2k.

Squaring n to get n² yields the following:

n²	=	n*n
	=	(2k)*(2k)
	=	4k²
	=	2(2k²)
	=	2ℓ

Because k is an integer, we have that 2k² = ℓ is also an integer, meaning n² is the double of some integer.

Thus, n² is even as desired.

n is even ⟸ n² is even

Here, we choose to work with the contrapositive:

n is odd → n² is odd.

Supposing n is odd, there exists some integer k such that

n = 2k + 1.

Squaring n to get n² yields the following:

n²	=	n*n
	=	(2k + 1)*(2k + 1)
	=	4k² + 4k + 1
	=	2(2k²) + 2(2k) + 1
	=	2(2k² + 2k) + 1
	=	2ℓ + 1

Because k is an integer, so is 2k² + 2k, meaning ℓ is an integer. Thus since n² = 2ℓ + 1 for integer ℓ, we have that n² is an odd integer. This proves the statement

n is odd → n² is odd,

and since this is logically equivalent to its contrapositive, we have also proven that

n² is even → n is even

as desired.

n is even ⟺ n² is even

Because we shown that

n is even ⟹ n² is even

and that

n is even ⟸ n² is even

we have that

n is even ⟺ n² is even

as desired.

In the proof we provided, we clearly delineated which part of the proof we were working on by providing underlined headers. This let’s us stay organized. We finished the proof by making clear we’ve shown the logical implication works both ways, which means we have a logical equivalency.

Notice also that Theorem 2.13.1 uses the “if and only if” construct. As a reminder, saying “if and only if” is how biconditionals are specified.

Something else worth pointing out is that when we were trying to provide a proof for the statement n is even ⟹ n² is even, we used a direct approach, whereas we used an indirect approach for the statement n² is even ⟹ n is even. We are allowed to mix and match proof techniques for either part. All we need to do is just provide some proof, regardless of the technique.

Multiple Equivalencies

Of course, multiple propositions may be logically equivalent to each other. For example, suppose we knew that

a ⟺ b
a ⟺ c

Can we conclude that b ⟺ c? Well, since a ⟺ b and a ⟺ c, we have that b ⟹ a and a ⟹ c. Thus, by the Law of the Syllogism, we must have that

b ⟹ c.

Similarly, we also have that c ⟹ a and a ⟹ b, meaning we also have that

c ⟹ b.

Finally, because we have both b ⟹ c and c ⟹ b, we must also have that

b ⟺ c

as well.

This means that overall, we have

a ⟺ b ⟺ c.

The proof technique for showing multiple equivalencies is based of the fact that

(p₁ ↔ p₂ ↔ p₃) ↔ [(p₁ → p₂) ∧ (p₂ → p₃) ∧ (p₃ → p₁)]

Figure 2.13.2: Showing multiple equivalencies requires showing multiple implications chained together via the Law of the Syllogism.

The most straight-forward way to show that

a ⟺ b ⟺ c

is to first show that a ⟹ b, and then show that b ⟹ c, and then to finally show that c ⟹ a.

Theorem 2.13.2

The following statements are all logically equivalent:

n is odd
n + 1 is even
n² is odd

Proof

n is odd ⟹ n + 1 is even

This is Theorem 2.9.2.

n + 1 is even ⟹ n² is odd

Since n + 1 is even, we know that n is odd.

Furthermore, because n is odd, Theorem 2.9.10 guarantees that n² is odd as desired.

n² is odd ⟹ n is odd

This is Theorem 2.9.11.

n is odd ⟺ n + 1 is even ⟺ n² is odd

Because we’ve shown n is odd ⟹ n + 1 is even, n + 1 is even ⟹ n² is odd, and n² is odd ⟹ n is odd, we have that

n is odd ⟺ n + 1 is even ⟺ n² is odd

as desired.

This completes the proof.

Because of all the work we did previously, we were able to make quick work of this proof. This is the power of proving theorems. Instead of having to work out every result from first principles, we can simply appeal to previously established theorems to do all the heavy lifting.

Note that we can extend logical equivalency to as many propositions as we can logically show. For example, if we wanted to show that some collection consisting of n propositions were logically equivalent, we make use of the fact

(p₁ ↔ p₂ ↔ p₃ ↔ … ↔ p_n-1 ↔ p_n) ↔ (p₁ ↔ p₂) ∧ (p₂ ↔ p₃) ∧ … ∧ (p_n-1 ↔ p_n) ∧ (p_n ↔ p₁)

The Book ofFoundational Mathematics

Quick Links