computabilityelementary-set-theory
Is there such a thing as a countable set with an uncountable subset?
Actually I know the answer. Well, I believe I know the answer, which is NO.
Unfortunately, the professor in a Theory of Computation class said that yes, there is such a subset.
This is to settle a discussion with fellow students. A discussion that is going nowhere so we go to the internets for a verdict.
Thanks in advance for weighing in on this question.
You have the uncountable set $A$ and its countable subset $B$. You want to show that $|A\setminus B|=|A|$, i.e., that there is a bijection between $A$ and $A\setminus B$. To see what that would mean, let’s imagine for a moment that we already have such a bijection $h:A\to A\setminus B$. $A$ is the union of the disjoint sets $B$ and $A\setminus B$, and $h$ is a bijection, so $h[A]$, which is $A\setminus B$, is the union of the disjoint sets $h[B]$ and $h[A\setminus B]$, as in the sketch below. And because $h$ is a bijection, we know that $B$ and $h[B]$ have the same cardinality; in particular, $h[B]$ is countable. In other words, if we’re to have this bijection $h$, we need to have some countable subset $h[B]$ of $A\setminus B$ that $h$ matches up with the subset $B$ of $A$. The set $C$ of your proof is going to be that set.
We know that $A\setminus B$ has a countably infinite subset $C$, and we know from an earlier result that $B\cup C$ is countably infinite. This means that $|B\cup C|=|C|$: there is a bijection $f:B\cup C\to C$. We can now use $f$ to build the desired bijection $h:A\to A\setminus B$ quite easily. We’ll split $A$ into two pieces, $B\cup C$ and the rest, which is $A\setminus(B\cup C)=(A\setminus B)\setminus C$; these are shown in red and white, respectively, in the lefthand set in the picture below. We’ll use the bijection $f$ to map $B\cup C$ to $C$, and we’ll use the identity map $\mathrm{id}$ to send $(A\setminus B)\setminus C$ to itself. Combining these two bijections gives us a bijection, which I’ll call $h$, from $A$ to $A\setminus $B$, as in the picture below.
Formally we define $h:A\to A\setminus B$ by
$$h(a)=\begin{cases} f(a),&\text{if }a\in B\cup C\\\\ a,&\text{if }a\in(A\setminus B)\setminus C\;. \end{cases}$$
The key idea is simply that all countably infinite sets are the same size, so we can find a bijection between any two of them. We use that fact to find the bijection $f$ that ‘collapses’ $B\cup C$ into $C$; then we leave all of the other elements of $A$ alone (i.e., those in $(A\setminus B)\setminus C$), and the net effect is to collapse $A$ into $A\setminus B$ with the bijection $h$.
Recall the definition of $\omega_1$. It is the set of all finite and countably infinite ordinals. You are asking why is this is a set. Which is an equivalent question to "why does $\aleph_1$ exists?".
But let me give some clarifications to your edit.
$2^{\aleph_0}$ is a cardinal number. Working in $\sf ZFC$, this means that this is an uncountable ordinal, which one we cannot say, but we can say that it is an uncountable ordinal.
But once you know that some uncountable ordinal exists, with or without choice, it is just an application of the axiom [schema] of separation, to pick the set of all countable ordinals.
We need the axiom [schema] of replacement to show that $\omega_1$ is a set, regardless to the above. Separation (which appear in some axiomatizations of set theory) is insufficient, so we really use replacement and the power of $\sf ZF$. Assuming $\sf ZF$ every well-ordered set is isomorphic to a von Neumann ordinal, and we can prove there is an uncountable well-ordered set, simply by noting that in $\mathcal P(\omega\times\omega)$ includes all the countable well-orders, so mapping each relation which is a well-ordering of its domain to the order type (and those which are not well-ordered to $0$), we get a definable function whose domain is a set, and by the replacement axioms the range is a set as well.
But every countable ordinal can be realized as a well-ordering of $\omega$. So the set of countable ordinals exists.
We also need the power set axiom to show that $\omega_1$ exists. And in fact, we need the power set axiom in order to show that there are uncountable sets at all. Recall that every set has a transitive closure, namely $\operatorname{tc}(X)$ is the smallest set $Y$ which is transitive (every element of $Y$ is also a subset of $Y$), and $X\subseteq Y$.
It turns out that $\mathrm{HC}=H(\aleph_1)=\{X\mid\operatorname{tc}(\{X\})\text{ is countable}\}$ satisfies all the axioms of $\sf ZFC$ except the power set axiom, and of course if $X\in\mathrm{HC}$ then there is an injection from $X$ into $\omega$ in $\mathrm{HC}$ as well. So $(\mathrm{HC},\in)$ satisfies the axiom "Every set is countable", as well $\sf ZFC-P$.
Without the axiom of replacement, but with power set and separation at least, we still cannot prove this set exists. The reason is that if you look at the von Neumann hierarchy of the universe, the $V_\alpha$'s then for any limit ordinal, $V_\alpha$ is a model of all the axioms of $\sf ZF$ except, perhaps replacement and if $\alpha=\omega$ then infinity fails. So taking $V_{\omega+\omega}$ is a model for the separation axioms, but there is no set of countable ordinals. Even $V_{\omega_1}$ is still a model of these axioms, but every von Neumann ordinal is countable there.
Best Answer
Of course it is easy to see that any subset of a countable set is countable. While enumerating the larger set, just skip over any elements that are not in the subset, and you have an enumeration of the subset.
Nevertheless, since you mentioned you were in a computability theory course, there are a few computability-like senses in which something like a positive answer to the question is possible.
Every infinite computably enumerable set has numerous subsets that are not computably enumerable. This is simply because every infinite set has uncountably many subsets, and most of these will not be computably enumerable, since there are only countably many c.e. sets. But from a computability perspective, computably enumerable is often the right analogue of countable, since those are the sets with a computable enumeration function, and so this is a very reasonable sense in which the claim is nearly true.
There can be c.e. sets whose complement is infinite, but contains no infinite c.e. subset. Thus, you can enumerate the set $S$, and infinitely many numbers are not in $S$, but there is no computable way to enumerate an infinite set of numbers not in $S$. These are known as the simple sets, and were studied from the time of Post.
Without AC, it is consistent that you can have a set $A$ with an equivalence relation $\sim$ on it, such that the number of equivalence classes of $\sim$ on $A$ is strictly larger than the cardinality of $A$. For example, we can make an equivalence relation $\sim$ having exactly $\mathbb{R}+\omega_1$ many equivalence classes, by saying that two reals are equivalent iff they are equal, or else they both code relations on $\omega$ that are well-orders of the same length. But under the Axiom of Determinacy, there is no $\omega_1$-sequence of distinct real numbers, and so this cardinality is strictly larger than $\mathbb{R}$.