Do these two constructions lead to the same set?

Question

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$.

Answer 1

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.

Answer 2

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}$.