Naive Set Theory: Functions

Set Algebra on Functions

Functions are sets, and because they are sets, we may use algebra operations such as union and intersection on them. Of importance is whether the resulting sets are also functions. For the following subsections, let $f : X \rightarrow Y$ and $g : A \rightarrow B$ be the two functions in question.

Restriction (Subset)

The subset of a function is always a function. This fact follows nearly directly from the definitions of both subset and function.

However, there is a second, equivalent way to think of the subset of a function. Namely, the function's domain is restricted to a subset of its original, and the image set is naturally restricted to only those values that still have corresponding elements in the restricted domain. Formally, the restriction of a function $f : A \rightarrow B$ to a subset $A' \subseteq A$ is a new function $f|A' : A' \rightarrow B$ defined by $f|A' = \{(a, f(a)) : a \in A'\}$. Equivalently, the rule for $f|A'$ is simply $f|A'(a) = f(a)$ for all $a \in A'.$

Complement

The complement of a function is almost never a function. Recall that a function is a subset of the Cartesian product of its domain and codomain. Therefore, the complement of a function includes all ordered pairs of elements in its domain with every element of the codomain that aren't in the function. It follows that only constant functions (i.e. functions with singleton codomains) have complements that are inverses.

Intersection

The intersection of two functions is always a function. However, a word of caution: recall that the empty set is a function. That the intersection of two functions is always a function does not imply that the resulting function is always nonempty.

Union

The union of two functions is a more interesting matter. If $g \subseteq f,$ then clearly $f \cup g = f$ and is therefore a function. In fact, the elements of any partition of $f$ are functions whose union is trivially $f.$ Thus we can see that the union of disjoint functions is a function. But need they be disjoint? There is clearly a problem if $x \in X \cup S$ but $f(x) \neq g(x).$ However, if $f(x) = g(x),$ then a lack of disjointedness is insufficient to preclude $f \cup g$ from being a function.

The Pasting Lemma resolves these investigations with a powerful biconditional: $f \cup g$ is a function $f \cup g : X \cup A \rightarrow Y \cup B$ if and only if $f|_{X \cap A} = g|_{X \cap A}.$

Set Difference

The set different $f - g$ is always a function unless $f = g,$ in which case the difference is empty and therefore not a function. But as with intersections, be wary of how easy it is to construct the empty function from a set difference.

