Properties of Functions

In the last section, we talked about certain kinds of functions that have properties not had by other functions. Surjective functions have properties not shared with injective functions, and vice-versa. In this section, we swing back to talking about properties that all functions have, though the last property we talk about is a bit more refined when the underlying function is injective.

Empty Inputs Produce Empty Outputs

One classic analogy mathematicians use to talk about functions is that of a machine. Simply put, a machine is a device that takes in some input, operates on that input, and produces an output. Like machines, a function takes in an input, and based on how the function is defined, produces an output.

The machine analogy provides some useful insight into how functions work. For example, what happens if nothing is put into a machine? We’d expect that with no input, the machine can’t produce anything because if there is no input, then there is nothing for the machine to operate on.

The next theorem formalizes this idea to work with our more rigorous definition of function.

Theorem 6.3.1

Let $f : A \to B$ be an arbitrary function.

Then we have that

f (\emptyset) = \emptyset

Proof 6.3.1

General Strategy: We’ll use a proof by contradiction to show that if there is an image in $f (\emptyset)$ , then the empty set would be non-empty!

Presume - for the purpose of showing a contradiction - that $y \in B$ such that $y \in f (\emptyset)$ .

\begin{aligned} y \in f (\emptyset) & Reason \\ ⟺ & \exists x [x \in \emptyset \land y = f (x)] & Definition of Image \\ ⟹ & \exists x [x \in \emptyset] & Rule of Conjunctive Simplification \\ \Rightarrow\Leftarrow & | \emptyset | = 0 & Definition of Empty Set \end{aligned}

Because the presupposition that $\exists y \in f (\emptyset)$ yields a contradiction, we must then have that

\exists y \in f (\emptyset)

which is the same thing as saying

f (\emptyset) = \emptyset

as desired.

We’ll use this theorem in some of the upcoming examples.

A Union of Subsets

Consider an arbitrary function $f : A \to B$ , along with two subsets of the domain $A_{1}, A_{2} \subseteq A$ . Since $A_{1}$ and $A_{2}$ are subsets of the domain of $f$ , we can consider their respective image sets $f (A_{1})$ and $f (A_{2})$ .

Suppose that we first take the union $A_{1} \cup A_{2}$ , and then form the image set $f (A_{1} \cup A_{2})$ . Is that the same thing as taking the union of the two image sets $f (A_{1}) \cup f (A_{2})$ ?

Theorem 6.3.2

Let $f : A \to B$ be an arbitrary function, with $A_{1} \subseteq A$ and $A_{2} \subseteq A$ .

Then we have that

f (A_{1} \cup A_{2}) = f (A_{1}) \cup f (A_{2})

Proof 6.3.1

General Strategy: Here, we really just need to appeal to the definitions for image, and union. We’ll use those definitions, as well as some logical equivalencies involving the Existential Quantifier, inside an element argument.

Suppose we pick an arbitrary element $y$ from the image set $f (A_{1} \cup A_{2})$ :

\begin{aligned} y \in f (A_{1} \cup A_{2}) & Reason \\ ⟺ & \exists x \in (A_{1} \cup A_{2}) [y = f (x)] & Definition of Image \\ ⟺ & \exists x [(x \in A_{1} \cup A_{2}) \land (y = f (x))] & \exists x \in U [p (x)] \Leftrightarrow \exists x [x \in U \land p (x)] \\ ⟺ & \exists x [(x \in A_{1} \lor x \in A_{2}) \land (y = f (x))] & Definition of Union \\ ⟺ & \exists x [(x \in A_{1} \land y = f (x)) \lor (x \in A_{2} \land y = f (x))] & Distribution of \land over \lor \\ ⟺ & (\exists x [x \in A_{1} \land y = f (x)]) \lor (\exists x [x \in A_{2} \land y = f (x)]) & Distribution of \exists over \lor \\ ⟺ & (\exists x \in A_{1} [y = f (x)]) \lor (\exists x \in A_{2} [y = f (x)]) & \exists x \in U [p (x)] \Leftrightarrow \exists x [x \in U \land p (x)] \\ ⟺ & (y \in f (A_{1})) \lor (y \in f (A_{2})) & Definition of Image \\ ⟺ & y \in f (A_{1}) \cup f (A_{2}) & Definition of Union \end{aligned}

Since we’ve just shown that

y \in f (A_{1} \cup A_{2}) ⟺ y \in f (A_{1}) \cup f (A_{2})

we also have that

f (A_{1} \cup A_{2}) = f (A_{1}) \cup f (A_{2})

as desired.

Let’s look at a couple of examples of this theorem in action.

Example 6.3.1

