7
$\begingroup$

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.

  • 2
    Maybe this is too naive, but isn't the subset of all identity functions in bijection with the class of all sets?2011-06-04
  • 0
    @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?2011-06-04
  • 1
    @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.2011-06-04

2 Answers 2

8

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}$?

1

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.