15
$\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 described above? It's different, 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 a function? Define a function not as a relation but a triple or define a relation not as a set of ordered pairs but a triple? Or another option?

$\endgroup$
8
  • 7
    $\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$ Commented Oct 10, 2015 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$ Commented Oct 10, 2015 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$ Commented Oct 10, 2015 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$ Commented Oct 10, 2015 at 12:43
  • $\begingroup$ @drhab: What? How are you defining $\langle x,y\rangle$? $\endgroup$ Commented Oct 10, 2015 at 12:52

2 Answers 2

Reset to default
7
$\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$
3
  • $\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$ Commented Oct 10, 2015 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$ Commented Oct 10, 2015 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$ Commented Oct 13, 2015 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$
8
  • $\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$ Commented Oct 10, 2015 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$ Commented Oct 12, 2015 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$ Commented Oct 12, 2015 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$ Commented Oct 12, 2015 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$ Commented Oct 12, 2015 at 19:37

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.