Nonlinear Arithmetic with SMTLIB Division is Undecidable

Dejan Jovanović · 2026

Read Nonlinear Arithmetic with SMTLIB Division is Undecidable by Dejan Jovanović (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-26181.txt.

Introduction

Jovanovic proves nonlinear real arithmetic in the SMTLIB standard cannot be decided by any algorithm. No algorithm can settle every formula in the theory. The cause is division by zero, treated as a placeholder function with no fixed meaning. That placeholder lets whole-number problems hide inside real formulas. Since integer arithmetic is itself undecidable in that sense, the encoding spreads undecidability to the SMTLIB theory. The result traces a sweeping consequence to a subtle defining choice.

Catalog record

CREATORDejan Jovanović
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE5053
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.26181

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Nonlinear Arithmetic with SMTLIB Division is Undecidable
Dejan Jovanović

Abstract
We show that the nonlinear real arithmetic theory (NRA) as defined in the SMTLIB standard is undecidable. The undecidability arises from the treatment of division by zero as an uninterpreted function, which allows encoding integer arithmetic problems into NRA formulas. Note. This is a short note that was written some time ago and is being archived here for reference. The reader interested in this topic is encouraged to consult the more comprehensive and authoritative treatment of division semantics in polynomial solvers by Brown [ 4 ] , which subsumes the observations in this note.



1
Undecidability of NRA

As shown by Tarski
[
8
]
, the theory of real closed fields is
decidable. Formulas of the theory of real closed fields are equalities and
inequalities over polynomials (polynomial constraints), commonly referred to in
the SMT community as nonlinear real arithmetic. The SMTLIB standard

[
1
]
formally defines the theory of nonlinear real arithmetic
(NRA) as the theory of the standard model of the reals
\mathbb{R}
. However, in
addition to polynomial constraints, the signature of NRA includes division. The
interpretation of division is as expected at all points except when the
divisor is
0
. When the divisor is
0
, division in NRA is uninterpreted in the sense that
any interpretation of
\frac{x}{0}
is valid as long as division behaves as expected
when the divisor is nonzero. In other words, division is axiomatized as

\displaystyle(\forall x,y\in\mathbb{R})\;\;(y\neq 0)\Rightarrow(x=\frac{x}{y}\cdot y)\kern 5.0pt.

We show that the inclusion of division as described above leads to
undecidability of the SMTLIB theory NRA. This is perhaps unexpected for a theory whose decidable fragment (polynomial constraints) is a landmark result in mathematical logic.

Lemma 1
.

Real arithmetic with one unary uninterpreted function is undecidable.

Proof.

Assume one uninterpreted function symbol
f
. We can axiomatize
f
as the floor
function
\lfloor\cdot\rfloor
as follows

\displaystyle(\forall x\in\mathbb{R})\;\;

\displaystyle f(x)+1=f(x+1)\kern 5.0pt,

(1)

\displaystyle(\forall x\in\mathbb{R})\;\;

\displaystyle(0\leq x<1)\Rightarrow(f(x)=0)\kern 5.0pt.

(2)

We denote the above axioms as
A
. By induction on
|\lfloor x\rfloor|
, it is easy to
show that in the standard model of the reals,
f(x)=\lfloor x\rfloor
. Let
F(x_{1},\ldots,x_{n})
be an arbitrary formula over integer variables
x_{i}
. Then
F
is equisatisfiable with the following formula over real
variables

\displaystyle A\wedge\bigwedge_{i=1}^{n}(x_{i}=f(x_{i}))\wedge F(x_{1},\ldots,x_{n})\kern 5.0pt.

If nonlinear real arithmetic with one uninterpreted function
f
were decidable,
using the above transformation, we could decide
satisfiability of an arbitrary integer formula
F
. This is impossible since
integer arithmetic is undecidable (Hilbert’s 10th problem

[
5
]
).
∎

Lemma 2
.

Real arithmetic with uninterpreted division by zero is undecidable.

Proof.

Using the previous lemma, we can use division by zero
\frac{x}{0}
as the function

f
, leading to undecidability.
∎

Example 1
.

The following example shows how to encode satisfiability of
a^{3}+b^{3}=c^{3}

over integer variables
a
,
b
, and
c
, as a satisfiability problem in NRA.

\displaystyle(\forall x\in\mathbb{R})\;\;

\displaystyle\frac{x}{0}+1=\frac{x+1}{0}\kern 5.0pt,

\displaystyle(\forall x\in\mathbb{R})\;\;

\displaystyle(0\leq x<1)\Rightarrow(\frac{x}{0}=0)\kern 5.0pt,

\displaystyle(\frac{a}{0}=a)\wedge(\frac{b}{0}=b)\wedge(\frac{c}{0}=c)\wedge(a^{3}+b^{3}=c^{3})\kern 5.0pt.

2
Discussion

Decision procedures.

Although mostly focusing on linear arithmetic, there is a large body of work in
SMT on efficiently deciding quantified real arithmetic constraints. Notable
examples are approaches that apply complete quantifier elimination in a lazy

[
6
]
or model-driven fashion (e.g.,

[
3
,
7
]
). These methods are appealing since,
in principle, they could be extended to decide quantified nonlinear constraints
by using, e.g., quantifier elimination techniques from CAD. Unfortunately, as
explained above, this is not possible in the presence of division by zero as an uninterpreted function.

Benchmarks.

The NRA category of the SMTLIB library contains thousands of benchmarks. While
most use division only with constant divisors (which is decidable), benchmarks
with non-constant divisors fall into the undecidable fragment described in this
note.

Potential solutions.

Two possible approaches to address this undecidability are:

1.

Make division total by assigning a specific value to division by zero, similar to the treatment in the bitvector theory
[
2
]
. The main challenge is choosing an appropriate value for
\frac{x}{0}
.

2.

Read the complete text