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?



On surjections, idempotence and axiom of choice
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. 


