Subconjunto de Conjunto de Números Naturales de Poder

Question

Hoy me hicieron una pregunta que pide encontrar un subconjunto del conjunto de poder de números naturales con cardinalidad$2^{\aleph_0}$ y en la que dos subconjuntos tienen muchos elementos en su intersección.

Mi solución fue considerar las secuencias de los racionales que convergen a un número real, para cada real, y luego tomar la bijección de esas secuencias de los racionales a las secuencias de los naturales.

¿Se puede probar esto más directamente? Es decir, ¿mostrar un subconjunto explícito del conjunto de potencias?

Answer 1

Deje ${^\Bbb N}\{0,1\}$ el conjunto de secuencias infinitas de $0$'s y $1$'s, y deje $\Sigma$ el conjunto de secuencias finitas de $0$'s y $1$'s. Para cada una de las $\sigma\in{^\Bbb N}\{0,1\}$ vamos $$S_\sigma=\{s\in\Sigma:s\text{ is an initial segment of }\sigma\}\;;$$ it's not hard to show that if $\sigma,\tau\in{^\N Bbb}\{0,1\}$, and $\sigma\ne\tau$, then $S_\sigma\cap S_\tau$ es finito.

Finalmente, $\Sigma$ es countably infinito, por lo que admite un bijection con $\Bbb N$. Con un poco de trabajo se puede producir una explícita bijection $h:\Sigma\to\Bbb N$, y, a continuación, la colección de $\big\{h[S_\sigma]:\sigma\in{^\Bbb N}\{0,1\}\big\}$ tiene las propiedades deseadas.

Agregó: he Aquí un buen bijection $h$. Si $s=\langle b_0,\dots,b_{n-1}\rangle\in\Sigma$, vamos $$h(s)=2^n+\sum_{k=0}^{n-1}b_k2^k\;.$$ As $s$ runs over all sequences in $\Sigma$ of length $n$, $\sum_{k=0}^{n-1}b_k2^k$ runs over all non-negative integers in $\{0,\dots,2^n-1\}$, and $h(s)$ runs over $\{2^n,\dots,2\cdot2^n-1\}=\{2^n,\dots,2^{n+1}-1\}$, so $h$ is clearly a bijection from $\Sigma$ to $\Bbb, N$. Indeed, given $n\in\Bbb, N$, we can calculate $h^{-1}(n)$ de la siguiente manera.

Primero vamos a $k=\lfloor \lg n\rfloor$ donde $\lg x$ es el registro binario; a continuación,$2^k\le n<2^{k+1}$. Deje $m=n-2^k$; a continuación,$0\le m<2^k$, lo $m$ tiene una única representación binaria $$m=\sum_{i=0}^{k-1}b_i2^i\;,$$ where each $b_i\en\{0,1\}$, and $h^{-1}(n)=\langle b_0,\dots,b_{k-1}\rangle$.

Answer 2

Para cada conjunto infinito de enteros$A\subset \omega$, asocie el conjunto infinito de enteros$S_A = \{\sum_{i \in A \cap n} 2^i : n<\omega\}$. Si$i \in A \setminus B$ entonces casi todos los elementos de$S_A$ tienen un "1" en el lugar$i$ - th en su expansión binaria, y no hay elementos de$S_B$, así que $S_A \cap S_B$ es finito. Queda por observar que existen muchos conjuntos infinitos de números enteros$A \subset \omega$.