I'm a little stumped on the aforementioned question. It's statement is as follows:

Let $M$ Be any class such that $\forall$x (x $\subset$ $M$ $\rightarrow$ x $\in$ $M$).

Show that $WF$ $\subset$ $M$.

$WF$ = well-founded sets defined by recursion as follows:

R(0) = 0

R($\alpha$ + 1) = P(R($\alpha$))

R($\alpha$) = $\bigcup$R($\beta$) (with $\beta$ < $\alpha$) for limit ordinals $\alpha$.

WF is then the Union of all sets which can be obtained by iterating powerset operation.

Am I supposed to define by recursion The class $M$ using $WF$?

Update: thanks to a hint of Brian M Scott, I think I've got the proof.

Claim: R($\alpha$)$\subset$ $M$ for each ordinal $\alpha$.

We proceed by transfinite induction.

Basis: $\alpha$ = 0. Trivial, but we do it anyway. Then R(0) = 0 and of course 0 $\subset$ $M$.

Successor case: $\alpha$ = $\beta$ + 1, and suppose that the claim holds for all ordinals $\beta$ < $\alpha$. Then by induction hypothesis R($\beta$) $\subset$ $M$. We note by the recursive definition of $WF$, asking whether R($\beta$ + 1) $\subset$ $M$ is equivalent to asking whether P(R($\beta$)) $\subset$ $M$. We also know R($\beta$) $\subset$ R($\beta$ + 1) which is just R($\beta$) $\subset$ P(R($\beta$)). Now every x $\in$ P(R($\beta$)) is either R($\beta$) or R($\gamma$) for some $\gamma$ < $\beta$, so that the inductive hypothesis applies and for every such x, x $\subset$ $M$ and in fact x $\in$ $M$. But this means P(R($\beta$)) $\subset$ $M$. So the claim holds here.

Limit case: $\alpha$ is a limit ordinal. Then R($\alpha$) = $\bigcup$ R($\beta$) for $\beta$ < $\alpha$. Suppose the claim does not hold here. Then some $\beta$ < $\alpha$ is such that either R($\beta$) $\subset$ $M$ fails or for some successor R($\beta$ + 1) such that R($\beta$) $\subset$ R($\beta$ + 1) then R($\beta$ + 1) $\subset$ $M$ fails. Either way, this contradicts the fact obtained in the successor case. So the claim hods here as well.

$END PROOF$. Right?

  • $\begingroup$ Hi Luis, looks like you're on the right track. In the successor case: it's not true that "every $x\in\mathcal{P}(R(\beta))$ is either $R(\beta)$ or $R(\gamma)$ for some $\gamma<\beta$". It is true that "$x\in\mathcal{P}(R(\beta))$ iff $x\subseteq R(\beta)$", and then you can use the transitivity of $\subseteq$. $\endgroup$ – user52534 Apr 21 '15 at 21:54
  • $\begingroup$ Also, in the case when $\alpha$ is a limit ordinal: We assume that $R(\beta)\subseteq M$ for every $\beta<\alpha$, and then show that this assumption implies $R(\alpha)\subseteq M$. $\endgroup$ – user52534 Apr 21 '15 at 22:03
  • $\begingroup$ Thanks! I follow. I'll make adjustments within the next day. $\endgroup$ – لويس العرب Apr 21 '15 at 23:30

HINT: Prove by induction on $\alpha$ that $R(\alpha)\subseteq M$ for each ordinal $\alpha$.


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.