/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Tarski's exponential function problem

Tarski proved that the first-order theory of the real ordered field $(\mathbb{R}, +, \cdot, -, 0, 1, \le)$ is decidable, and asked whether the same holds for the real exponential field $\mathbb{R}{\exp} = (\mathbb{R}, +, \cdot, -, 0, 1, \le, \exp)$. The problem is open. Macintyre and Wilkie proved that the theory of $\mathbb{R}{\exp}$ is decidable if the real version of Schanuel's conjecture holds.

Decidability of a theory is formalised in FirstOrder.Language.Theory.IsDecidable: the set of consequences of the theory is computable, with respect to the Gödel numbering of sentences from FormalConjecturesForMathlib.ModelTheory.Encoding. The theory in question is the complete theory of $\mathbb{R}{\exp}$, which contains every sentence true in $\mathbb{R}{\exp}$, so this is the same as asking for an algorithm deciding membership (FirstOrder.Language.Theory.isDecidable_completeTheory_iff). The statements use the language of ordered rings with the order symbol ≤ in place of <. Some sources state the problem for $(\mathbb{R}, +, \cdot, \exp)$ instead. Since $<$, $\le$, $-$, $0$ and $1$ are definable from $+$ and $\cdot$, all these structures are interdefinable, and the choice does not affect decidability.

References:

@[expose] public sectionnamespace TarskiExponentialFunctionProblemopen FirstOrder

Tarski's theorem. The first-order theory of the real ordered field $(\mathbb{R}, +, \cdot, -, 0, 1, \le)$ is decidable.

@[category research solved, AMS 3 12] theorem isDecidable_completeTheory_real_orderedField : ((Language.ring.sum Language.order).completeTheory ℝ).IsDecidable := ⊢ ((Language.ring.sum Language.order).completeTheory ℝ).IsDecidable All goals completed! 🐙

Tarski's exponential function problem. Is the first-order theory of the real exponential field $\mathbb{R}_{\exp} = (\mathbb{R}, +, \cdot, -, 0, 1, \le, \exp)$ decidable?

@[category research open, question, AMS 3 12] theorem tarski_exponential_function_problem : (Language.orderedExpField.completeTheory ℝ).IsDecidable := ⊢ (Language.orderedExpField.completeTheory ℝ).IsDecidable All goals completed! 🐙

The real version of Schanuel's conjecture: if $x_1, \ldots, x_n$ are real numbers that are linearly independent over $\mathbb{Q}$, then the field $\mathbb{Q}(x_1, \ldots, x_n, e^{x_1}, \ldots, e^{x_n})$ has transcendence degree at least $n$ over $\mathbb{Q}$.

It is the special case of real arguments of Schanuel's conjecture, which is stated for complex numbers as Schanuel.schanuel_conjecture.

def RealSchanuelConjecture : Prop := ∀ (n : ℕ) (x : Fin n → ℝ), LinearIndependent ℚ x → n ≤ Algebra.trdeg ℚ (IntermediateField.adjoin ℚ (Set.range x ∪ Set.range (Real.exp ∘ x)))

Schanuel's conjecture for complex numbers, as stated in Schanuel.schanuel_conjecture, implies its real version.

h:∀ (n : ℕ) (z : Fin n → ℂ), LinearIndependent ℚ z → ↑n ≤ Algebra.trdeg ℚ ↥(IntermediateField.adjoin ℚ (Set.range z ∪ Set.range (Complex.exp ∘ z)))n:ℕx:Fin n → ℝhx:LinearIndependent ℚ xf:ℝ →ₐ[ℚ] ℂ := AlgHom.restrictScalars ℚ Complex.ofRealAmhz:↑n ≤ Algebra.trdeg ℚ ↥(IntermediateField.map f (IntermediateField.adjoin ℚ (Set.range x ∪ Set.range (Real.exp ∘ x))))hexp:Complex.exp ∘ ⇑f ∘ x = ⇑f ∘ Real.exp ∘ x⊢ ↑n ≤ Algebra.trdeg ℚ ↥(IntermediateField.adjoin ℚ (Set.range x ∪ Set.range (Real.exp ∘ x))) All goals completed! 🐙

Macintyre–Wilkie. If the real version of Schanuel's conjecture holds, then the first-order theory of the real exponential field is decidable.

@[category research solved, AMS 3 11 12] theorem isDecidable_completeTheory_realExp_of_realSchanuelConjecture (h : RealSchanuelConjecture) : (Language.orderedExpField.completeTheory ℝ).IsDecidable := h:RealSchanuelConjecture⊢ (Language.orderedExpField.completeTheory ℝ).IsDecidable All goals completed! 🐙end TarskiExponentialFunctionProblem