Let $X,Y$ be the collections of all finite subsets of $A$ and $B$ respectively. Assume $|X| \le |Y|$. Is it true that $|A| \le |B|$?

Question

In proving the dimension of infinite-dimensional vector space is well-defined, I come across below question.

Let $A,B$ be sets. Let $X,Y$ be the collections of all finite subsets of $A$ and $B$ respectively. Assume $|X| \le |Y|$ and axiom of choice. Is it true that $|A| \le |B|$?

Could you elaborate on this issue?

Answer 1

If $A$ and $B$ are finite, then this $X$ and $Y$ are just their respective power sets, and for finite sets power sets are injectively increasing. Likewise if $A$ is finite and $B$ is not, then it's even more trivial.

For infinite sets, assuming the axiom of choice, we have that $|X|=|A|$ and $|Y|=|B|$, so this is easy. This can be seen, relatively straightforward, by proving that $|A|=|A\times A|$, so by induction $|A|=|A^n|$ for any finite $n>0$, therefore $A$ and all the finite sequences from $A$ have the same cardinality, and the latter clearly maps onto $X$, which completes the proof.

But without the axiom of choice, well, this isn't quite true anymore. Suppose that $\{P_n\mid n<\omega\}$ is a countable sequence of pairwise disjoint pairs such that there is choice function from any infinitely many pairs. Let $A=\bigcup P_n$ and let $B=A\setminus P_0$. By the above property, $A$ is a Dedekind-finite set, and so $B$ is strictly smaller. We can also assume, without the loss of generality, that $P_0$ just happened to be $\{0,1\}$ (or we can replace it by that one pair if needed).

Now, given any $A_0$ finite subset of $A$, let $n$ be $\max\{k+1\mid P_k\cap A_0\neq\varnothing\}$. We define $B_0$ as follows:

1. If $n=1$, namely $A_0=\varnothing$, then take $B_0=\varnothing$;
2. If $n>1$, then $A_0\neq\varnothing$ and we define $B_0=A_0\cap B\cup P_k$ where $k$ is defined as follows:
   • if $A_0\cap P_0=\{0\}$, then $k=4n$,
   • if $A_0\cap P_0=\{1\}$, then $k=4n+1$,
   • if $A_0\cap P_0=\{0,1\}$, then $k=4n+2$,
   • if $A_0\cap P_0=\varnothing$, then $k=4n+3$.

The map is injective, since if $A_0\neq A_1$, we have the following possibilities:

1. Exactly one of the two is empty, in which case exactly one of $B_0$ and $B_1$ is empty.
2. Both are non-empty, and $n_0\neq n_1$, in which case we have that $k_0\neq k_1$, and so $B_0\neq B_1$.
3. Both are non-empty, but $n_0=n_1$ and $A_0\cap B=A_1\cap B$, in which case $k_0\neq k_1$, since $A_0\cap P_0\neq A_1\cap P_0$, otherwise the two sets are empty.
4. Both are non-empty, $n_0=n_1$ and $A_0\cap B\neq A_1\cap B$, in which case we can detect the difference already in that part of $B_0$ and $B_1$.

So, we have that $|X|\leq|Y|$, and indeed we have equality there, but $|B|<|A|$.