# In ZF, can a Dedekind-finite set (or even an amorphous set) be smaller than a non-trivial partition of its elements

axiom-of-choiceset-theory

For context: A set is amorphous if every subset of it is either finite or cofinite but not both (in particular is infinite). A set is D(edekind)-finite if every injection into itself is a surjection. One can easily that $$X$$ is D-finite iff $$\omega \preceq X$$, an thus, that an amorphous set must be an infinite D-finite set. (Finite here means in bijection with some $$n < \omega$$).

Question 1: Is it possible to have a D-finite set $$X$$ and nontrivial (i.e different from $$\{\{x\} : x \in X\}$$) partition $$\Pi$$ such that $$X \preceq \Pi$$? (Clearly $$X$$ can't be finite)

Of course, in presence of the axiom of choice this is not possible, since if we have
an injective function $$f : X \to \Pi$$, then, if $$g : \Pi \to X$$ is a choice function we get
that $$g \circ f$$ is an injective function, and thus since $$X$$ is D-finite, a surjection also. Concluding that $$\Pi$$ must be trivial. We also conclude of this that $$\Pi$$ must have infinite non-singleton elements.

Question 2: Can $$X$$ be amorphous?

One can prove that for an amorphous set $$A$$ and a partition $$\Pi$$ of $$A$$ into finite sets there must exist a unique $$n \in \omega$$ such that all but finitely many elements in $$\Pi$$ are of size $$n(\Pi)$$. $$A$$ is called bounded amorphous if $$n(\Pi)$$ is bounded over the possible partitions, otherwise is called unbounded. It is called strictly amorphous if $$n(\Pi) = 1$$ for all such partitions. See for example Wikipedia's entry, or Truss's paper "The structure of amorphous sets" for more on this.

Question 3: Can $$X$$ be bounded amorphous?

I've proved that $$X$$ can't be strictly amorphous, but not much more.

Edit: I think the answer to 1 is a "yes": I've realized that the existence of such partition (assuming X D-finite) is equivalent to the existence of a surjective $$f : X \to X$$ which is not injective. And I think is known that there are D-finite sets with non-injective surjections into itself.

Yes, no, and consequently also no.

The first one is actually a theorem: if there is an infinite Dedekind-finite set, then there is one which can be mapped onto a strictly larger set. That means that the surjection defines the partition you are looking for.

Suppose that $$A$$ is Dedekind-finite, then $$S_{inj}(A)$$, which is the set of all injective finite sequences from $$A$$, is also Dedekind-finite. For if it wasn't, then we would have a countably infinite set of enumerated finite sets, and their union is therefore a countably infinite subset of $$A$$, and that is impossible.

Now take, for example $$S_{inj}(A)$$ without the empty sequence. Then the function erasing the first coordinate from each non-empty sequence is surjective onto $$S_{inj}(A)$$. Indeed, taking any subset which contains "all sequences of length $$n\in I$$" for some fixed infinite $$I\subseteq\omega$$ will work in a similar way.

For the second question, note that if $$A$$ is amorphous and $$f\colon A\to X$$ is surjective, then $$X$$ must be amorphous (or finite, if you'd like to require that amorphous implies infinite). For otherwise, simply partition $$X$$ into two infinite subsets and look at their preimages, both would have to be infinite subsets of $$A$$ which are disjoint.

How does that help us? Well, if $$X$$ is infinite, then the preimage of each point is finite. Now, starting with some $$x\in X\setminus A$$, consider $$f^{-1}(x)=A_0$$, then $$f^{-1}(A_0)=A_1$$ is also finite, and it must be distinct from $$A_0$$, and then we can continue by recursion and define a countably family of finite subsets of $$A$$. But this is impossible as the power set of an amorphous set is itself Dedekind-finite.

Note, however, that if $$X$$ is amorphous, its partitions are either finite; almost all singletons; or incomparable with $$X$$ itself. So we can get a partition that is incomparable, just not a partition that is strictly bigger.