6
$\begingroup$

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.

  • 0
    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\}$”?2012-12-03
  • 0
    @PeterLeFanuLumsdaine Yes.2012-12-03

2 Answers 2

4

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

  • 0
    What is an enumerated union and why is it in bold face? And how do you finish the proof?2012-12-03
  • 0
    What do you map $n$ to?2012-12-03
  • 0
    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$.2012-12-03
  • 0
    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$.2012-12-03
  • 0
    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.2012-12-03
  • 0
    Regarding your last paragraph: No, actually. If you read my question you will notice that I want to prove _countable_ recursive construction. And I'm sure that's possible using countable choice.2012-12-04
  • 0
    What is the **countable** recursive construction? And why do you think you can prove it using countable choice?2012-12-04
4

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.

  • 0
    Where does the contradiction comes in? Did you mean contrapositive? This is not contrapositive either. This is a direct proof...2012-12-03
  • 0
    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?2012-12-03
  • 1
    You constructivists and your crazy avoidance from negations. :-)2012-12-03
  • 2
    (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.)2012-12-03
  • 0
    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.2018-09-04
  • 0
    @LeAnhDung: No, my argument doesn’t require Dependent Choice/PGRC. DC/PGRC is required for defining a function recursively if, at the successor stage, all you know in advance is that there exists *some* possible “next value” satisfying the desired property (i.e. lying in the function $G^*$, in the statement from the OP). Recursively defining a function on $\omega$ whose value is *uniquely* specified at each stage (as in my construction of $f_\omega$ from the sequence of injections $f_n$) does not require DC/PGRC. The only place my answer uses any choice is in picking the sequence $f_n$.2018-09-04
  • 0
    There are various versions of Recursion Theorem. Could you please mention explicitly which version you are using to construct $f_\omega : \omega \to X$? From your above explanation, I understood that your construction does not appeal to any form of Axiom of Choice, but I found hard to find your versions of Recursion Theorem.2018-09-05
  • 0
    I didn’t have any particular from in mind — there are lots that suffice. E.g. “Suppose you have a set $P$, some $p_0 \in P$, and a function $h : \mathbb{N} \times P \to P$. Then there’s a unique function $g : \mathbb{N} \to P$ such that $g(0)=p_0$ and for each $n$, $g(n+1)=h(n,g(n))$.” The proof of this is a direct induction, needing no choice. Then my answer applies it with $P$ being the set of all injections from any initial segment of $\mathbb{N}$ to $X$, $p_0$ the empty function, and $h(n,k)$ as the extension of $k$ using $f_n$, if possible, or otherwise $k$.2018-09-06