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.

  • 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

9

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.