From Introduction to Topology, Bert Mendelson, ed. 3, page 15:

A function may be viewed as a special case of what is called a relation.

Yet, a relation is a set

A relation $R$ on a set $E$ is a subset of $E\times E$.

while a function is a correspondence or rule. Is then a function also a set?

  • 1
    $\begingroup$ How do you define "rule?" $\endgroup$ – Thomas Andrews Aug 30 '13 at 13:57

Functions correspond to an abstract rule. Not to something like $f(x)=x+3$. This abstract rule need not be expressible, or even something that you can imagine. Functions, just like any other mathematical object, can be represented as a set. For example, real numbers can be thought of as sets.

Functions are represented as sets of ordered pairs. When we say that $f$ is a function from $X$ into $Y$ then we mean to say that $f$ is a set of ordered pairs $(x,y)$ such that $x\in X$ and $y\in Y$, and the following holds:

  1. For every $x\in X$ there is some $y\in Y$ such that $(x,y)\in f$.
  2. If $(x,y)\in f$ and $(x,y')\in f$ then $y=y'$.

When the latter occurs we can simply replace the $y$ by $f(x)$.

For example, $\{(0,0),(1,0)\}$ is a function from $\{0,1\}$ into $\{0\}$.

  • 4
    $\begingroup$ +1 for "can be represented as a set" rather than "is a set"! $\endgroup$ – Peter Smith Aug 30 '13 at 13:54
  • 1
    $\begingroup$ @Stefan: First of all, it's a matter of usability. If I want to define a class of functions, say all functions from $\kappa$ into $\sf Ord$ (the class of all ordinals) then there is no shared codomain to all functions that I can just quantify over all $f\colon\kappa\to X$. And these sort of classes appear frequently in set theory. As for the second question, no. We don't define everything as sets. The definitions are abstract and we just interpret them as sets. $\endgroup$ – Asaf Karagila Aug 31 '13 at 22:21
  • $\begingroup$ @AsafKaragila : Thanks. If I were just defining one function from set $X$ to set $Y$ (I'm not talking about classes of functions), like in your simple example, I would rather ''represent'' it as an ordered triple $(X, Y, S)$ where $S$ is a subset of $X \times Y$ with the usual requirements. The inclusion of $Y$ is so you know what the codomain is. The inclusion of $X$ is not really necessary but looks nice. I don't know if this is standard. $\endgroup$ – Stefan Smith Aug 31 '13 at 22:37
  • $\begingroup$ @Stefan: But what good is one function? Is all you ever use in mathematics is one function? Why was set theory developed as a foundation for mathematics anyway? So we can talk about sets of objects with certain properties. If a certain definition makes it harder to define and discuss a certain collection, and another definition is easier, then why not use the latter? As for the definition as a triplet, that's the Bourbaki approach and it's standard in many places in mathematics (there's a nice MO thread about it, I'll look for the link). $\endgroup$ – Asaf Karagila Aug 31 '13 at 22:40
  • 1
    $\begingroup$ @Stefan: mathoverflow.net/questions/30381/definition-of-function $\endgroup$ – Asaf Karagila Sep 1 '13 at 1:08

Yes, a function $f:X\to Y$ can be modeled by a set.

And yes, a function can be thought of as a special case of a relation, that is, a subset $R\subseteq X\times Y$. ("Function" after all can be thought of as shorthand for "functional relation.")

This is just reexpressing $f(x)=y$ as $(x,y)\in R$. So, the regular "function-is-a-rule" picture is equivalent to thinking of a subset $f\subseteq X\times Y$, where the set $f$ has special properties that make it a function. (The properties you are probably familiar with, I imagine.)

Relations don't have to be on the same set, as you gave as an example. However, when people say "relation on $E$", that is just shorthand for "relation from $E$ to $E$."

  • 4
    $\begingroup$ +1 for "can be modelled by a set" rather than "is a set"! $\endgroup$ – Peter Smith Aug 30 '13 at 13:53
  • $\begingroup$ @rschweib : I have the same comment for you that I did for Asaf. If you define, or "think of" $f$ as a subset of $X \times Y$, with no other information, then if you give me such a function, I can't tell what the codomain is. $\endgroup$ – Stefan Smith Aug 31 '13 at 22:21
  • $\begingroup$ Dear @StefanSmith : $f$ isn't just any subset, it's a subset with properties that make it a function. Namely, for every $x\in X$ there is a pair in $f$ with $x$ in the first coordinate, and there are not two distinct pairs sharing the same first coordinate. The domain is $X$ and the codomain is $Y$. $\endgroup$ – rschwieb Aug 31 '13 at 23:19
  • $\begingroup$ @rschwieb : Yes, I know $f$ has to have certain properties, I just mean that it is nice to know what the codomain is. If you show me that subset of $X \times Y$ and nothing else, I can't tell what the codomain is. Please see Asaf's comments above. $\endgroup$ – Stefan Smith Sep 2 '13 at 20:44
  • $\begingroup$ @StefanSmith Ah, I see what you mean now. Mainly, I don't think this is a real issue, because when you talk about $f$ being a subset of something, you have to say a subset of what, and then you will say "$X\times Y$" and the codomain will be there. Otherwise it's just a set of pairs, and yes, I would agree with you that the codomain would be unspecified in that case. I'm just not convinced people would present it as a set and not a subset. Thanks for helping me see your idea. $\endgroup$ – rschwieb Sep 2 '13 at 23:23

Others have said, clearly and nicely, how to represent or model functions by sets.

And that's the right way to put it. Here are three reasons not to say that functions are sets.

  1. It might be conventional to treat the binary function $f(x) = y$ as corresponding to a certain set of ordered pairs $(x, y)$, and then treat the ordered pairs by the Weiner-Kuratowski construction. But at both steps we are making arbitrary choices from a range of possibilities. You could use the set of ordered pairs (y, x) [I've seen that done], and you could choose a different set-theoretic representation of ordered pairs [I've seen that done]. Since the conventional association of the function with a set involves arbitrary choices, there isn't a unique right way of doing it: none, then, can be reasonably said to reveal what a function really is. We are in the business of representing (relative to some chosen scheme of representation).

  2. Some functions are "too big" to have corresponding sets. Take the function that maps a set to its singleton. The ordered pairs $(x, \{x\})$ are too many to form a set. If a function is too big to have a corresponding set, it can't be that set.

  3. Most importantly, it would be a type confusion to identify a function with an object like a set. A function maps some object(s) to an object. In terms of Frege's nice metaphor, functions are "unsaturated", come with one or more slots waiting to be filled (where filling the single slot in, say, the unary numerical function the square of ... gives us a number). In modern terminology, functions have an intrinsic arity. By contrast, objects aren't unsaturated, don't have slots waiting to be filled, don't have arities, don't do mapping. And what applies to objects in general applies to those objects which are sets in particular. So functions aren't sets.

  • $\begingroup$ @Peter : Thank you for answering an obvious question. Please forgive my ignorance, but I'm not sure I understand your point #2. The domain of your "function" from #2 is the "set of all sets", and from what I have heard, there is no such thing as the set of all sets, because if you assume such a thing exists, it leads to contradictions. So the domain of your "function" in #2 is not a set. Isn't the domain of any function supposed to be a set? I am not a logician, so please correct any incorrect assertions I may have made. $\endgroup$ – Stefan Smith Aug 31 '13 at 22:28
  • $\begingroup$ One man's modus ponens is another man's modus tollens. It's a mistake to suppose that every function has a set as domain-qua-set, as this example shows. We should think of the domain of a function as being the objects (plural) for which the function is defined: it is a further question whether those objects can form a set. Uusally they do -- but not always. $\endgroup$ – Peter Smith Sep 1 '13 at 16:10
  • $\begingroup$ @PeterSmith : thank you. I ask you again to forgive any ignorance I display. I consulted Wikipedia (I've never found an actual mistake there) and they stated a function ''is a relation between a set of inputs'' etc. I encountered a bit of category theory in grad school. Wasn't the idea of a functor developed so you could define mappings between categories (not just sets)? So wouldn't most people call your ''function'' from your #2 a functor, since its domain is the category of all sets? $\endgroup$ – Stefan Smith Sep 2 '13 at 20:51
  • $\begingroup$ Hello Dr. Smith. Could you please clarify your second point? Why can't $\{ (n, \{n \})| n \in \mathbb{N} \}$ be a set? $\endgroup$ – Ovi Jun 9 '18 at 2:09
  • $\begingroup$ Of course $\{ (n, \{n \})| n \in \mathbb{N} \}$ is a set! The point I was making is that the pairs $(x, \{x \})$, for $x$ any set, are too many to be a set. $\endgroup$ – Peter Smith Jun 9 '18 at 15:20

Let's begin at the other end.

A function can be regarded as a rule for assigning a unique value $f(x)$ to each $x$. Let's construct a set $F$ of all the ordered pairs $(x,f(x))$.

If $f:X\to Y$ we need every $x\in X$ to have a value $f(x)$. So for each $x$ there is an ordered pair $(x,y)$ in the set for some $y\in Y$. We also need $f(x)$ to be uniquely defined by $x$ so that whenever the set contains $(x,y)$ and $(x,z)$ we have $y=z$. In this way there is a unique $f(x)$ for each $x$ as we require.

The ordered pairs can be taken as elements of $X \times Y$ so that $F\subset X \times Y$

If we have a set of ordered pairs with the required properties, we can work backwards and see that this gives us back our original idea of a function.


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.