In set theory, if we do not assume the Axiom of Choice, we cannot prove the Trichotomy Law between cardinals. That is, we cannot prove that for any two sets, there exists an injection from one to the other. But this raises the question: what is an example of a pair of sets between which there does not exist an injection?
[Math] an example of two sets which cannot be compared
axiom-of-choicecardinalselementary-set-theory
Related Solutions
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.
Under the axiom of choice, for any two infinite cardinal numbers, their sum, which corresponds to their disjoint union, is simply the maximum of the two numbers. This is a standard fact of cardinal arithmetic you can find in every set theory book.
So if $S$ is uncountable with cardinal $\alpha$, we have $\alpha+\alpha=\alpha$. So their exists two disjoint copies $S_1, S_2$ of $S$ such that their union has the same cardinality as $S$. So there is a bijection $f:S_1\cup S_2\to S$. So $f(S_1)$ and $f(S_2)$ are two disjoint uncountable subsets of $S$.
Here is an actual method to "construct" a bijection from $S$ to $S\times\{0,1\}$. Let $\mathcal{F}$ be the family of all bijections of some subset $T$ of $S$ to $T\times\{0,1\}$. Such a bijection always exists when $T$ is a countably infinite subset. Order these functions by set inclusion on their graph. Then the conditions of Zorn's Lemma are satisfied, and their exists a maximal such function of the form $f:T\to T\times\{0,1\}$. If $S\backslash T$ would be infinite, it would contain a countable subset and then we could extend $f$ to a larger such function in contradiction to it being maximal. So $S\backslash T$ must be finite. So there is a bijection $g:\{0,1,\ldots,n-1\}\to S\backslash T\times\{0,1\}$. Let $C=\{x_0,x_1,\ldots\}\subseteq S$ be countably infinite. You can construct now a new bijection $f':S\to S\times\{0,1\}$ by $$f'(x) = \begin{cases} g(m) &\mbox{if } x_m\in\{x_0,\ldots,x_{n-1}\}\subseteq C\\ f(x_{m-n}) & \mbox{if } x_m\in C\text{ and }m\geq n.\\ f(x) &\mbox{otherwise.}\end{cases} $$
The proof is essentially from Halmos little set theory book.
Best Answer
If we could give an explicit example of sets for which we could prove the non-existence of such injections, the axiom of choice would be false. However, there are models of $\mathsf{ZF}$ without the axiom of choice in which there are Dedekind finite sets that are not finite. If $X$ is such a set, there is no injection from $X$ to $\Bbb N$ or from $\Bbb N$ to $X$.
Specifically, $X$ has the property that there is no injection from $X$ properly into $X$. This is easily shown to be equivalent to the property that there is no injection from $\Bbb N$ to $X$. If there were an injection $f:X\to\Bbb N$, the fact that $X$ is not finite means that $f[X]$ would be an infinite subset of $\Bbb N$, and it would then be a straightforward matter recursively to construct a bijection from $\Bbb N$ to $X$. Since $X$ is Dedekind finite, no such bijection exists.