The ordinal $\omega_1$ can (consistently) be a countable union of countable ordinals, i.e., the supremum of a countable set of countable ordinals.
This consistency result was one of the first found with forcing. It was announced in S. Feferman-A. Levy, "Independence results in set theory by Cohen's method II", Notices Amer Math Soc., 10, (1963) 593.
The result is that it is consistent with $\mathsf{ZF}$ that ${\mathbb R}$ is a countable union of countable sets. From this, it follows easily that $\omega_1$ also has this property. A proof can be found in Jech's book on the Axiom of Choice.
The problem is that, as you suspect, "The supremum of a countable set of countable ordinals" cannot be proved without some choice to be countable. The issue is that although we know that each countable ordinal is in bijection with $\omega$, there is no uniform way of picking for each countable ordinal one such bijection. Now, you need this to run the usual proof that a countable union of countable sets is countable.
In fact, things can be worse: Gitik showed that it is consistent with $\mathsf{ZF}$ that every infinite (well-ordered) cardinal has cofinality $\omega$. ("All uncountable cardinals can be singular", Israel J. Math, 35, (1980) 61-88.)
On the other hand, one can check that a countable union of countable sets of ordinals must have size at most $\omega_1$ (which is essentially what your HW is asking to verify). So, in Gitik's model, $\omega_2$ is a countable union of countable unions of countable ordinals, but not a countable union of countable ordinals.
Let me add two comments about other things you say in your question: You write "I have read that it is provable in $\mathsf{ZF}$ that there are no cardinals $\kappa$ such that $\aleph_0<\kappa<\aleph_1$". This is true, but it is stronger than that: By definition $\aleph_1$ is the first ordinal that is not countable, so of course there are no cardinals in between $\aleph_0$ and $\aleph_1$. Similarly, there are no cardinals between any (well-ordered) cardinal $\kappa$ and its successor $\kappa^+$, by definition.
It is true, however, that a countable union of countable sets need not be comparable with $\aleph_1$ without choice. In fact, we can have a non-well-orderable set that can be written as a countable union of sets of size 2.
Edit, Jun 24/16: To see that a countable union of countable sets of ordinals cannot equal $\omega_2$, we check more generally that if $\kappa$ is a (well-ordered) cardinal, then a union of $\kappa$ many sets, each of size at most $\kappa$, cannot have size $\kappa^{++}$: Let $S_0,S_1,\dots,S_\beta,\dots$, $\beta<\kappa$, be sets of ordinals, each of size at most $\kappa$. Let $S$ be their union and let $\alpha={\rm ot}(S)$, the order type of $S$. Similarly, let $o_\iota={\rm ot}(S_\iota)$ for each $\iota<\kappa$. Each $o_\iota$ is an ordinal below $\kappa^+$ and therefore $o=\sup_\iota o_\iota\le\kappa^+$. Use this to define a surjection $f$ from $\kappa\times o$ onto $\alpha$, from which it follows that there is an injection from $\alpha$ into $\kappa\times o$, and therefore a injection from $\alpha$ into $\kappa^+$:
Given $(\iota,\beta)\in \kappa\times o$, define $f(\iota,\beta)=0$ unless $\beta<o_\iota$ and, letting $\gamma$ be the $\beta$-th element in the increasing enumeration of $S_\iota$, we have that $\iota$ is least such that $\gamma\in S_\iota$. If this is the case, then set $f(\iota,\beta)=\delta$, where $\delta$ is defined so that $\gamma$ is the $\delta$-th member of $S$ in its increasing enumeration. It should be clear that $f$ is a surjection, and we are done.
(It is perhaps clear, but let me remark that if $\omega_1$ can be written as the countable union of countable sets, then any $\alpha<\omega_2$ can be written this way as well, so $\omega_2$ cannot be replaced with any smaller bound.)
The idea behind Scott's trick of turning the equivalence classes into rather complicated sets is merely to allow working with the partial order of cardinalities within the theory with ease.
In the presence of AC, we can always pick a canonical example for each cardinality, namely the initial ordinal of the equivalence class.
It is consistent with ZF that no choice of canonical representatives exist. Namely, there is no definable class-function $C$ such that for all $X\in V$:
- $C(X)=C(Y)\iff |X|=|Y|$;
- $|C(X)|=|X|$
This sort of $C$ exists naturally with the axiom of choice, as I have mentioned above. It seems that we somewhat take for granted this existence.
With or without the axiom of choice we can consider $|X|$ as in Scott's trick, namely taking the equipollent sets of the least possible rank. However with the axiom of choice we can set $C(X)=\min\{a\in Ord\mid |X|=|a|\}$, and just assume $|X|=C(X)$.
The point is that without the axiom of choice we simply cannot have this luxury, and we are reduced to handling these complicated sets of cardinalities. This is just one more reason why the cardinal arithmetics become so heavy when leaving the axiom of choice behind.
When canonical representatives are not guaranteed, the use of Scott's trick become essential when writing theorems about cardinalities.
Suppose $A$ is amorphous (that is $B\subseteq A$ implies $B$ is finite or $A\setminus B$ is finite).
I want to describe $(\{|Y|\colon Y\subseteq A\},<)$. Using Scott's trick this is easily done, since $Y\mapsto |Y|$ is a definable function, the domain of this partially ordered set is definable nicely from $A$.
However using the first approach I am left to wonder what is the domain of the cardinalities of subsets of $A$? In this approach $|A|$ is a syntactic object, not semantic.
I can describe that this is a linearly ordered set (i.e. every two subsets of $A$ have comparable cardinalities) but can I prove that this set is exactly $\omega+\omega^*$? (that is to say, a linear order in which every point has either finitely many points above or finitely below; but not both) No, I cannot.
This is because $B_X=\{|B|\colon |B|<|X|\}$ cannot be described uniformly within the model, and so we cannot describe its size in a uniform way (that is as a function $X\mapsto |B_X|$).
As Andres commented on the main question, in many cases it is not a big issue. This is the main reason why this "example" seems a bit artificial. However it does help when you have a nice way to define cardinalities in the times you actually need it.
I should mention that ordinals are always well-ordered and therefore of an $\aleph$-number kind of cardinality, and such $C$ can be defined for the class of well-orderable sets. The thing is that without the axiom of choice we just tend to have sets which cannot be bijected with ordinals with the absence of choice.
For more information: T. Jech, The Axiom of Choice Ch. 11
Added note: Scott's trick makes a heavy use of the axiom of regularity (also: axiom of foundation), and I am not aware of a clean way for defining cardinalities with the lack of both regularity as well choice (or even with only the former absent).
Another important note is that Scott's trick is not only useful to define cardinalities when lacking choice, but also to define any other equivalent relation over classes. Things such as ultraproducts of the universe, for example, rely heavily on this construction.
Best Answer
Abstractly, the cardinality of a set $X$ is an object $|X|$ such that given any two sets $X, Y$ the equality $| X | = | Y |$ holds iff $X \approx Y$ (there is a bijection between $X$ and $Y$). An object is called a cardinal if it is the cardinality of a set.
Now, some basic observations:
From these observations it follows that if to each well-orderable set $X$ we define its cardinality $|X|$ to be the least ordinal such that $X$ admits a well-ordering of order-type $\alpha$, then within the class $\mathbf{WO}$ of well-orderable sets we have that $| X | = |Y|$ iff $X \approx Y$.
Now, if AC holds, then every set can be well-ordered, and the above gives an appropriate definition of cardinality of a set.
However, if AC does not hold, then there is some set $X$ which cannot be well-ordered. How should we then assign a cardinality to $X$? Note that if we assign $|X|$ to be some ordinal $\alpha$, then the biconditional $$|X| = |Y| \Longleftrightarrow X \approx Y$$ must fail for some set $Y$, namely the set $\alpha$: As $X$ cannot be well-ordered, $X$ cannot be equipotent with any ordinal, in particular $\alpha$. It follows that the above scheme of defining the cardinality of a set to be some ordinal cannot be continued in a manner consistent with the desired properties of the assignment.