Proving that for structure $M=(\mathbb R; +,<,0)$, the function $f(x,y)=x \cdot y$ is not a definable set in $M$

361 Views Asked by At

Proving that for structure $M=(\mathbb R; +,<,0)$, the function $f(x,y)=x \cdot y$ is not a definable set in $M$.

Note: A function is called a definable set, if its graph, meaning the set $(x,f(x)), x \in M $ (the structure's universe) is a definable set in the structure.

So in this case we need to prove the set $(x,y,x \cdot y)$ is not definable in $M$. Using the last section in the Wikipedia article on a definable set, we know that if $X$ is definable on structure $M$ over parameters $c_1, \cdots, c_s$ then for every automorphism $\alpha: M \rightarrow M$ so that for every parameter $\alpha(c_i)=c_i$ , if $(x_1, x_2,..) \in X$ then $(\alpha(x_1), \alpha (x_2),..) \in X$ as well.

So to show that the function is not definable without parameters, we can assume it is definable, then look at the homomorphism $\alpha(x)=2x$ and see it isn't invariant, as $(2,3,6)\in X$, however $(4,6,12) \not\in X$.

What I try to do now for a really long time is proving it is not definable with parameters as well. Any help will be great!

Idea I thought of, not sure if correct. Lets assume $X$ is definable over parameters $c_1,...,c_s$. $\mathbb R$ is a vector space over $\mathbb Q$. Lets set $V_1=\text{span} \{c_1, c_2, ..., c_s\}$. So we know there is some $V_2$ so that $\mathbb R=V_1 \oplus V_2$. And for every $r \in \mathbb R$, there are unique $v_1 \in V_1, v_2 \in V_2$ so that $r=v_1+v_2$.

So lets set a homomorphism like so: $\alpha(r)=\alpha(v_1+v_2)=v_1+2v_2$. It indeed preserves $<$ and $+$, so it is a homomorphism. And for every $c_i \in V_1$, $\alpha(c_i)=c_i$, so it's invariant over the parameters. The only question is whether, for $a_1,a_2 \in V_2$, $a_1 \cdot a_2 \in V_2$. Because, if so, we can look at $\alpha(a_1 \cdot a_2)=2a_1a_2$, while $\alpha(a_1)\cdot \alpha(a_2)=4a_1a_2$, thus showing $X$ is not definable.

2

There are 2 best solutions below

0
On BEST ANSWER

As hot_queen notes in the comments, you can show this using quantifier elimination. But the idea the you suggested will actually work! The problem was that any collection of parameters from $\mathbb{R}$ control all of $\mathbb{R}$ (as in David Ullrich's answer) - you don't have the flexibility of automorphisms that you'd like. The solution is to leave $\mathbb{R}$ behind and move to an elementary extension which is more flexible.

Pick some elementary extension $\langle \mathbb{R}^*;+,<,0\rangle$ of $\mathbb{R}$ which contains "infinite elements", i.e. realize the type $\{x > r\mid r\in \mathbb{R}\}$. Now let $V_1$ be the convex hull of $\mathbb{R}$ in $\mathbb{R}^*$: $$V_1 = \{x\mid \exists r_1, r_2\in\mathbb{R}, r_1 < x < r_2\}.$$ Notice that $V_1$ is not all of $\mathbb{R}^*$ (since there are infinite elements), but $V_1$ is a $\mathbb{Q}$-subspace of $\mathbb{R}^*$. So we can write $\mathbb{R}^* = V_1\oplus V_2$ and decompose any element $r\in\mathbb{R}^*$ as $r = v_1 + v_2$ with $v_1\in V_1$ and $v_2\in V_2$.

Consider, just as you suggested, the map $\alpha(r) = v_1 + 2v_2$. $\alpha$ is clearly an invertible linear map which fixed $\mathbb{R}$ but is not the identity on $\mathbb{R}^*$. And this time it respects $<$.

[Why? If $r < r'$, then writing $r = v_1 + v_2$ and $r' = v_1' + v_2'$, we have that $r' - r = (v_2' - v_2) + (v_1' - v_1) > 0$. Since $v_2' - v_2\notin V_1$, it's either positive and greater than everything in $V_1$ or negative and less than everything in $V_1$. Well, it must be positive since the sum is positive, so also $\alpha(r') - \alpha(r) = 2(v_2' - v_2) + (v_1'-v_1) > 0$, and $\alpha(r) < \alpha(r')$.]

Now suppose multiplication is definable in $\mathbb{R}$. We can use the same formula to define a multiplication function on $\mathbb{R}^*$ with the same first-order properties (since $\mathbb{R}^*$ is an elementary extension). Take $r\in V_2$ with $r>0$. Since multiplication by a positive element is an increasing function, and $r$ is greater than every element of $\mathbb{R}$, the same is true of $r^2$. Then $(\alpha(r))^2 = (2r)^2 = 4r^2$, but $\alpha(r^2) \leq 2r^2$.

4
On

This doesn't show that multiplication is not definable with parameters, but it shows that the first approach you mention can't work. (Unless I'm still confused. Thanks to Asaf for straightening me out here, unless it turns out he didn't, in which case it's my fault...)

Say multiplication is definable with parameters from $X$. We can't have $X=\{0\}$, because $0$ is definable without parameters so that would imply that multiplication was definable without parameters. So $X$ must contain something nonzero. But:

Fact: If $f:\mathbb R\to \mathbb R$ is a homomorphism of that structure, $t\ne0$, and $f(t)=t$ then $f(x)=x$ for all $x$.

Proof: It's well known that the condition $f(x+y)=f(x)+f(y)$ implies that $f$ is either a straight line or very bad (for example non-measurable). Our $f$ is monotone, hence not so bad, hence a straight line. And now $f(t)=t$ gives qed.