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}$.

Solution 1:

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.)

Solution 2:

I should add on Andres' answer with a minor variation:

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.