Proving equivalences

Proving A ≡ B

There are two common approaches to proving that two statements are equivalent to one another. One approach is to treat ≡ similarly to =. That is commonly done for propositional logic, for example.

Theorem. ¬(p → q) ≡ p ∧ ¬ q.

Proof.

¬(p → q)	≡	¬(¬p ∨ q)	(by the definition of p → q)
	≡	¬(¬p) ∧ ¬ q	(by DeMorgan's law)
	≡	p ∧ ¬q	(by the double-negation law)

But often, it is convenient to break the proof down into two major steps by using the propositional equivalence (p ↔ q) ≡ ((p → q) ∧ (q → p)). The following example uses the definitions from the preceding page. We also need one more definition.

Definition. For integers n and m, where m > 0, n mod m is the remainder when you divide n by m. More precisely, dividing n by m yields a quotient q and a remainder r where

n = qm + r
0 ≤ r < m

and n mod m is the remainder, r.

Theorem. The following two statements are equivalent.

(a) x ≡ y (mod m).
(b) x mod m = y mod m.

Proof. We break the proof into two parts.

((a) → (b)). Suppose that

(1) x ≡ y (mod m).

By definition, that means

(2) m | (x − y)

which in turn means

(3) ∃k(x − y = km)

So select an integer c such that

(4) x − y = cm
(5) x = cm + y (by algebra from (4)

Now take both sides of equation (5) mod m.

(6) x mod m = (cm + y) mod m

But

(7) (cm + y) mod m = y mod m

since adding multiples of m to the dividend cannot change the remainder. Putting (6) and (7) together yields

(8) x mod m = y mod m

which is just what we are trying to prove.

((b) → (a)). Suppose that

(1) x mod m = y mod m.

By division and the definition of the mod operator, there must exist integers q₁, r₁, q₂ and r₂ so that

(2) x = q₁m + r₁
(3) 0 ≤ r₁ < m
(4) y = q₂m + r₂
(5) 0 ≤ r₂ < m
(6) r₁ = r₂ (restatement of fact (1))

By facts (2) and (4),

(7) x − y = q₁m + r₁ − (q₂m + r₂)
(8) x − y = (q₁ − q₂)m + (r₁ − r₂)
(9) x − y = (q₁ − q₂)m (by facts (6) and (8))

But fact (9) tells us that

(10) ∃d(x − y = dm)

since d = (q₁ − q₂) clearly works. But that is equivalent to

(11) x ≡ y (mod m)

by the definition of what x ≡ y (mod m) means.

♦