As far as I can tell, there are certain non-stratified formulas $\phi(x)$ such that NF proves that $\{x : \phi(x)\}$ exists. For example, fix a set $y$, and let $A = \{x : y \in x\}$ and $B = \{x : x \in y\}$. Then the set $A \cup B = \{x : x \in A \vee x \in B\}$ exists. We have $A \cup B = \{x : x \in y \vee y \in x\}$, so the non-stratified formula $x \in y \vee y \in x$ defines a set.

Can anything be said in general about what classes of non-stratified formulas define sets in NF?

  • 1
    $\begingroup$ I'm no expert on the matter, but what exactly do you have in mind? As far as I am aware, the only non-stratified stuff you get in $NF(U)$ is anything you can generate out of objects you already have and Boolean operations. Thus if you can generate a particular set by a non-stratified formula, it must have come from a Boolean operation on something defined in a stratified manner. $\endgroup$ – Neil Barton Sep 18 '13 at 20:42
  • $\begingroup$ @NeilBarton: If anybody can confirm your idea, then that would be an answer to my question. I am specifically wondering if and to what extent non-stratified formulas involving quantifiers can be imitated. E.g., what about $\{x : \exists z ((x \in z \wedge z \in y) \vee (y \in z \wedge z \in x))\}$? $\endgroup$ – Nick Thomas Sep 21 '13 at 21:04

In $NF$ non-stratified formulas can be used in proofs. They are not forbidden like in Russell's Theory of Types. However we can't use non-stratified formulas to prove the existence of sets. In general, if I remember you prove that the sets exist by a different argument, instead of trying to appeal to stratified comprehension which would be hopeless if the formula is non-stratified.

If I am correct, in your example, you have $A \cup B = \{x : x \in y \vee y\in x\}$. You would instead write $A \cup B = \{x : x \in z \vee y\in x\}$ for $A=\{x : y\in x\}$ and $B=\{x: x\in z\}$, so that you can assign 1 to $y$, 2 to $x$ and 3 to $z$, this is stratified so now the union exists by stratified comprehension. But this does not exclude the case $z=y$ so we have the set $A \cup B = \{x : x \in y \vee y\in x\}$ even though $x \in y \vee y\in x$ is non-stratified.

A similar example is done in the book Logical Foundations of Mathematics and Computational Complexity: A Gentle Introduction (Springer Monographs in Mathematics), page 233.


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.