For the sets $A = {1, 2, 3, 4, 5}$ and $B = {a, b, c, d, e}$ , consider the function $f_{1} : A \to B$ where $\begin{aligned} f (1) & = b \\ f (2) & = b \\ f (3) & = b \\ f (4) & = e \\ f (5) & = e \end{aligned}$ depicted below as an arrow diagram:

$An arrow diagram for $f_1: A \rightarrow B$$

Figure 6.3.1

Suppose we let

\begin{aligned} A_{1} & = {1, 2, 3} \\ A_{2} & = {3, 4, 5} \end{aligned}

We have that

A_{1}, A_{2} \subseteq A

. Let's verify that

f (A_{1} \cup A_{2}) = f (A_{1}) \cup f (A_{2})

First, we calculate

f (A_{1} \cup A_{2})

. We start by calculating

A_{1} \cup A_{2}

\begin{aligned} A_{1} \cup A_{2} & = {1, 2, 3} \cup {3, 4, 5} \\ = {1, 2, 3, 4, 5} \end{aligned}

Now, we can calculate

f (A_{1} \cup A_{2})

\begin{aligned} f (A_{1} \cup A_{2}) & = f ({1, 2, 3, 4, 5}) \\ = {b, e} \end{aligned}

Second, we calculate

f (A_{1}) \cup f (A_{2})

\begin{aligned} f (A_{1}) \cup f (A_{2}) & = f ({1, 2, 3}) \cup f ({3, 4, 5}) \\ = {b} \cup {b, e} \\ = {b, e} \end{aligned}

Thus, we have that

f (A_{1} \cup A_{2}) = f (A_{1}) \cup f (A_{2}) = {b, e}

as asserted by Theorem 6.3.1.

Example 6.3.2

Consider the function $f_{2} : {1, 2, 3, 4, 5} \to {a, b, c, d, e}$ where

\begin{aligned} f_{2} (1) & = a \\ f_{2} (2) & = b \\ f_{2} (3) & = d \\ f_{2} (4) & = c \\ f_{2} (5) & = b \end{aligned}

Suppose we wanted to calculate $f_{2} ({1, 3}) \cup f_{2} ({4})$ . We know that ${1, 3} \subseteq Dom (f_{2})$ and ${4} \subseteq Dom (f_{2})$ . Thus, we can use Theorem 6.3.1 to simplify our work a little bit:

\begin{aligned} f_{2} ({1, 3}) \cup f_{2} ({4}) & = f_{2} ({1, 3} \cup {4}) \\ = f_{2} ({1, 3, 4}) \\ = {a, c, d} \end{aligned}

An Intersection of Subsets

We may expect we have a similar result when considering the intersection $A_{1} \cap A_{2}$ , but there is a slight hiccup.

Theorem 6.3.3

Let $f : A \to B$ be an arbitrary function with $A_{1}, A_{2} \subseteq A$ .

Then we have that

f (A_{1} \cap A_{2}) \subseteq f (A_{1}) \cap f (A_{2})

Proof 6.3.2

General Strategy: Here, we’ll use another element argument similar to the one used in Proof 6.3.1. Of course, we’ll appeal to the definition of intersection instead of union.

Let $y$ be an arbitrarily picked element in $f (A_{1} \cap A_{2})$ .

\begin{aligned} y \in f (A_{1} \cap A_{2}) & Reason \\ ⟺ & \exists x \in (A_{1} \cap A_{2}) [y = f (x)] & Definition of Image \\ ⟺ & \exists x [(x \in (A_{1} \cap A_{2})) \land (y = f (x))] & \exists x \in U [p (x)] \Leftrightarrow \exists x [x \in U \land p (x)] \\ ⟺ & \exists x [(x \in A_{1}) \land (x \in A_{2}) \land (y = f (x))] & Definition of Intersection \\ ⟺ & \exists x [(x \in A_{1}) \land (x \in A_{2}) \land (y = f (x)) \land (y = f (x))] & Idempotent Law of \land \\ ⟺ & \exists x [(x \in A_{1}) \land (y = f (x)) \land (x \in A_{2}) \land (y = f (x))] & Commutative Law of \land \\ ⟹ & \exists x [(x \in A_{1}) \land (y = f (x))] \land \exists x [(x \in A_{2}) \land (y = f (x))] & One-sided Distribution of \exists over \land \\ ⟺ & \exists x \in A_{1} [y = f (x)] \land \exists x \in A_{2} [y = f (x)] & \exists x \in U [p (x)] \Leftrightarrow \exists x [x \in U \land p (x)] \\ ⟺ & [y \in f (A_{1})] \land [y \in f (A_{2})] & Definition of Image \\ ⟺ & y \in A_{1} \cap A_{2} & Definition of Intersection \end{aligned}

