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}$.
Best Answer
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.)