8
$\begingroup$

Most authors define functions this way:

Given the sets $A$ and $B$. A relation is a subset of $A\times B$. Then given a relation $R$, we define $Dom_R=\{x|(x,y)\in R\}$ and $Img_R=\{x|(y,x)\in R\}$.

Then a function from $A$ to $B$, $f:A\rightarrow B$, is a relation with the property that each element of the domain is related to exactly one element of the image, such that $Dom_f=A$ and $Img_f\subseteq B$.

Well, if we accept those definitions, functions are just special sets of ordered pairs (remember, functions are relations and, as far as I know, this is emphasized in most books). Specifying the set of inputs and the set of outputs is just necessary when describing functions using the axiom of replacement of ZFC, but what really dictates which set is which is its elements. Thus, for example, the function \begin{align}f:\{0,1\}&\rightarrow \mathbb{R}\\0&\mapsto2\\1&\mapsto 3\end{align} and the function \begin{align}g:\{0,1\}&\rightarrow \{2,3\}\\0&\mapsto2\\1&\mapsto 3\end{align} are the same, since both are the set $\{(0,2),(1,3)\}$. The thing is that $g$ is considered a surjection while $f$ is not. And this is really a problem.

Furthermore, the concept of a graph of a function $Gr(f)$, which is the set $\{(x,f(x))|x\in Dom_f\}$, loses its sense, since the graph would be the function itself.

Wouldn't be much better to define the function as an ordered triple $(A,B,f)$, where $A$ is the domain, $B$ the codomain and $f$ the relation with the properties decribed above? It's diferent, since $f$ itself would not be a function, but only the ordered triple would. Then we could define $Gr((A,B,f)):=f$. In this case, the graph of the function would be a relation instead of the function. Also, the notation $f:A\rightarrow B$ could still be used to describe $(A,B,f)$.

To force the function to be a relation, we would have to define relation the same way: the relation would also be an ordered triple $(A,B,R)$, where $R \subseteq A\times B$. But in this case, the relation is not a set of ordered pairs, but the 'graph of the relation' is.

The third and last option is to define both relation and function as a set of ordered pairs, as usually. But although injectivity is a property of a function, surjectivity would rather be a relation between a function $f$ and another given set $B$ called codomain.

Am I getting it right? If so, what is the best way to define function? Define function not as a relation but a triple or define relation not as a set of ordered pairs but a triple? Or another option?

$\endgroup$
  • 5
    $\begingroup$ The correct way to define a function is as a triple $(A,f,B)$ where $A$ is the domain, $B$ is the codomain, and $f\subseteq A\times B$ satisfying the familiar conditions. $\endgroup$ – Ittay Weiss Oct 10 '15 at 12:27
  • $\begingroup$ It depends on the context you are working in. In settheory functions are identified as special subsets of $A\times B$. In the theory of categories $f:=\langle A,G_f,B\rangle$ is a function with domain $A$, codomain $B$ and graph $G_f\subseteq A\times B$. In my view the best strategy is just to go along with these (mastered) differences. $\endgroup$ – drhab Oct 10 '15 at 12:36
  • $\begingroup$ Also for a set $A$ domain (and codomain) can be defined. $A$ is not demanded to be a relation for that: $x\in\text{Dom}(A)$ if $\langle x,y\rangle\in A$ for some $y$. $\endgroup$ – drhab Oct 10 '15 at 12:42
  • $\begingroup$ drhab. The problem is, in settheory, it seems that surjectivity is treated as a property of the function. And I guess that would be wrong... $\endgroup$ – João Victor Bateli Romão Oct 10 '15 at 12:43
  • $\begingroup$ @drhab: What? How are you defining $\langle x,y\rangle$? $\endgroup$ – MPW Oct 10 '15 at 12:52
4
$\begingroup$

One way to proceed is the following, starting from the concept of ordered couple, defined set-theoretically in the usual way.

We define when a set is a relation :

$R \text { is a relation } \ ↔ ∀z(z \in R → ∃x \ ∃y \ (z = \langle x,y \rangle \ ))$.

Thus, a relation is a set of ordered couples.

As usual, we write $xRy$ for $\langle x,y \rangle \in R$.

We define :

$\mathcal {Dom}_R = \{ x : \exists y \ (x R y) \}$

and :

$\mathcal {Img}_R = \{ y : \exists x \ (x R y) \}$.

Then we define when a relation is a function :

$f \text { is a function } ↔ f \text { is a relation } \land ∀x \ ∀y \ ∀z \ (xfy ∧ xfz → y=z)$.

Up to now, no "$A$s" nor "$B$s".

Then we say :

$f \text { is a function from } A \text { into } B \leftrightarrow f \text { is a function } \land \mathcal {Dom}_f=A \land \mathcal {Img}_f \subseteq B$;

$f \text { is a function from } A \text { onto } B \leftrightarrow f \text { is a function } \land \mathcal {Dom}_f=A \land \mathcal {Img}_f = B$.


