27
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I'm pretty sure this is impossible in set theory. $\endgroup$ – Mr. Chip May 31 '17 at 21:24
  • 8
    $\begingroup$ This is definitely possible in Python and Javascript. def f(): return f $\endgroup$ – Chris Chudzicki Jun 1 '17 at 0:40
  • 1
    $\begingroup$ Doesn't the Halting Problem proof depend on this being possible? $\endgroup$ – Mason Wheeler Jun 1 '17 at 1:07
  • 2
    $\begingroup$ @UTF-8 I'm wondering about the motivation behind this question. If the answer were yes, how would use that result? Regarding the "call to the" expression, it might first be useful to consider that "calling a function" is an artifact of procedural languages. It's an instruction, not an equality. In Wikipedia function article, terms like "value of a function with input x" are used. Using that template you could say the value of $id$ with argument $id(5)$ or the value of $id$ with the argument which is the value of $id$ with the argument 5. Very wordy though - "call" or "invoke" is clear enough. $\endgroup$ – Χpẘ Jun 1 '17 at 4:40
  • 1
    $\begingroup$ @UTF-8 Worth pointing out that "mathematics" doesn't prohibit a function returning itself, rather ZFC set theory does. There are other set theories, including "naive set theory", created by Cantor. Inconsistencies in naive set theory led to the development of alternatives such as ZFC. However, despite its inconsistencies naive set theory is still used and taught. Therefore you have a menu of set theories with various tradeoffs. $\endgroup$ – Χpẘ Jun 1 '17 at 16:50
35
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very neat explanation! The first paragraph pretty much killed it. $\endgroup$ – UTF-8 May 31 '17 at 21:30
  • $\begingroup$ @Hagen If I understand your answer correctly, it answers part of the OP's question: "return itself", but doesn't answer the other part "take itself as an argument". $\endgroup$ – Χpẘ Jun 1 '17 at 4:22
  • 1
    $\begingroup$ "With different foundations" -- any examples? $\endgroup$ – Burnsba Jun 1 '17 at 13:00
  • 1
    $\begingroup$ @Burnsba See Akababa's answer using lambda calculus and Florian Brucker's answer using (any implementation of) recursion theory. $\endgroup$ – Colin McLarty Jun 1 '17 at 13:21
  • 1
    $\begingroup$ @Burnsba lambda calculus and (other implementations of) recursion theory can be taken as foundations. Or they can be interpreted in ZFC, in which case those answers refer to what Hagen von Eitzen calls different concepts of functions. $\endgroup$ – Colin McLarty Jun 1 '17 at 16:18
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I know that there are functionals (even an integral is one and everyone knows about integrals) and know about the the Y combinator (doesn't exactly seem like a good entry point to lambda calculus, though ;-) ). My question, however, is not whether one can pass functions to functions or have functions return functions. It is whether this is allowed if those functions are the same. $\endgroup$ – UTF-8 May 31 '17 at 21:25
  • $\begingroup$ Though if you pass to simply-typed lambda calculus for example, the Y combinator can't be given a valid type signature as far as I recall. I think also, in simply-typed lambda calculus, it wouldn't be possible to have a function that returns itself since the return type of a function has to be a strict subterm of the type of the function. $\endgroup$ – Daniel Schepler May 31 '17 at 21:39
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ See my comment below the question from 4 to 5 hours ago. $\endgroup$ – UTF-8 Jun 1 '17 at 12:41
  • $\begingroup$ @UTF-8 Ah, that comment was hidden by default. Nevertheless my answer might be of interest to other readers with a CS background. $\endgroup$ – Florian Brucker Jun 1 '17 at 12:44
  • $\begingroup$ If you also have def g(): return g, is it possible to proof or disproof $f=g$? $\endgroup$ – Hagen von Eitzen Jun 1 '17 at 18:27
  • $\begingroup$ @HagenvonEitzen: From Python's point of view, f and g are in that case neither identical (the expression f is g evaluates to False) nor are they equal (the expression f == g also evaluates to False). This is because, for Python, functions exist as entities separately from the computation that they represent. Even on a byte-code level (i.e. in compiled form), f and g will be different because their return statements refer to them via their names, which therefore end up in the byte-code... $\endgroup$ – Florian Brucker Jun 2 '17 at 10:18
  • $\begingroup$ ... Even if you do def h(): return f then f and h will still be neither identical nor equal. However, they will have the same byte-code. $\endgroup$ – Florian Brucker Jun 2 '17 at 10:19

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.