Can a function return itself or take itself as an argument?

Question

I'm curious whether a function can take itself as an argument or return itself. That is to say: Is there a function $f$ such that $f() = f$? Or perhaps less confusingly if you aren't used to functions which don't take arguments: Is there a function $f$ and an object $x$ such that $f(x) = f$? To make it even more clear: This would imply that $(f(x))(x) = f(x) = f$.

Please don't confuse this with something like $\text{id}(\text{id}(5))$. What's happening here is that the outer (call to the)* identity function takes the result of the inner (call to the)* identity function as an argument, not the identity function itself.

 * I have no idea how mathematicians would say this. Too much computer science, too little math. ;-) Would be nice if you dropped this in, though, so that I can learn about mathematical terminology.

Answer 1

A function from a set $A$ to a set $B$ is a subset of $A\times B$ with some additional properties required. You want that this subset of $A\times B$ is again an element of $B$.

For example, if $A=\emptyset$ then, no matter what $B$ is, there is only one function $A\to B$ because already $\emptyset\times B=\emptyset$. Now all we need is $\emptyset \in B$. Granted, this does not make $f(x)=f$ for some $x\in A$, so we go to the next simple case that $A$ has precisely one element, $A=\{a\}$. Then we need $f=\{( a,f)\}$ (and of course $f\in B$). In the most common foundation of math, ZFC set theory, this is not possible: Thee, the ordered pair $(a,f)$ is usually defined as $\{\{a\},\{a,f\}\}$ and so $f=\{\{\{a\},\{a,f\}\}\}$ is a set of which one element has one element that is the original set again - and this contradicts the Axiom of Regularity.

With different foundations (a different set theory or a different concept of function), your mileage may vary.

Answer 2

These are called higher-order functions. An interesting example is the Y combinator in lambda calculus.

Answer 3

You say that you come from a computer science background, and from that point of view it's absolutely possible that a function returns itself. For example, here's a very basic example in Python:

In [1]: def f():
   ...:     return f
   ...: 

In [2]: f() is f
Out[2]: True

In computer science such functions are called (a variant of) a quine, and their existence can be formally proven using Kleene's recursion theorem.

However, in computer science and mathematics you must be very careful about the words you use for the concepts you are thinking about: many words have multiple meanings in different branches of mathematics, and "function" is definitely one of them:

• In theoretical computer science, "functions" usually model computations, i.e. they're a formal way of talking about algorithms.
• In most other parts of mathematics, however, "functions" are today usually seen as relations between sets, i.e. they formalize how one set is related to another one.

As Hagen von Eitzen has already pointed out, a function in the second of these views cannot return itself.

This might be a good time to read the Wikipedia page about mathematical functions, which also describes other types of mathematical objects that might be called "functions" in certain contexts. For example, despite its name the Dirac's delta function isn't a function (in the second sense above), either.