On surjections, idempotence and axiom of choice

Question

The following assertion is trivial in ZFC, or even in much weaker theories. Is it also true in ZF?

(I couldn't find it in the Consequences site so far.)

If $A$ is an infinite set such that $A$ can be mapped onto $A\times 2$ then $|A\times 2|=|A|$

The problem is that we cannot necessarily choose from every fiber of $f$, so we cannot construct an injection from $A$ to $f^{-1}(A\times\lbrace 0\rbrace)$, which will prove the assertion.

While I'm on the topic, is it possible for a D-finite set to have such property? It is possible for a D-finite set to be surjected onto a larger set than itself, but what about that large?

Answer 1

The answer is no.

First, I argue that it is consistent with ZF that a Dedekind finite set $A$ can map onto $A\times 2$, and much more.

To see this, begin with any infinite Dedekind finite set $B\subset 2^\omega$, which is furthermore dense in the sense that any finite binary sequence has extensions in $B$. It is consistent with ZF that such a dense set $B$ exists, since in fact the usual symmetric-model arguments produce infinite Dedekind-finite sets that are dense.

Let $A$ consist of the finite non-repeating sequences from $B$. Note that $A$ is still Dedekind finite, since any countably infinite subset of $A$ can be used to produce a countably infinite subset of $B$. Moreover, I claim that $A$ surjects onto $A\times 2$ and indeed, onto $A^{{\lt}\omega}$.

To see that $A$ surjects onto $A\times 2$, given $a=\langle b_0,\ldots,b_n\rangle\in A$, let $j$ be the first bit of $b_0$ and define $f(a)=(\langle b_1,\ldots,b_n\rangle,j)$. This is onto, since given any $(\langle b_1,\ldots,b_n\rangle,j)$, we just adjoin $b_0$ starting with digit $j$ to form $a=\langle b_0,\ldots b_n\rangle$, which maps to the original pair.

For fun, let me show somewhat more, namely, that $A$ actually surjects onto $A^{{\lt}\omega}$. I shall define a function $f:A\to A^{{\lt}\omega}$ as follows. Suppose that we are given $a=\langle b_0,\ldots,b_n\rangle\in A$. In order to define $f(a)$, we look at a certain finite initial segment of $b_0$, which we take to code a number $k$ and maps $\pi_i:n_i\to n$ for $i\lt k$. This can be coded in some canonical way, whose details are not important. (For example, perhaps $b_0$ starts with $k$ many $0$s, and after this there are $k$ blocks of $1$s, with the $i^{th}$ block of length $n_i$, and after this the bits are given to define the maps $\pi_i:n_i\to n$.) We use these maps to assemble $f(a)$ from the rest of the reals $b_1,\ldots,b_n$. Specifically, let $f(a)=\langle \vec x_0,\ldots,\vec x_k\rangle\in A$, where $\vec x_i=\langle b_{\pi_i(0)},\ldots,b_{\pi_i(n_i-1)}\rangle$. That is, each $\vec x_i$ enumerates a subset of $b_1,\ldots b_n$ in the order specified by $\pi_i$. In summary, a finite part of $b_0$ tells us how to assemble $f(a)$ according to a definite procedure from the other reals $b_1,\ldots,b_n$ appearing in $a$. (And if $b_0$ happens not to code things correctly, then we default to some constant value.) This defines $f:A\to A^{{\lt}\omega}$ without using the axiom of choice. Furthermore, the map is surjective, since for any finite sequence of injective tuples $\langle \vec x_0,\dots,\vec x_k\rangle$ from $B$, we may consider the reals appearing in those tuples and enumerate them $b_1,\ldots,b_n$, deleting repetitions, and then assemble a suitable $b_0$, using the fact that $B$ is dense in order to know that our desired collection of maps $\pi_i$ for $i\lt k$, which is coded by some finite binary sequence, can be extended to an element $b_0\in B$. It follows that $f(b_0,b_1,\ldots,b_n)$ is exactly the desired sequence of tuples. This surjectivity argument does not use the axiom of choice.

In summary, $A$ surjects onto $A\times 2$ and even $A^{{\lt}\omega}$, but it is not bijective with $A\times 2$ or indeed with any superset of $A$, since it is Dedekind finite.

Thus, one cannot deduce in ZF that $A$ is bijective with $A\times 2$, just from knowing that it surjects onto $A\times 2$. This is true even when $A$ is a set of reals, since the example provided above has a bijection to a set of reals.

Answer 2

This is only a partial answer, but it's way too long to go in the comments. I'll describe a permutation model (of ZF with atoms) that seems to give a counterexample $A$ for your statement. It will be easy to see that $A$ maps onto $A\times2$, but I haven't proved that there's no bijection between $A$ and $A\times2$; all I can say is that it looks quite plausible. If the example is correct, it will automatically transfer to ZF (without atoms) by the Jech-Sochor theorem. So here's the model.

Start with a set $U$ of atoms in 1-1 correspondence with the product $2^\omega\times3$ of the Cantor set and the ordinal 3. I'll write [x,i] for the atom that corresponds to the pair $(x,i)$, where $x\in2^\omega$ and $i\in3$. Let $G$ be the group of those permutations of $U$ that leave the first component (in the Cantor set) of each atom unchanged. So $G$ is the direct product of continuum-many copies of the symmetric group $S_3$. To define the class of supports, let me first introduce the terminology "thread" for an $\omega$-sequence of atoms $[x_n,i_n]$ such that, for each $n$, $x_{n+1}$ is obtained from $x_n$ by deleting the first bit, i.e., $x_{n+1}(k)=x_n(k+1)$. Let the supports be those subsets of $U$ that are covered by finitely many threads. This choice of supports (along with the choice of $U$ and $G$) determines a permutation model $M$.

In $M$, let $A$ be the set of all the threads. There is a surjection from $A$ to $A\times 2$, namely the map that sends any thread $T$ to the pair $(T',b)$ where $T'$ is obtained from $T$ by deleting its first term, say $[x_0,i_0]$, and $b=x_0(0)$. (So $b$ is the one component in the real $x_0$ that is omitted when one forms $x_1$.) This surjection is exactly 3 to 1, as it essentially just "forgets" the $i_0$ from $T$.

I believe, but have not proved, that $M$ contains no injection from $A\times2$ into $A$. The idea of the proof would be to assume there is such an injection, fix a finite number of threads that support it, and then look at what the injection could do with threads $T$ whose $x_0$ has no tail in common with anything from the support.

I further believe that the model would also work if I had used 2 instead of 3, but that the missing part of the proof will be easier with 3. The point is that, with 2, each thread would support the "complementary" thread, consisting of the same reals $x_n$ but the other elements $i_n$ in 2. It would also support various "mixtures" of itself and the complementary thread. With 3, a thread should support no threads other than itself and truncations of itself.

Going even further out on a limb, I also believe that the model would work if, instead of the whole Cantor space $2^\omega$, I used only the subspace consisting of the eventually periodic sequences of 0's and 1's and required threads also to be eventually periodic. In this model, $A$ should be Dedekind-finite, thus answering the last part of your question.

Answer 3

Building on Joel's answer, here is an explicit construction:

Suppose that $X$ is an infinite Dedekind finite set. Let $A=X\times 2$, this is a Dedekind-finite set as well. We denote $A_i = X\times\lbrace i\rbrace$.

The set $S=\lbrace f\in A^{<\omega}\mid f\text{ is injective}\rbrace$ is Dedekind-finite as well, since a countably infinite subset of $S$ gives a countably infinite subset of $A$.

I claim that $S+S\leq^\ast S$, and since both are Dedekind-finite we also have that $S < S+S$. We need to show there is a surjective map from $S$ onto $S\times 2$. We choose two elements $a_i\in A_i$, and we consider the set $S\times\lbrace a_0,a_1\rbrace$, where every element is a finite function with an extra element.

We now define the surjection:

For $f\in S$ let $k_f$ be the maximal element of the domain of $f$. If $f(k_f)\in A_0$ we map $f$ to the pair $\langle f\upharpoonright_{f_k},a_0\rangle$, and otherwise to $\langle f\upharpoonright_{f_k},a_1\rangle$.

That is we look at the last element in the sequence defined by $f$, if it belongs to $A_0$ we map $f$ with the last element removed to a pair with $a_0$ and otherwise to a pair with $a_1$.

To see that this function is surjective, given any pair $\langle f,a_0\rangle$ we can find $a\in A_0$ such that $f(k)\neq a$ for all $k\leq f_k$, and extend $f$ by $f(f_k+1)=a$. Similarly for pairs with $a_1$ in the right coordinate.

Note that this may seem confusing why we cannot find an injective inverse by simply adding $a_0$ or $a_1$ to $f$. Observe that we require $f$ to be an injective function, if $a_0$ was used then we cannot use it to extend $f$.

Answer 4

A simpler version (using the length of a sequence for coding, rather than its entries): Let $X$ be infinite but Dedekind finite. Let $S$ be the set of all finite 1-1 sequences from $X$. Then $S$ is Dedekind finite.

Now define a surjective map $f$ from $S$ onto $S\times \{0,1\}$ as follows.

• If $s\in S$ has length $2k+i$ with $i\in \{0,1\}$, map $s$ to $(s\mathord\restriction k, i)$ where $s\mathord\restriction k$ is the initial segment of $s$ of length $k$.

---

To get a surjective map from $S$ onto $S^{<\omega}$, we fix a surjective function $$H:\omega\to (\omega^{<\omega})^{<\omega}$$ with the property that all numbers appearing in $H(n)$ will be $< n$.

Now define $f:S\to S^{<\omega}$ as follows: Given a sequence $s\in S$ of length $n$, write $H(n)$ as $ (h_0,\ldots, h_{k-1})$, and let $F(s) := (s\circ h_0, \ldots, s\circ h_{k-1})$. (If some $h_i$ is not 1-1, let $F(s):=()$; alternatively, modify the function $H$ so that its range is the set of all sequences of 1-1 sequences.)

It is clear that $f$ is onto: given any sequence $t=(t_0,\ldots, t_{k-1})$ of elements of $S$, first find a 1-1 sequence $s$ enumerating the union of the ranges of the $t_i$. So there 1-1 sequences $h_i$ such that t $t_i = s\circ h_i$ for all $i$. Now extend $s$ (in a 1-1 way) to a sequence $r$ whose length codes the family of the $h_i$'s. We will have $f(r)=t$.