Example 7.
Prove that \(\Z\subseteq\Q\text{.}\)
Section 1.3 Sets and Functions
Recall that \(A\) is a subset of \(B\) (written \(A\subseteq B\)) if every element \(x\in A\) is also an element of \(B\text{.}\) When a set is defined as a subset of another set with a given property, we often use “set builder” notation, such as
\begin{equation*}
\setof{n\in\Z}{2\text{ divides } n}
\end{equation*}
for defining the even numbers. If a set has no elements, such as
\begin{equation*}
\setof{\text{episodes } E \text{ of}\textit{ Andor}}{E\text{ is bad}},
\end{equation*}
we call it the empty set, \(\emptyset\text{.}\) The familiar intersection (\(\cap\)) and union (\(\cup\)) operators are very useful. Recall that \(A\subsetneq B\) means that \(A\) is a subset of \(B\) and \(A\ne B\text{.}\) Finally, we define \(A\setminus B\) to be the set of all elements in \(A\) which are not in \(B\text{.}\)
Example 8.
Decide whether \(\N \cup \setof{-n}{n\in\N} = \Z\text{.}\)
Example 9.
Find three nonempty sets \(A, B, C\) such that \(A\cap B = \emptyset\text{,}\) \(B\in C\text{,}\) and \(A\notin C\text{.}\)
Example 10.
More interestingly, we can define infinite combinations of these things, if we have a collection of sets \(X_\alpha\text{,}\) one for each element \(\alpha \in A\text{,}\) where \(A\) is an infinite set.
Problem 11.
Find (nonempty) sets \(S_i \subseteq \N\) indexed by \(i\in \N\) such that \(S_{i+1}\subsetneq S_i\) and
\begin{equation*}
\bigcap\limits_{i=1}^\infty S_i = \emptyset.
\end{equation*}
Problem 12.
Find (nonempty) sets \(S_i\subsetneq \N\) indexed by \(i\in \N\) such that \(S_i\subsetneq S_{i+1}\) but
\begin{equation*}
\bigcup\limits_{i=1}^\infty S_i\ne \N.
\end{equation*}
We should also recall that, for us, a function is a set.
Definition 13.
A function from a set \(A\) to a set \(B\) is a subset \(f\) of the Cartesian product \(A\times B\) such that there is precisely one \((a,b)\in f\) for each \(a\in A\text{.}\) We call \(A\) the domain, and say that \(f(a) = b\) if \((a,b)\in f\text{.}\) There is no standard name for \(B\text{,}\) but if you insist on having one, use codomain. We write \(f : A\to B\text{.}\)
Example 14.
Write some function from \(\Z\) to itself this way.
Note that Definition 13 means that \(A\) and \(B\) are inextricably part of the definition of a function. The rule for determining the output for a given input is only part of the story.
Recall a few properties that functions might have.
-
A function from \(A\) to \(B\) is onto, or surjective if, for each \(b\in B\) there is an \(a\in A\) such that \(f(a) = b\text{.}\)
-
A function from \(A\) to \(B\) is one-to-one, or injective if, whenever \(a,a'\in A\) and \(a\ne a'\text{,}\) then \(f(a) \ne f(a')\text{.}\)
-
A function from \(A\) to \(B\) is a one-to-one correspondence, or bijection, if it is one-to-one and onto.
Example 15.
Suppose that \(f : A\to B\) is given by \(f(x) = x^2\text{,}\) where \(A = B = \Z\text{.}\) Explain why \(f\) is neither one-to-one nor onto. Then, change \(A\) or \(B\) so that it is one-to-one. Finally, find a way to change it to be onto.
Example 16.
Find a bijection from \(\Z\) to itself that is not the identity. If you remember what an inverse function is, find that, too.
There are two more important sets relevant to a given function.
Definition 17.
Let \(f : A\to B\) be a function.
-
If \(S\subseteq A\text{,}\) we call the image of \(S\) under \(f\), denoted \(f(S)\text{,}\) the set\begin{equation*} \setof{f(x)}{x\in S}. \end{equation*}
-
If \(T\subseteq B\text{,}\) we call the preimage of \(T\) under \(f\), denoted \(f^{-1}(T)\text{,}\) the set\begin{equation*} \setof{x\in A}{f(x)\in T}. \end{equation*}
Notice that the preimage exists whether or not the inverse function exists (and the notation \(f^{-1}\) refers only to the preimage in this course). We call the image of the entire domain the image of the function, \(f(A)\text{.}\)
Example 18.
If \(f(x) = x^2\) from \(\Z\) to itself, find \(f(\set{-2,-1,0,1,2})\) and \(f^{-1}(\set{0,1,4})\text{.}\)
Problem 19.
Find functions \(f,g\) and sets \(S,T\) such that \(f(f^{-1}(T))\ne T\) and \(g^{-1}(g(S))\ne S\text{.}\) (Note that this is not composition!)
Problem 20.
With all sets appropriately defined, only one of the two following statements is true. Prove one and disprove the other.
\begin{equation*}
f(X\cap Y) = f(X) \cap f(Y)
\end{equation*}
\begin{equation*}
f^{-1}(X\cap Y) = f^{-1}(X) \cap f^{-1}(Y).
\end{equation*}
