# Intuition behind existence of "function sets"

The usual axioms ensure the existence of certain sets that serve as functions. For example (which is chosen arbitrarily) the function f which maps real values of x to x^2+2 can be represented by the set containing all the pairs of the form (x,x^2+2) where x is a real number. I wondered what the intuition behind the existence of such sets is, since it might feel weird that the second (or in general n-th) value depends on a preceding one. Are there some interpretations/reasons on this, for example when interpreting sets as collections? I guess that one could argue that it should be intuitive that the collection of exactly all objects of R matched with exactly those that are of the form x^2+2 should exist, but I wanted to see if there are better views on this. Thanks in advance.

Edit for clarification: This question came up when thinking about foundations from a platonistic viewpoint. Surely I can just accept this by a formalistic viewpoint, but I find that to be not satisfying.

I am aware that functions are intuitively viewed as processes, but I feel like this intuition is not well captured by the definition in set theory, given by a relation (maybe its just me but thats the way I feel about it). It is intuitive that one can have subsets where the objects satisfy certain properties. However, in this case one has a set of objects where the 2nd "coordinate" depends on the first, which made me ask why this dependency "should be allowed" or is "natural to allow". Surely the concept is useful and widely used in many areas, but I was looking for an intuitive explanation justified by the interpretation of sets and not the usefulness of the concept. This lead to the question: Why should collections of pairs be allowed where the second coordinate depends on the first?

