Mathematics for Computer Science

4.4. Binary Relations 81

For each of the following possible properties ofR, indicate whether it is always
determined by

1. graph.R/alone,


2. graph.R/andAalone,


3. graph.R/andBalone,


4. all three parts ofR.

Properties:

(a)surjective

(b)injective

(c)total

(d)function

(e)bijection

Problem 4.9.
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,Ris antotaliffR^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 bijection

Hint:Explain what’s going on in terms of “arrows” fromAtoBin the diagram
forR.