5
$\begingroup$

Is the Russell paradox the only possible contradiction to the axiom schema of comprehension due to Frege (1893)? The axiom that says that if $\varphi$ is a property, then there exists a set $Y = \{X: \varphi(X)\}$ of all elements having property $\varphi$.

If not then what are other paradoxes that result from that axiom?

$\endgroup$
2
  • 1
    $\begingroup$ Can you define precisely what you mean? Any contradiction implies anything, so all paradoxes (and all true results) follow from adopting unbounded comprehension. $\endgroup$ – Andrés E. Caicedo Mar 10 '15 at 22:16
  • $\begingroup$ Forgive me if I'm wrong, but a nice way to see $\emptyset$ is that $x\in \emptyset \iff x$ verifies all properties. So I don't think the axiom you mention here can be contradicted - but I might miss the point. $\endgroup$ – krirkrirk Mar 10 '15 at 22:27
11
$\begingroup$

No.

The Russell paradox looked at $\varphi(x)$ to be $x\notin x$. But we can use any of the "it cannot be a set" paradoxes.

  1. Burali-Forti paradox, define an ordinal to be a transitive set $A$ such that $(A,\in)$ is well-ordered. This can be expressed in a formula in the language of set theory, and $\{A\mid A\text{ is an ordinal}\}$ cannot be a set, since it is well-ordered by $\in$ and it is transitive, so it will have to be a member of itself and contradict the well-ordering.

  2. Cantor's paradox, consider just $\varphi(x)$ to be "$x$ is a set", which is really just $x=x$ in the context of set theory where everything is a set. Then Cantor's paradox says there is no bijection between a set and its power set; but every set has a power set. In particular the set $X=\{x\mid x\text{ is a set}\}$, but then $\mathcal P(X)\subseteq X$ so there is an injection which is a contradiction.

  3. The set of all singletons, consider the formula $\varphi(x)$ to be a statement saying that $x=\{y\}$ for some $y$. If $X=\{x\mid\varphi(x)\}$ is a set, then $\bigcup X$ is a set, and we reduce to the previous paradox.

There are other paradoxes as well.

$\endgroup$
2
  • 1
    $\begingroup$ A variation on Cantor's paradox: The collection $X$ of all cardinal numbers is not a set, because if it were the cardinal $|\bigcup X|^+$ would be in the set, leading to $|\bigcup X|^+\subseteq \bigcup X\implies|\bigcup X|^+\le|\bigcup X|$, a contradiction. $\endgroup$ – Mario Carneiro Mar 11 '15 at 8:34
  • 2
    $\begingroup$ i have no choice but to say thank you for your answer! $\endgroup$ – user153330 Mar 11 '15 at 19:49
5
$\begingroup$

In addition to the paradoxes mentioned by Asaf, there is also the infinite family:

$$\begin{align} \varphi(x) & = \lnot\exists y.x\in y \land y\in x\\ \varphi(x) &= \lnot\exists y\exists z.x\in y \land y\in z \land z\in x\\ &\vdots\end{align}$$

Somewhat different is Curry's paradox: $$\varphi_Y(x) = (x\in x)\to Y$$Then following the same pattern of reasoning that gives Russell's paradox (that is, let $X = \{x\mid \varphi_Y(x)\}$ and ask if $X\in X$), in this case we can conclude $Y$. But since $Y$ was completely arbitrary, we can prove anything at all by this method.

$\endgroup$
2
  • $\begingroup$ thank you for your answer! $\endgroup$ – user153330 Mar 11 '15 at 19:48
  • $\begingroup$ An advantage of Curry's paradox is that it does not involve negation and hence remains even if we throw away LEM! All we need is that we can derive set membership from the satisfied formula and vice versa. $\endgroup$ – user21820 Oct 18 '16 at 11:58

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