S. D. V. Stephens

notes / Studies in Algebra and Group Theory / chapter 1: Sets and Groups / From my book

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 into means that the function is from to .

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 into is a relation such that

  1. , and
  2. if and , then .

Thus for each there is exactly one with , and we write (instead of or ). We call the value that assumes at the argument , and say that maps (sends, transforms) to , written . We denote the function by and call its domain and its codomain. We use the terms map, mapping, transformation, correspondence, operator, and function interchangeably.

The set of all functions from to is a subset of the power set and is denoted .

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 , the range of need not be all of : consists of those such that for some . More generally, for , the image of under is so that . We also write and call it the image of .

Definition 1.3.2 (Injective, surjective, and bijective maps). Let .

  1. is surjective, or maps onto , if ; that is, for every there is an with . We denote surjectivity by .
  2. is injective, or one-to-one, if for all , implies ; equivalently, implies . We denote injectivity by .
  3. 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 , the inclusion map of into is the function defined by for all . The inclusion of into itself is the identity map , ; relation-wise, it is equality on , the set .

Inclusion maps are injective, since says , and identity maps are bijective. An injective map from a set to itself need not be the identity: is an injection , and it is not even surjective.

Definition 1.3.4 (Restrictions and extensions). Let and . The restriction of to is the function given by for all ; conversely, is called an extension of to . Note that .

Definition 1.3.5 (Projections). The projections of onto its factors are the maps

For a relation , the domain and range are the images of under the projections: and .

Definition 1.3.6 (Characteristic functions). Let . If , the characteristic function of is the function given by

Proposition 1.3.7 (Subsets and characteristic functions). The map , , is a bijection. Every function is for exactly one , namely .

Proof. A subset is recovered from its characteristic function as ; so implies , and the map is injective. Given , let . For we have , and for we have , because takes only the values and . So , and the map is surjective. ∎

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 injective?

Show solution

The projection is injective if and only if or has at most one element.

If or , then , and a function with empty domain is injective vacuously. If , then means , so . Conversely, suppose and contains two elements . For any , the pairs and are distinct by Proposition 1.1.1, yet both map to ; so is not injective.

Question 1.3.9. Prove:

  1. has exactly one element, namely , whether or not is empty.
  2. If is nonempty, then is empty.
Show solution
  1. 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 .
  2. Since , choose . A function would contain a pair . But , so no such function exists, and .