Cardinality of a certain set of distinct subsets of $\mathbb{N}$ - MathOverflow

Cardinality of a certain set of distinct subsets of $\mathbb{N}$

2012-05-03T16:17:31Z

A recent question here has convinced me that folks here have a warm heart for the foundations of quantum mechanics, so I decided to ask a question that has been bothering me for a while.

Quantum motivation

Hardy has proved a theorem saying the the cardinality of the ontic space $\Lambda$ must always be infinite. As Spekkens put it more clearly, his proof works by making a injection of the set of pure quantum states into the set of distinct subsets of $\Lambda$. Since the set of pure states is continuous, it follows that $\Lambda$ must be infinite.

But the injection isn't exactly onto $\mathcal{P}(\Lambda)$, but rather onto a set $D$ of distinct subsets of $\Lambda$ such that that for no $A,A'\in D$ is it true that $A \subset A'$. My question is then: is this additional restriction enough to show that $\Lambda$ must be continuous? Or is there a countable $\Lambda$ such that $D$ is uncountable?

Quantum-free question

Let $D$ be a set of distinct subsets of $\mathbb{N}$ such that for no $A,A'\in D$ is it true that $A \subset A'$. What is the maximal cardinality of such a $D$?

This question seems simple enough, but I haven't been able to answer it.

Answer by Andres Caicedo for Cardinality of a certain set of distinct subsets of $\mathbb{N}$

2012-05-03T19:26:53Z

Mateus, say that a family ${\mathcal F}$ of infinite subsets of ${\mathbb N}$ is almost disjoint iff $A\cap B$ is finite for any distinct sets $A,B$ in ${\mathcal F}$.

The answer to your question is that there is a family as you require of size $|{\mathcal P}({\mathbb N})|=|{\mathbb R}|$, which is of course largest possible. In fact, one can find an almost disjoint such family.

There are several ways of exhibiting an example. I am fond of this construction: Identify ${\mathbb N}$ with ${\mathbb Q}$, and assign to each real $r$ (the range of) a strictly increasing sequence of rationals converging to $r$.

Another way is to identify ${\mathbb N}$ with the nodes of the binary tree $\{0,1\}^{<\mathbb N}$ whose elements are finite sequences of $0$s and $1$s. Now, each infinite sequence of $0$s and $1$s (and there are $|\{0,1\}^{\mathbb N}|=|{\mathcal P}({\mathbb N})|$ many such sequences) can be thought of as an infinite branch through this tree. Associate to it the collection of its initial segments (its "path"). This uniquely identifies the branch, and any two different paths eventually diverge, so they have finite intersection.

If $|X|=\kappa$ is infinite, the question of the size of a maximal almost disjoint family of subsets of $X$, where we now require $|A\cap B|<\kappa$ for distinct $A,B$ in the family, is more delicate if $2^{<\kappa}>\kappa$ (otherwise the second argument above adapts to give a family of size $2^\kappa$). For example, (Baumgartner showed that) it is independent of the usual axioms of set theory with choice whether there is a family of almost disjoint subsets of $\omega_1$ of size $2^{\omega_1}$.

Answer by Noah S for Cardinality of a certain set of distinct subsets of $\mathbb{N}$

2012-05-03T20:28:18Z

Here's a way of showing the existence of a family $\mathcal{D}$ of sets with $\vert \mathcal{D}\vert=2^{\aleph_0}$ and $\forall A\not=A'\in\mathcal{D}(A\not\subseteq A')$, using computability theory:

Say that a set $A\subseteq \mathbb{N}$ is introreducible if it is infinite and is computed by all of its infinite subsets (i.e., $\forall B\subseteq A, B\ge_T A)$.

Claim: for all $X\subseteq\mathbb{N}$, there is an introreducible set $Y\subseteq \mathbb{N}$ with $Y\equiv_T X$.

Proof: Assume WLOG that $X$ is infinite (otherwise $X$ is computable, and $Y=\mathbb{N}$ fulfills the claim), and write $X=\lbrace x_0 < x_1 < . . .\rbrace $. Let $Y=\lbrace \langle x_0, x_1, . . . , x_n\rangle: n\in\mathbb{N}\rbrace$. Clearly $Y$ is introreducible and $Y\equiv_T X$.

Now it is known that there exist antichains of size $2^{\aleph_0}$ in the Turing degrees (i.e., families $\mathcal{C}=(X_r)_{r\in\mathbb{R}}$ with $X_r\not\le_T X_s$ whenever $r\not=s$). Let $Y_r$ be an introreducible set of the same degree as $X_r$ for each $r\in\mathbb{R}$. Then clearly $\mathcal{D}=\lbrace Y_r: r\in\mathbb{R}\rbrace$ is a family of sets of size $2^{\aleph_0}$ no one of which is a proper subset of another.

Answer by Goldstern for Cardinality of a certain set of distinct subsets of $\mathbb{N}$

2012-05-03T22:16:07Z

A simpler construction, which yields pairwise incomparable sets (but not almost disjoint sets):

For any subset $A\subseteq \mathbb N$, let $X_A:= \{ 2n: n\in A\}$ , and let $Y_A:= \{ 2n+1: n\notin A\}$ , and let $Z_A:= X_A \cup Y_A$.

Then the family of all $Z_A$ has size continuum, and $Z_A \subseteq Z_B$ implies both

$A\subseteq B$ (because of $X_A\subseteq X_B$)
and also $B \subseteq A$ (because $Y_A\subseteq Y_B$),

hence $A=B$. So the $Z_A$ are pairwise incomparable.

(A similar construction works also for larger cardinalities; a set of size $\kappa$ has $2^\kappa$ many pairwise incomparable subsets; here I use a bijection between $\kappa$ and $\kappa\times 2$.)