We now modify our notion of function so that the domain and range are not restricted to subsets of the real numbers. From this point on, we will also allow the possibility that a set is empty.
Given two sets \(X\) and \(Y\text{,}\) \(X \times Y = \{(x,y): x \in X, y\in Y\}\text{.}\) A relation on \(X \times Y\) is a subset of \(X \times Y\text{.}\) A function on \(X \times Y\) is a relation on \(X \times Y\) with the property that no two elements have the same first coordinates. The set of all first coordinates is called the domain of the function and the set of all second coordinates is called the range of the function.
For a function \(f\) on \(X \times Y\) we will write \(f : X \to Y\) and if \((u,v)\) is an element of \(f\) then we will use the notation, \(f(u)=v\text{.}\) In this case, we say that \(f\) maps \(u\) to \(v\text{.}\)
If \(f: X \to Y\) is a function, then \(f\) is injective (one-to-one) if no two elements of \(X\) map to the same element in \(Y\text{.}\) We say that \(f\) is surjective (onto \(Y\)) if for each element \(y \in Y\) there is some element \(x \in X\) such that \(f(x) = y\text{.}\) We call an injective function an injection, a surjective function a surjection, and a function that is both injective and surjective a bijection.
Show that the function \(f: \R \to Y\) defined by \(f(x) = \frac{x}{x-2}\) is not surjective if \(Y=\R\text{,}\) but is surjective if \(Y\) is the range of \(f\text{.}\)
Let \(f: X \to Y\) be a surjection. Show that \(f\) is injective if and only if there is a function \(g: Y \to X\) so that \(g(f(x)) = x\) for all \(x \in X\text{.}\)
Given a function \(f: X \to Y\text{,}\) the relation \(f^{-1}\) is defined by \(f^{-1} = \{ (v,u) : (u,v) \in f \}\text{.}\)
The set \(f^{-1}\) might not be a function. If \(f\) is injective then by Theorem 8.4 we have that \(f^{-1}\) is a function. From this point forward, we may use (i) “\(\exists\)” to mean “there exists,”(ii) “\(\not \in\)” to mean “is not in” and (iii) “\(\ni\)” to mean “such that.”
If \(f: X \to Y\) and \(A \subseteq X\) then the image of \(A\) under \(f\) is \(\{ f(x) : x \in A\}\) and is denoted by \(f(A)\text{.}\) More precisely, \(f(A) = \{ y \in Y : \exists x \in A \ni f(x) = y \}\text{.}\)
If \(f : X \to Y\) and \(A \subseteq Y\) then the inverse image of \(A\) under \(f\) is \(\{ x \in X : f(x) \in A \}\) and is denoted by \(f^{-1}(A)\text{.}\) This is called the pre-image of \(A\) under \(f\).
Are Definition 8.6 and Definition 8.7 acceptable definitions or are they an abuse of notation?
Show that if \(f : X \to Y\) then \(f\) is surjective if and only if the inverse image of every non-empty subset of \(Y\) is non-empty.
Assume that each of \(A\) and \(B\) are subsets of the set \(X\text{.}\) Assume that \(\Lambda\) is a set and that \(A_{\lambda}\) is a subset of \(X\) for each \(\lambda \in \Lambda\text{.}\) The set \(\Lambda\) is called an index set.
\(\emptyset =\) the empty set
\(\displaystyle{ A^c = \{ x \in X : x \not\in A \}}\)
\(\displaystyle{ A \cup B = \{ x \in X : x \in A \mbox{ or } x \in B \}}\)
\(\displaystyle{ A \cap B = \{ x \in X : x \in A \mbox{ and } x \in B \}}\)
\(\bigcup_{\lambda \in \Lambda} A_{\lambda} = \{ x \in X : x \in A_{\lambda} \mbox{ for some } \lambda \in \Lambda \}\)
\(\bigcap_{\lambda \in \Lambda} A_{\lambda} = \{ x \in X : x \in A_{\lambda} \mbox{ for every } \lambda \in \Lambda \}\)
We won't present the next theorem. You only need to write down a proof if you cannot write down a proof.
Assume that each of \(A, B\) and \(C\) are subsets of the set \(X\text{.}\)
\(\displaystyle{ A \cup B = B \cup A \mbox{ and } A \cap B = B \cap A}\)
\(\displaystyle{ A \cup \emptyset = A \mbox{ and } A \cap \emptyset = \emptyset}\)
\(\displaystyle{ A \cup X = X \mbox{ and } A \cap X = A}\)
\(\displaystyle{ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \mbox{ and } A \cup (B \cap C) = (A \cup B) \cap (A \cup C)}\)
\(\displaystyle{ \left( A^c \right)^c = A, \; \; A \cap A^c = \emptyset, \; \; \emptyset^c = X, \mbox{ and } X^c = \emptyset}\)
\(\displaystyle{ A \subseteq B \iff B^c \subseteq A^c }\)
Assume that \(\Lambda\) is a set and that \(A_{\lambda}\) is a set for each \(\lambda \in \Lambda\text{.}\) Show that
\(\left( \bigcup_{\lambda \in \Lambda} A_\lambda \right)^c = \bigcap_{\lambda \in \Lambda} \left(A_\lambda\right)^c\text{,}\)
\(\left( \bigcap_{\lambda \in \Lambda} A_\lambda \right)^c= \bigcup_{\lambda \in \Lambda} \left( A_\lambda \right)^c\text{,}\)
\(A \cap (\bigcup_{\lambda \in \Lambda} A_\lambda) = \bigcup_{\lambda \in \Lambda} (A \cap A_\lambda)\text{,}\) and
\(A \cup (\bigcap_{\lambda \in \Lambda} A_\lambda) = \bigcap_{\lambda \in \Lambda} (A \cup A_\lambda)\text{.}\)
Assume that \(f: X \to Y\) is a function, \(\Lambda\) is a set, and \(B_{\lambda}\) is a subset of \(Y\) for each \(\lambda \in \Lambda\text{.}\) Show that
\(f^{-1} (\bigcup_{\lambda \in \Lambda} B_\lambda) = \bigcup_{\lambda \in \Lambda} f^{-1}(B_\lambda)\text{,}\) and
\(f^{-1} (\bigcap_{\lambda \in \Lambda} B_\lambda) = \bigcap_{\lambda \in \Lambda} f^{-1}(B_\lambda)\text{.}\)
Assume that \(f: X \to Y\) is a function and \(D\) is a subset of \(Y\text{.}\) Show that \(\left( f^{-1}(D) \right)^c = f^{-1}(D^c)\text{.}\)
Assume that \(f : X \to Y\) is a function, \(A \subseteq X\text{,}\) and \(D \subseteq Y\text{.}\) Show that
\(f(f^{-1}(D)) \subseteq D,\)
\(f^{-1}(f(A)) \supseteq A,\) and
if \(f\) is surjective, then \(f(f^{-1}(D))=D\text{.}\)
A set is countable if it is the range of some sequence.
Every finite set is countable, the natural numbers are countable and the integers are countable.
The rational numbers are countable.
If \(A_i\) is a countable set for \(i = 1, 2, \dots , n\) then \(\bigcup_{i=1}^n A_i\) is a countable set.
If \(A_i\) is a countable set for \(i \in \Nat\text{,}\) then \(\bigcup_{i \in \Nat} A_i\) is a countable set.
A set is perfect if every point of the set is a limit point of the set.
Show that there exists a set, other than \(\R\text{,}\) that is countable, infinite and closed. Show there exists a set that is countable and perfect. Show that there exists a set that is closed and perfect.
No set is countable, closed and perfect.
The real numbers are not countable.
This fun foray to show that \(\R\) is not countable was unnecessary, since we showed this in Theorem 2.19.