Número mínimo de aparatos Necesarios para Generar el juego de Poder

Question

Tomar un conjunto finito $A$ $|A|=n.$ Deje $\mathscr{F}$ ser el juego de poder de $A$. ¿Cuál es el menor número de sets necesarios para generar $\mathscr{F}$? Es decir, si $\mathscr{C}$ es un conjunto de subconjuntos de a$A$, ¿cuál es el tamaño mínimo de $\mathscr{C}$ tal que $\sigma (\mathscr{C})=\mathscr{F},$ donde $\sigma (\mathscr{C})$ denota la sigma-campo generado por $\mathscr{C}.$

Mi enfoque es para ver el $\mathscr{C}$ ser capaces de generar todos los embarazos únicos de $A$. Así que tenemos un límite superior en el tamaño de $\mathscr{C}$$n$, esto viene de dejar que las $\mathscr{C}$ el conjunto de los embarazos únicos.

Sin embargo, mirando el ejemplo de $A=\{ 1,2,3\},$ puedo conseguir un conjunto que $\mathscr{C}=\{\{1,2\},\{2,3\}\}$ genera $\mathscr{F}$. Así que sé que $n$ no es el tamaño mínimo, pero estoy seguro de cómo ir sobre la búsqueda de su tamaño mínimo.

Gracias por la ayuda!

Answer 1

El mínimo tamaño es $\lceil \log_2 n \rceil$.

Para ver esto, vamos a demostrar que si $|\mathscr{C}| < \lceil \log_2 n \rceil$, $\mathscr{C}$ no se puede generar el $\mathscr{F}$. Esto se deduce del hecho de que $2^{|\mathscr{C}|} < n$, por lo que dos elementos de $A$ debe aparecer exactamente de la misma conjuntos de $\mathscr{C}$, por lo que aparece en exactamente la misma establece en $\sigma(\mathscr{C})$. Sin embargo, existen conjuntos en $\mathscr{F}$ que contienen uno de estos dos elementos, pero no el otro, por lo tanto conduce a una contradicción.

Por otro lado, vamos a mostrar que hay un $\mathscr{C}$ $|\mathscr{C}| = \lceil \log_2 n \rceil$ eso basta. Deje $S_i$ ser el subconjunto de $\{0, 1, \dots, n-1\}$ que consta de los elementos cuyas $i$th bits (de la derecha) es igual a $1$ (cuando escriben en binario), y deje $\mathscr{C}$ ser la colección de $S_i$$1 \leq i \leq \lceil \log_2 n \rceil$. Ahora, para la construcción de cualquier singleton $\{i\}$, vamos a $X$ igual que el conjunto de posiciones $j$ de manera tal que el $j$th bits de $i$$1$, y deje $Y$ igual que el conjunto de posiciones $j$ de manera tal que el $j$th bits de $i$$0$. A continuación, se deduce que

$$\{i\} = \bigcap_{j\in X} S_j \cap \bigcap_{j \in Y} \overline{S_j}$$

y por lo tanto, este conjunto genera $\mathscr{F}$.