See : Patrick Suppes, Axiomatic set theory (1960), page 88.

See also : Kenneth Kunen, The Foundations of Mathematics (2009), page 24-25.


Regarding your example, with this approach we have that $f=g$, where $f$ is a function from $\{ 0,1 \}$ into $\mathbb R$, while $g$ is a function from $\{ 0,1 \}$ onto $\{ 2,3 \}$.

In this case, surjectivity is not an "intrinsic" property of $g$; the applicability of the word "onto" depends both on $g$ and on the set $B$, not just on $g$.


A different approach is possible, of course; see :

modify the definition of function in the following way. Firstly for sets $A$ and $B$ we define the product set or Cartesian product of $A$ and $B$ to be the set of all ordered pairs whose first elements are in $A$ and second elements in $B$. This is denoted $A \times B$, and so

$$A \times B = \{ \langle x, y \rangle : x \in A \land y \in B \}.$$

A function is now defined as a triple $f = \langle A, B, R \rangle$, where $R \subseteq A \times B$ is a relation from $A$ to $B$ (the graph of $f$), such that for each $x \in A$ there is one and only one $y \in B$ for which $\langle x, y \rangle \in R$. Thus the domain ($A$) and codomain ($B$) are incorporated in the definition of a function from the outset.


With this approach, the two "objects $\langle \{ 0,1 \}, \mathbb R, f \rangle$ and $\langle \{ 0,1 \}, \{ 2,3 \}, f \rangle$ are not the "same" function.

In this second case, surjectivity is an "intrinsic" property of $\langle \{ 0,1 \}, \{ 2,3 \}, f \rangle$.

$\endgroup$
  • $\begingroup$ Wouldn't that be my third (and last) option? In your case, we can also say that surjection is a relation between a function $f$ and a set $B$, right? $\endgroup$ – João Victor Bateli Romão Oct 10 '15 at 17:04
  • $\begingroup$ Interesting! So what's really wrong in all of this is to treat surjection as a property of the function. All of the options I gave works, but if that's the best and the standard, then I will prefer to use it. In the comments above, they say function are defined as triples in Theory of Categories. Why don't mathematicians come into an agreement and use one universal definition? Anyway, thanks for the answer. $\endgroup$ – João Victor Bateli Romão Oct 10 '15 at 17:33
  • $\begingroup$ Really, your answer is great and it will be accepted (again) soon! You provided really good sources too. But, let me get this straight: as far as I have seen, it seems everybody works with function as it was defined as a triple, and there is the problem of the identity/inclusion function as your source pointed out... and yet the standard definition is the first one you posted (only set of ordered pairs)!? $\endgroup$ – João Victor Bateli Romão Oct 13 '15 at 0:17
0
$\begingroup$

The reason your $g$ is surjective and your $f$ is not, using your definition of function, is that the relation $g$ is taken from $\{0,1\}\times\{2,3\}$ while $f$ is taken from $\{0,1\}\times\mathbb R$.

So $\operatorname{Img}_g$ covers $\{2,3\}$, but $\operatorname{Img}_f$ does not cover $\mathbb R$.

$\endgroup$
  • $\begingroup$ So surjectivity does not depend only of the function, but how we describe them using the Axiom of Replacement (which can be in a non-unique way)? Because $f$ and $g$ are the same set. $\endgroup$ – João Victor Bateli Romão Oct 10 '15 at 12:55
  • $\begingroup$ In the end, @IttayWeiss is correct. The function is not fully defined until you specify (1) the domain, (2) the range, and (3) the rule of assignment. The rule of assignment amounts to the list of ordered pairs you furnish. That, alone, is not a function. The domain and range furnish a context in which to decide if two functions are equal. So equality of the set of ordered pairs is not enough either to define a function or to determine if a function equals a surjective function. $\endgroup$ – MPW Oct 12 '15 at 1:37
  • $\begingroup$ If that's correct and someone provide a proper answer explaining why it is correct and providing sources about this definition in ZFC, then I will undo my last acceptance. Although all of the options given works well (if we also change some other concepts), we have to have a standard. I believe this is too important to overlook. $\endgroup$ – João Victor Bateli Romão Oct 12 '15 at 9:56
  • $\begingroup$ You know what, I will undo my acceptance, so this will be an open problem again. If no one gives another answer, I am going to accept it again within a month. $\endgroup$ – João Victor Bateli Romão Oct 12 '15 at 10:02
  • $\begingroup$ There are clearly different ways to define "function". Defining $f:A\to B$ as as a certain kind of subset of $A\times B$ , means that $f:A\to C$ is the same function when $B\subset C$. This can be a convenience or an annoyance, depending on context. Or depending on your stylistic preference. Textbooks are not unanimous on the definition.Textbooks on set theory are not even unanimous on what an ordered pair is, although $(x,y)=\{x,\{x,y\}\}$ seems to be the favorite. $\endgroup$ – DanielWainfleet Oct 12 '15 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.