Let $\mathcal{M}=\{M,<,\ldots\}$ be an o-minimal first order structure, namely a structure where every definable set in $M$ is finite union of points and intervals with endpoints in $M\cup \{\pm\infty\}$.

For $n,m<\omega$, $n\neq m$, can there exists a definable bijection $b:M^n\rightarrow M^m$?

I summarise some of the results which hold in o-minimal structures.

Monotonicity Theorem Every definable function $f:M\rightarrow M$ is piecewise continuous and monotone (i.e. strictly increasing, decreasing or constant).

Uniform finiteness Let $\phi(x,y)$ be a formula, $x\in M^n$, $y\in M^m$, and let's denote $A_{y}:=\{x\in M^n\,:\,\mathcal{M}\models \phi(x,y)\}$. We say $\{A_y\,:\, y\in M^m\}$ is a uniformly definable family of sets. There exists $k<\omega$ such that for all $y\in M^m$ either $|A_{y}|<k$ or $A_{y}$ is infinite.

By the monotonicity theorem it is easy to see that there is no definable bijection $b:M\rightarrow M^2$.

Proof Let $b:M\rightarrow M^2$ be a definable bijections. Consider function $b_0:p_0 \circ b$, namely the composition of $b$ with the proyection onto the first coordinate. $b_0$ is definable and so by the monotonicity theorem there exist $x_1<\cdots<x_l$ in $M$ such that $b_0$ is monotote in $I_0=(-\infty, x_1)$, $I_i=(x_i,x_{i+1})$ for $1\leq i <l$ and $I_l=(x_l,+\infty)$.

Note that $b_0$ is surjective and reaches every value in $M$ infinitely many times. For $a\in M$, since $b_0^{-1}(a)$ is infinite there must be an interval $I_i$ where there are more than two elements that map to $a$, so $b_0$ is constant in $I_i$. Hence it follows from the fact that every element in the image of $b_0$ is mapped infinitely many times that the image of $b_0$ must be finite, so $b_0$ cannot be surjective.

  • $\begingroup$ Google for "invariance of domain" and "o-minimal structure" and you will find references showing that no such bijection can exist. The cell decomposition theorem is the main tool needed in the proofs. $\endgroup$ – Rob Arthan Mar 17 '16 at 20:45

Definable subsets of o-minimal structures admit a good notion of dimension, which is invariant under definable bijections. As you would expect, $\dim(M^n) = n$ and $\dim(M^m) = m$, so there can be no definable bijection between $M^n$ and $M^m$.

For a reference on o-minimal dimension, you can look at Chapter 4 of van den Dries's book Tame topology and o-minimal structures, where dimension is defined using cell-decomposition, or Section 1 of Pillay's paper On groups and fields definable in o-minimal structures, where it is defined using (model-theoretic) algebraic closure.

  • 2
    $\begingroup$ I should remark perhaps that both of these sources require the underlying order to be dense. If you care about non-dense o-minimal structures (but who does, really?) you probably have to think a bit harder... $\endgroup$ – Alex Kruckman Mar 17 '16 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.