Cardinality of a certain set of distinct subsets of $\mathbb{N}$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T23:23:25Z http://mathoverflow.net/feeds/question/95889 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95889/cardinality-of-a-certain-set-of-distinct-subsets-of-mathbbn Cardinality of a certain set of distinct subsets of $\mathbb{N}$ Mateus Araújo 2012-05-03T16:17:31Z 2012-05-03T22:16:07Z <p>A <a href="http://mathoverflow.net/questions/95537" rel="nofollow">recent question</a> 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.</p> <h2>Quantum motivation</h2> <p><a href="http://dx.doi.org/10.1016/j.shpsb.2003.12.001" rel="nofollow">Hardy</a> has proved a theorem saying the the cardinality of the ontic space $\Lambda$ must always be infinite. As <a href="http://arxiv.org/abs/quant-ph/0406166" rel="nofollow">Spekkens</a> 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. </p> <p>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?</p> <h2>Quantum-free question</h2> <p>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$?</p> <p>This question seems simple enough, but I haven't been able to answer it.</p> http://mathoverflow.net/questions/95889/cardinality-of-a-certain-set-of-distinct-subsets-of-mathbbn/95907#95907 Answer by Andres Caicedo for Cardinality of a certain set of distinct subsets of $\mathbb{N}$ Andres Caicedo 2012-05-03T19:26:53Z 2012-05-03T22:07:40Z <p>Mateus, say that a family ${\mathcal F}$ of infinite subsets of ${\mathbb N}$ is <em>almost disjoint</em> iff $A\cap B$ is finite for any distinct sets $A,B$ in ${\mathcal F}$. </p> <p>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.</p> <p>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$. </p> <p>Another way is to identify ${\mathbb N}$ with the nodes of the binary tree <code>$\{0,1\}^{&lt;\mathbb N}$</code> whose elements are finite sequences of $0$s and $1$s. Now, each infinite sequence of $0$s and $1$s (and there are <code>$|\{0,1\}^{\mathbb N}|=|{\mathcal P}({\mathbb N})|$</code> many such sequences) can be thought of as an infinite <em>branch</em> 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.</p> <hr> <p>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|&lt;\kappa$ for distinct $A,B$ in the family, is more delicate if $2^{&lt;\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}$. </p> http://mathoverflow.net/questions/95889/cardinality-of-a-certain-set-of-distinct-subsets-of-mathbbn/95913#95913 Answer by Noah S for Cardinality of a certain set of distinct subsets of $\mathbb{N}$ Noah S 2012-05-03T20:28:18Z 2012-05-03T20:35:05Z <p>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:</p> <p>Say that a set $A\subseteq \mathbb{N}$ is <em>introreducible</em> if it is infinite and is computed by all of its infinite subsets (i.e., $\forall B\subseteq A, B\ge_T A)$.</p> <p>Claim: for all $X\subseteq\mathbb{N}$, there is an introreducible set $Y\subseteq \mathbb{N}$ with $Y\equiv_T X$. </p> <p>Proof: Assume WLOG that $X$ is infinite (otherwise $X$ is computable, and $Y=\mathbb{N}$ fulfills the claim), and write $X=\lbrace x_0 &lt; x_1 &lt; . . .\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$.</p> <p>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.</p> http://mathoverflow.net/questions/95889/cardinality-of-a-certain-set-of-distinct-subsets-of-mathbbn/95926#95926 Answer by Goldstern for Cardinality of a certain set of distinct subsets of $\mathbb{N}$ Goldstern 2012-05-03T22:16:07Z 2012-05-03T22:16:07Z <p>A simpler construction, which yields pairwise incomparable sets (but not almost disjoint sets): </p> <p>For any subset $A\subseteq \mathbb N$, let <code>$X_A:= \{ 2n: n\in A\}$</code>, and let <code>$Y_A:= \{ 2n+1: n\notin A\}$</code>, and let $Z_A:= X_A \cup Y_A$. </p> <p>Then the family of all $Z_A$ has size continuum, and $Z_A \subseteq Z_B$ implies both </p> <ul> <li>$A\subseteq B$ (because of $X_A\subseteq X_B$)</li> <li>and also $B \subseteq A$ (because $Y_A\subseteq Y_B$),</li> </ul> <p>hence $A=B$. So the $Z_A$ are pairwise incomparable. </p> <p>(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$.)</p>