6
$\begingroup$

Let's say that a formula in the language of set theory is flexibly stratified iff there exists a function $f$ from variable symbols to $\omega$ such that if $x=y$ appears in the formula, then $f(x)=f(y)$, and if $x\in y$ appears in the formula, then $f(x)<f(y)$ (this is in contrast to regular stratification which requires $f(y) = f(x) + 1$ exactly).

I'm going to define Flexible NF as:

  • Extensionality (same as in NF)
  • Flexibly Stratified Comprehension (same as in NF except allowing comprehension over "flexibly stratified" formulae)

This is clearly at least as strong as NF, since every theorem of NF is a theorem of Flexible NF.

Is Flexible NF obviously inconsistent, or obviously equiconsistent with NF?

My thoughts:

Could we somehow use flexible stratified comprehension to define the bijection $f: x \mapsto \{x\}$ on e.g. the universal set, and then use that in contradiction with Cantor's Theorem to get inconsistency?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
9
$\begingroup$

Flexibly Stratified Comprehension is inconsistent. By Flexibly Stratified Comprehension, there is an s such that

$$\forall x\:\bigl(x\in s\leftrightarrow\exists y\:\bigl(\forall t\:(t\in y\leftrightarrow t\in x)\land y\notin x\bigr)\bigr).$$ If $s\in s$, then there is an $S$ with the same members as $s$ such that $S\notin s$.

But if $S\notin s$, then for all $T$ with the same members as $S$, $T\in S$. In particular $S\in S$ and thus $S\in s$.

If $s\notin s$, then for all $S$ with the same members as $s$, $S\in s$. In particular $s\in s$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Very nice. It might be slightly simpler to say that $x\in y$ is logically equivalent to $$\exists z[x\in z\land\forall w(w\in z\to w\in y)],$$ whence $x\notin x$ is logically equivalent to the "flexibly stratified" formula $$\forall z[x\in z\to\exists w(w\in z\land w\notin x)].$$ $\endgroup$
    – bof
    Commented Nov 17, 2022 at 3:48
  • $\begingroup$ Nice! My intuition of the answer is that we could define the "same elements" relation $$x \equiv y \leftrightarrow \forall t (t\in x \leftrightarrow t\in y)$$ Notice that this can can be flexibly stratified with any assignment of values for $x$ and $y$. Thus, the flexibly stratified formula $\exists y (y \equiv x \wedge y \not\in x)$ is a form of Russell's Paradox. In fact, with extensionality, it's exactly the same, but it looks like the paradox goes through even without extensionality, which is really cool! $\endgroup$
    – Dylan Pizzo
    Commented Nov 17, 2022 at 5:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .