Question on Dually Dedekind-infinite sets

I got an email a few days ago from Lucas Polymeris, a Chilean student, who asked me a very nice question. I want to go through the journey I took from that question to the answer.

Before we get to the question, let's review some definitions.

• We say that a set \(A\) is Dedekind-finite if every injective \(f\colon A\to A\) is also surjective.
  Otherwise, we call \(A\) Dedekind-infinite.
• We say that a set \(A\) is dually Dedekind-finite if every surjective \(f\colon A\to A\) is also injective.
  Otherwise, we call \(A\) dually Dedekind-infinite.
• We say that a function \(f\colon A\to B\) is finite-to-one if for all \(b\in B\), \(f^{-1}(b)\) is finite.
  No otherwise here.

Now. Lucas asked me the following, very natural question (rephrased from his original phrasing):

Suppose that \(A\) is a set such that any surjective \(f\colon A\to A\) is finite-to-one, must \(A\) be dually Dedekind-finite? (Note that it must be Dedekind-finite, at the very least.)

This seems like it should be false. Namely, there can be a dually Dedekind-infinite set \(A\) such that all of its self-surjections are finite-to-one. But in fact, the answer to the question is positive. Instead of immediately revealing how we got to this positive answer, I want to take you on the journey that I had to go in order to find that out. Because the knee-jerk reaction is always to say that if something can fail, then it will fail.

So, we started with "there should be a dually Dedekind-infinite with such property". What are the obvious examples? Well, let's start with the Russell set, namely, a Dedekind-finite set which is a countable union of pairs. Well, this Dedekind-finite set certainly maps onto \(\omega\), alas in the case of dually Dedekind-finiteness, this is not enough (recall that in the case of Dedekind-finiteness, \(A\) is Dedekind-infinite if and only if \(\omega\) injects into \(A\)).

Indeed, if \(R=\bigcup_{n<\omega}R_n\) is a Russell set, \(f\colon R\to R\) is surjective, then for all but finitely many pairs, \(f\) must behave the same on each pair, namely \(f''R_n\subseteq R_m\), for some \(m\). If this is not the case, then we can choose from \(R_n\) the point that was sent to the lower-indexed pair. Moreover, for all but finitely many pairs we actually must have \(f''R_n=R_m\), otherwise we can choose from \(R_m\) the one whose preimages start from a lower point. So in reality, \(f\) must be injective on all but finitely many pairs, and so it must be injective, since the finite remainder is, well, finite.

So, Russell sets are no good. But you know what works well? Trees. Because if we have a finitely-splitting tree, then we can map each point to its predecessor, and the root to itself, and this will be a finite-to-one surjection. But where do we find such finitely-splitting trees that are themselves Dedekind-finite? Well, the choice-tree for a Russell set is one such example. Namely, \(T=\bigcup_{n<\omega}\prod_{k < n}R_k\) ordered by inclusion, is the tree approximating a choice function. Or even more directly, consider the structure of the binary tree with finite supports. At first glance, it seems that the only functions we get are indeed just those mapping a point to its predecessor, or some finite combination of those.

Alas, this won't do. Because the tree levels are definable. Since the height of the tree is just \(\omega\). So we can be clever, map all the even levels to the root, and "compress" the odd levels to the least predecessor not yet in the image. Formally, if you allow me to think about the elements of the tree as finite sequences ordered by end-extension, then we get \[f(s)=\begin{cases}\varnothing && |s|=2n\\ s\restriction n && |s|=2n+1\end{cases}\] as our function. It is certainly surjective, and the root will have infinitely many preimages.

So, using a selection tree of a Russell set won't work. Indeed any tree is going to fail us. So maybe we can understand from this failure how to get the right answer? Well. If \(f\colon A\to A\) is surjective but not injective, pick a point \(a_0\in A\) whose preimage is non-trivial, and define recursively, \(A_0=\{a_0\}\), and \(A_{n+1}=f^{-1}(A_n)\setminus A_n\). This gives us a sequence of sets, perhaps finite, if \(f\) was finite-to-one, but it defines a tree of height \(\omega\), and we know how to create non finite-to-one surjections when we have a tree of height \(\omega\).

And indeed, this is the answer. Originally phrased as a proof by contradiction, but now, as Lucas noted, phrased in a direct implication. If we have any non-injective surjection \(f\colon A\to A\), then there is one which is not finite-to-one. And so, if \(A\) is such that any \(f\colon A\to A\) is finite-to-one, it must be that \(A\) is dually Dedekind-finite.

I hope this journey was interesting to you, it was certainly interesting to me. I think it's a fun example of how mathematicians will often think about something. And how the knee-jerk reaction of someone with semi-decent intuition might not be the right one, but exploring it further will lead to some beautiful mathematics.