Recall that we defined inverses for any relation:
Definition. If is a relation from
to
, then
is a relation from
to
, defined by
iff
.
Thus (in our formalism) every function has an inverse. The inverse of a function so defined, however, may not be a function itself! (Remember that most operations we do to sets or to relations will not preserve functionhood.) So let's discover when taking the inverse (``swapping and
") actually does result in a function.
Recall that means that two conditions hold:
.
Exercise 1. Suppose . By substituting
for
,
for
, and
for
, write what it means for
.
Exercise 2. Use the definition of to rewrite your conditions solely in terms of
(with no
anywhere).
Definition. Let . We call
onto or surjective if
. We call
one-to-one or injective if for any
, we have that
guarantees
.
Definition. A function which is both one-to-one and onto is called a one-to-one correspondence or a bijection.
The following theorem is important, but its proof is just the combination of Exercises 1 and 2.
Theorem. Let . Then
iff
is both one-to-one and onto.
Theorem. Suppose is one-to-one and
is one-to-one. Then
is one-to-one.
Proof. Note that the condition that be defined on the range of
is necessary in order to compose the two functions as functions.
Let . Suppose
. Applying the fact that the composition of functions is a function, we have
Since is one-to-one, we have
. Since
is one-to-one, we have
. Since
were arbitrary, we've shown
is one-to-one.
.
Theorem. Suppose is onto and
is onto. Then
is onto.
Proof. This is an exercise for you.