# Proving Dedekind finite implies finite assuming countable choice

I'd like to show that if a set $X$ is Dedekind finite then is is finite if we assume $(AC)_{\aleph_0}$. As set $X$ is called Dedekind finite if the following equivalent conditions are satisfied: (a) there is no injection $\omega \hookrightarrow X$ (b) every injection $X \to X$ is also a surjection.

Countable choice $(AC)_{\aleph_0}$ says that every contable family of non-empty, pairwise disjoint sets has a choice function.

There is the following theorem:

from which I can prove what I want as follows: Pick an $x_0 \in X$. Define $G(F(0), \dots, F(n-1)) = \{x_0\}$ if $x_0 \notin \bigcup F(k)$ and $G(F(0), \dots , F(n-1)) = X \setminus \bigcup F(k)$ otherwise. Also, $G(\varnothing) = \{x_0\}$. Let $F: \omega \to X$ be as in the theorem. Then $F$ is injective by construction.

The problem with that is that I suspect that the proof of theorem 24 needs countable choice. So what I am after is the following: consider the generalisation of theorem 24:

(note the typo in $(R^\ast)$, it should be $F(z) \in G^\ast (F \mid I(z), z)$), and its proof (assuming AC):

I want to modify this proof to prove the countable version of the theorem. But I can't seem to manage. I need a countable set $\{G^\ast \mid \{\langle f,z \rangle \} : \langle f,z \rangle \in dom(G^\ast) \}$. Ideas I had were along the lines of picking $f_0(x) = x_0$ the constant function and then to consider $\{G^\ast \mid \{\langle f_0,n \rangle \} : \langle f_0,n \rangle \in dom(G^\ast) \}$ but what then?

• For the statement “Dedekind finite implies finite”, what definition of “finite” are you using? “$X$ is finite if for some $n$, $X$ has a bijection with $\{1 \ldots n\}$”? – Peter LeFanu Lumsdaine Dec 3 '12 at 17:53
• @PeterLeFanuLumsdaine Yes. – Rudy the Reindeer Dec 3 '12 at 18:30

Let $X$ be an infinite set. For $n\in\omega$ let $$A_n=\{\langle a_0,\ldots,a_{n-1}\rangle\mid\forall i: a_i\in X\land\forall i,j: i\neq j\implies a_i\neq a_j\}$$ Because $X$ is infinite every $A_n$ is non-empty.

Use countable choice to choose $f_n\in A_n$. Now show that the union of the ranges of the $f_n$ is an enumerated union which is therefore well-ordered. This union cannot be finite, otherwise there would be some $f_k$ in which appears an element not in the union. Therefore it is countably infinite, as wanted.

Note that generally the principle of recursive construction is in fact stronger than countable choice and it is equivalent to the principle of Dependent Choice. (In fact this appears in the paragraph after the exercise you are trying to solve.)

• What is an enumerated union and why is it in bold face? And how do you finish the proof? – Rudy the Reindeer Dec 3 '12 at 20:20
• What do you map $n$ to? – Rudy the Reindeer Dec 3 '12 at 20:21
• Enumerated union is the union of sets where their enumeration is also given to you. It is in bold so you can't miss it. You should finish the proof by showing this is a countably infinite subset of $X$. – Asaf Karagila Dec 3 '12 at 20:25
• Ok, let's try this: $f: \omega \to \{f_n\}_{n \in \omega}, n \mapsto f_n$ and $f_n : A_n \to X$ ($f_n \in A_n$). Then take $g: \omega \to \omega \times \omega$ be a bijection and define $F: \omega \to X, n \mapsto f(g(n)_0)(g(n)_1)$. Then $F$ is an injection from $\omega \to X$. – Rudy the Reindeer Dec 3 '12 at 20:35
• No, $f_n\in A_n$, and $f_n\colon n\to X$. But aside for that point, almost. Note that each $f_n$ only counts a finite number of elements, and the same elements may appear more than once. However you can show that $F(n)=f_{g(n)_0}(g(n)_1)$ (whenever defined, and some fixed value otherwise) is a surjection from $\omega$ onto an infinite subset of $X$. Surjections from well-ordered domains can be reversed and therefore there $X$ has a countably infinite subset. – Asaf Karagila Dec 3 '12 at 20:42

To answer your first question (Dedekind finite implies finite), not your second (principle of generalised recursive constructions): we prove the contrapositive, showing that infinite implies Dedekind-infinite.

Suppose $X$ is infinite, i.e. has no bijection with $\{1 \ldots n \}$, for any $n \in \omega$. Then by induction on $n$, there exists for each $n \in \omega$ some injection $f : \{1 \ldots n\} \to X$.

By countable choice, choose for each $n$ some such injection $f_n$. Now define an injection $f_\omega : \omega \to X$ by taking $f_\omega(n)$ to be $f_n(i)$, for the least $i$ such that $f_n(i)$ has not perviously appeared as a value of $f_\omega(n)$.

This gives an injection $\omega \to X$, showing that $X$ is Dedekind-infinite, as desired.

• Where does the contradiction comes in? Did you mean contrapositive? This is not contrapositive either. This is a direct proof... – Asaf Karagila Dec 3 '12 at 18:02
• You’re right, I should have said contrapositive (I’ve been working in constructive maths too long; classical proofs no longer feel like a native language to me). But this is surely the contrapositive of the statement OP originally asked for, isn’t it? – Peter LeFanu Lumsdaine Dec 3 '12 at 18:05
• You constructivists and your crazy avoidance from negations. :-) – Asaf Karagila Dec 3 '12 at 18:07
• (As a logical note, though: in general, the principle “any implication is equivalent to its contrapositive” is equivalent to the principle of proof by contradiction, even over a very minimal logical background; hence why I tend to forget to distinguish between them.) – Peter LeFanu Lumsdaine Dec 3 '12 at 18:11
• Please correct me if i'm wrong. 1. Your injection $f_\omega : \omega \to X$ is constructed on the basis of Principle of Generalized Recursive Construction (Theorem 5 in the picture in the OP's post) in the sense that $f_\omega(n)$ depends on $f_\omega(1),f_\omega(2),\cdots,f_\omega(n-1)$? 2. Principle of Generalized Recursive Construction (Theorem 5 in the picture in the OP's post) is in fact equivalent to Axiom of Dependent Choice. – Le Anh Dung Sep 4 '18 at 4:23