# Do these two constructions lead to the same set?

Be $A=\bigcup_{n=0}^\infty A_n$ where $A_0=\emptyset$, $A_{n+1}=P(A_n)$.

Be $B=\bigcup_{n=0}^\infty B_n$ where $B_0=\{\emptyset\}$, $B_{n+1}=\{P(X):X\in B_n\}\cup\{X\setminus Y:X,Y\in B_n\}$.

Question: Is $A=B$?

Note: Here $P(X)$ denotes the power set of $X$.

-
Note that $A_n\subseteq P(A_n)$, the definition there is a bit surplus. I also suspect that there are parts of the definition of $B_n$ which are excessive. – Asaf Karagila Aug 15 '12 at 10:51
Thanks for noting this; I'll change the post accordingly. Indeed $B_n$ has also a surplus because each $B_n$ contains the empty set, and thus $B_n\subset \{X\setminus Y:X,Y\in B_n\}$. – celtschk Aug 15 '12 at 10:57
I'm failing to see what we get out of the differences you union on to the $B_n$. It looks to me like $B_0$ has one element, so $B_1$ will be a set containing one element, its powerset, unioned to the empty set, so $|B_1|=1$, and similarly through the construction. Am I misreading? – Kevin Carlson Aug 15 '12 at 11:37
@Luke: It’s not that simple; $A_1=B_0$ and $A_2=B_1$, but $A_3\ne B_2$. – Brian M. Scott Aug 15 '12 at 11:52
@Luke Mathieson: Note that in the defintion of $B_{n+1}$ the powersets $\mathcal P(X)$, $X\in B_n$, become elements of $B_{n+1}$, not subsets. The $A_n$ grow exponentially, the $B_n$ don't. $B$ is the smallest set containing $\emptyset$ that is closed under the power set operation and under taking differences. $A$ is also closed under these operations and contains $\emptyset$. Hence $A\subseteq B$. But $B\subseteq A$ is unclear to me right now. – Stefan Geschke Aug 15 '12 at 11:57

Clearly, $B\subseteq A$, because $A=V_\omega$, the set of all hereditarily finite well-founded sets, and all members of $B$ are hereditarily finite and well-founded. Thus it is enough to show that $A\subseteq B$.

For this, it is enough to show that for each $n$, there exists $m$ such that $A_n\subseteq B_m$. We will prove it by induction with respect to $n$.

1. for $n=0$, $A_0\subseteq B_0$.
2. Choose arbitrary $n\geq 0$, and suppose $A_n\subseteq B_{m_n}$ for some $m_n$.
3. Notice that $B_m$ is nondecreasing.
4. Notice that $A_n\in B_{n}$ (so $A_n\in B_m$ for all $m\geq n$), so to show that every subset of $A_n$ is a member of some $B_{m}$, it is enough to show that every singleton subset is (because then we can subtract successive singletons from $A_n$ to eventually obtain each subset, so if some $B_m$ has as a member $A_n$ as well as all its singleton subsets, $B_{m+\lvert A_n\rvert}$ will have all subsets of $A_n$).
5. Choose arbitrary $x\in A_n$. We need to find $m$ such that $\{x\}\in B_m$.
6. Notice that every subset of $x$ is also a member of $A_n$ (so $B_{m_n}$ too), and that $\{x\}=P(x)\setminus(\bigcup_{y\subsetneq x} P(y))$ (it would be enough to choose $y$ whose complement in $x$ is a singleton, but that does not matter).
7. Since for every $y\subsetneq x$ we have $P(y)\in B_{m_n+1}$, we also have that $\{x\}\in B_{m_n+1+\lvert P(x)\rvert}$
8. Therefore, all singletons of elements of $A_n$ are in $B_{m_n+1+\lvert P(A_n)\rvert}$, and all subsets of $A_n$ are in $B_{m_n+1+\lvert P(A_n)\rvert+\lvert A_n\rvert}$.

