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,
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,
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
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{.}\)