Implicit and explicit definability over $\mathbb{R}$ of the exponential function

132 Views Asked by At

Let $L$ be a language, $M$ an $L$-structure, and $r$ an $n$-ary relation on $U_{M}$ (the domain of $M$).

Implicit definability:

We say that $r$ is implicitly definable over $M$ if there is a sentence $\varphi$ in the language $L'=L\cup\{R\}$, where $R$ is a new $n$-ary predicate, such that for all $n$-ary relations $s$ on $U_{M}$ we have $$(M,s)\vDash\varphi\text{ iff } r=s.$$ Where $(M,s)$ is the $L'$-structure with $R$ interpreted as $s$.

Explicit definability:

We say that $r$ is explicitly definable over $M$ if there is an $L$-formula $\varphi$ with free variables $x_{1},\ldots, x_{n}$ such that $$r=\{(a_{1},\ldots,a_{n}):M\vDash\varphi[x_{1}/a_{1},\ldots x_{n}/a_{n}]\}.$$

Let $\mathbb{R}:=(\mathbb{R},+,-,\cdot,0,1,<,=)$ be the ordered field of real numbers. How de we prove that the relation defined by the exponential function $e^{x}$ is implicitly definable but not explicitly definable?

1

There are 1 best solutions below

3
On BEST ANSWER

I think there are too many details here to write an explicit solution in this answer box. But I'll give you a quick sketch (or, perhaps, an implicit solution?).

$e^x$ is implicitly definable: Use the fact that $e^x$ is the unique function $f\colon \mathbb{R}\to \mathbb{R}$ such that $f(0) = 1$, $f$ is differentiable everywhere, and $f'(x) = f(x)$ for all $x$. The work here is in expressing these concepts in a first-order way.

$e^x$ is not explicitly definable: Using the fact that the theory of the real field has quantifier elimination, show that every definable function $f\colon \mathbb{R}\to \mathbb{R}$ grows asymptotically like a rational power of $x$, and hence is eventually dominated by $e^x$ as $x$ limits to $\infty$.