The set of all countable subsets of $X := \{0,1\}^\omega$ has the same cardinality as $X$. Does this generalize to larger sets?

83 Views Asked by At

Let $X$ be $\{0,1\}^\omega$, which can be thought of as the set of all sequences of $0$ and $1$s.

In Munkries Topology, an exercise in section 1-7 asks to show that the set of all countable susbsets of $X$ has the same cardinality as $X$. This has a straightforward solution which, I believe, makes use of the axiom of choice; a sketch of the proof goes as follows: For any such subset $S$, choose a mapping $M:S \rightarrow \mathbb N$, write each $S$ as row $M(S)$ of an array $A$; then the usual trick of making a path starting from the upper left element of $A$ and traveling along each down-left to up-right diagonal allows you to read off a sequences of $0$ and $1$s, that is, a member of $x(S)$ of $X$. If two such members $x(S_1),x(S_2)$ are equal, then $S_1=S_2$, so there is an injection from the set of all countable subsets, into $X$, so the former is not "larger" than the latter. (The opposite direction is trivial.)

Since that was not too hard, I decided to see if the generalization is true:

Conjecture $J$: Given an infinite set $Y$. Then $Y$ as the same cardinality as the set of all subsets of $Y$ that have lesser cardinality than $Y$.

This has the same flavor as a lot of the rules of cardinal arithmetic, so it seems plausible that it can be proven. I tried to prove $J$; theorems that depend on the axiom of choice would be fair game, since already for the case of $\{0,1\}^\omega$ I needed choice. But I got nowhere.

Just to build muscles, so to speak, I tried what I thought would be a much easier conjecture:

Conjecture $K$: Any infinite set $A$ contains two disjoint subsets such that each has the same cardinality as $A$.

$K$ is evidently false; https://en.wikipedia.org/wiki/Amorphous_set. So my instincts about $J$ being true are highly suspect as well.

Can anybody outline a proof that the set of all lesser-cardinality subsets of infinite set $Y$ has the same cardinality as $Y$? Or show that this is not the case for some sufficiently large $Y$?

2

There are 2 best solutions below

2
On BEST ANSWER

Your Conjecture K is true. Suppose $A$ is infinite, with $|A| = \kappa$. Since $\kappa = 2\cdot \kappa$, we can pick a bijection $f\colon \{0,1\}\times \kappa\to A$. Then $f(\{0\}\times \kappa)$ and $f(\{1\}\times\kappa)$ are disjoint subsets of $A$ of cardinality $\kappa$.

Your Conjecture J is not a direct generalization of the exercise from Munkres. With $X = \{0,1\}^\omega$, $|X| = 2^{\aleph_0}$. If the Continuum Hypothesis (CH) is true, then every subset of $X$ with cardinality less than $|X|$ is countable. But if CH is false, then $X$ has subsets $Y$ with $\aleph_0<|Y|<|X|$.

Given a set $X$ with $|X| = \kappa$, the number of subsets of $X$ of cardinality less than $\kappa$ is $\kappa^{<\kappa} = \mathrm{sup}_{\lambda<\kappa}\kappa^\lambda$. So your Conjecture J is equivalent to the statement that for all infinite $\kappa$, $\kappa^{<\kappa} = \kappa$.

Conjecture J is provably false in ZFC: by König's theorem, if $\kappa$ is a singular cardinal (meaning $\mathrm{cf}(\kappa)<\kappa$), then $\kappa^{<\kappa} \geq \kappa^{\mathrm{cf}(\kappa)}>\kappa$.

In this previous answer of mine, I gave a characterization of those infinite cardinals $\kappa$ satisfying $\kappa^{<\kappa} = \kappa$. I also explained that it is consistent with ZFC that Conjecture J is true for all regular cardinals (so it only fails at the singular cardinals), but at the other extreme, it is consistent with ZFC (assuming a large cardinal axiom) that Conjecture J is false for all infinite cardinals.

In particular, it is consistent that Conjecture J is false at the continuum ($\kappa = 2^{\aleph_0}$). For one thing, it is consistent with ZFC that the continuum is singular (for example, if $2^{\aleph_0} = \aleph_{\omega_1}$). But it is also consistent with ZFC to have $2^{\aleph_0} = \aleph_2$ and $2^{\aleph_1} = \aleph_3$. Then the continuum is regular, but with $\kappa = 2^{\aleph_0}$, we have $\kappa^{<\kappa} = 2^{\aleph_1} = \aleph_3>\kappa$.

0
On

Generally speaking, there are $\lambda^\kappa$-many $\kappa$-sized subsets of $\lambda$. So for $X^\omega$, the countable subsets are always $X^{\omega\times\omega}\cong X^\omega$. But there is a theorem of König that $\lambda^\kappa\neq\lambda$ when $\kappa$ has a specific form.

More precisely, you get into the issue of cofinality. Every cardinal $\kappa$ has a cardinality $\mathrm{cf}(\kappa)$ which is at most $\kappa$. When $\mathrm{cf}(\kappa)=\kappa$, then $\kappa$ is said to be regular and has various nice properties with cardinal arithmetic. For example, it's possible to have $\kappa^{<\kappa}=\kappa$ (your conjecture J). But for non-regular (which are called singular) cardinals, the cardinal arithmetic is a bit more complicated because in that case, $\kappa^{<\kappa}$ is never $\kappa$.

Your conjecture K is actually true, as amorphous sets contradict the axiom of choice.