Problems

  1. Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a function whose rule is $f(x) = \cos(x)$. Graph the following:

    1. $f|\mathbb{R}_{[-\pi,\pi]}$
    2. $f|\mathbb{R}_{[-\frac{3\pi}{4},-\frac{\pi}{4}]}$
    3. $f|\mathbb{R}_{[-\frac{pi}{2},\frac{3\pi}{4}]}$
    1. f|R_[-pi,pi]
    2. f|R_[-3pi/4,-pi/4]
    3. f|R_[-pi/2,3pi/4]
    Show Answer

  2. Let $f : A \rightarrow B$ be a function, and let $A'' \subseteq A' \subseteq A$. Show that $f|A'' = (f|A')|A''$.

    The restriction $(f|A')|A''$ is a function whose codomain is $B$ and whose rule is $\{(a, f|A'(a)) : a \in A''\}$. In turn, the restriction $f|A'$ is a function whose codomain is $B$ and whose rule is $\{(a, f(a)) : a \in A'\}$. It follows that for all $a \in A''$, $f|A'(a) = f(a)$. Therefore we can rewrite the rule for $(f|A')|A''$ as $\{(a, f(a)) : a \in A''\}$. But this is exactly the rule for $f|A''$. Because $(f|A')|A''$ and $f|A''$ have the same codomain and rule, the two restrictions are equal.

    Show Answer

  3. Provide an example of a function whose complement is a nonempty function.

    Let $f : \{x, y\} \rightarrow \{a, b\}$ be defined by $f(x) = a$ and $f(y) = b.$ The Cartesian product of the domain and codomain is $\{x, y\} \times \{a, b\} = \{(x, a), (x, b), (y, a), (y, b)\}.$ We see therefore that $f^c = \{(x, b), (y, a)\}$ and is therefore a function.

    Show Answer

  4. Give and example of a function whose complement is not a function.

    Let $f : \{x, y, z\} \rightarrow \{a, b, c\}$ be defined by $f(x) = a,$ $f(y) = b,$ and $f(z) = c.$ The Cartesian product of the domain and codomain is $\{x, y, z\} \times \{a, b\} = \{ (x, a), (x, b), (x, c), (y, a), (y, b), (y, c), (z, a), (z, b), (z, c)\}.$ We therefore see that $f^c = \{(x, b), (x, c), (y, a), (y, c), (z, a), (z, b)\}.$ Because $f^c$ maps $x$ (and $y$ and $z$ for that matter) to multiple elements in its codomain, it is not a function.

    Show Answer

  5. Show that if a function has a singleton range, then its complement is an empty function.

    Let $f : X \rightarrow Y$ be a function. Assume $Y = \{y\}.$ Then $f = \{(x, y) : x \in X\} = X \times Y.$ It follows that $f^c$ is empty and therefore a function.

    Show Answer

  6. Show that if a function has a range with 2 elements in it, then its complement is a function.

    Let $f : X \rightarrow \{a, b\}$ be a function. It follows that for any $x \in X,$ either $f(x) = a$ or $f(x) = b.$ Whichever is the case, the alternate choice is a member of $f^c.$ Since these cases cover all elements of $X \times \{a, b\},$ it follows that $f^c$ is a function.

    Show Answer

  7. Show that the intersection of two functions is always a function.

    Consider two functions $f$ and $g.$ Since $f \cap g \subseteq f,$ and the subset of a function is a function, it follows that $f \cap g$ is a function.

    Show Answer

  8. Give an example of two functions whose union is also a function.

    Consider the two functions $f = \{(x, y)\}$ and $g = \{(a, b)\}.$ We can see that their union $f \cup g = \{(x, y), (a, b)\}$ is also a function.

    Show Answer

  9. Give an example of two functions whose union is not a function.

    Consider the functions $f = \{(x, y)\}$ and $g = \{(x, z)\}.$ We can see that $f \cup g = \{(x, y), (x, z)\}$ is not a function.

    Show Answer

  10. Pasting Lemma: Show that for any two functions $f : X \rightarrow Y$ and $g : A \rightarrow B,$ their union $f \cup g$ is a function $f \cup g : X \cup A \rightarrow Y \cup B$ if and only if $f|_{X \cap A} = g|_{X \cap A}.$

    First, assume $f \cup g$ is a function $f \cup g : X \cup A \rightarrow Y \cup B.$ Consider $(x, y) \in f \cup g$ where $x \in X \cap A.$ Since $f \cup g$ is a function, $y$ is unique. Therefore $f(x) = y = g(x).$. It follows that $f|_{X \cap A} = g|_{X \cap A}.$

    Conversely, assume $f|_{X \cap A} = g|_{X \cap A}.$ Then $f|_{X - A} \cup f|_{X \cap A} \cup g_{A - X}$ is a partition of $f \cup g$ whose domains are all disjoint. Since the union of functions with disjoint domains is a function, it follows that $f \cup g$ is a function.

    Alternate proof of the first direction: Proof by contraposition: Assume $f|_{X \cap A} \neq g|_{X \cap A}.$ Then there exists some $x \in X \cap A$ such that $f(x) = y$ and $g(x) = z$ and $y \neq z.$ This precludes $f \cup g$ from being a function.

    Show Answer

  11. Show that the union of two functions with disjoint domains is a function.

    Consider two functions $f : X \rightarrow Y$ and $g : A \rightarrow B$ with the property that $X$ and $A$ are disjoint. Consider $x \in X \cup A.$ Since $X$ and $A$ are disjoint, then either $x \in X$ or $x \in A.$ If $x \in X,$ then there is a unique $y \in Y$ such that $(x, y) \in f,$ and therefore $(x, y) \in f \cup g.$ Likewise, since $x \notin A,$ there is no $z$ such that $(x, z) \in g.$ If instead $x \in A,$ then there is a unique $b \in B$ such that $(x, y) \in g,$ and therefore $(x, y) \in f \cup g.$ Likewise, since $x \notin X,$ there is no $c$ such that $(x, c) \in f.$ Since there is a unique element in the codomain for each element in the domain, $f \cup g$ is a function.

    Show Answer

  12. Show that the set difference of two functions is a function.

    Let $f$ and $g$ be functions. Since $f - g \subseteq f,$ and the subset of a function is always a function, it follows that $f - g$ is a function.

    Show Answer