Consider a function . We say that
is a finite function if and only if both
and
are finite sets. As mentioned two weeks ago, function
is surjective if and only if
where and
range over sets
and
, respectively. We now introduce the surjectivity predicate
, defined by
so that function
is surjective if and only if
evaluates to
.
Let and
denote the cardinalities of sets
and
, respectively. Deciding
should then require a total of
evaluations of predicate
. Let us write
and
, and introduce
, a Boolean matrix defined as follows
Stating that is surjective, i.e.,
evaluates to
, is equivalent to saying that every column of matrix
contains at least one entry that evaluates to
. We now introduce a new predicate,
, defined by
so that can be rewritten in the form
, where
ranges over set
. Note that
can be viewed as the disjunction of the
atoms
, i.e.,
.
Note also that can be viewed as the conjunction of the
atoms
. Thus, we can decide surjectivity using the following procedure:
- Compute
for all
.
- Compute the conjunction
. If its truth value is
, then the function is surjective.
Let us now consider two simple examples and implement this decision procedure in Haskell.
__________
Example #1
Let us define . Consider the finite function
where denotes modulo 4 arithmetic. Note that
,
,
, and
. Hence, we easily conclude that
is both injective and surjective (and, thus, is bijective). In Haskell:
Prelude> let f n = (3 * n) `mod` 4 Prelude> let xs = [0..3] Prelude> let ys = [0..3] Prelude> let psi y = or [(f x == y) | x <- xs] Prelude> all psi ys True
which allows us to conclude that is surjective. Note that we used function or to perform disjunction, and function all to perform universal quantification.
__________
Example #2
Consider now the following finite function
Note that and
. Hence, function
is neither injective nor surjective. In Haskell, we have the following:
Prelude> let g n = (2 * n) `mod` 4 Prelude> let xs = [0..3] Prelude> let ys = [0..3] Prelude> let psi y = or [(g x == y) | x <- xs] Prelude> all psi ys False
which allows us to conclude that is not surjective. Why? The following code returns a list of lists of Booleans where each sublist is a column of matrix
(where each entry is
)
Prelude> [[(g x == y) | x <- xs] | y <- ys] [[True,False,True,False],[False,False,False,False], [False,True,False,True],[False,False,False,False]]
Note that the 2nd and 4th sublists contain only truth values. Hence, it is not the case that every column of matrix
contains at least one entry that evaluates to
. Thus,
is not surjective.