Note the use of the single-sided logical implication $⟹$ instead of the double-sided logical equivalence $⟺$ in the seventh row of the above sequence of steps. Because that single step required a logical implication, and not a logical equivalency, what we’ve shown is that

y \in f (A_{1} \cap A_{2}) ⟹ y \in A_{1} \cap A_{2}

which means we’ve shown that

f (A_{1} \cap A_{2}) \subseteq f (A_{1}) \cap f (A_{2})

as desired.

Proof 6.3.2 required a logical implication because of the way the Existential Quantifier distributes over the conjunction operator $\land$ . This is why Theorem 6.3.2 uses subset $\subseteq$ instead of equality $=$ .

The logic used was abstract, but we can look at some concrete examples to drive the point home.

Example 6.3.3

Consider the function $g_{1} : {1, 2, 3, 4, 5} \to {a, b, c, d, e}$ depicted below:

A case where the intersection results in a proper subset. — **Figure 6.3.2**

Let's consider the subsets

A_{1} = {1, 2}

and

A_{2} = {3, 4, 5}

. We see that

A_{1} \cap A_{2} = \emptyset

; as such,

g_{1} (A_{1} \cap A_{2}) = g_{1} (\emptyset) = \emptyset

Now we compute

g_{1} (A_{1}) \cap g_{1} (A_{2})

g_{1} (A_{1}) \cap g_{1} (A_{2}) = {b, c} \cap {c, d, e} = {c}

In this case, since

g_{1} (A_{1} \cap A_{2}) = \emptyset

and

g_{1} (A_{1}) \cap g_{1} (A_{2}) = {c}

, we have a proper subset relationship:

g_{1} (A_{1} \cap A_{2}) \subset g_{1} (A_{1}) \cap g_{1} (A_{2})

Example 6.3.4

Consider the function $g_{2} : {1, 2, 3, 4, 5} \to {a, b, c, d, e}$ shown below:

A case where the intersection yields set equality. — **Figure 6.3.3**

Letting

A_{1} = {1, 2}

and

A_{2} = {4, 5}

, we get the following:

\begin{aligned} g_{2} (A_{1} \cap A_{2}) & = g_{2} (\emptyset) \\ = \emptyset \\ = {a} \cap {d, e} \\ = g_{2} (A_{1}) \cap g_{2} (A_{2}) \end{aligned}

Here, we have set equality:

g_{2} (A_{1} \cap A_{2}) = g_{2} (A_{1}) \cap g_{2} (A_{2})

The previous examples relied on splitting up a function’s domain into disjoint subsets. This is an easy way to demonstrate the validity of Theorem 6.3.2 because the mpty set is a subset of every set. Because the empty set was present in both of the previous examples, we were also able to use Theorem 6.3.1 in our calculations as well.

The next few examples will not split up the function’s domain into disjoint subsets.

Example 6.3.5

Consider the function $g_{3} : {1, 2, 3, 4, 5} \to {a, b, c, d, e}$ pictured below:

Another demonstration of Theorem 6.3.2. — **Figure 6.3.4**

Using this function, we see that

\begin{aligned} g_{3} ({1, 2, 3} \cap {3, 4, 5}) & = g_{3} ({3}) \\ = {e} \\ \subset {c, e} \\ = {a, c, e} \cap {c, d, e} \\ = g_{3} ({1, 2, 3}) \cap g_{3} ({3, 4, 5}) \end{aligned}

So here, we have a proper subset:

g_{3} ({1, 2, 3} \cap {3, 4, 5}) \subset g_{3} ({1, 2, 3}) \cap g_{3} ({3, 4, 5})

Example 6.3.6

Consider the function $g_{4} : {1, 2, 3, 4, 5} \to {a, b, c, d, e, f}$ depicted below:

This function is injective. — **Figure 6.3.5**

We consider the subsets

{1, 2, 3}

and

{3, 4, 5}

of the domain again, and proceed as usual:

\begin{aligned} g_{4} ({1, 2, 3} \cap {3, 4, 5}) & = g_{4} ({3}) \\ = {b} \\ = {a, b, c} \cap {b, d, e} \\ = g_{4} ({1, 2, 3}) \cap g_{4} (3, 4, 5) \end{aligned}

This time, we have set equality:

g_{4} ({1, 2, 3} \cap {3, 4, 5}) = g_{4} ({1, 2, 3}) \cap g_{4} (3, 4, 5)

