When do two functions become equal?

Question

When do two functions become equal?

I have stumbled over this definition of equality of functions in elementary real analysis.

Let $X$ and $Y$ be two sets. Let $f:X\rightarrow Y$ and $g:X\rightarrow Y$ be two functions. $f=g$ iff $f(x)=g(x)$ for all $x\in X$.

Of course, this definition is so standard and I have no problem with it. However, as far as I know, this definition is actually a theorem. It can be proved in ZFC set theory. A function is just a set of ordered pairs (with some conditions). Two sets are equal if they have the same elements (the Axiom of Extensionality). With this assumption, one can prove the above definition. However, the proof does not require that the ranges of $f$ and $g$ have to be the same.

Suppose that the ranges are different, let's say $f:\mathbb{R}\rightarrow\mathbb{R}$ defined by $f(x)=x$ and $g:\mathbb{R}\rightarrow\mathbb{C}$ defined by $g(x)=x$. If we consider these functions as sets of ordered pairs, then they are just the set $\lbrace (x,x):x\in\mathbb{R}\rbrace$. Thus they are equal by the Axiom of Extensionality. However, the equality also requires that if objects $a$ and $b$ are equal, then any property which is true for $a$ is also true for $b$. In this case, we know that $f$ is a surjective, but $g$ isn't. Thus $f$ should not be equal to $g$ and hence a contradiction. But this is not a proof by contradiction to show that the ranges must be equal, everything assumed here is just axioms of ZFC and what is equality itself. So it looks like it is inconsistent.

I have searched similar questions in this website, but there is no question or answer that relate to this. The most related answer would be $f$ and $g$ must have the same range so there would be no problem. But logically, this is just an additional assumption to restrict the ability to compare two functions. If they don't have the same range, then you can't compare it, or there will be a paradox. The problem for this answer is, it doesn't solve the above paradox. It just restricts itself to the situation that the paradox won't arise, but the inconsistency is still there.

Lastly, I found another way to solve this problem in a set theory book. In the book, when one considers surjection, one have to specify which set the surjection is over. For example, one has to say whether it's surjection over $\mathbb{R}$ or surjection over $\mathbb{C}$. In this case, the paradox won't arise because $f$ and $g$ are both surjective over $\mathbb{R}$ and not surjective over $\mathbb{C}$. Thus the surjective property are the same for $f$ and $g$. The only problem for this answer is, if one consider the property of 'surjection over its range' instead, then this property is true for $f$ but not for $g$, which implies that $f\neq g$ again.

When do two functions become equal in general? Can anyone clarify this for me?

Thank you in advance.

Answer 1

The problem is that there are two slightly different conventions about what “function” means. The more common one is that, for any function, the codomain has to be specified. So, if two functions have different codomains (e.g. $\Bbb R$ and $\Bbb C$ in your example), then they are different functions, even if they have the same graph. The other convention is to identify the function with its graph, so that any set $f$ of ordered pairs $(x,y)$ such that $y_1=y_2$ whenever $(x,y_1)\in f$ and $(x,y_2)\in f$ is a function. This latter convention is elegant, and does away with the seemingly unnecessary codomain. However, the property of being “onto” becomes relative—onto what?—and the idea of a function being a surjection cannot be used. This matters in some branches of mathematics but not in others.

Answer 2

You're mixing up range with codomain.

If $f:X \to Y$, then $Y$ is the codomain; the intuitive definition is that $Y$ tells you what type of values $f(x)$ has ($f(x)\in Y$). The range is the actual set of values of $\{f(x) \mid x \in X\}$.

If you have $f$ represented as a set of ordered pairs, you can find the domain and range, but you can't find the codomain $Y$. (What's the codomain for the function $\{ (1,1) \}$? You might say $\{1\}$, or $\mathbb Z$, or $\mathbb Q$, etc.) Hence, $Y$ must be specified.

Now when we get back to the question "when are functions $f$ and $g$ equal?", the answer is: a function does not depend on its relation $R_f$; a codomain $Y_f$ must also be supplied. Then $$f=g \iff (R_f = R_g \wedge Y_f = Y_g).$$ The equivalence relation $$f\sim g \iff R_f = R_g$$ is hence useful most of the time, but not always (as you pointed out).

Answer 3

Most of the time, we don't really care about the precise set theoretical definition of a function $f \colon X \to Y$ and this is the cause of your confusion.

