Section 5.1 Relations
341
If we assume that 3x 4 ∙ 3z 4, we must then show that 3x 4 d 3z 4 does not contain anything, which might be hard to do. So instead, we’ll prove the contrapositive of a. ii:
3x 4 d 3z 4 ∙ [ S 3x 4 = 3z 4
(contrapositive of a.ii)
Therefore, we assume that 3x 4 d 3z 4 ∙ [ and that there is a y [ S such that
y [ 3x 4 d 3z 4. What does this tell us?
y [ 3x 4 d 3z 4
(assumption)
y [ 3x 4, y [ 3z 4
(definition of d)
x r y, z r y
(definition of 3x 4 and 3z 4)
x r y, y r z
(symmetry of r)
x r z
(transitivity of r)
Now we can show that 3x 4 = 3z 4 by proving set inclusion in each direction:
3. 3z 4 # 3x 4
4. 3x 4 # 3z 4
To show (3), 3z 4 # 3x 4, let q [ 3z 4 (we know 3z 4 ∙ [ because y [ 3z 4.) Then
z r q
(definition of 3z 4)
x r z
(from above)
x r q
(transitivity of r)
q [ 3x 4
(definition of 3x 4)
3z 4 # 3x 4
(definition of #)
Practice 12 asks for a proof of (4), 3x 4 # 3z 4. Once this proof is supplied, it
completes (3) and (4), which leads to the conclusion 3x 4 = 3z 4. This completes the
proof of the contrapositive of part (a. ii) and therefore proves part (a. ii), which in
turn completes the proof of part (a). Whew!
Practice 13 asks for a proof of part b.
End of Partial Proof
PRaCtiCe 12 For the foregoing argument, supply the proof that 3x 4 # 3z 4.
■
PRaCtiCe 13 Prove part (b) of the theorem. Given a partition of a set S, define a relation r by
x r y 4 x is in the same block of the partition as y
and show that r is an equivalence relation on S, that is, show that r is reflexive, symmetric, and transitive. ■
example 13
The equivalence relation on N given by
x r y 4 x + y is even
341
If we assume that 3x 4 ∙ 3z 4, we must then show that 3x 4 d 3z 4 does not contain anything, which might be hard to do. So instead, we’ll prove the contrapositive of a. ii:
3x 4 d 3z 4 ∙ [ S 3x 4 = 3z 4
(contrapositive of a.ii)
Therefore, we assume that 3x 4 d 3z 4 ∙ [ and that there is a y [ S such that
y [ 3x 4 d 3z 4. What does this tell us?
y [ 3x 4 d 3z 4
(assumption)
y [ 3x 4, y [ 3z 4
(definition of d)
x r y, z r y
(definition of 3x 4 and 3z 4)
x r y, y r z
(symmetry of r)
x r z
(transitivity of r)
Now we can show that 3x 4 = 3z 4 by proving set inclusion in each direction:
3. 3z 4 # 3x 4
4. 3x 4 # 3z 4
To show (3), 3z 4 # 3x 4, let q [ 3z 4 (we know 3z 4 ∙ [ because y [ 3z 4.) Then
z r q
(definition of 3z 4)
x r z
(from above)
x r q
(transitivity of r)
q [ 3x 4
(definition of 3x 4)
3z 4 # 3x 4
(definition of #)
Practice 12 asks for a proof of (4), 3x 4 # 3z 4. Once this proof is supplied, it
completes (3) and (4), which leads to the conclusion 3x 4 = 3z 4. This completes the
proof of the contrapositive of part (a. ii) and therefore proves part (a. ii), which in
turn completes the proof of part (a). Whew!
Practice 13 asks for a proof of part b.
End of Partial Proof
PRaCtiCe 12 For the foregoing argument, supply the proof that 3x 4 # 3z 4.
■
PRaCtiCe 13 Prove part (b) of the theorem. Given a partition of a set S, define a relation r by
x r y 4 x is in the same block of the partition as y
and show that r is an equivalence relation on S, that is, show that r is reflexive, symmetric, and transitive. ■
example 13
The equivalence relation on N given by
x r y 4 x + y is even