Examples 6.3.3 and 6.3.4 showed functions that were neither injective nor surjective. Even though both domains were split up into disjoint sets, Example 6.3.3 yielded a proper subset while Example 6.3.4 yielded two equal sets. This means that splitting up the domain of a function $f$ into disjoint subsets is not enough to guarantee that $f (A_{1} \cap A_{2}) = f (A_{1}) \cap f (A_{2})$ .

The function in Example 6.3.5 was also neither injective nor surjective, and its domain was split up into two subsets that shared an element. Still, we got that $g_{3} (A_{1} \cap A_{2}) \subset g_{3} (A_{1}) \cap g_{3} (A_{2})$ .

Now consider the function in Example 6.3.6. That function was injective, but not surjective, and when we split up the domain, we did get equal subsets $g_{4} (A_{1} \cap A_{2}) = g_{4} (A_{1}) \cap g_{4} (A_{2})$ .

Subsets of an Injective Function’s Domain

For two sets $A, B$ , the set $A \cap B$ depends on what elements are shared between $A$ and $B$ . As such, it stands to reason that in order to guarantee that $f (A_{1} \cap A_{2}) = f (A_{1}) \cap f (A_{2})$ , we need to focus on what elements are shared between image sets. This is addressed by determining if a function is injective.

As was shown in Example 6.3.6, $f : A \to B$ being injective may be enough to guarantee that $f (A_{1} \cap A_{2}) = f (A_{1}) \cap f (A_{2})$ .

However, Example 6.3.4 shows that just because $f (A_{1} \cap A_{2}) = f (A_{1}) \cap f (A_{2})$ , that does not tell us if $f : A \to B$ is injective.

This pair of observations yields the following theorem:

Theorem 6.3.4

Let $f : A \to B$ be an injective, but otherwise arbitrary, function with $A_{1}, A_{2} \subseteq A$ .

Then we have that

f (A_{1} \cap A_{2}) = f (A_{1}) \cap f (A_{2})

Proof 6.3.3

General Strategy: We’ll proceed in the same way as we did in Proof 6.3.2. This time, we’ll use the fact that $f$ is injective instead of the one-sided distribution of the Existential Quantifier. This will let us use logical equivalence instead of logical implication.

Let $y$ be an arbitrarily picked element in $f (A_{1}) \cap f (A_{2})$ .

\begin{aligned} y \in f (A_{1}) \cap f (A_{2}) & Reason \\ ⟺ & [y \in f (A_{1})] \land [y \in f (A_{2})] & Definition of Intersection \\ ⟺ & \exists x_{1}, x_{2} [x_{1} \in A_{1} \land y = f (x_{1}) \land x_{2} \in A_{2} \land y = f (x_{2})] & Definition of Image \\ ⟺ & \exists x_{1} [x_{1} \in A_{1} \land y = f (x_{1}) \land x_{1} \in A_{2} \land y = f (x_{1})] & x_{1} = x_{2} since f (x_{1}) = f (x_{2}) and f is Injective \\ ⟺ & \exists x_{1} [x_{1} \in A_{1} \land x_{1} \in A_{2} \land y = f (x_{1}) \land y = f (x_{1})] & Commutative Law of \land \\ ⟺ & \exists x_{1} [x_{1} \in A_{1} \land x_{1} \in A_{2} \land y = f (x_{1})] & Idempotent Law of \land \\ ⟺ & \exists x_{1} [x_{1} \in A_{1} \cap A_{2} \land y = f (x_{1})] & Definition of Intersection \\ ⟺ & y \in f (A_{1} \cap A_{2}) & Definition of Image \end{aligned}

We’ve just shown that

y \in f (A_{1} \cap A_{2}) ⟺ y \in A_{1} \cap A_{2}

which means we’ve shown that

f (A_{1} \cap A_{2}) = f (A_{1}) \cap f (A_{2})

as desired.

Theorem 6.3.4 is useful for calculating certain sets that come from intersections of image sets because we have equality. With Theorem 6.3.3, we don’t have equality, but a sort of “upper bound” on what the result could be because without an injective function, all we have is a subset relationship.

Example 6.3.7

Consider the function $h : {1, 2, 3, 4, 5} \to {a, b, c, d, e, f}$ depicted below:

Another injective, but not surjective, function. — **Figure 6.3.6**

Suppose we wanted to calculate

h ({1, 4, 5}) \cap h ({2, 3, 5})

. We see that

{1, 4, 5} \subseteq Dom (h)

and

{2, 3, 5} \subseteq Dom (h)

, and that

h

is injective. This means we can apply Theorem 6.3.3 to simplify our calculation:

\begin{aligned} h ({1, 4, 5}) \cap h ({2, 3, 5}) & = h ({1, 4, 5} \cap {2, 3, 5}) \\ = h ({5}) \\ = {c} \end{aligned}