Basic Definitions 221output. Some people also have more than one child from which to choose, and in this
case, the function would not know which child to output. However, there is a function
ChildrenOf that assigns to each person the set of that person's children. If a person has
no children, the output of ChildrenOf is the empty set (0).We now define informally some basic vocabulary that will be more carefully defined
later. We will illustrate these terms with the function SeatOf from Example 1.
The domain of a function is the set of all things that may be input to produce some
output. The domain is usually apparent from the definition of the function. For example,
the domain of SeatOf is the set of all students in the classroom.
The range of a function is the set of all things that are output. The range of SeatOf is
the set of all occupied chairs in the classroom. Once one knows the domain of a function,
one can determine the range by applying the function to each element of the domain.
The codomain of a function is the set of all values that are potential outputs. In in-
formal descriptions, codomains are often not specified. For example, it is perhaps most
reasonable to infer that the codomain of the function SeatOf is the set of all chairs in the
classroom, but it is also plausible to infer that the codomain is the set of all occupied chairs.
The codomain often cannot be determined from the description of the function alone; it
must be inferred from the rest of the discussion. In less formal treatments, the codomain
will often be implicitly defined. For example, in many mathematics courses, the codomain
of most functions is implicitly R. In other cases, as a convenience, the codomain is simply
assumed to be equal to the range.
Everything so far has been intuitively expressed in terms of a black box. A formal
definition of the term function is needed. Traditionally, there have been two ways to define
this term. The first is to consider a function to be a rule. The second is to consider a function
to be a specific kind of set. We will discuss the idea of a function as a rule first, since it is
familiar from both computer programming and mathematics courses. After dealing with a
function as a rule, we will discuss the idea of a function as a set. (We will give our formal
definition in terms of sets.)
4.1.1 Functions as Rules
The notion of a function as a rule is familiar to anyone involved in computer programming.
A function subprogram can be viewed as a series of instructions that tell how to calculate
an output from some input.
Example 5. The following rules define functions:
(a) Let H be the function with domain and codomain equal to N that outputs n/2 for even
inputs and 3n + 1 for odd inputs.
(b) For n e N, compute Fact(n) = n! as follows:
input N
Fact = 1
while N > 0
Fact = Fact. N
N=N-l
print Fact