In what manner are functions sets?

3,006

Solution 1

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:

For every $x\in X$ there is some $y\in Y$ such that $(x,y)\in f$.
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\}$.

Solution 2

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$."

Solution 3

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.

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).
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.
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.

Solution 4

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.

View more solutions

3,006

Doubt

Updated on August 01, 2022

Comments

Doubt 10 months

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?
- Thomas Andrews over 9 years
  
  How do you define "rule?"
Peter Smith over 9 years

+1 for "can be modelled by a set" rather than "is a set"!
Peter Smith over 9 years

+1 for "can be represented as a set" rather than "is a set"!
Stefan Smith over 9 years

@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.
Asaf Karagila over 9 years

@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.
Stefan Smith over 9 years

@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.
Stefan Smith over 9 years

@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.
Asaf Karagila over 9 years

@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).
rschwieb over 9 years

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$.
Asaf Karagila over 9 years

@Stefan: mathoverflow.net/questions/30381/definition-of-function
Peter Smith over 9 years

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.
Stefan Smith over 9 years

@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.
Stefan Smith over 9 years

@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?
rschwieb over 9 years

@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.
Ovi almost 5 years

Hello Dr. Smith. Could you please clarify your second point? Why can't $\{ (n, \{n \})| n \in \mathbb{N} \}$ be a set?
Peter Smith almost 5 years

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.