These bounds are by no means optimal, but that's not what we needed.

-
As for the bounds not being optimal, note that the largest term in the estimate of $m_{n+1}$ is $|\mathcal P(A_n)|$, which is exactly what I would expect. – Stefan Geschke Aug 15 '12 at 15:12
@StefanGeschke: Well, I'm pretty sure they are optimal in terms of growth magnitude, just not strictly optimal (or anywhere near). :) – tomasz Aug 15 '12 at 15:13
Thank you. That's a really nice proof. BTW, I already suspected that $A$ might already have a name :-) – celtschk Aug 15 '12 at 15:23

We will prove both of the expressions $A\subset B$ and $B\subset A$. The first is more difficult, but it follows from $$A_n\subset B_{n+1},$$which we demonstrate below.

First, though, let us verify that $A_n\in B_n$ through induction. Clearly, $A_0\in B_0$, and if $A_n\in B_n$, then $A_{n+1}=P(A_n)\in B_{n+1}$.

Next, we define a sequence $C_n$ by $$C_0=\emptyset\qquad C_{n+1}=\{C_n\}.$$ For $n>0$, the subsets of $A_n$ are classified by those do not contain $C_n$ and those which are equal to a subset of $A_{n-1}$ plus the element $C_n$.

To show that $A_n\subset B_{n+1}$, we begin with $A_0\subset B_0\subset B_1$, establishing the base case of another proof by induction. Assume that $A_n\subset B_{n+1}$. Let $S\subset A_n$, i.e. an element of $A_{n+1}$. If $S$ is empty, then it is an element of $B_0\subset B_{n+2}$. If the nonempty set $S\subset A_{n-1}$, then by hypothesis $S\subset B_{n}\subset B_{n+2}$. Otherwise $C_{n+1}\in S$. There is a subset $T\subset A_{n-1}$ such that $S=A_n\setminus T.$ Since $A_n$ and $T$ are both elements of $B_{n+1}$, it follows that their difference $S\in B_{n+2}$, concluding the proof.

Therefore, $A\subset B$. The other direction is implied by the proposition $$B_n\subset A_{n+1}.$$ Obviously, $B_0\subset A_1$, so assume the induction hypothesis that $B_n\subset A_{n+1}$. If $X$ is an element of $B_n$, then it is a subset of $A_n$. So, its power set $P(X)$ is a a subset of $P(A_n)=A_{n+1}$. That is $x\in A_{n+2}$. If $X,Y\in B_n$, then $$X-Y\subset X\subset A_n.$$ Hence, the difference is an element of $A_{n+1}\subset A_{n+2}$.

-
I don't understand this step: "If $X\in B_{n+1}$ then $P(X)\subset B_n=B_{n+1}$." First, you surely didn't mean $=$ here, because clearly $B_n\neq B_{n+1}$. However, I also don't get the left hand side: Why should the powerset of a set in $B_{n+1}$ be subset of $B_n$? – celtschk Aug 15 '12 at 13:55
Thank you for pointing out my mistakes on the last part. Allow me to correct them. – peoplepower Aug 15 '12 at 14:01
As I pointed out in my comment above, the $B_n$ grow polynomially, while the $A_n$ grow exponentially. So $A_n\subseteq B_{n+1}$ is simply not true for all $n$. – Stefan Geschke Aug 15 '12 at 14:29
I think I've found another error: "For $n>0$, the subsets of $A_n$ are classified by ..." — Take the set $X=\{C_2,\{C_0,C_1\}\}$. Then $X\in A_4$, $X\notin A_3$ but $C_3\notin X$ and $C_4\notin X$ (I see two reasonable interpretations of "plus $C_n$", and both are covered by this example). Therefore it fits into neither of your classes. – celtschk Aug 15 '12 at 14:52
@celtschk Thanks, that is precisely the reason why this answer is incorrect. – peoplepower Aug 15 '12 at 14:54