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

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.

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

Solution 2:

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