B1.3 Functions
First I want to remind us of some notation and terminology (mathematicians are very specific).
Note. To say a function is on
Definition 1.3.1 (Functions). We all know what functions are at some level, but here we are going to be extraordinarily explicit. A function from
, and- if
and , then .
Thus for each
The set of all functions from
Note that a function is not an active entity, despite action words such as transforms; it merely is. A function is a static set of pairs, much like a directory that pairs names with addresses.
While
Definition 1.3.2 (Injective, surjective, and bijective maps). Let
is surjective, or maps onto , if ; that is, for every there is an with . We denote surjectivity by . is injective, or one-to-one, if for all , implies ; equivalently, implies . We denote injectivity by . is bijective, or a one-to-one correspondence, if it is both injective and surjective. There is no universally agreed notation for bijections; we write or .
Definition 1.3.3 (Inclusion and identity maps). If
Inclusion maps are injective, since
Definition 1.3.4 (Restrictions and extensions). Let
Definition 1.3.5 (Projections). The projections of
For a relation
Definition 1.3.6 (Characteristic functions). Let
Proposition 1.3.7 (Subsets and characteristic functions). The map
Proof. A subset
Question 1.3.8. Inclusion maps are always injective; projections, except in a few trivial special cases, are not. What are these special cases? That is, when is the projection
Show solution
The projection
If
Question 1.3.9. Prove:
has exactly one element, namely , whether or not is empty.- If
is nonempty, then is empty.
Show solution
- A pair
would need , and there is no such ; so . Hence , so has at most one element, and the only candidate is . It remains to check that is a function from to . It is a subset of ; its domain is , because it contains no pairs; and the uniqueness condition holds vacuously, again because it contains no pairs. So , and its element is called the empty function. Some intuition comes from counting: if has elements and has , a function makes an independent choice among values for each of the arguments, so there are of them, and . - Since
, choose . A function would contain a pair . But , so no such function exists, and .