Functions

This chapter covers notes on functions.

Images
Preimage
Restrictions and Extensions
Compositions
Partial Orders of Functions
Surjections
Injections
Bijections
Valued Functions
1. Addition of Valued Functions
Families

In these materials, functions are a particular type of map. A function ${f: X \to Y}$ is a relation from ${X}$ to ${Y,}$ where every element of ${X}$ is paired with exactly one element of ${Y.}$ We say that ${X}$ is the domain of ${f,}$ and ${Y}$ is the range of ${f.}$ Here's the working definition we'll use:

function. Let ${X}$ and ${Y}$ be sets, and ${f \subseteq X \times Y}$ a relation. We call ${f}$ a function if, and only if, for each ${x \in X,}$ there is one element ${y \in Y}$ with ${(x,y) \in f.}$ We call ${X}$ the domain of ${f,}$ denoted ${\dom{f} = X.}$ We call ${Y}$ the range of ${f,}$ denoted ${\ran{f} = Y.}$

A few more bits of terminology: We can expression a function ${f}$ in general with the expression ${f: X \to Y,}$ which we read as " ${f}$ is a function from ${X}$ to ${Y.}$ " Given ${(x,y) \in f}$ the element ${y}$ is called the result of ${f}$ at the argument ${x.}$ Given an argument ${x,}$ we say that ${f}$ sends or maps or transforms ${x}$ onto ${y.}$ Specifically for binary functions, given ${(x,y) \in f,}$ we call ${x}$ the abscissa of the tuple ${(x,y),}$ and ${y}$ the ordinate of ${(x,y).}$

It's important to remember that all functions are relations. However, the converse — all relations are functions — is false. This means that, given a function ${f: X \to Y}$ with ${x \in X}$ and ${y \in Y,}$ all these expressions mean the same thing:

\eqs{ (1) ~~~ & f(x) = y \\[1em] (2) ~~~ & x ~f~ y \\[1em] (3) ~~~ & x ~f~ f(x) }

\eqs{ (4) ~~~ & (x,y) \in f \\[1em] (5) ~~~ & (x,~f(x)) \in f }

Clearly, some notations are superior to others in terms of readability. Option (3) is clearly needlessly unclear, and options (4) and (5) are just short of being too long. We also see that ${f(x) \neq f.}$ In fact, ${f(x)}$ is quite removed from ${f}$ — it's the ordinate of a tuple in the relation ${f.}$

A bit more terminology: Functions can be classified according to relations between their domain and range. Note that the definition below does not establish that ${f}$ is a function from ${A}$ to ${B}$ — it's just some function.

classification of functions. Let ${A}$ and ${B}$ be sets, and ${f}$ some function.

If ${\dom{f} = A,}$ then ${f}$ is a function on ${A.}$
If ${f \subset B,}$ then ${f}$ is a function into ${B.}$
If ${f = B,}$ then ${f}$ is a function onto ${B.}$

Images

While some authors treat image and range synonymously, we distinguish the two terms. From the definition of a function, it's clear that we can have function ${f : X \to Y}$ where ${X = Y.}$ In this case, we say that ${f}$ maps ${X}$ onto ${Y,}$ and we call ${X}$ the domain and ${Y}$ the range, using the usual syntax:

\dom{f} = X \\ \ran{f} = Y

If, however, it turns out that ${Y \subset X,}$ we say that ${Y}$ is the image of ${f,}$ and use the following syntax:

\dom{f} = X \\ \image{(f)} = Y

We use this different notation and wording to make it clear that the codomain ${Y}$ is a subset of the domain ${X}$ (in later sections, we'll see that for some situations, a function's range is often more important than the function itself). If it turns out that ${X \subset Y,}$ we say that ${f}$ is an embedding of ${X}$ into ${Y.}$ For this case, we simply use the notation ${\dom{f} = X}$ and ${\ran{f} = Y.}$

Preimage

Let's suppose we're playing some game consisting of two sets, ${B}$ and ${C.}$ The set ${B}$ consists of a variety of buttons, and the set ${C}$ consists of various checks — a check for ten, a check for a hundred, a checking for a thousand ... incrementing by powers of ten all the way up to a billion. Now suppose that every button in ${B,}$ if pushed, returns some check in ${C.}$

