A set $z$ is transitive if $x\in y\in z$ implies $x\in z$.

Given a set $x$, we define the successor of $x$, denoted $x^+$, to be $x\cup\{x\}$.

Now, let $x$ and $y$ be transitive sets. If $x\in y$, does it follow that $x^+\in y^+$? This question came up in my Set Theory class because we wanted to prove that this is true if $x$ and $y$ are natural numbers (since we were using elementhood to define the ordering of the natural numbers). We wanted to prove it directly, but since we didn't know if the above statement is true or not, we instead had to use induction.

  • $\begingroup$ If you don't know whether it's true, try to find a counterexample. Concentrate on sets which are transitive but not hereditarily transitive. $\endgroup$ – Yuval Filmus Oct 1 '14 at 21:21
  • $\begingroup$ Unfortunately, it's hard for me to think of such sets. Could you give me an example? $\endgroup$ – Nishant Oct 1 '14 at 21:22
  • $\begingroup$ I didn't say an example existed. What I would do trying to construct an example you can do as well, so since it's your question, I suggest you spend a few minutes trying to construct one yourself. Take some transitive set $y$ which is not hereditarily transitive, say $x \in y$ isn't transitive, and see if this leads to a counterexample. $\endgroup$ – Yuval Filmus Oct 1 '14 at 21:24

There's no reason for this to be true in general. (Assume the axiom of regularity, or restrict the generality to well-founded transitive sets.)

Consider the following example, let $A$ be any transitive set with at least than two elements, then $\mathcal P(A)$ is also transitive. We have that $A\in\mathcal P(A)$. However, $A\cup\{A\}\notin\mathcal P(A)$ and certainly $A\cup\{A\}\notin\{\mathcal P(A)\}$ either, since $A\cup\{A\}\neq\mathcal P(A)$.

So $A\in\mathcal P(A)$ but $A^+\notin\mathcal P(A)^+$.

This is true for ordinals, however, in particular for finite ordinals. And you can prove this by transfinite induction. The key point is that ordinals are linearly ordered by $\in$, whereas $\mathcal P(A)$ was not linearly ordered by $\in$.

  • $\begingroup$ Oh wow, so $2$ and $\mathscr P(2)$ would have worked just fine... $\endgroup$ – Nishant Oct 1 '14 at 22:59
  • $\begingroup$ Pretty much, yeah. :-) $\endgroup$ – Asaf Karagila Oct 1 '14 at 23:11

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.