7
$\begingroup$

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.

$\endgroup$
1
  • $\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
    Commented Mar 17, 2016 at 20:45

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\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$ Commented Mar 17, 2016 at 21:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .