Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
@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
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. –  Stefan Geschke Aug 15 '12 at 11:57

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
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}$.

share|improve this answer
    
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
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$. –  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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.