Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to prove "There is no set to which every function belongs." Can I approach it as follows?

Attempt No. 1: Let $$F: A\rightarrow B$$ Since $$F\subset A\times B,$$ it follows that $$F\in \mathcal{P}(A\times B).$$ Now, let $$\mathcal{P}(A\times B)$$ be the set of all functions from A into B. Since $$\mathcal{P}(A\times B)\subseteq \mathcal{PP}(A\times B),$$ it follows that $$\mathcal{PP}(A\times B)$$ is also a set of all functions from A into B. Therefore $$\mathcal{P}(A\times B)=\mathcal{PP}(A\times B).$$

Attempt No. 2 is to approach it by the concept of Russel Paradox. Then I must build a set of all functions that are not in itself, but, honestly, I have not a clue of what constitute a function that is not in itself.

share|cite|improve this question
Maybe this is too naive, but isn't the subset of all identity functions in bijection with the class of all sets? – t.b. Jun 4 '11 at 18:45
@Theo: That seems true (I'm naive also), but what do you do next? Does this fact, that there's a bijection to a "smaller" set, help in some way? – ShreevatsaR Jun 4 '11 at 19:27
@ShreevatsaR: I'd say: If the collection of all functions were a set then the subcollection of all identity functions would be a set as well, but it isn't by Russell. – t.b. Jun 4 '11 at 19:47
@Theo: Ah, thanks. – ShreevatsaR Jun 4 '11 at 19:48

Here's is a Russell's Paradox type solution:

Suppose there exists a set $\mathcal{F}$ of all functions. Consider the following subset of $\mathcal{F}$: $$ \mathcal{S} \;=\; \{f\in\mathcal{F} \mid f\text{ is not an element of the domain of }f\}. $$ Clearly $\mathcal{S}$ is nonempty, so there exists at least one function $f$ with domain $\mathcal{S}$ (e.g. the constant zero function). Is $f$ an element of $\mathcal{S}$?

share|cite|improve this answer

Assume the class of all functions, $\mathcal F$, is a set, then it has a rank, i.e. some $\alpha$ such that the class is an element of $V_\alpha$ (and $\alpha$ is the minimal one), this is not true, as the identity function from $V_\alpha$ to itself is in the class $\mathcal F$ so it must have appeared in a higher rank, contradicting the assumption about $\alpha$.

To finish the proof we just observe that a class is also a set if and only if it has a rank, therefore $\mathcal F$ is a proper class.

share|cite|improve this answer

Your Answer


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.