Chapter 4 Mathematical Data Types80
Problems for Section 4.2
Homework Problems
Problem 4.6.
Prove that for any setsA,B,C, andD, ifABandCDare disjoint, then either
AandCare disjoint orBandDare disjoint.
Problem 4.7. (a)Give an example where the following result fails:
False Theorem.For setsA,B,C, andD, let
LWWD.A[B/.C[D/;
RWWD.AC/[.BD/:ThenLDR.
(b)Identify the mistake in the following proof of the False Theorem.Bogus proof.SinceLandRare both sets of pairs, it’s sufficient to prove that
.x;y/ 2 L !.x;y/ 2 Rfor allx;y.
The proof will be a chain of iff implications:
.x;y/ 2 R
iff .x;y/ 2 .AC/[.BD/
iff .x;y/ 2 AC, or.x;y/ 2 BD
iff (x 2 Aandy 2 C) or else (x 2 Bandy 2 D)
iff eitherx 2 Aorx 2 B, and eithery 2 Cory 2 D
iff x 2 A[Bandy 2 C[D
iff .x;y/ 2 L.(c)Fix the proof to show thatRL.Problems for Section 4.4
Practice Problems
Problem 4.8.
For a binary relation,RWA!B, some properties ofRcan be determined from
just the arrows ofR, that is, from graph.R/, and others require knowing if there
are elements in domain,A, or the codomain,B, that don’t show up in graph.R/.