Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 4 down vote favorite
3

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

Thanks

share|improve this question
1  
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
1  
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
1  
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
1  
@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

up vote 7 down vote

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\;.$$

share|improve this answer
Also, the empty function is a counter example. – Olivier Bégassat Dec 1 '12 at 0:56
1  
@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 – Peter 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
up vote 5 down vote

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

share|improve this answer
1  
In this question included means $\in$, I suppose? – Peter Tamaroff Dec 1 '12 at 0:46
@PeterTamaroff: That is how I interpreted the question. – André Nicolas Dec 1 '12 at 0:47
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.