2
$\begingroup$

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)?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ian Oct 30 '17 at 21:33
  • 1
    $\begingroup$ 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. $\endgroup$ – user14972 Oct 30 '17 at 21:59
  • $\begingroup$ 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 :). $\endgroup$ – fonini Oct 31 '17 at 12:46
  • $\begingroup$ 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. $\endgroup$ – Dan Christensen Nov 1 '17 at 4:44
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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