Una pregunta acerca de subconjuntos

Question

La pregunta es a partir de la siguiente elección múltiple problema:

Deje $A$ $B$ ser subconjuntos de un conjunto $M$ y deje $S_0=\{A,B\}$. Para $i\geq 0$, definir $S_{i+1}$ inductivamente a ser la colección de subconjuntos $X$ $M$ que son de la forma $C\cup D$, $C\cap D$, o $M-C$ (el complemento de $C$$M$), donde $C,D\in S_i$. Deje $S=\cup_{i=0}^{\infty}S_i$. ¿Cuál es la larest número posible de elementos de $S$?

A. 4
B. 8
C. 15
D. 16
E. $S$ puede ser infinito.

Parece que esto podría estar relacionado con el "$\sigma$-álgebra". Pero no tengo idea de lo que la técnica que uno necesita para resolver este problema. He intentado algunas conjunto finito, por ejemplo, $\{0,1,2,3,4,5\}$ y dejar $A=\{0\}$, $B=\{1\}$. Pero no puedo encontrar ningún patrón en el ejemplo. Alguna idea de cómo solucionarlo?

También, tengo una pregunta:

Se trata simplemente de un ejercicio trivial para algunas pruebas de conocimiento? O es que hay una foto grande detrás de este problema?

Editar: Como la respuesta sugirió, me dibujar la imagen. Sin embargo, a menos que yo finalmente enumerar todos los 16 de posibilidades y no puedo más, no puedo convencerme de que la respuesta es la D. Cualquier forma rápida de hacer esto?

Answer 1

Dibuje un Diagrama de Venn. Para "general" $A$$B$, el mundo, $M$ se divide en $4$ partes. Es bastante fácil ver que el uso de las operaciones permitidas, podemos conseguir cualquier conjunto que es la unión de $0$ o más de estas partes. Así que antes de cada parte, parar y decidir si lo incluyen. Para cada una de las partes, no se $2$ opciones, para un total de $2^4$.

La idea se puede generalizar a situaciones en las que empezamos con $3$ conjuntos, $4$ conjuntos, y así sucesivamente. Cuando empezamos con $n$ conjuntos, el máximo total generado es $2^{(2^n)}$, y este vaue es, en general, se supone.

Podemos pensar en este como un ejercicio de combinatoria, o como una manera de hacer que la gente piense acerca de qué tipos de juegos pueden ser generados usando el importante conjunto de la teoría de operaciones de el problema. También podríamos pensar en él como parte de un ejercicio de lectura y comprensión del lugar lenguaje formal usado en la formulación del problema.

Añadido: Podemos utilizar el diagrama de Venn como la intuitiva base detrás de un diagrama de enfoque libre. Vamos a decir que $X$ es un conjunto básico si $X$ es uno de $A\cap B$, $A\cap B^c$, $A^c \cap B$, o $A^c \cap B^c$, donde en general $U^c$ denota el complemento de $U$$M$. Estos conjuntos son disjuntos a pares. Obviamente, algunos podrían estar vacíos, pero para cualquier $M$, con al menos $4$ elementos, es fácil llegar a $A$ $B$ que no son exactamente $4$ no vacío básica de conjuntos.

Para la construcción formal, tenga en cuenta primero que, en general,$S_i \subseteq S_{i+1}$, ya que por definición si $X\in S_i$$X\cap X \in S_{i+1}$. Es obvio que los sets básicos son construibles el uso de nuestras operaciones, y que lo es cualquier unión de $0$ o más conjuntos. En el caso genérico hay $2^4$ distintos sindicatos. Esto no acaba de terminar las cosas. Para la integridad necesitamos para demostrar la intuitivamente obvio hecho de que no hay otros subconjuntos de a $M$ son construibles.

En principio, esto se hace por inducción sobre el número de pasos en la construcción. Para la base de paso, se observa que el $A$ $B$ son los sindicatos (posiblemente vacía) de básica de conjuntos. Para la inducción de paso, tenemos que mostrar que si cualquiera de las tres operaciones fundamentales es aplicada a una unión de los sets básicos, el resultado es una unión de conjuntos básicos. Esto es muy fácil para cada uno de $\cup$, $\cap$, y complemento relativo.