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
    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.2012-08-15
  • 0
    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\}$.2012-08-15
  • 0
    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?2012-08-15
  • 0
    Shouldn't $B_{1} = \{\emptyset,\{\emptyset\}\}$? And for the original question, $A_{1} = P(A_{0}) = \{\emptyset\} = B_{1}$, and hence the construction ends up with $A=B$.2012-08-15
  • 0
    @Kevin: $B_1=\{\wp(\varnothing)\}\cup\{\varnothing\setminus\varnothing\}=\{\{\varnothing\},\varnothing\}$.2012-08-15
  • 1
    @Luke: It’s not that simple; $A_1=B_0$ and $A_2=B_1$, but $A_3\ne B_2$.2012-08-15
  • 0
    Of course, is there a \facepalm in amssymb?2012-08-15
  • 1
    @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.2012-08-15
  • 0
    @StefanGeschke: The smallest set containing $\emptyset$ would be $\{\emptyset\}$, wouldn't it?2012-08-15
  • 0
    Sorry, I had not finished writing my comment. See the edited comment.2012-08-15
  • 0
    @StefanGeschke, yeah, I just got overexcited for a moment.2012-08-15
  • 0
    @Stefan: I think that you reversed the inclusions, didn’t you? You showed that $B\subseteq A$.2012-08-15
  • 0
    @StefanGeschke: Ah, I see, this makes more sense. But wouldn't every (nonempty) set which is closed under taking differences necessarily include $\emptyset$ (because for any $X$, $X\setminus X=\emptyset$)?2012-08-15
  • 0
    @BrianM.Scott $B_1=\{P(\emptyset)\}\cup\{\emptyset\}=\{\emptyset,\{\emptyset,\{\emptyset\}\}\}$.2012-08-15
  • 0
    @Mercy: No: $\wp(\varnothing)=\{\varnothing\}$. The only subset of $\varnothing$ is $\varnothing$.2012-08-15
  • 0
    Oh yeah, you were right!2012-08-15
  • 0
    @Brian: Yes, you are right. $B\subseteq A$ is clear, but $A\subseteq B$ is not.2012-08-15
  • 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
    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.2012-08-15
  • 0
    @StefanGeschke: Well, I'm pretty sure they are optimal in terms of growth magnitude, just not strictly optimal (or anywhere near). :)2012-08-15
  • 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
    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$?2012-08-15
  • 0
    Thank you for pointing out my mistakes on the last part. Allow me to correct them.2012-08-15
  • 2
    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$.2012-08-15
  • 0
    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.2012-08-15
  • 0
    @celtschk Thanks, that is precisely the reason why this answer is incorrect.2012-08-15
  • 0
    @StefanGeschke Thanks, the problem is significantly more difficult than I thought. Do you have any ideas on what might qualify as a counterexample if one exists?2012-08-15
  • 0
    My statement about growth requires some clarification: The size of $B_{n+1}$ is bounded by a polynomial in the size of $B_n$ but independent of $n$, but the size of $A_{n+1}$ is $2^{|A_n|}$. But this still shows that for almost all $n$, $A_n$ is not contained in $B_{n+1}$. These different growth rates seem to indicate that a rather tricky argument would be needed to show $A\subseteq B$.2012-08-15
  • 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