How much choice follows from the existence of derangement?

Question

We can show that every set has a derangement (that is, a bijection $f$ from itself to itself such that $f(x)\neq x$ for all $x$) if we assume the axiom of choice. In fact, the full axiom of choice is not necessary: if $|A+A|=|A|$ for all $A$, then we can find a derangement.

Moreover, some kind of axiom of choice is necessary to prove it. (According to the linked answer, $\mathsf{AC}_\kappa$ and $\mathsf{DC}_\kappa$ does not suffice to provide a derangement for any set.)

My question is: what kind of choice axioms follow from the existence of derangement for all sets? What I can show is the following simple fact:

If every set has a derangement, then either every set has a countably infinite subset or there is a set $A$ such that every derangement $f$ over $A$ satisfies $\forall x\in A\exists n<\omega: f^n(x)=x.$

(The proof is easy: if every set has an element which satsify $f^n(x)\neq x$ for all $n<\omega$, then it witnesses a countably infinite subset.)

This fact has a choice-related aspect (i.e. every infinite set has a countably infinite subset) but also has a counterweight for the choice (i.e. every derangement does not have an element of an infinite order w.r.t. $f$.) I wonder there is a known choice principle follows from the existence of derangement. I would appreciate your help!

Answer 1

Well. Not much is known.

As you said, the existence of derangements follows from $|A|+|A|=|A|$ for any infinite set $A$. This is a "strange axiom", in the sense that it does not follow from $\sf BPI$ (as witnessed by Cohen's model, where there is a Dedekind-finite set for which every permutation only moves finitely many points), nor from $\sf DC_\kappa$ (as witnessed by the fact that $\sf DC_\kappa$ is consistent with the existence of a strongly $\kappa^+$-amorphous set).

We also know that $|A|+|A|=|A|$ does not imply the axiom of choice, and in fact it does not even imply countable choice for countable sets of reals.

Okay, you say, so derangements follow from something which implies very very little choice. But maybe we can say something more intelligent? The problem is that the choice principles which are not related to either $\sf BPI$ or $\sf (AC/DC)_\kappa$ tend to be very hard to study. Our techniques are limited in constructing models with refined control over these sort of principles.

But maybe in the future we can develop some preservation theorems for these principles as well (compare to preservation theorems for $\sf BPI, DC_\kappa, AC_{WO}$, and the likes of these).

---

Here is a positive observation, though. If every set admits a derangement, then there are no strongly amorphous sets. The point, of course, is that a derangement, by looking at orbits, induces a partition of a set into non-singletons, and any infinite part must be countable.

But what if we want to talk about arbitrary amorphous set? Well, suppose that every amorphous set has a partition into pairs. Well, in that case, every amorphous set admits a derangement. Of course, by saying this we mean that there might be one part which is a singleton, but in that case we can add it into one of the pairs and simply rearrange that triplet "by hand".

So you see, it's not as obvious, what kind of proper choice principle we can obtain from this assumption.

Answer 2

One can generalize the fact you stated in the midde using other finiteness definitions:

If $A$ is infinite set with $f$ derangement then:

• If the cycles are not a partition of $A$, then $A$ is Dedekind infinite.

• If the cycles are a partition of $A$ and the size of the sets in the partition is unbounded then $\mathcal{P}(A)$ is Dedekind infinite.($Δ_4$-infinite by Truss notation)

• If they are a partition and the size of the elements of the partition are bounded then $A$ is not strictly amorphous.

---

You showed the first case, now if $P$ is the partition generated from the cycles, and $\{n∈ω\mid ∃x∈P(|x|=n)\}$ is indeed infinite, one can just take the function $g:ω→{\cal P}(A)$ to be $g(n)=\bigcup\{a⊆A\mid a\in P\mbox{ and }|a|=n\}$, then by removing $g^{-1}(0)$ from the domain we get that $ω<|\mathcal P(A)|$.

The definition of strictly amorphous is an amorphous set with gauge equal to $1$, in other words, for every partition of $A$ we have finitely many non-singeltons, which implies every bijection on $A$ will have a fixed point.

---

Note that it is possible for amorphuous set to have derangement, for example if it's gauge is $2$, then $A$ is weakly even(we can partition it to subsets of size 2), and just map each element in $A$ to the unique element that is with it in the partition.

And because $\kappa$ has derangement $⇒$ $\kappa+1$ has derangement(if there exists a cycle you can just modify a single cycle to include the new element, if there are no cycles just insert it in one of the $\Bbb Z$-chains), we must have that weakly odd sets also have a derangement.

I think that it is consistent that there exists amorphous set and that all amorphous sets are either weakly even or weakly odd(please correct me if I am wrong), in that case it is consistent that all amorphuous sets has derangement.

It is also consistent that there exists an infinite Dedekind finite set and that the class of Dedekind finite cardinals is linearly order, a consequences of that is that the class of Dedekind finite cardinals is a model of arithmetic(if someone has reference to this I would love to get it), and so every Dedekind finite cardinal is either odd or even, so it is either weakly odd or weakly even, hence it is consistent that all Dedekind finite cardinals have a derangement.