Chapter 4 Mathematical Data Types104
Problems for Section 4.4
Practice Problems
Problem 4.15.
Theinverse,R ^1 , of a binary relation,R, fromAtoB, is the relation fromBtoA
defined by:
b R ^1 a iff a R b:
In other words, you get the diagram forR ^1 fromRby “reversing the arrows” in
the diagram describingR. Now many of the relational properties ofRcorrespond
to different properties ofR ^1. For example,RistotaliffR ^1 is asurjection.
Fill in the remaining entries is this table:
Ris iff R ^1 is
total a surjection
a function
a surjection
an injection
a bijectionHint:Explain what’s going on in terms of “arrows” fromAtoBin the diagram
forR.
Problem 4.16.
Describe a total injective functionŒD 1 outç,Œ 1 in;çfromR!Rthat is not a
bijection.
Problem 4.17.
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 the domain,A, or the codomain,B, that don’t show up in graph.R/.
For each of the following possible properties ofR, indicate whether it is always
determined by
- graph.R/alone,
- graph.R/andAalone,
- graph.R/andBalone,