4
$\begingroup$

Let us state axiom schemata without parameters, so as to facilitate readability, but with the understanding that we really mean with parameters.

Under this convention, the infamous Axiom Schema of Unrestricted Comprehension can be written follows.

$$\exists A\forall e(e \in A \leftrightarrow P(e))$$

Russell's paradox derives a contradiction from this schema. The proof is roughly as follows.

  1. Substitute $P(e)$ with $e \notin e.$ $$\exists A\forall e(e \in A \leftrightarrow e \notin e)$$

  2. Let $A$ be fixed but arbitrary satisfying the above sentence. $$\forall e(e \in A \leftrightarrow e \notin e)$$

  3. Replace $e$ with $A$. $$A \in A \leftrightarrow A \notin A$$

Now presumably, when this paradox was first discovered, mathematicians tried very hard to salvage unrestricted comprehension. An obvious first attempt would be:

$$\exists A\forall e(e \in A \leftrightarrow e \neq A \wedge P(e))$$

This time, we obtain

$$A \in A \leftrightarrow A \neq A \wedge A \notin A$$

which isn't contradictory, indeed we may conclude $A \notin A.$

But, I'm guessing the modified schema falls prey to some kind of "modified Russell's paradox." Ideas, anyone?

Edit. As aws points out in the comments, this schema is actually consistent. Consider a model with a single element $*$ and define $* \notin *$.

Thus, we should at least assume there exists a non-empty set. Feel free to use something stronger, like the existence of an infinite set.

$\endgroup$
  • 2
    $\begingroup$ As it stands, your axiom scheme is consistent: consider the model with one element, $\ast$, and define $\in$ by $\ast \notin \ast$. If you add the axiom $\exists x, y\; x \in y$ it might make something like Russell's paradox work. I'll think about it. $\endgroup$ – aws Sep 10 '13 at 17:27
  • $\begingroup$ @aws, ahhh good point. This calls for an edit! $\endgroup$ – goblin Sep 10 '13 at 17:42
3
$\begingroup$

We can do something that's essentially similar to Russell's paradox, but requires a bit more work and the assumption that there are $X$ and $Y$ with $X \neq Y$. Let $A$ be such that for all $x$: $$ x \in A \leftrightarrow (x \neq A \wedge \neg (\exists y\; y \in x \wedge x \in y)) $$

If we can only show that the singleton $\{A\}$ exists, then we can reason as follows:

Since $A \notin A$, we clearly can't have $A = \{A\}$. Suppose $\{A\} \in A$. Then, since $A \in \{A\}$, we would have $\exists y\; y \in \{A\} \wedge \{A\} \in y$, and conclude $\{A\} \notin A$, a contradiction. Hence $\{A\} \notin A$. But now suppose that $y$ is such that $y \in \{A\}$ and $\{A\} \in y$. Since $y \in \{A\}$ we must have that $y = A$, and so $\{A\} \in A$, and so, by contradiction with $\{A\} \notin A$, we must have $\neg (\exists y\;y\in \{A\} \wedge \{A\} \in y)$. But now we can conclude $\{A\} \in A$ and finally deduce that the theory in inconsistent.

To show $\{A\}$ exists, we will show $A$ is nonempty and then apply the following lemma:

Lemma Suppose that $X$ is nonempty. Then there is a set $Y$ such that for all $y$, $y \in Y$ if and only if $y = X$.

Proof Let $Y$ be such that $y \in Y \leftrightarrow (y \neq Y \wedge y = X)$. Suppose $Y$ is empty. Then $X \notin Y$, and so we are forced to conclude $X = Y$. But $Y$ is empty and $X$ is non empty, contradiction. Hence $Y$ is nonempty, but this easily implies the result.

Now we just have to construct an element of $A$. This is also the first place where we will require "non triviality," so let's assume that there are $X$ and $Y$ such that $X \neq Y$.

Let $C$ be such that for all $x$, $$ x \in C \leftrightarrow x \neq C $$ Note that $C$ has to contain either $X$ or $Y$, and so $C$ can't be empty. Note also that we can construct an empty set, $E$. Since $C$ is nonempty we have $C \neq E$, and so $E \in C$.

Now let $B$ be such that for all $x$, $$ x \in B \leftrightarrow (x \neq B \wedge \exists y \in x\;y \text{ is empty}) $$ Note that $C \neq B$ because $B$ can't contain any empty sets. Hence $C \in B$, and so $B$ isn't empty. Hence $\{B\}$ exists by the lemma. Note that if $y \in \{B\}$ and $\{B\} \in y$, then we would have $y = B$ and so $\{B\} \in B$. But then $\{B\}$ would have to contain an empty set and so $B$ would be empty. Contradiction. Hence $\neg (\exists y \; y \in \{B\} \wedge \{B\} \in y)$. Note that if $\{B\} = A$, then we would already know that $A$ is non empty, and so we can assume $\{B\} \neq A$. But this implies $\{B\} \in A$, and so we do have that $A$ is nonempty, and so $\{A\}$ exists, resulting in the theory being inconsistent.

$\endgroup$
  • $\begingroup$ Oh I see, I'll fix it. $\endgroup$ – aws Sep 10 '13 at 23:01
  • $\begingroup$ To be honest, I'm having difficulty following this argument, near the beginning. "Suppose {A}∈A. Then, since A∈{A}, we would have ∃y(y∈{A}∧{A}∈y), and conclude {A}∉A, a contradiction." How are you able to deduce a positive formula ∃y(y∈{A}∧{A}∈y)? I can see how to deduce $\neg$∃y(y∈{A}∧{A}∈y). $\endgroup$ – goblin Sep 11 '13 at 0:07
  • $\begingroup$ Deduce $\exists y(y \in \{A\}\wedge\{A\}\in y)$ by setting $y := A$ and applying the assumption that $\{A\} \in A$. This sort of thing is a bit tricky. $\endgroup$ – aws Sep 11 '13 at 1:05
  • $\begingroup$ wait do you mean setting $x := A$? $\endgroup$ – goblin Sep 11 '13 at 6:55
  • $\begingroup$ I mean from $(A \in \{A\} \wedge \{A\}\in A)$ deduce $\exists y(y \in \{A\} \wedge \{A\} \in y)$. In other words, there is a $y$ such that $y \in \{A\} \wedge \{A\} \in y$, because $A$ is an example of such a $y$. Then $x := \{A\}$ cannot satisfy $x \neq A \wedge \neg (\exists y(x \in y \wedge y \in x))$, so $\{A\} \notin A$. $\endgroup$ – aws Sep 11 '13 at 10:29

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.