More about functions

Section A.1 More about functions

Definition A.1.1.

Let \(A\) and \(B\) be sets. The set of all functions between \(A\) and \(B\) is denoted \(B^A\) or \(Hom(A,B)\text{.}\)

The reason for the abbreviation \(Hom\) is because a certain special kind of function that many mathematicians are interested in is called a “homomorphism”.

Theorem A.1.2.

Let \(A\) and \(B\) be finite sets. Then,

\begin{equation*} |B^A| = |B|^{|A|} \end{equation*}

If you were wondering why the set of functions from \(A\) to \(B\) was called \(B^A\) and not \(A^B\text{,}\) hopefully this theorem answers your question. We will not provide a proof of this theorem just yet, and wait until Part III of the book.

Recall that in Chapter 1 we stated but did not prove the following theorem concerning the cardinality of the power set.

Theorem A.1.3.

Let \(A\) be a finite set. Then,

\begin{equation*} |\mathscr{P}(A)| = 2^{|A|} \end{equation*}

For the student who is interested enough to read about cardinalities of functions, we can use the fact that \(|B^A|=|B|^{|A|}\) to prove this theorem by recontextualizing the power set as a function \(A \to \{0,1\}\text{.}\)

Proof.

Let \(A\) be a set and consider the set \(\{0,1\}\) of two elements. We will construct a function \(f:A \to \{0,1\}\text{.}\) The point is that there is a correspondence between the subsets of \(A\) (the elements of \(\mathscr{P}(A)\)) and such functions. Take a subset \(E \subseteq A\text{;}\) if \(a \in E\text{,}\) then we can say \(f(a)=1\text{;}\) and if \(a \not\in E\text{,}\) we can say \(f(a)=0\text{.}\) Likewise, we can go from functions to subsets. So, since there are \(2^{|A|}\) functions \(A \to \{0,1\}\text{,}\) there are also \(2^{|A|}\) subsets.

That proof may have been a little abstract. Consider the following example.

Example A.1.4.

The power set of \(B = \{c,d,e\}\) is

\begin{equation*} \mathscr{P}(B) = \Big\{ \varnothing, \{c\}, \{d\}, \{e\}, \{c,d\}, \{c,e\}, \{d,e\}, \{c,d,e\}\} \end{equation*}

We can see for ourselves that \(|\mathscr{P}(B)|=8=2^3\text{.}\) To understand how each element of the power set can be viewed as a function \(f:B \to \{0,1\}\text{,}\) take the subset \(\{c,d\}\) as an example. Because \(c\) and \(d\) are both in the subset, we say \(f(c)=1\) and \(f(d)=1\text{.}\) On the other hand, \(f(e)=0\text{.}\)

For the two extreme examples, \(\varnothing\) corresponds to the function where \(f(x)=0\) for all \(x \in B\) and \(\{c,d,e\}\) corresponds to the function where \(f(x)=1\) for all \(x \in B\text{.}\)