¿Conducen estas dos construcciones al mismo conjunto?

Question

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

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

Pregunta: ¿Es $A=B$ ?

Nota: Aquí $P(X)$ denota el conjunto de potencias de $X$ .

Answer 1

Claramente, $B\subseteq A$ porque $A=V_\omega$ el conjunto de todos los conjuntos hereditarios finitos bien fundados, y todos los miembros de $B$ son hereditariamente finitos y bien fundados. Por lo tanto, basta con demostrar que $A\subseteq B$ .

Para ello, basta con demostrar que para cada $n$ existe $m$ tal que $A_n\subseteq B_m$ . Lo demostraremos por inducción con respecto a $n$ .

1. para $n=0$ , $A_0\subseteq B_0$ .
2. Elige lo que quieras $n\geq 0$ y supongamos que $A_n\subseteq B_{m_n}$ para algunos $m_n$ .
3. Observe que $B_m$ no es decreciente.
4. Observe que $A_n\in B_{n}$ (así $A_n\in B_m$ para todos $m\geq n$ ), por lo que para demostrar que todo subconjunto de $A_n$ es un miembro de algún $B_{m}$ basta con demostrar que todo subconjunto de singletons lo es (porque entonces podemos restar los singletons sucesivos de $A_n$ para obtener eventualmente cada subconjunto, por lo que si algún $B_m$ tiene como miembro $A_n$ así como todos sus subconjuntos de un solo dígito, $B_{m+\lvert A_n\rvert}$ tendrá todos los subconjuntos de $A_n$ ).
5. Elige lo que quieras $x\in A_n$ . Tenemos que encontrar $m$ tal que $\{x\}\in B_m$ .
6. Obsérvese que todo subconjunto de $x$ también es miembro de $A_n$ (así $B_{m_n}$ también), y que $\{x\}=P(x)\setminus(\bigcup_{y\subsetneq x} P(y))$ (bastaría con elegir $y$ cuyo complemento en $x$ es un singleton, pero eso no importa).
7. Ya que para cada $y\subsetneq x$ tenemos $P(y)\in B_{m_n+1}$ también tenemos que $\{x\}\in B_{m_n+1+\lvert P(x)\rvert}$
8. Por lo tanto, todos los monotonos de elementos de $A_n$ están en $B_{m_n+1+\lvert P(A_n)\rvert}$ y todos los subconjuntos de $A_n$ están en $B_{m_n+1+\lvert P(A_n)\rvert+\lvert A_n\rvert}$ .

Estos límites no son en absoluto óptimos, pero no es lo que necesitábamos.

Answer 2

Demostraremos las dos expresiones $A\subset B$ y $B\subset A$ . La primera es más difícil, pero se deduce de $$A_n\subset B_{n+1},$$ que demostramos a continuación.

Pero primero verifiquemos que $A_n\in B_n$ a través de la inducción. Claramente, $A_0\in B_0$ y si $A_n\in B_n$ entonces $A_{n+1}=P(A_n)\in B_{n+1}$ .

A continuación, definimos una secuencia $C_n$ por $$C_0=\emptyset\qquad C_{n+1}=\{C_n\}.$$ Para $n>0$ los subconjuntos de $A_n$ se clasifican por los que no contienen $C_n$ y las que son iguales a un subconjunto de $A_{n-1}$ más el elemento $C_n$ .

Para demostrar que $A_n\subset B_{n+1}$ comenzamos con $A_0\subset B_0\subset B_1$ estableciendo el caso base de otra prueba por inducción. Supongamos que $A_n\subset B_{n+1}$ . Dejemos que $S\subset A_n$ es decir, un elemento de $A_{n+1}$ . Si $S$ está vacío, entonces es un elemento de $B_0\subset B_{n+2}$ . Si el conjunto no vacío $S\subset A_{n-1}$ entonces, por hipótesis $S\subset B_{n}\subset B_{n+2}$ . De lo contrario, $C_{n+1}\in S$ . Hay un subconjunto $T\subset A_{n-1}$ tal que $S=A_n\setminus T.$ Desde $A_n$ y $T$ son ambos elementos de $B_{n+1}$ se deduce que su diferencia $S\in B_{n+2}$ , concluyendo la prueba.

Por lo tanto, $A\subset B$ . La otra dirección está implícita en la proposición $$B_n\subset A_{n+1}.$$ Obviamente, $B_0\subset A_1$ por lo que se asume la hipótesis de inducción de que $B_n\subset A_{n+1}$ . Si $X$ es un elemento de $B_n$ entonces es un subconjunto de $A_n$ . Por lo tanto, su conjunto de poder $P(X)$ es un subconjunto de $P(A_n)=A_{n+1}$ . Es decir $x\in A_{n+2}$ . Si $X,Y\in B_n$ entonces $$X-Y\subset X\subset A_n.$$ Por lo tanto, la diferencia es un elemento de $A_{n+1}\subset A_{n+2}$ .