Some questions about the Exercise $3.15$ in Jech Set Theory and the Axiom of Choice.

Question

I have $3$ questions about the following exercise in Jech Set Theory (Exercise $3.15$ ($ii$)):

Show that the set of all finite one-to-one sequences in a Dedekind-finite set is Dedekind-finite.

Part of my solution:

Assume that it is Dedekind-infinite. Then, it has a countable subset. Call it $S = \{S_i \mid i<\omega\}$, where $S_i$'s are finite one-to-one sequences. Now, let $s = \bigcup_{i<\omega} \operatorname{ran}(S_{i})$. It is easy to show that $s$ is not finite, so it is infinite. My first question is: Can I now say directly that $s$ is countably infinite without the Axiom of Choice? If this is valid, then we would arrive at a contradiction since it is a subset of the original set.

In case this cannot be said without the Axiom of Choice, I have thought about the following:

For $a \in s$, let $n(a)$ be the least finite ordinal $i$ such that $a \in \operatorname{ran}(S_{i})$. Now, define the ordering $\prec$ on $s$ by:

$$(a \prec b) \ \ \ \text{iff} \ \ \ ((n(a) < n(b)) \ \ \ \text{or} \ \ \ (n(a) = n(b) \ \ \ \text{and} \ \ \ \text{$a$'s index is less than $b$'s index in the common range}))$$

Now, since this is a well-order on $s$, and $s$ is infinite, we can form a countable subset of $s$ by:

$$a_0 = \text{the least element of $s$}$$ $$a_{n+1} = \text{the least element of $s \setminus \{a_1, \ldots, a_n \}$}$$

My second question is: Is this approach correct?

Finally, my last question is a follow up to this exercise: What if the question asked the same thing but with Dedekind-finite sequences? Can we prove it in that case without the Axiom of Choice? Thank you.

Answer 1

No, you can't say that a countable union of finite sets is countable without appealing to the axiom of choice. The second approach is indeed correct.

For the Dedekind-finite sequences, that's a very nice question, and that is more intricate. Of course you mean injective sequences, otherwise just the finite sequences are already Dedekind-infinite (fix $a$ and consider $s_n$ to be the sequence which is just $n$ times $a$).

But now comes the question, what exactly do we mean by that.

1. Do we mean just injective functions from a subset of $X$ to $X$? In that case, there's no reason to expect that the result is Dedekind-finite. For example, if $X$ can be mapped onto $\omega$, i.e. it has a Dedekind-infinite power set, then we can simply pick countable many subsets and consider the identity function. But note that it is certainly possible that those countably many subsets are indeed finite, which is now in contradiction with what you just proved.

2. Do we mean injective functions from cardinals of subsets of $X$ to $X$? That's not always a possible definition. If $X$ is amorphous, then every subset is finite or co-finite, but we cannot choose a representative for each infinite cardinal, since that would allow us to define a surjection from $X$ onto $\omega$ (take the complements, these are finite, now map each element in $X$ to the least index of a finite set in which it appears, or $0$ otherwise; easily this map has an infinite range).

So we are in a situation where "the right definition" is not obvious at all. So there's no good answer, other than "it's complicated and it depends on both $X$ and on what exactly you mean by that".