Cardinalidad de un determinado conjunto de subconjuntos distintos de $\mathbb{N}$

Question

A pregunta reciente aquí me ha convencido de que la gente de aquí tiene un corazón cálido para los fundamentos de la mecánica cuántica, así que decidí hacer una pregunta que me ha estado molestando durante un tiempo.

Motivación cuántica

Hardy ha demostrado un teorema que dice que la cardinalidad del espacio óntico $\Lambda$ debe ser siempre infinito. Como Spekkens Dicho más claramente, su prueba funciona haciendo una inyección del conjunto de estados cuánticos puros en el conjunto de subconjuntos distintos de $\Lambda$ . Como el conjunto de estados puros es continuo, se deduce que $\Lambda$ debe ser infinito.

Pero la inyección no es exactamente en $\mathcal{P}(\Lambda)$ sino en un conjunto $D$ de subconjuntos distintos de $\Lambda$ tal que para ningún $A,A'\in D$ ¿es cierto que $A \subset A'$ . Mi pregunta es entonces: ¿es esta restricción adicional suficiente para demostrar que $\Lambda$ debe ser continua? ¿O hay un contable $\Lambda$ tal que $D$ es incontable?

Cuestión libre de quantum

Dejemos que $D$ sea un conjunto de subconjuntos distintos de $\mathbb{N}$ tal que para ningún $A,A'\in D$ ¿es cierto que $A \subset A'$ . ¿Cuál es la cardinalidad máxima de tal $D$ ?

Esta pregunta parece bastante sencilla, pero no he podido responderla.

Answer 1

Una construcción más sencilla, que produce conjuntos incomparables por pares (pero no conjuntos casi disjuntos):

Para cualquier subconjunto $A\subseteq \mathbb N$ , dejemos que $X_A:= \{ 2n: n\in A\}$ y dejemos que $Y_A:= \{ 2n+1: n\notin A\}$ y que $Z_A:= X_A \cup Y_A$ .

Entonces la familia de todos $Z_A$ tiene un tamaño continuo, y $Z_A \subseteq Z_B$ implica tanto

• $A\subseteq B$ (por $X_A\subseteq X_B$ )
• y también $B \subseteq A$ (porque $Y_A\subseteq Y_B$ ),

por lo que $A=B$ . Así que el $Z_A$ son incomparables entre sí.

(Una construcción similar funciona también para cardinalidades mayores; un conjunto de tamaño $\kappa$ tiene $2^\kappa$ muchos subconjuntos incomparables entre sí; aquí utilizo una biyección entre $\kappa$ y $\kappa\times 2$ .)

Answer 2

Mateus, digamos que una familia ${\mathcal F}$ de subconjuntos infinitos de ${\mathbb N}$ es casi disjuntos si $A\cap B$ es finito para cualquier conjunto distinto $A,B$ en ${\mathcal F}$ .

La respuesta a su pregunta es que hay una familia como usted requiere de tamaño $|{\mathcal P}({\mathbb N})|=|{\mathbb R}|$ que, por supuesto, es el más grande posible. De hecho, se puede encontrar una familia de este tipo casi disjunta.

Hay varias formas de exponer un ejemplo. A mí me gusta esta construcción: Identificar ${\mathbb N}$ con ${\mathbb Q}$ y asignar a cada real $r$ (el rango de) una secuencia estrictamente creciente de racionales que convergen a $r$ .

Otra forma es identificar ${\mathbb N}$ con los nodos del árbol binario $\{0,1\}^{<\mathbb N}$ cuyos elementos son secuencias finitas de $0$ s y $1$ s. Ahora, cada secuencia infinita de $0$ s y $1$ s (y hay $|\{0,1\}^{\mathbb N}|=|{\mathcal P}({\mathbb N})|$ muchas secuencias de este tipo) puede considerarse como un infinito rama a través de este árbol. Se le asocia la colección de sus segmentos iniciales (su "camino"). Esto identifica de forma única la rama, y dos caminos diferentes acaban por divergir, por lo que tienen una intersección finita.

---

Si $|X|=\kappa$ es infinito, la cuestión del tamaño de una familia máxima casi disjunta de subconjuntos de $X$ donde ahora requerimos $|A\cap B|<\kappa$ para los distintos $A,B$ en la familia, es más delicada si $2^{<\kappa}>\kappa$ (si no, el segundo argumento anterior se adapta para dar una familia de tamaño $2^\kappa$ ). Por ejemplo, (Baumgartner demostró que) es independiente de los axiomas habituales de la teoría de conjuntos con elección si existe una familia de subconjuntos casi disjuntos de $\omega_1$ de tamaño $2^{\omega_1}$ .

Answer 3

Esta es una forma de mostrar la existencia de una familia $\mathcal{D}$ de conjuntos con $\vert \mathcal{D}\vert=2^{\aleph_0}$ y $\forall A\not=A'\in\mathcal{D}(A\not\subseteq A')$ utilizando la teoría de la computabilidad:

Digamos que un conjunto $A\subseteq \mathbb{N}$ es introreducible si es infinito y es computado por todos sus subconjuntos infinitos (es decir, $\forall B\subseteq A, B\ge_T A)$ .

Reclamación: para todos $X\subseteq\mathbb{N}$ hay un conjunto introreducible $Y\subseteq \mathbb{N}$ con $Y\equiv_T X$ .

Prueba: Supongamos que WLOG que $X$ es infinito (en caso contrario $X$ es computable, y $Y=\mathbb{N}$ cumple con la demanda), y escribe $X=\lbrace x_0 < x_1 < . . .\rbrace $ . Sea $Y=\lbrace \langle x_0, x_1, . . . , x_n\rangle: n\in\mathbb{N}\rbrace$ . Claramente $Y$ es introreducible y $Y\equiv_T X$ .

Ahora se sabe que existen anticanales de tamaño $2^{\aleph_0}$ en los grados de Turing (es decir, las familias $\mathcal{C}=(X_r)_{r\in\mathbb{R}}$ con $X_r\not\le_T X_s$ siempre que $r\not=s$ ). Sea $Y_r$ sea un conjunto introreducible del mismo grado que $X_r$ para cada $r\in\mathbb{R}$ . Entonces, claramente $\mathcal{D}=\lbrace Y_r: r\in\mathbb{R}\rbrace$ es una familia de conjuntos de tamaño $2^{\aleph_0}$ ninguno de los cuales es un subconjunto propio de otro.