Assumption of existence of which sets lead to Russell's paradox?

Why does the assumption of the existence of a set of all functions lead to Russell's paradox, but is not the case with the set of all continuous functions on (0,1)?

• If there is a set of all functions then presumably there is a set of all sets which gives Russell's paradox if you do not further restrict comprehension. Restricting just your domain and codomain sorts that out. – Ian Oct 30 '17 at 21:33
• While you can reduce the set of all functions to the case of the set of all sets, note that you can directly apply a number of various diagonal constructions to the set of all functions directly so as to get a contradiction. – user14972 Oct 30 '17 at 21:59
• I believe that, in general, any collection "parameterized" by sets which are not restricted will lead to Russell's paradox (unless the collection itself is restricted to be a subset of a known set). The classical case is the collection of all sets $\left\{X\,\middle|\,X\in V\right\}$. You have mentioned the collection of all functions: $\left\{f:X\to Y\,\middle|\,X,Y\in V\right\}$. If you substitute the $V$ for some set of allowed domains and codomains, you will find yourself in the realms of ZFC set-theory again, where no paradoxes have been found (yet :). – fonini Oct 31 '17 at 12:46
• It seems obvious to me that you cannot construct the set F of all functions using the axioms of set theory (without classes). Suppose for the sake of argument that such a set F does exist. If we could then derive a contradiction, then we would have proof that F cannot exist. But since we cannot prove otherwise, we would not have a RP-style inconsistency within our set theory. – Dan Christensen Nov 1 '17 at 4:44

If $X$ is a set, then $\{(X,X)\}$ (in the usual ZFC construction of functions) is a function which maps $X$ to $X$ (functions are a very general thing). So the set $F$ of all functions contains $\{(X,X)\}$ for all sets $X$. Depending on how the pairs $(a,b)$ are defined via sets we can do stuff like this

$$V=\bigcup\bigcup F$$

or similar to obtain $V$, the set of all sets. From this we can extract the Russel set $$R=\{X\in V\mid X\not\in X\}.$$

I am not very convinced that the same problem will not occure for continuous functions, but assuming the term continuous is only define for functions $\Bbb R\to\Bbb R$, the above argument does not apply because any such function will only map real numbers to real numbers instead of arbitrary sets $X$. This makes the set of continuous functions to a set $F_{\mathrm{cont}}\subseteq\mathcal P(\Bbb R\times\Bbb R)$ which can be proven to exist in ZFC.

If you have a set of all functions, then you can construct an injection from the class of all sets to the set of all functions (e.g. send a set to its identity function).

You can then pick out the subset of all functions that correspond to the image of a set, and translate Russell's paradox to apply to this set.

Or, you can use the axiom of replacement to replace every function with its domain, thus producing a set of all sets.

Alternatively, you can get by without replacement. Applying the union operation a few times to the set of all functions will produce a set of all sets.

If the collections of all functions $U$ were a set, then the power set $\mathbf{2}^U$ would exist (by the power set axiom) and we could define a function $f: U \rightarrow \mathbf{2}^U$ by

$$f(g) = \{ x \mid P(g,x) \}$$

where the predicate $P(g,x)$ is defined to be true if either $g(x)$ is a set of which $x$ is not an element or $g$ is not a set-valued function. This function would itself be an element of $U$. But do we have that $f$ is an element of $f(f)$? If $f \in f(f)$, then $f \notin f(f)$. Conversely, if $f \notin f(f)$, then by definition we must have $f \in f(f)$.

We cannot use this proof to show that the collection of continuous functions over the closed interval $[0;1]$ is not a set, since the $f$ constructed above is not a function over the reals.