The answer is no. My question actually is, what are the sufficient and necessary conditions so that an arbitrary $\mathcal{L}$-structure $\mathcal{M}$ is rich enough to be able to define bijections between any two definable sets of the same cardinality?
I use these terms in this sense:
$\mathcal{L}$-structure $\mathcal{M}$: It is an structure with domain $M$, with an associated set of named constants and another associated set of named relations.
Definable set: It is a subset of $M^n$, for any natural number $n$, that can be defined using logical formulas and the associated sets of constants and relations.
Definable function: A definable set, which contains only ordered pairs and $(x,y)\in f$ and $(x,z) \in f$ imply $y=z$.
Let's call the property of being able to define a bijection for any two definable sets of the same cardinality as bijection-complete. Here are some examples:
- The $\mathcal{L}$-structure $\mathcal{N}$ that has as domain $\mathbb{N}$, no constants, and only a one-placed relation $R(x)$ that holds if $x$ is even, is not bijection-complete, since we can define the sets of even numbers $\{x:R(x)\}$ and odd numbers $\{x: \lnot R(x)\}$ and the only definable function is the identity (be it ranging through all the naturals, just the evens or just the odds) $\{(x,x): x=x\}$
- If we add to the structure $\mathcal{N}$ of the previous point, the functions $S(x, y)=x+y$ and $M(x,y)=x*y$, the structure becomes bijection-complete. Given that we can define $0$ as the $\{x: \forall y[S(x, y)=y] \}$, and $1$ in a similar maner, we can start defining all the naturals and hence, be able to define any finite set and any bijection between finite sets. Furthermore, for any infinite definable sets $A$ and $B$ we can well order them ($x<y$ iff $\exists z [z \not = 0 \land S(x, z)=y]$), define their associated successor functions $S_A$ and $S_B$, and define the bijection by recursion.
- For the $\mathcal{L}$-structure $\mathcal{Q}$ that has as domain $\mathbb{Q}$, all it's elements named by a constant (the decimal expansion) and all the usual relations (if it's in a math textbook, we'll count it as included), it is not clear at all (to me) if it is bijection-complete. The definition by recursion of the previous point can no longer apply here given that a successor function can't be defined (because $\mathbb{Q}$ is dense), and I see no straightforward way of (dis)proving bijection-completeness. Consider the difficulty of defining a bijection between $\{x: \text{the first three numbers of its decimal expansion sum 12} \}$ and $\{x: \text{in it's continued fraction form, the third element is a prime} \}$.
So again, what is needed for $\mathcal{M}$ to be bijection complete? How can it be proved that a certain $\mathcal{M}$ is or isn't bijection complete? (exhaustion or recursion as in $\mathcal{N}$ is not, in general, possible)
Edited: point 2 of examples and the definition of definable set