# Uncountable subset with uncountable complement, without the Axiom of Choice

Let $X$ be a set and consider the collection $\mathcal{A}(X)$ of countable or cocountable subsets of $X$, that is, $E \in \mathcal{A}(X)$ if $E$ is countable or $X-E$ is countable. If $X$ is countable, then $\mathcal{A}(X)$ coincides with the power set $\mathcal{P}(X)$ of $X$. Now suppose that $X$ is uncountable. Assuming the axiom of choice, we can conclude that $\mathcal{A}(X) \ne \mathcal{P}(X)$, since $|X| = |X| + |X|$. So the question is:

Can we prove in ZF that $\mathcal{A}(X) \ne \mathcal{P}(X)$ for every uncountable set $X$?

I'm assuming that a set $X$ is uncountable if there is no injective function $f : X \rightarrow \mathbb{N}$.

-
@Nuno: Perhaps you could look at Dedekind-infinite sets? – PEV Jan 13 '11 at 20:50
My guess is that the question mainly concerns uncountable sets of cardinality not greater than $\mathbb{R}$, because in $\mathbb{R}$ you can take for example $E=(-\infty,0)$, and then copies of $E$ under injective images of $\mathbb{R}$ in other sets. I say "guess" because I am not comfortable dealing with cardinalities in the absence of choice. – Jonas Meyer Jan 13 '11 at 20:55
@Jonas: A bit more: We want sets where neither ${\mathbb R}$ nor $\omega_1$ can be injected. In natural models without Dedekind finite sets, this tends to cover all cases. – Andrés Caicedo Jan 13 '11 at 21:19
@Nuno: You are correct. For example, in Solovay's model where all sets of reals are Lebesgue measurable or in natural models of determinacy, ${\mathbb R}$ and $\omega_1$ simply are incomparable. It happens that there are no infinite Dedekind finite sets in these models, so every uncountable set has cardinality at least ${\mathbb R}$ or $\omega_1$, but this is not an easy result. – Andrés Caicedo Jan 13 '11 at 21:30
@Nuno: In the absence of choice, $A(X)$ is not even a sigma algebra, in general. A countable union of countable sets can be uncountable. In fact, there are models of ZF set theory in which the reals are a countable union of countable sets. – George Lowther Jan 13 '11 at 23:13

A Dedekind finite set is one all of whose subsets have strictly smaller cardinality. If $X$ is infinite Dedekind finite (iDf), then $X$ and ${\mathbb N}$ are incomparable in size. This means that no subset of $X$ is countable unless it is finite. Certain Dedekind finite sets may be amorphous, this means that any subset is finite or cofinite.

It is consistent that there are iDf sets, but no amorphous sets. It is also consistent that there are infinite amorphous sets, so the answer to your question is no, in general. However, if every Dedekind finite set is amorphous, then there are no iDf sets. Hence, if there is an iDf set at all, there is one that can be split into two infinite sets, and neither is countable.

(Of course, under choice, there are no iDf sets and every uncountable set admits an uncountable subset with uncountable complement.)

-
Thanks Andres, I'll try to digest everything in your post before accepting it – Nuno Jan 13 '11 at 21:19

It is consistent with ZF without the axiom of choice that there is a set $X$ such that every subset of $X$ is countable or co-countable. These sets are called $\aleph_1$-amorphous (and sometimes quasi-minimal). They make peculiar counterexamples to some propositions.
If $X$ is $\aleph_1$-amorphous then $\mathcal P(X)=\mathcal A(X)$. Note that this is the "maximal" counterexample that we can produce since anything larger would have a subset which is not countable nor co-countable.
One remark is that amorphous sets are vacuously $\aleph_1$-amorphous, since every subset is finite (ergo countable) or co-finite (ergo co-countable). However it is possible to have an $\aleph_1$-amorphous set and still retain the Principle of Dependent Choice, a choice principle which amongst other things imply that every infinite set has a countable subset. In such model the $\aleph_1$-amorphous set is "non-degenerate", namely it has a countably infinite subset.
@Nuno: No problems. I was hoping to be able and add a sketch of some nice construction using $\aleph_1$-amorphous sets, but so far I could not find the proper way of doing so. The construction is that $\aleph_1$-amorphous sets can be linearly ordered (unlike amorphous sets which cannot be), but I was told that it is consistent to have a linear order on an $\aleph_1$-amorphous set that every countable subset is well-ordered in the restricted order. What a peculiar example! :-) – Asaf Karagila May 21 '12 at 18:48
@Nuno: One minor remark, which I wouldn't bump this thread for is that in ZFC there is a group of size $\aleph_1$ that every proper subgroup is countable. This is not exactly what you were looking for, but it is still interesting and relatively close to the $\aleph_1$-amorphous case (I can easily engineer an $\aleph_1$-amorphous set which is a vector space over $\mathbb Q$, and every proper subspace (read: subgroup) is countable). – Asaf Karagila Jul 3 '12 at 21:34