A finite model of power set

83 Views Asked by At

This is a two part question.

I. I ran across the following problem in Roitman. If there is a finite nonempty model of power set, then there exists a set $\{x_0, .... , x_n\}$ such that $x_0 \in x_1 \in ... \in x_n \in x_0$. Is the following proof right?

Proof. Let $X \vDash $ power set with $X$ finite and nonempty. This means that $\forall r \in X \exists s \in X s \subseteq r$. From this we can construct the set of $x_n$'s.

  • Pick $x_0 \in X$ and $s \in X$ with $s \subseteq x_0$.

  • Pick $x_n \in s$. Then $x_n \in x_0$.

  • Now pick another $s \in X$ such that $s \subseteq x_n$. Let $x_{n-1} \in s$, and then $x_{n-1} \in x_n$. Thus $x_{n-1} \in x_n \in x_0$.

  • We will eventually exhaust the elements of $X$ such that we can choose $x_0 \in s$ for some $s \subseteq x_1$, in which case $x_0 \in x_1 \in x_2 \in .... \in x_n \in x_0$.

II. This means that $V_n$ for $n \in \omega$ cannot model the power set, otherwise $x_0 \in x_0$ (since $V_n$ is transitive and finite), otherwise we violate foundation.

1

There are 1 best solutions below

0
On BEST ANSWER

You have the right idea about exhausting the elements of $X.$ Unfortunately, your approach won't work, since you've no guarantee that $s$ is non-empty at each stage. Critically, note that you never used the hypothesis that $X\vDash\mathsf{Power\:Set}.$

Let's think about what $\mathsf{Power\:Set}$ says about $X$: $$\forall r\in X,\exists s\in X:\forall t\in X,(t\subseteq r\implies t\in s)$$

In particular, since we always have $r\subseteq r$ for any $r\in X,$ then this means that for all $r\in X,$ there is some $s\in X$ such that $r\in s.$ Can you see how to take it from there?


As for your conclusion that $V_n$ cannot model $\mathsf{Power\:Set}$ for $n\in\omega,$ it is correct, but your reasoning is off. It is true that $V_n$ is a transitive set. However, it is not a transitive set of transitive sets--that is, it is not an ordinal--so we cannot conclude that $x_0\in x_0$ in this way. However, the set $A=\{x_0,...,x_n\}$ has the property that for all $x\in A,A\cap x\ne\emptyset,$ which contradicts $\mathsf{Foundation},$ but $\in$ is well-founded on $V_n,$ so this is impossible.