Exercise 3.5.10
If $f:X \to Y$ is a function, define the graph of $f$ to be the subset of $X \times Y$ defined by $\{(x, f(x)) : x \in X\}$.
(i) Show that two functions $f:X \to Y$, $\tilde{f}:X \to Y$ are equal if and only if they have the same graph.
(ii) Conversely, if $G$ is any subset of $X \times Y$ with the property that for each $x \in X$, the set $\{ y \in Y : (x,y) \in G \}$ has exactly one element ($G$ obeys the vertical line test), show that there is exactly one function $f:X \to Y$ whose graph is equal to $G$.
(iii) Suppose we define a function $f$ to be an ordered triple $f = (X, Y, G)$, where $X$, $Y$ are sets, and $G$ is a subset of $X \times Y$ that obeys the vertical line test. We then define the domain of such a triple to be $X$, the codomain to be $Y$, and for every $x \in X$, we define $f(x)$ to be the unique $y \in Y$ such that $(x,y) \in G$. Show that this definition is compatible with Definition 3.3.1 in the sense that every choice of domain $X$, codomain $Y$, and property $P(x,y)$ obeying the vertical line test produces a function as defined here that obeys all the properties required of it in that definition, and is also similarly compatible with Definition 3.3.8.
Exploration
It is worth thinking a little about what the graph is and isn't. The graph is all the mappings from $x \in X$ to $f(x) \in Y$. It is an important and very informative part of the definition of a function, alongside specifying the domain and co-domain. A graph on its own is not technically the same as a function.
Part (i)
We need to show the following two statements:
- Two functions are equal $\implies$ they have the same graph.
- Two functions with the same graph $\implies$ they are equal.
Let's start with the first statement. Consider two functions $f_1: X \to Y$ and $f_2: X \to Y$. If these two functions are equal, they have the same domain, same co-domain and the same mapping between the two. This last requirement is $f_1(x)=f_2(x)$ for every $x \in X$.
The graph of $f_1$ is $\{(x, f_1(x)) : x \in X\}$.
The graph of $f_2$ is $\{(x, f_2(x)) : x \in X\}$.
Since the two functions are the same, we have $f_1(x)=f_2(x)$ for all $x \in X$, and so the graphs of $f_1$ and $f_2$ are the same.
Let's now consider the second statement. If we have two functions $f_1:X \to Y$ and $f_2:X \to Y$ with the same graph, we have:
$$\{(x, f_1(x)) : x \in X\} = \{(x, f_2(x)) : x \in X\} $$
This means the two functions map each $x \in X$ to the same element of the co-domain, that is, $f_1(x)=f_2(x)$ for all $x \in X$. We are given that the two function share the same domain, $X$, and also the same co-domain, $Y$. Together, this allows us to say the two functions are equal.
Having shown both statements, we have proven that two functions $f:X \to Y$, $\tilde{f}:X \to Y$ are equal if and only if they have the same graph. $\square$
Part (ii)
Let's first show the existence of $f:X \to Y$. We can define a function $f$ with the following properties:
- it has a domain $X$
- it has a co-domain $Y$
- it maps each $x \in X$ to a unique $y \in Y$ as $f(x) = y$
We need to show that the mapping is unique, that is, for every $x \in X$ there is only one $y \in Y$, the vertical line test. We are given that for each $x \in X$ the set $\{ y \in Y : (x,y) \in G \}$ has exactly one element, which is equivalent to the vertical line test.
Thus the function $f(x)=y$ exists, and has a graph $\{(x, f(x)): x \in X\}$
Now let's show the function $f:X \to Y$ is unique. Consider two functions $f_1:X \to Y$ and $f_2:X \to Y$ which meet the given criteria, that is, both have a graph equal to $G \subseteq X \times Y$. We have shown in part (i) that two functions which the same graph are equal. Therefore $f_1=f_2$.
We have shown there is exactly one function $f:X \to Y$ whose graph is equal to $G$. $\square$
Part (iii)
Let's remind ourselves of Definition 3.3.1:
Definition 3.3.1 (Functions). Let $X$, $Y$ be sets, and let $P(x,y)$ be a property pertaining to an object $x \in X$ and an object $y \in Y$, such that for every $x \in X$, there is exactly one $y \in Y$ for which $P(x,y)$ is true (vertical line test). Then we define the function $f: X \to Y$ defined by $P$ on the domain $X$ and codomain $Y$ to be the object, which, given any input $x \in X$, assigns an output $f(x) \in Y$, defined to be the unique object $f(x) \in Y$ for which $P(x,f(x))$ is true. Thus, for any $x \in X$ and $y \in Y$,
$$y = f(x) \iff P(x,y) \text{ is true}$$
Let's also remind ourselves of Definition 3.3.8:
Definition 3.3.8 (Equality of functions). Two functions $f"X \to Y$, $g:X' 'to Y'$ are said to be equal if their domains and codomains agree, and furthermore that $f(x)=g(x)$ for all $x \in X$.
Let's be clear about what is required of us. We need to show that:
- A function defined with a domain $X$, codomain $Y$ and property $P(x,y)$ as per Definition 3.3.1 produces a function as defined by the ordered triple $(X, Y, G)$.
- Such a function defined by the ordered triple $(X, Y, G)$ obeys the properties as required by Definition 3.3.1 and 3.3.8.
Let's consider the first objective.
For a given domain $X$ and codomain $Y$, we can form a unique ordered pair $(X, Y)$. Now a function, as per Definition 3.3.1, has a property $P(x,y)$ which for any $x \in X$ is true for exactly one $y \in Y$ (vertical line test). Thus we can form a set $G \subseteq X \times Y$ such that $G$ obeys the vertical line test. To do this we can use the Axiom of Replacement on the set $X$ and replace each $x$ with the ordered pair $(x,y)$ such that $P(x,y)$ is true, which we know is only true for one $y$ for each $x$. Then we can form an ordered triple $(X, Y, G)$ which is unique to the domain $X$, codomain $Y$ and property $P(x,y)$.
Let's now consider the second objective.
The properties of Definition 3.3.1 are met by virtue of how we constructed $(X, Y, G)$. For example, we know $G$ obeys the vertical line test because it is constructed using $P(x,y)$ which by definition must obey the vertical line test.
Definition 3.3.8 states that two functions are the same if they have the same domain, codomain and map elements from the domain to the codomain in the same way. If we have two functions $(X, Y, G)$ and $(X', Y', G')$, these ordered $n$-tuples are only equal if $X=X'$, $Y=Y'$ and $G=G'$. That is, the domains are the same, the codomains are the same, and the. graphs are the same. We have already shown in part (i) that equal graphs implies equal functions.
No comments:
Post a Comment