3
$\begingroup$

Does permitting comprehension over all well-formed formulas that are neither contradictions nor tautologies result in paradoxes?

I have a hunch that a simple extensional set theory with the "axiom schema of contingent comprehension" is probably susceptible to a well-known paradox and there's a short proof of its inconsistency, but I'm having trouble finding one.

This question is inspired by the argument that plural logic is not susceptible to Russell's paradox given here and the set theory NFU which uses the type system of the simple theory of types only in its comprehension schema. The idea is to insist that all sets are nonempty (similar to rules about plurals in plural logic), but to identify all the different levels of our hierarchy, like NFU does.


Let's take a set theory with the following axioms.

  1. Every set has at least one element.

  2. Every set has at least one non-element.

  3. Extensionality. Sets with the same elements are equal.

Let us additionally insist on the following axiom schema of restricted comprehension.

$$ \text{there exists a $z$ such that $\varphi(z)$ holds and a $w$ such that $\varphi(w)$ fails} \implies \{ x : \varphi(x) \} \; \text{exists} $$

Russell's paradox begins by defining the Russell set $R = \{ x : x \not\in x \} $.

However, in this setting, using this notation in first place brings with it the additional assumption that $z \not\in z$ is contingent.

If we reject this and say that $z \not\in z$ is either a tautology or a contradiction, then we can defuse Russell's paradox by refuting one of its hypotheses.

A version of Curry's paradox has us consider the set

$$ A = \{ x : x \in x \to \varphi \} $$

However, if we insist that $z \in z$ is a contradiction, then $x \in x \to \varphi$ is not allowed as the body of an expression in set-builder notation.

$\endgroup$
2
  • 1
    $\begingroup$ First of all, Russell's paradox doesn't begin with $\{x: x\in x\}$, but just with $\{x: x\notin x\}$. Secondly, it sounds like you're talking about positive set theory. $\endgroup$
    – Asaf Karagila
    Jun 2, 2021 at 21:19
  • $\begingroup$ Fixed. Sorry. I don't think this is equivalent to positive set theory. Positive set theory has a syntactic constraint in its comprehension schema; this construction has a semantic one. $\endgroup$ Jun 2, 2021 at 21:21

1 Answer 1

5
$\begingroup$

Well, if you allow empty models, then this theory is consistent because the empty model satisfies it. There are also two different models with just two sets: one in which each set contains only itself, and another in which each set contains only the other set. But if you add an axiom saying that more than two sets exist, then I claim your axioms become inconsistent.

By Russell's paradox, you must have either $x\in x$ for all $x$ or $x\not\in x$ for all $x$. Suppose first that $x\in x$ for all $x$. By comprehension, the singleton $\{x\}$ exists for any $x$, so $\{x\}\in \{x\}$, so $x=\{x\}$. In particular, every set is a singleton. But now since there exist more than two sets, we can pick two different sets $x$ and $y$ and form the set $\{x,y\}$ (which we know exists because it is not the whole universe). This set is not a singleton, which is a contradiction.

The case where $x\not\in x$ for all $x$ is similar, you just take complements of all the sets. For any $x$, the set $V\setminus\{x\}$ exists (where $V$ is the universe). Since $V\setminus\{x\}\not\in V\setminus\{x\}$, we must have $x=V\setminus\{x\}$, so every set is the complement of a singleton. But we also know that singletons exist, and they are not complements of singletons since there exist more than two sets. This is a contradiction.

(In fact, you can deduce the second case from the first case by symmetry, since your axioms are unchanged if you swap the relation $\in$ with its negation.)

$\endgroup$
2
  • $\begingroup$ "By comprehension, the singleton $\{x\}$ exists for any $x$" – Why? Which $\varphi$ are you using for this? $\endgroup$ Jun 3, 2021 at 7:47
  • 1
    $\begingroup$ @PaŭloEbermann: The formula $\varphi(y)$ that is $y=x$. $\endgroup$ Jun 3, 2021 at 15:28

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.