# A function cannot be included in its own domain

For what set theoretic reasons can a function not be included in its own domain?

Thanks

-
Can you please clarify what you mean by that? What exactly is a function to you? What does it mean for it to be included in its domain? –  Ittay Weiss Dec 1 '12 at 0:42
What about the function $\emptyset:\emptyset\to\emptyset$? We do have $\emptyset\subset\emptyset$. Do you mean that a function $f:E\to F$ cannot be an element of $E$? –  Olivier Bégassat Dec 1 '12 at 0:44
Indeed, in Lambda Calculus, every element is a function with domain every element. (That doesn't help understand the set theoretic reasons for not allowing it, just pointing out that as a rule, it is possible to apply a function to itself...) –  Thomas Andrews Dec 1 '12 at 1:29
@ThomasAndrews, you are identifying lambda expressions with functions, and the two are quite different things. One can attach semantics to lambda calculus where the meaning of lambda expressions is a function, but in any case the way to do this properly is somewhat complicated. It is probable not the best example to bring out in this context! :-) –  Mariano Suárez-Alvarez Dec 1 '12 at 6:35
@MarianoSuárez-Alvarez well, it is the primary interpretation I know for Lambda calculus. Even the set theoretic definition of function is just a formality that we interpret as something like what we think of as a "function." As soon as I saw a question about "functions which are in their own domain," I thought of Lambda calculus. –  Thomas Andrews Dec 1 '12 at 7:20

## 2 Answers

Corrected: A non-empty function can be a subset of its own domain. Let $x_0=0$, for each $n\in\omega$ let $x_{n+1}=\langle x_n,0\rangle$, and let $X=\{x_n:n\in\omega\}$; then

$$f\triangleq\big\{\langle x_n,0\rangle:n\in\omega\big\}=\{x_{n+1}:n\in\omega\}\subseteq X=\operatorname{dom}f\;.$$

-
Also, the empty function is a counter example. –  Olivier Bégassat Dec 1 '12 at 0:56
@Olivier: Since that’s immediately apparent, I’ve been tacitly assuming all along that $f\ne\varnothing$. –  Brian M. Scott Dec 1 '12 at 0:57
Alright :). characters –  Olivier Bégassat Dec 1 '12 at 0:59
OK. I'll delete –  Pedro Tamaroff Dec 1 '12 at 1:21
Very nice answer. Another variation would be to take $f$ defined on $V_\omega$ to be $f(x)=x\cup\{x\}$, then $f\subseteq V_\omega$ as well. –  Asaf Karagila Dec 3 '12 at 15:06

One could use such a function to construct a set that violates the Axiom of Regularity.

Note: This answer assumes that "included" means "is an element of."

-
In this question included means $\in$, I suppose? –  Pedro Tamaroff Dec 1 '12 at 0:46
@PeterTamaroff: That is how I interpreted the question. –  André Nicolas Dec 1 '12 at 0:47
Presumably, if $f\in\mathrm{Dom}(f)$, that'd be the descending sequence $$f\ni \big(f,f(f)\big)=\lbrace f,\lbrace f,f(f)\rbrace\rbrace\ni f\ni \big(f,f(f)\big)=\lbrace f,\lbrace f,f(f)\rbrace\rbrace\ni f\ni\cdots$$ –  Olivier Bégassat Dec 1 '12 at 1:03