Equivalent definitions of Dedekind-finite sets

axiom-of-choiceset-theory

Definition 1. A set $A$ will be called Dedekind-finite if every injection $f:A\hookrightarrow A$ is a bijection; otherwise, $A$ is called Dedekind-infinite.

Definition 2. set $A$ is called ${}^*$–Dedekind-finite if every surjection $f:A\twoheadrightarrow A$ is a bijection; otherwise, $A$ is called ${}^*$–Dedekind-infinite.

Question. Are these two definitions equivalent (in $\mathsf{ZF}$)?

Also, I am trying to prove part 5 of the following equivalents of a Dedekind-infinite set:

Proposition 3. The following conditions are equivalent for a set $A$:

  1. $A$ is Dedekind-infinite.
  2. $A$ admits a proper subset $B\subsetneq A$ with the same cardinality, $A\approx B$.
  3. $\aleph_0 \le A$, that is, there exists an injection $f:\Bbb{N}\hookrightarrow A$.
  4. $A$ is $1$-absorbing, that is, $A\approx A\cup \{x\}$ for every set $x$.
  5. There exists a set $B$ with $A\approx B$, but $A\setminus B \not\approx B \setminus A$.

Proof of 1-4.

$(1\Longrightarrow 2)$ Let $f:A\hookrightarrow A$ be injective and not surjective, so $B=f[A]$ is a proper subset with $A\approx B$.

$(2\Longrightarrow 3)$ Let $f:A\to B$ be a bijection to a proper subset $B$, and let $x\in A \setminus B$. Then $F:\Bbb{N}\to A, n\mapsto f^{(n+1)} (x) $ is injective by simple induction.

$(3\Longrightarrow 4)$ Let $D\subseteq A$ be a countable subset. Then for any $x\notin A$ there exists a bijection $g:D\to D\cup \{x\}$, so $f=g\cup \operatorname{id}_{A\setminus D}:A\to A\cup \{x\}$ is a bijection.

$(4\Longrightarrow 1)$ Let $x\notin A$, so there exists a bijection $f:A\cup \{x\} \to A$. So the restriction $f\restriction A : A\to A\setminus \{f(x)\}$ is injective but not a bijection. $\square$

Best Answer

The two definitions are certainly not equivalent.

Suppose that $A$ is any infinite Dedekind-finite set. Let $S$ be the set of finite injective sequences from $A$, namely, all the injective functions from a natural number into $A$.

Claim. $S$ is Dedekind-finite.

Proof. Suppose not, then we have a countably infinite subset of sequences, $f_n$ for $n<\omega$, and without loss of generality $f_n\neq\varnothing$ for all $n<\omega$ as well, otherwise just omit that one empty function. Define the following function by recursion $F(0)=f_0(0)$; $F(n+1)=f_n(k)$ where $n$ is the least such that for some $k\in\operatorname{dom}(f_n)$, $F(i)\neq f_n(k)$ for all $i\leq n$. This is well-defined since the first $n$ functions enumerated only a finite union of finite sets, and there are only finitely many injections from a finite ordinal into a finite set, so there will be some $n$ and $k$.

In other words, go through the functions in order, and along their domains, in order, and when you find a new element you've not encountered before, add it to your list.

Easily, $F$ is injective and with domain $\omega$. So $A$ must be Dedekind-infinite, which is a contradiction. So, indeed, $S$ is Dedekind-finite. $\square$

Claim. There is a surjection from $S$ onto itself which is not a bijection.

Proof. Let $f\in S$, if $f=\varnothing$, then $f\mapsto f$; otherwise, the domain of $f$ is some $n+1$, simply define $f\mapsto f\restriction n$. In other words, remove the last point from each sequence, if such point exists.

Easily, this function is a surjection, and it is certainly not a bijection since any $1$-tuple is mapped to the empty function, as well as the empty function itself.

So, what we have shown is that if there is any kind of Dedekind-finite set, then there is one which is $*$-Dedekind-infinite.

To your second question, since you've proved the equivalences of all the others, let me use that.

Assuming (2), or equivalently (4), we can take either $B$ to be a proper subset of $A$ of the same cardinality, or $A=\cup\{x\}$ for some $x\notin A$. So we get the case that $B\subsetneq A$ or $A\subsetneq B$, respectively. In both cases, exactly one of $A\setminus B$ and $B\setminus A$ is empty.

So (1)–(4) all imply (5).

In the other direction, assume that there is no bijection between $A\setminus B$ and $B\setminus A$ and let $f\colon A\to B$ be a bijection.

Then we know that either there is some $a\in A\setminus B$ such that $f(a)\in A\cap B$ or there is some $b\in B\setminus A$ such that $f^{-1}(b)\in A$. Since otherwise, $f\restriction A\setminus B\to B\setminus A$ would have been a bijection.

Let's consider all the images and preimages of points in $A$ that are in $A$; and let's do the same for those in $B$ (by $f^{-1}$). So given a point $a\in A$, if $f(a)\in A$, or $f^{-1}(a)\in A$, we will chart that course. Once we've hit $B\setminus A$ or $A\setminus B$, we stop. Now let's consider our cases.

  1. There is some $a\in A$ with an infinite orbit. In this case, we have (3) holds, so $A$ is Dedekind-infinite.

  2. There are no infinite orbits. But if $a\in A\setminus B$ or $b\in B\setminus A$, then the orbits of $a$ and $b$ must not only be finite, but linear and satisfy these two properties:

    1. If $f^n(a)$ is the last point in the orbit, then $f^{n+1}(a)\in B\setminus A$. Otherwise, we can continue and apply $f$ for longer.

    2. If $a\notin A\setminus B$, then it is the only point in that orbit satisfying that property. Because $f\colon A\to B$, it is impossible for a point in $A\setminus B$ to be in the image of $f$.

    The two properties have versions for $b\in B\setminus A$, of course. However, what it means is that we can identify for each $a\in A\setminus B$, some $b\in B\setminus A$ which is uniquely determined by some finitely many applications of $f$. In other words, $f$ determines an injection from $A\setminus B$ into $B\setminus A$, and likewise $f^{-1}$ determines an injection in the other direction. By Cantor–Bernstein, this means that $A\setminus B$ and $B\setminus A$ have the same cardinality.

Therefore, either $A$ is Dedekind-infinite, or $A\setminus B$ and $B\setminus A$ have the same cardinality. Since we assumed the latter failed, it must be that the former holds. $\square$

Related Question