• The "intuition" behind a function is that of "rule": to every input the rule produces an output. This intuition evolved into the general notion of correspondence (map). Mar 14 at 12:34
• I'm a little confused by this question. Specifically, you say "it might feel weird that the second (or in general n-th) value depends on a preceding one", but that's not necessary or typical of functions in general (and certainly doesn't apply to the function you've listed. That sounds more like a generated series (like the Fibonacci sequence) than a proper function. What precisely is the intuition that's behind your question? Mar 14 at 16:38
• You have the "rule view": input x and compute x^2+2, and you have the correspondence view: a pair (x,y) such that y satisfies the "equation" y=x^2+2 Mar 14 at 16:47
• @TedWrigley Sorry if I have caused confusion. I edited the question which hopefully clarifies what I meant and gives some context. If I understand you correctly however, you misunderstood my question. I meant the set theoretic notion of a function where the value of an object x is given by the second coordinate of the pair. Mar 14 at 17:29
• @MauroALLEGRANZA Thanks for the comments. I am aware of the process concept, but I am not sure if this is captured in the set theory view. I edited my question in hopes to clarify. Mar 14 at 17:29

It may help to focus on the axiomatic grounding of these sets. Let's say, for the sake of simplicity, that we already accept the existence of the cartesian product R^2 (that is, the set of all ordered pairs (x,y), ranging over all real values of x and y). Then we can use the axiom schema of separation to select the subset of ordered pairs which happen to satisfy the equation y = x^2 + 2. It is intuitively obvious that, for every ordered pair, it will either satisfy the equation or it won't (by the law of the excluded middle), and so intuitively, this seems like a perfectly "reasonable" thing to do - we are just taking a well-defined subset of an existing set. Importantly, this process isn't specific to functions, but can be used to construct any binary relation you like. For example, we might select (x, y) such that x and y have the same integral part, which is certainly not a function because it contains (1, 1.1) and (1, 1.2), but is nevertheless a relation that you can construct in the same way.

1. Is the axiom schema of separation justified in allowing us to do this?
2. Does R^2 exist?

For (2), we can appeal to the axiom of the power set (along with some other tools) to prove that R^2 exists if R exists. If desired, we can further explain the Dedekind cut construction of the reals, etc. all the way down to the axiom of infinity (which states that N exists), but I am doubtful that this level of detail is really what you wanted out of this question, so I am eliding the rest of it.

As for (1), that's arguably the more "philosophical" part of your question. The axiom schema of separation is a weakening of a much stronger axiom, the axiom of unrestricted comprehension, which appears in naive set theory, and states that any set we may describe exists. This turns out to cause logical problems such as Russell's paradox, so Zermelo and Fraenkel added the restriction that we must be taking a subset of some previously-existing set, rather than making up a whole new set from scratch. This then creates the problem that we need some sort of "starting point" for constructing sets, which is why the axiom of infinity exists.

The short and simple answer to "why does the axiom of separation allow these sorts of subsets to be taken?" is "because further restrictions were not necessary to avoid paradoxes." At the time, mathematicians very much wanted a powerful set theory, which would enable the construction of as many sets as reasonably possible, without leading to paradox or contradiction. The notion that a set might "not exist" did not appear in naive set theory, and mathematicians routinely assumed the existence of sets simply by describing them. Nowadays, this is still true, at least for sets containing "simple" objects such as numbers, because nearly all such sets are either possible to explicitly construct using some combination of power set, separation, and replacement, or else they violate the axiom of regularity and are explicitly ruled out. Mathematicians generally don't bother figuring out exactly which sequence of ZFC axioms is required, unless they're doing some kind of computer-assisted proof, where you need to exhaustively prove every single statement, no matter how obvious.

It is exactly the idea of a function

F: X ----> Y

to formalize the fact that each element y of a second set Y depends on exactly one element x of a first set X: y=F(x).

Besides X and Y the function F is a third set, F is a subset of the Cartesian product of X and Y. Hence the concept of a function is formalized by the triple (X,Y,F). One cannot dismiss one of the tree components.

Note that the order of the two components from (x,y) from F is significant: The order expresses that y depends on x, hence a change of y implies a preceeding change of x. But not vice versa: If x changes, the value y=F(x) may remain unchanged: As an example consider a constant function.

• Thanks for taking the time to answer. My question was supposed to aim at why it is reasonable to allow dependence, however. I have edited my question hoping to clarify. Mar 14 at 17:30
• After reading your edit: In mathematics a "function" is a static concept; it documents an existing relationship between elements of two sets. On the other hand, the concept from mathematics and computer science which formalizes a process, is the "algorithm". Note. The same function can be computed by different algorithms. Mar 14 at 19:05

There are twists and turns in the foundations of mathematics that are only worked out by expansive reading.

The "intuitive" picture of functions as "processes" should be contrasted with the historical disparagement of Kant's statements about intuition and the emphasis on removing temporal language from mathematics. Although Frege eventually retracted his logicism, his arguments against describing numeric succession with comparisons to time are still cited in defense of received views in foundations. One aspect of the success had by Hilbert's "Foundations of Geometry" is its explicit intention to present geometry with the pragmatic and temporal language of Euclid.

It is this period of history which explains why the set-theoretic notion of function has the form that it does.

Although rarely mentioned, I believe it had been Dirichlet who first suggested altering the notion of a function to that of a collection of pairs. Since functions use ordered pairs, Weiner's construction of ordered pairs is celebrated. But, of course, it is Kuratowski's pairs which are standard for Zermelo-Fraenkel set theory.

The notion of dependence of a resultant on a given really has no place here beyond a form which conforms to such usage. The notion of models in the form of cumulative hierarchies will simply be a class of sets among which are those with the form of functions.

This notion of function is significant because the replacement schema allows one to conclude that the images associated with these forms are sets whenever the domains are sets.

This notion of function is significant with respect to how advocates of this sort of foundation explain the ability to reason about infinity with only countably many symbols. Look up Skolem's paradox and the Lowenheim-Skolem theorem. Changing logic to undermine the latter is unthinkable because of the effect it would have on the former (hence, even if mathematics could be performed without the axiom of choice, those who accept this foundational view protest as if it cannot).

This notion of function is also important for a way of explaining uncountability without uncountably many symbols in a language. If, for a given set in a given model, no function exists with the given set as the image and the least countably infinite ordinal as the domain, the set is uncountable.

There is, of course, some sleight of hand here. To even speak of a model, one must assume consistency. Since such a thing cannot be satisfactorily proven, this could all be just a house of cards meeting the aesthetic of precisely those schools who emphasized the folklore discussed at the beginning.

Other people who prefer other folklore think of functions differently.

• I don't think this deserves the downvote, but before I vote it up to balance out, would it be okay for you to provide some explicit references here for additional reading, rather than just prompting the reader to "look them up"? Apr 14 at 16:25