In the context of showing that in $ZFC-Foundation$, that $R\neq V$, Kunen, "Set Theory" (2011) states (page 22) that $\{x: x=\{x\}\}$ can be a proper class. (As an aside, does "can be" mean is?) He defines $V:\{x: x=x\}$ and the Russell set as $R:\{x:x\notin x\}$.

I think the members of $\{x: x=\{x\}\}$ violate Foundation as $x\cap\{x\}=\{x\}\ne\emptyset$.

-- Is $\{x: x=\{x\}\}$ a proper class since without the constraint of Foundation, it would include all sets?

-- Does the context $ZFC-Foundation$ alter what is considered as $V$, or does it effect $R$,(since in general $x\in\{x\}$ but now we can have $\{x\}=x\in\{x\})$?

(This seems a little strange as wikipedia defines $V$ as the class of hereditary, well-founded sets; so how does Kunen discuss this in the context of $ZFC-Foundation$?)

-- Lastly, how would this be used to show $V\neq R$?

Thanks

  • Assuming ZFC is consistent, then there can't be any proof of $ZFC - F \vdash V \ne R$. – Daniel Schepler May 1 at 19:09
  • @DanielSchepler Please forgive me. Perhaps if you have a copy of "Kunen" you would look at the top of page 22. Maybe I'm misreading it. Thanks, – Andrew May 1 at 19:13
  • Kunen has written several books and many papers. You may want to specify which one you mean. – Andrés E. Caicedo May 1 at 20:03
up vote 2 down vote accepted
+50

Given a class $S$, to say that it can be proper means that it is consistent (with the axioms under consideration) that $S$ is a proper class, that is, there is a model $M$ of these axioms such that the interpretation $S^M$ of $S$ in $M$ is a proper class in the sense of $M$. It does not mean that $S$ is always a proper class. In fact, it could also be consistent that $S$ is empty (of course, the model $M'$ where this happens would be different from $M$).

Things tend to be a bit more delicate, since the theories we are usually discussing here cannot quite be proved consistent unless one assumes a rather strong metatheory (due to issues related to the incompleteness theorems). In that case, one talks of relative consistency. For instance: If $\mathsf{ZF}$ is consistent, then the theory $(\mathsf{ZFC}-{\rm Foundation})+$"$\{x:x=\{x\}\}$ is a proper class" is also consistent. In practice, to establish results of this kind, one starts with a model $N$ of the first theory (in the example, $\mathsf{ZF}$) and somehow modifies it to produce a model $M$ of the second theory (in the example, $(\mathsf{ZFC}-{\rm Foundation})+$"$\{x:x=\{x\}\}$ is a proper class"). Another common approach is to show that there is a way of interpreting one theory inside the other one.

(Anyway, it seems from your questions that you do not quite understand yet how relative consistency and models of set theory work, and this is causing confusions beyond the difficulties of the actual technical question you posted here. It may be more profitable to read about these topics for a while, and once you have a better grasp on them, to revisit these questions regarding the axiom of foundation.)

Briefly:

Yes, any set in $\{x:x=\{x\}\}$ violates foundation.

No, the class $\{x:x=\{x\}\}$ never includes all sets, regardless of whether we assume foundation. For instance, $\emptyset$ is not in this class (or $\mathbb R$, or $\{1,2\}$, or ...).

You cannot prove in the theory $\mathsf{ZFC}-{\rm Foundation}$ that $\{x:x=\{x\}\}$ is a proper class, because this is false in the stronger theory $\mathsf{ZFC}$. Or rather: If you prove in a theory $A$ that $\phi$ holds, and if $A\subset B$ and the theory $B$ proves that $\lnot\phi$ holds, then $B$ is inconsistent (it proves a contradiction, and therefore it proves everything). So, if we assume that $\mathsf{ZFC}$ is consistent, then no weaker theory can prove that $\{x:x=\{x\}\}$ is a proper class.

It is in general difficult to produce models of set theory, you are not going to easily guess how to build a model of $(\mathsf{ZFC}-{\rm Foundation})+$"$\{x:x=\{x\}\}$ is a proper class". In any case, (assuming the consistency of $\mathsf{ZF}$) there are models of $(\mathsf{ZFC}-{\rm Foundation})+\lnot{\rm Foundation}$ where $\{x:x=\{x\}\}$ is not a proper class. I am not sure you can currently understand how to build any of these models, it is a non-trivial task. My suggestion is that you postpone learning about how to build these models for a while, until you are more comfortable with the topics I mentioned in my parenthetical paragraph above.

It is not clear what you mean when you ask whether a context alters what $V$ is. You may want to clarify that (it may be harder than you anticipate). It seems to me that you are asking whether not assuming foundation implies that $V$ is larger than if we assume it. This is too vague still, but the answer is no. The point is that if $M$ is a model of a theory $B$ then it is also a model of any weaker subtheory $A$ of $B$. What is true is that there may well be models of $A$ that are not models of $B$. Indeed, (again, assuming the consistency of $\mathsf{ZF}$) there are models of $\mathsf{ZFC}-{\rm Foundation}$ with ill-founded sets. In any such model, we can define the subclass of well-founded sets, and that subclass is in turn a model of $\mathsf{ZFC}$, and the $V$ of this subclass is the class of well-founded sets of the original model. In that sense, $V$ has been altered due to the "context", being "larger" in the model where foundation fails.

I prefer to call $V$ the universe of all sets, the class $\{x:x=x\}$. Of course, under foundation, this is certainly the class $\mathrm{WF}$ of well-founded sets, but without assuming the axiom of foundation, both classes may well be different. This is not the convention used in the Wikipedia page you visited, but my usage is the standard one.

(By the way, you never told us what $R$ is, and it is not standard notation.)

  • Dear Professor - My carelessness as this was part of a larger question that was appropriately suggested be split into several pieces, so I neglected to carry over the introductory remarks that dealt with what you raised. Best regards, – Andrew May 1 at 20:33
  • Thank you for all your kind advice. As a result of my intention to avoid posting a question without any indication that I made some effort, I think the actual question: How to show in $ZFC-Foundation$ that $V\neq R$ got lost in my misguided remarks. Maybe you would please add something in that regard. (I pray I haven't yet overlooked that in your answer.) Thanks. While I wish I had the acuity of my youth, I do love stumbling around in Cantor's "paradise." Best regards, – Andrew May 1 at 21:09
  • 1
    Andrew, you cannot show that $V\ne R$, because this is false in $\mathsf{ZFC}$. The best you can hope for is to build a model where foundation fails, and $V\ne R$. This is non-trivial. In this answer I describe the anti-foundation axiom and give some references. Perhaps the easiest models to describe where $V\ne R$ (certainly, the best known) are the models of anti-foundation. – Andrés E. Caicedo May 1 at 21:21
  • 1
    To exhibit such a model, the natural approach is to start with a model of set theory (where foundation holds). You can introduce a (proper class) equivalence relation on graphs that ``should have the same decoration'' (in the sense described in the answer linked to from my previous comment). In the quotient of $V$ by this relation there is a natural way of defining a membership relation, and the resulting structure is a model of anti-foundation. Verifying the details takes some work, but it is doable. Aczel's book also has details. – Andrés E. Caicedo May 1 at 21:24
  • 1
    The works by Forti and Honsell (such as the one mentioned in the answer linked to from two comments ago) also describe several models where foundation fails (in different ways). – Andrés E. Caicedo May 1 at 21:26

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.