4
$\begingroup$

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

  • 0
    @celtschk: You are right, any nonempty set closed under taking differences contains the empty set. So you arrive at an equivalent charakterization of $B$.2012-08-15

2 Answers 2

5

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.

  • 0
    Thank you. That's a really nice proof. BTW, I already suspected that $A$ might already have a name :-)2012-08-15
0

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

  • 0
    @CLarue: It might be possible to come up with some explicit set in $A$ that is not in $B$. Or some class of sets. Can some body prove that $B$ contains sets of all finite cardinalities?2012-08-15