Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

The Book of
Foundational Mathematics

Detailed Contents

Propositional Logic
  1. Propositions
  2. Modeling Logic with Truth Tables
  3. Logical Equivalence
  4. The Laws of Logic
  5. Application: Switching Networks
  6. Logical Implications
  7. Propositions with Variables
  8. Quantifiers
  9. Logic with Quantified Statements
  10. Nested Quantifiers
  11. Application: Logic Puzzles
  12. A Primer on Fuzzy Logic
  1. Mathematical Logic with Maple
  2. Defining Propositions with Maple
Arguments and Proof
  1. The Structure of Basic Arguments
  2. Rules of Inference
  3. Using the Rules of Inference
  4. Logically Equivalent Arguments
  5. Invalid Arguments
  6. Universal Specification
  7. Universal Generalization
  8. Axioms, Definitions, Theorems, and Proofs
  9. Proof Technique: Direct Proofs
  10. Proof Technique: Indirect Proofs
  11. Proof Technique: Contradiction
  12. Mistakes in Proofs
  13. Proof Technique: Equivalence
  1. Verifying Mathematical Arguments in Maple
Set Theory
  1. Sets
  2. Subsets
  3. Proof Technique: Element Arguments
  4. A Set of Operations on Sets
  5. The Laws of Set Theory
  6. Proof Technique: Exhaustion
  1. Set Theory in Maple

Proof Technique: Equivalence

All of the proof techniques we’ve discussed so far seem to only go one way. That is to say, when we provide a proof for a statement such as

a ⟹ b

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 of 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 n2 is even.

Proof

n is even ⟹ n2 is even

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

n = 2k.

Squaring n to get n2 yields the following:

n2=n*n
=(2k)*(2k)
=4k2
=2(2k2)
=2ℓ

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

Thus, n2 is even as desired.

n is even ⟸ n2 is even

Here, we choose to work with the contrapositive:

n is odd → n2 is odd.

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

n = 2k + 1.

Squaring n to get n2 yields the following:

n2=n*n
=(2k + 1)*(2k + 1)
=4k2 + 4k + 1
=2(2k2) + 2(2k) + 1
=2(2k2 + 2k) + 1
=2ℓ + 1

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

n is odd → n2 is odd,

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

n2 is even → n is even

as desired.

n is even ⟺ n2 is even

Because we shown that

n is even ⟹ n2 is even

and that

n is even ⟸ n2 is even

we have that

n is even ⟺ n2 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 ⟹ n2 is even, we used a direct approach, whereas we used an indirect approach for the statement n2 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

(p1 ↔ p2 ↔ p3) ↔ (p1 → p2) ∧ (p2 → p3) ∧ (p3 → p1)

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
  • n2 is odd

Proof

n is odd ⟹ n + 1 is even

This is Theorem 2.9.2.

n + 1 is even ⟹ n2 is odd

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

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

n2 is odd ⟹ n is odd

This is Theorem 2.9.11.

n is odd ⟺ n + 1 is even ⟺ n2 is odd

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

n is odd ⟺ n + 1 is even ⟺ n2 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

(p1 ↔ p2 ↔ p3 ↔ … ↔ pn) ↔ (p1 ↔ p2) ∧ (p2 ↔ p3) ∧ … ∧ (pn ↔ p1)