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:

enter image description here

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:

enter image description here

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

enter image description here

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?

Thanks for your help.

  • $\begingroup$ 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\}$”? $\endgroup$ Dec 3, 2012 at 17:53
  • $\begingroup$ @PeterLeFanuLumsdaine Yes. $\endgroup$ Dec 3, 2012 at 18:30

2 Answers 2


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.)

  • $\begingroup$ What is an enumerated union and why is it in bold face? And how do you finish the proof? $\endgroup$ Dec 3, 2012 at 20:20
  • $\begingroup$ What do you map $n$ to? $\endgroup$ Dec 3, 2012 at 20:21
  • $\begingroup$ 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$. $\endgroup$
    – Asaf Karagila
    Dec 3, 2012 at 20:25
  • $\begingroup$ 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$. $\endgroup$ Dec 3, 2012 at 20:35
  • $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Dec 3, 2012 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.

  • $\begingroup$ Where does the contradiction comes in? Did you mean contrapositive? This is not contrapositive either. This is a direct proof... $\endgroup$
    – Asaf Karagila
    Dec 3, 2012 at 18:02
  • $\begingroup$ 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? $\endgroup$ Dec 3, 2012 at 18:05
  • 1
    $\begingroup$ You constructivists and your crazy avoidance from negations. :-) $\endgroup$
    – Asaf Karagila
    Dec 3, 2012 at 18:07
  • 2
    $\begingroup$ (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.) $\endgroup$ Dec 3, 2012 at 18:11
  • $\begingroup$ 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. $\endgroup$
    – Akira
    Sep 4, 2018 at 4:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .