# Avoiding reflexive paradox in set theory

I am an amateur mathematician, and certainly not a set theorist, but there seems to me to be an easy way around the reflexive paradox: Add to set theory the primitive $A(x,y)$, which we may think of as meaning that $x$ is allowed to belong to $y$ and the axiom

$\forall x,\forall y, x\in y \rightarrow A(x,y)$

and modify the axiom schema for abstraction to read, given any wff $\phi(y)$ in which $x$ is not a free variable,

$\exists x,\forall y, y\in x \leftrightarrow A(y,x) \wedge \phi(y)$

Then if we try to construct the set $B$ of all sets not belonging to themselves, we get

$\forall x, x\in B \leftrightarrow A(x,B) \wedge x\notin x$

$B\in B \leftrightarrow A(B,B) \wedge B\notin B$

which is a consistent statement that implies both $B\notin B$ and $\neg A(B,B)$. Moreover, since $B$ is arbitrary, it follows that no set can be a member of itself.

Now, this all looks correct to me, but I can not believe that such a simple trick has been overlooked for over a century. So I have to believe that either its been done and I am simply unaware of it, or I've made a mistake that is staring me in the face and I just can't see it. Can someone set me straight on this?

-
I'm not sure this is appropriate for MO, but two quick comments: first, this is basically the spirit behind Russell/Whitehead's theory of types (IIRC), where your $A(x, y)$ would be shorthand for $tp(x)+1=tp(y)$ or something similar. Second, your version of the abstraction axiom is (without more axioms) very weak: one possible model has a necessarily empty" set $x$ with $A(y, x)$ never holding. This $x$ satisfies your version of abstraction for all formulas. In trying to fix this, I imagine you'll wind up with a theory of comparable complexity to ZF or type theory. – Noah Schweber May 22 '13 at 23:17
Let me point out that the difficulty is not avoiding the paradox, but avoiding the paradox in a natural way. The issue with what you propose isn't that it doesn't work (I believe it does, or can be made to), but rather that there's not a clear picture behind it. If you can come up with one - which would certainly require more axioms governing $A$ - that would be interesting, although probably more from a philosophical perspective than a mathematical perspective. – Noah Schweber May 22 '13 at 23:25
Landsburg is correct. Please ignore that sentence. I believe Noah S has answered my question. If he will enter an answer, I will accept it. I had thought the generality of $A$ was an advantage. It can represent a type theory approach, or we can define $A(x,y$ to mean $x$ is not a proper class and $y$ is a class to get something like vNBG set theory. But as Noah S observed $A(x,y)$ could also be identically false, making all sets empty. I'm not sure how big a drawback the generality might be. After all, the axioms of group theory allow for the trivial group. – Richard Thrasher May 23 '13 at 2:33
Now it is possible to have a model where $x\in^* y$ is true for all $x,y$. Such an attempt to define $\in^*$ must fail because connectivity in graphs is not definable in first-order logic. Thus you would have to rely on set-theoretic operations to get a meaningful definition of the transitive closure, but you do not yet have these operations. – The User May 23 '13 at 23:23
Richard, you are coming now quite close to a principle like "Sets are given by well-founded comprehension"; this is the spirit behind ZF, and once you have that, the rest of its axioms are not far behind [you'll find that the existence of infinite sets, powersets, etc., are not automatically assured, and you may want to assure them]. – Sridhar Ramesh May 24 '13 at 1:29

As The User says in the comments, you still have a problem, aesthetically at least -- in order to prevent the existence of "silly" models, you need some axiom asserting that $\in^*$ isn't too big. As is, a model in which $\in^*$ always holds between any $x$ and $y$ satisfies your axioms; this means that your separation axiom just asserts the existence of the empty set, and so any collection of sets containing the empty set can form a model of your axioms. In particular, your theory is now certainly consistent, since the structure consisting of a single object, interpreted as the emptyset, is a model.

This is the primary difficulty in creating a useful set theory -- not avoiding the paradoxes, but avoiding them in such a way that the resulting theory has some semantic power, so that models of the theory all share some intuitive properties. Also, we want the theory to be powerful, in the sense that any of its models interpret the rest of mathematics. These two demands are actually tied together, since one of the semantic properties we tend to demand of a set theory is that its models function well as universes for mathematics. In this case, avoiding paradoxes too easily is actually in some sense a bad thing -- having too many models can get in the way of interpretive power. For example, one theorem showing that ZFC is a powerful theory -- the Reflection Theorem, that asserts that for each finite fragment F of ZFC, ZFC proves the consistency of F -- can also be thought of as a near-inconsistency result: ZFC is "as close as possible" to inconsistency, in terms of what it says about its own finite fragments.

(This is not to argue that you should stop thinking about these things! I think coming up with alternate set theories is one of the best things a logician can do with their time; or at least that's how I justify it to my advisor! But it is a good idea to keep all of these things in one's mind. In particular, I recommend at the outset setting down a list of requirements you want your set theory to satisfy: is consistent relative to PA? interprets ZFC? is formulated in seven-valued infinitary logic?* since this will guide your process.)

* Nobody said those demands had to be reasonable, after all!

-
This is a very good explanation, but, even though I like aesthetic considerations, I'd de-emphasize them here and give primary importance to usefulness. For foundational purposes, a set theory must provide the sets that are used in mathematical practice while avoiding Russell's "set" and its relatives. "Avoiding paradoxes" is a quick way to say something like "distinguish, in a principled way, between the sets that should exist and those that shouldn't". The $A$ predicate of the question seems to be evading or postponing this crucial issue. – Andreas Blass May 24 '13 at 5:14
A very good point. For me, I think of the "in a principled way" as aesthetic - since the only real test of whether a theory's distinctions are principled is whether some compelling intuition rests behind it - and the usefulness is the theory's interpretive power. – Noah Schweber May 24 '13 at 17:07
My perspective is that ZF responded to the paradoxes by replacing abstraction with separation, thus guarding abstraction by the restriction that elements must already belong to some given set. This seems to me an overly conservative approach since there are many formulas $\phi$ for which no such guard is needed. What I have attempted to do is to ask the question, what is the weakest guard $A$ that protects against paradoxes. My efforts have been compromised by my limited experience and knowledge. Noah has pointed out that I need to be careful to avoid set theories that allow trivial models. – Richard Thrasher May 24 '13 at 18:32
Continued from previous comment: and The User has pointed out that one can't do everything in first-order logic that one might want. Both excellent points and very helpful, but I think the validity of the question---what is the weakest guard---remains. One doesn't have to be creating a new set theory, the existing theories have done pretty well. – Richard Thrasher May 24 '13 at 18:37

I've just read an interesting paper that addresses the question of how best to remove paradoxes from the naive abstraction axiom. Reference is:

Goldstein, L. 2013. Paradoxical partners: semantical brides and set-theoretical grooms. Analysis 73: 33-37.

His idea is quite simple. Keep the abstraction axiom as is,

$\exists y,\forall x,x\in y\leftrightarrow \phi(x)$

and add the restriction that one can only make substitutions for $y$, $x$ and $\phi$ that don't reduce the expression $x\in y\leftrightarrow \phi(x)$ to either a tautology or a contradiction.

This seems like a simple and elegant solution, though it does place a small but reasonable burden on the user of the axiom.

-
I see two problems with this approach. First, consider all the abstraction axioms that are kept. By definition of what's kept, each of these axioms, considered by itself, is consistent. But does that guarantee that all these axioms are consistent with each other? Second, one usually wants the axioms of a foundational theory to be a decidable set; there should be an algorithm to decide what is and what isn't an axiom. There seems to be no such algorithm for the proposed axioms. In the absence of such an algorithm, it's hard to sede how the system could serve as a foundation. – Andreas Blass May 27 '13 at 17:27
Notice that recursive enumerability is usally enough, and in typical logics for every recursively enumerable axiom system there is an equivalent one which is actually recursive. However, in this case it is not even recursively enumerable, and that is indeed very bad for a foundation of mathematics. – The User Jun 7 '13 at 15:29