Skip to main content

# 3.4.4: First-class objects

One difficulty that people sometimes have with mathematics is its generality. A set is a collection of entities, but an ‘entity’ can be anything at all, including other sets. Once we have defined ordered pairs, we can use ordered pairs as elements of sets. We could also make ordered pairs of sets. Now that we have defined functions, every function is itself an entity. This means that we can have sets that contain functions. We can even have a function whose domain and range are sets of functions. Similarly, the domain or range of a function might be a set of sets, or a set of ordered pairs. Computer scientists have a good name for this. They would say that sets, ordered pairs, and functions are first-class objects or first-class citizens. Once a set, ordered pair, or function has been defined, it can be used just like any other entity. If they were not first-class objects, there could be restrictions on the way they can be used. For example, it might not be possible to use functions as members of sets. (This would make them ‘second class.’)

One way that programming languages differ is by what they allow as first- class objects. For example, Java added a ‘lambda syntax’ to help writing ‘closures’ in version 8.

For example, suppose that A, B, and C are sets. Then since A × B is a set, we might have a function f : A × B C. If (a, b) ∈ A × B, then the value of f at (a, b) would be denoted f ((a, b)). In practice, though, one set of parentheses is usually dropped, and the value of f at (a, b) is denoted f (a, b). As a particular example, we might define a function p : N × N → N with the formula p(n, m) = nm + 1. Similarly, we might define a function q : N × N × N → N × N by q(n, m, k) = (nm k, nk n).

Suppose that A and B are sets. There are, in general, many functions that map A to B. We can gather all those functions into a set. This set, whose elements are all the functions from $$A$$ to $$B,$$ is denoted $$B^{A} .$$ (We'll see later why this notation is reasonable.) Using this notation, saying $$f : A \rightarrow B$$ is exactly the same as saying $$f \in B^{A} .$$ Both of these notations assert that f is a function from A to B. Of course, we can also form an unlimited number of other sets, such as the power set $$\mathcal{P}\left(B^{A}\right),$$ the cross product $$B^{A} \times A,$$ or the set $$A^{A \times A}$$, which contains all the functions from the set A × A to the set A. And of course, any of these sets can be the domain or range of a function. An example of this is the function $$\varepsilon : B^{A} \times A \rightarrow B$$ defined by the formula $$\mathcal{E}(f, a)=f(a) .$$ Let's see if we can make sense of this notation. Since the domain of $$\mathcal{E}$$ is $$B^{A} \times A,$$ an element in the domain is an ordered pair in which the first coordinate is a function from A to B and the second coordinate is an element of A. Thus, E( f , a) is defined for a function f : A B and an element a A. Given such an f and a, the notation f (a) specifies an element of B, so the definition ofE( f , a) as f (a) makes sense. The function E is called the ‘evaluation function’ since it captures the idea of evaluating a function at an element of its domain.

Exercises

1. Let A = {1, 2, 3, 4} and let B = {a, b, c}. Find the sets A × B and B × A.

2.Let A be the set {a,b,c,d}. Let f be the function from A to A given by the set of ordered pairs {(a, b), (b, b), (c, a), (d, c)}, and let g be the function given by the set of ordered pairs{(a, b), (b, c), (c, d), (d, d)}. Find the set of ordered pairs for the composition g f .

1. Let A = {a, b, c} and let B = {0, 1}. Find all possible functions from A to B. Give each function as a set of ordered pairs. (Hint: Every such function corresponds to one of the subsets of A.)
2. Consider the functions from Z to Z which are defined by the following formulas. Decide whether each function is onto and whether it is one-to-one; prove your answers.

a) f (n) = 2n b) g(n) = n + 1 c) $$h(n)=n^{2}+n+1$$ d) $$s(n)=\left\{\begin{array}{ll}{\mathrm{n} / 2,} & {\text { if } n \text { is even }} \\ {(\mathrm{n}+1) / 2,} & {\text { if } n \text { is odd }}\end{array}\right.$$

5. Prove that composition of functions is an associative operation. That is, prove that functions f : A B, g : B C, and h : C D, the compositions (h g) ◦ f and h ◦ (g f ) are equal.

6. Suppose that f : A B and g : B C are functions and that g f is one-to-one.a) Prove that f is one-to-one. (Hint: use a proof by contradiction.)
b) Find a specific example that shows that g is not necessarily one-to-one.

7.Suppose that f: A B and g: B C, and suppose that the composition gf is an onto function.

a) Prove that g is an onto function.
b) Find a specific example that shows that f is not necessarily onto.