Anyone playing this game is likely interested in the set of buttons ${b \in B}$ where each button returns a check of a particular subset of ${Y}$ — perhaps the subset of checks ${c \subset C}$ such that ${c}$ is at least a million. In this case, we're only interested in a function ${f: B' \to C}$ such that ${c \in C}$ is at least a million. But, even more importantly, we're interested in the set ${B'.}$ We call ${B'}$ a preimage of ${f.}$

preimage. Let ${f}$ be a function from ${X}$ to ${Y.}$ Then the preimage of a set ${S \subseteq Y}$ under ${f}$ is defined as:

f^{-1}[S] = \set{x \in X : f(x) \in S}.

Restrictions and Extensions

In the case where ${f: X \to X,}$ we call ${f}$ the identity map. The identity map introduces us to a special kind of relation called the restriction.

restriction. Let ${f: X \to Y}$ be a function from ${X}$ to ${Y,}$ and the set ${A}$ be a subset of ${X}$ (i.e., ${A \subset X}$ ). Where ${x \in X}$ and ${y \in Y,}$ the function:

f(x) = y ~~~(\text{for}~~ x \in A)

is called the restriction of ${f}$ to ${A}$ . We may denote such a function with:

\eval{f}{A}: A \to X

Informally, restrictions are simply a more convenient way of defining functions for a common scenario. Suppose we have the function:

f: B \to C

We want to define a function ${g: A \to C,}$ but ${A \subset C.}$ That is, we want to communicat that there's a relationship between the members of ${A}$ and the members of ${C,}$ that doesn't include the members of ${B.}$ The identity map allows us to say that:

g(x) = f(x)

where ${x \in A.}$ The function ${g(x)}$ is called the restriction of ${f}$ to ${X,}$ and the function ${f(x)}$ is called the extension of ${g}$ to ${B.}$

Compositions

Suppose we had a function ${f : X \to Y,}$ and a funtion ${g : Y \to Z.}$ In many applications, we want to have some function ${h}$ that takes the result ${y}$ in ${(x,y) \in f,}$ as the argument ${y}$ in ${(y,z) \in g.}$ That is, a function ${h}$ whose result is some value:

g(f(x)).

We call the function ${h}$ the composition of ${g}$ with ${f,}$ and the result ${g(f(x))}$ a composite of ${g}$ with ${f.}$ Simply a put, a composition is a function whose domain consists of the results of another function.

composition. Let ${A,}$ ${B,}$ and ${C}$ be sets with ${f: A \to B}$ and ${g : B \to C.}$ Then the composition of ${g}$ with ${f,}$ denoted ${g \circ f,}$ is defined as a function from ${A \to C}$ where

(g \circ f)(x) = g(f(x))

for all ${x \in A.}$

Compositions are relations that appear in everyday life. For example, a recipe is a composition. Each step in a recipe is a function. E.g., cracking an egg takes an argument — an egg — accompanied with a result — an albumen (egg white) usually encasing a vitellus (yolk). Using the result of the previous step to perform another a step is a composition. E.g., whisking the cracked eggs (the result of the previous step) to produce a mixture.

Partial Orders of Functions

Now that we've defined the concepts of restriction and extension, one interesting consequence is examining them as they relate to partial orders. Suppose ${X,}$ ${Y,}$ and ${F}$ are sets, where ${F}$ is the set of all functions whose domain is included in ${F}$ and whose range is included in ${Y.}$ Now suppose we have the relation:

f \rel g \iff \dom{f} \subset \dom{g} \land \forall x \in \dom{f}\ix{f(x) = g(x)}

That is, ${f}$ is a restriction of ${g}$ (or, equivalently, ${g}$ is an extension of ${f}$ ). Given that all the functions in ${F}$ are just subsets of the Cartesian product ${X \times Y,}$ it follows that the relation:

f \rel g \equiv f \subset g

Surjections

A function ${f: X \to Y}$ is called surjective if every element of ${Y}$ is mapped to at least once.

surjection. Let ${f}$ be a map from the set ${X}$ to the set ${Y.}$ If, for each ${y}$ in ${Y,}$ there exists an ${x \in X,}$ such that:

f(x) = y

then ${f}$ is a surjection, and we write:

f: X \surj Y.

In other words, every element of ${Y}$ gets at least one of ${X.}$ They can get many of ${x,}$ but they must at least have one. For example, this the functions below are surjective functions.

But the functions below are not.

If ${X}$ are ${Y}$ sets, and ${f}$ is a surjective function mapping elements from ${X}$ to ${Y,}$ then:

\card(X) \gte \card(Y).

It follows that either

${X}$ has more members than ${Y,}$ or
${X}$ and ${Y}$ have the same number of members.

Injections

A function ${f: X \to Y}$ is called injective if every element of ${Y}$ is mapped to at most once.

injection. Let ${f}$ be a map from the set ${X}$ to the set ${Y,}$ and ${x \in X.}$ If, for each ${x \neq x',}$

f(x) \neq (x'),

then ${f}$ is an injection, and we write:

f: X \inj Y.

That is, every element of ${Y}$ gets at most one of ${X.}$ They can get none of ${X,}$ but if they do get something from ${X,}$ they can only get one. For example, these are injective functions:

But these are not:

Another way of thinking about injections: They're functions that map distinct elements of the domain to distinct elements of the codomain.

If ${X}$ and ${Y}$ are sets, and ${f}$ is an injective function mapping elements from ${X}$ to ${Y,}$ then:

\card(X) \lte \card(Y)

Thus, it follows that:

${X}$ has less members than ${Y,}$ or
${X}$ and ${Y}$ have the same number of members.

Bijections

A function ${f: X \to Y}$ is called bijective iff it is both surjective and injective.

bijection. Let ${f}$ be a map from the set ${X}$ to the set ${Y.}$ If, for each ${y \in Y,}$ there exists a unique ${x \in X,}$ such that:

f(x) = y,

then ${f}$ is an bijection, and we write:

f: X \bij Y.

For example, these functions only take one appearance:

That is, every element of ${X}$ maps to one, and only one, element of ${Y,}$ and every element of ${Y}$ is mapped to once, and only once. None of these functions are bijective:

From top-left to bottom-right: The first is surjective but not injective, the second is injective but not surjective, and the last two are not functions.

If ${X}$ and ${Y}$ are sets and ${f}$ is a bijective function mapping elements from ${X}$ to ${Y,}$ then:

\card(X) = \card(Y)

That is, ${X}$ and ${Y}$ have the same number of members.

Valued Functions

A function whose codomain is some number set is called a valued function. Such functions are of particular interest in many other areas of mathematics. For example, a function whose codomain is ${\reals}$ is called a real-valued function, a functions whose codomain is ${\uint}$ is called an integer-valued function, and so on. Both real-valued functions and integer-valued functions have some special properties. In the examples that follow, let's suppose the domain and codomain is ${\reals.}$

Addition of Valued Functions

Say we had the functions ${f(x) = x^2}$ and ${g(x) = x - x^2.}$ We can add these two functions:

f + g~~~\ni~~~(f + g)(x) = \tnote{x^2}{$f$} + \tnote{(x - x^2)}{$g$}.

Here is a more explicit definition:

addition of functions. Let ${f: A \to \reals}$ and ${g: A \to \reals}$ with ${x \in \reals.}$ Then ${f + g : A \to \reals}$ is defined for all ${x \in \reals}$ where

f + g~~~\ni~~~f(x) + g(x) = (f + g)(x).

Note that we use the notation ${\ni}$ to denote that ${(f+g)(x)}$ is a member of the function ${f+g.}$ We do so to emphasize the fact that ${f+g}$ is a set, and ${(f+g)(x)}$ is an element of the set. Some authors write ${f+g = (f+g)(x),}$ but this isn't quite correct. Nevertheless, no one ever really writes the notation above. We use it here to make the underlying ideas clearer.

Families

Now that we've seen functions, we introduce another special relation called the family.

family. Let ${I}$ and ${X}$ be sets, and ${f}$ a function defined as follows:

${f: I \to X.}$
Where ${i \in I}$ and ${x \in X,}$ ${f(x) = (i,x) = x_i.}$

We call ${I}$ the index set, ${i \in I}$ an index, ${X}$ the indexed set, ${x \in X}$ a term, and the function ${f}$ a family.

A particularly special type of family is the sequence. But before we examine sequences, we need a special set called the natural numbers.