In order to answer your question, let me talk about one possible definition in ZF.

For sets $a,b$ we define their ordered pair as $(a,b) := \{ \{a\}, \{a,b\} \}$. Feel free to prove that $(a,b) = (c,d)$ if and only if $a=c$ and $b=d$.

By induction on the number of entries, we define a $(n+1)$ tupel by $(a_1, a_2, \ldots, a_n, a_{n+1}) := ((a_1, \ldots, a_n), a_{n+1})$. Again we can prove $(a_1, a_2, \ldots, a_n) = (b_1,b_2, \ldots, b_n)$ if and only if $a_1 = b_1, \ldots, a_n=b_n$.

We define $X_1 \times \ldots \times X_n := \{ (x_1, \ldots, x_n) \mid x_1 \in X_1, \ldots, x_n \in X_n \}$. Finally, write $f \colon X \to Y$ and call $f$ a function if $f \subseteq X \times Y$ and for all $x \in X$ there is a unique $y \in Y$ s.t. $(x,y) \in f$. We write $f(x)$ for this unique $y$.

Using this definition (which is probably the "standard" one), one can easily read off the domain of $f$, namely $\operatorname{dom} f = \{ x \mid \exists y \in Y \colon (x,y) \in f \}$ and similarly one can read off the image of $f$.

However, one can not read off the co-domain of $f$. In fact, given two functions $f,g$ with domain $X$ s.t. $f(x) = g(x)$ for all $x \in X$, we indeed have $f = g$ as sets, no matter what their co-domains are (as long as they include the image of $f$). As a result of this, the statement "$f$ is surjective" doesn't really make sense, while "$f$ is surjective on $Y$" does.

If one considers this to be undesirable, there is an easy fix: Define a function $f \colon X \to Y$ to be a subset $f \subseteq X \times Y \times \{Y \}$ s.t. for each $x \in X$ there is a unique $y \in Y$ s.t. $(x,y,Y) \in f$. This works fine as long as one doesn't want to differentiate between functions with empty domain.

Answer 4

Here is one way to answer this. I'll start with the axiom of extensionality. It seems like a very useful and common-sense axiom to have. It allows us to assert that functions are equal given that they produce the same outputs on the same inputs. Fine.

But things get messed up when you clash this axiom with a function definition that carries around the extra baggage with it of a domain and a co-domain. Your functional "object" is now not just a set of tuples any more. It is that set plus the extra information of domain and codomain. Under this, awfully cumbersome definition of a function, the nice, common-sense, axiom of extensionality breaks down.

But the axiom of extensionality is so useful, and so common-sense, that it would be absurd to reject it as paradoxical. So we're left instead to examine the definition of a function. Do we really want to be carrying around that cumbersome domain and codomain? For all mathematical intents and purposes, we don't.

Rather, what we can do is consider the domain and co-domain not as integral parts of a function but rather properties of that function. Just like the length of the longest path in a graph is a property of a graph and not inherent to the structure of the graph, so too can a domain and co-domain of a function be viewed. To say a function has a certain domain/co-domain is a typing judgement.

This view of things allows us to define multiple domains/do-domains for the same function. E.g. look at the function $\lambda x \rightarrow 2x$. We can say that the domain is integers, and the co-domain the even integers. Or that both domain and co-domain are the real numbers. My point is, these are properties of the function, not a part of the function itself. And so the following statement appearing in the question no longer leads to a contradiction:

equality also requires that if objects $a$ and $b$ are equal, then any property which is true for $a$ is also true for $b$

I could go on about syntactic equality vs. semantic equality, and the importance of these things when working with formal proof systems, but I think the above suffices for the scope of the question.

---

Edit: I got a bit ahead of myself here. The example $\lambda x \rightarrow 2x$, as rightly pointed out by the commenter below, is really a function class. It is also sometimes called a polymorphic function. Carl Heckman's answer correctly identifies extensionality as an equivalence relation rather than "true" equality (whatever that means). But it's an equivalence relation that we can use as if it were equality most of the time. John Bentin also sheds some light on the usefulness of the codomain, and I must somewhat retract my earlier rejection of this feature "for all mathematical intents and purposes". Stefan's answer gives yet another perspective. If we forget types and just go back to sets, we really don't need the idea of domain/co-domain. However, I personally prefer when types are there- albeit usually in the background as an implicit assumption.