Passmore Diophantine Sets and their Decision Problems

A Mathematical Monograph and Honors Thesis

Diophantine Sets and Their

Decision Problems

Grant Olney Passmore

Department of Mathematics, University of Texas at Austin, and

Mathematical Research Institute in The Netherlands

Advised by Robert Stephen Boyer

Acknowledgements

The aesthetic event is something as evident, as immediate, as inde-
finable as love, the taste of fruit, of water. We feel poetry as we feel
the closeness of a woman, or as we feel a mountain or a bay. If we
feel it immediately, why dilute it with other words, which no doubt
will be weaker than our feelings?

Jorge Luis Borges, Lecture titled “Poetry,” 1977

My years at the University of Texas at Austin have transformed me and my

life in ways so wonderful that I find words for the experience nearly impossi-
ble to sequence. I am barely into the beginning of reflecting upon this strange
and fantastical morphism, and while my perspective is necessarily short-sighted,
there is one fact about this time I know even now to be manifestly certain. This
is the fact that my interest in mathematics was awakened and nourished chiefly
by a very small handful of inspiring professors and friends, and had I not had
the good fortune of their insight and friendship, I might be living now a very
different life. Against Borges’s better judgement, I shall try to thank some of
those to whom I am most indebted. Though with joys and friends and magic
such as these, my “other words” below, as Borges points out, are sure to do no
more than to dilute.

First and foremost, I would like to thank Professor Bob Boyer. He has a way

of encouraging one’s desire towards maturing as a mathematician and philoso-
pher like no one else I know. His kindness and sense of ethical responsibility are
rivaled only by his brilliance. He and his wife Anne, with their weekly gift of
kind hospitality, stories, and advice, made this treasure hunt of a thesis truly a
joy to compose. I will miss those early Wednesday and Saturday summer morn-
ings filled with many laughs, music, cookies, coffee, and pretty mathematics.

During my time in Holland, my close friendship with Joost J. Joosten and

his lovely wife Emma provided me with both a sense of family belonging in
a distant land and a source of mathematical inspiration. I owe much of the
fruitfulness of my year at the Mathematical Research Institute in The Nether-
lands to him. I would also like to thank our students in the Computational
Logic course that Joost and I taught together at the University of Amsterdam.
Studying mathematics with our students in beautiful Amsterdam was one of
my favorite experiences in Holland. I am excited to see what they accomplish
in their futures.

I would like to thank my parents for their ongoing love and support, Starr

and Chad Dickerson, Jacqueline Passmore, Skye Clarke, David and Eddy Ho-
bizal, Denis Ignatovich, Jacob Kornerup, Matt Kaufmann, J Strother Moore,
and Barry Cooper. Also, I would like to thank my colleagues and friends at the
Mathematical Research Institute in The Netherlands: Andrew Polonsky, Yves
Fomatati, Takako Nemoto, Danko Iilik, Johann Suarez, and Dave Carchedi for
their friendship, advice, and mathematical playfulness, as well as my advisor at
MRI, Jaap van Oosten.

Finally, I would also like to thank the Mathematical Research Institute in

the Netherlands and the Discrete Interactive Algorithmic Mathematics Algebra
and Number Theory (DIAMANT) Dutch Mathematics Cluster for providing
my fellowship while working on a portion of this manuscript.

Contents

A Sketch of Our Endeavour

Diophantine Fundamentals and Decisions

2.1

Decision Problems . . . . . . . . . . . . . . . . . . . . . . . . . .

2.1.1

Negative Solutions to Decision Problems . . . . . . . . . .

2.1.2

Decision Problem Reductions . . . . . . . . . . . . . . . .

2.2

Diophantine Equations . . . . . . . . . . . . . . . . . . . . . . . .

2.2.1

LHS Form . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3

Systems of Diophantine Equations . . . . . . . . . . . . . . . . .

2.4

Solutions in N . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.5

Families of Diophantine Equations . . . . . . . . . . . . . . . . .

2.6

Diophantine Sets and Representations . . . . . . . . . . . . . . .

Algebra of Diophantine Sets

3.1

Union and Intersection . . . . . . . . . . . . . . . . . . . . . . . .

3.2

Assumed Values Characterization . . . . . . . . . . . . . . . . . .

3.3

Diophantine Predicates and Logic . . . . . . . . . . . . . . . . . .

3.4

Diophantine Representations of Predicates . . . . . . . . . . . . .

3.5

Generalized Diophantine Representations

. . . . . . . . . . . . .

3.6

Some Simple Diophantine Representations . . . . . . . . . . . . .

Exponential Diophantine Equations

4.1

A Note on Our Historical Presentation . . . . . . . . . . . . . . .

4.2

Foundational work of Robinson and Davis . . . . . . . . . . . . .

4.3

The Robinson Results . . . . . . . . . . . . . . . . . . . . . . . .

4.3.1

Some Results on Pell’s Equation . . . . . . . . . . . . . .

4.3.2

Exponentiation . . . . . . . . . . . . . . . . . . . . . . . .

4.4

Every R.E. Set is Exponential Diophantine

. . . . . . . . . . . .

Hilbert’s Tenth Problem is Unsolvable

5.1

Rough Exponentiation as the Missing Link

. . . . . . . . . . . .

5.2

Historical Interlude: Spirit of the Time . . . . . . . . . . . . . . .

5.3

Exponentiation is Diophantine

. . . . . . . . . . . . . . . . . . .

5.4

Unsolvability of Hilbert’s Tenth Problem . . . . . . . . . . . . . .

CONTENTS

New Results on Multiplicative Definability

6.1

Results on Definability Theory of (N, ∗, !) . . . . . . . . . . . . .

6.2

Every R.E. Set is F.O. Definable in (N, ∗, !) . . . . . . . . . . . .

6.3

Multiplicative Conjunctive Normal Form . . . . . . . . . . . . . .

6.4

Sufficient Condition for Undecidability of T h(N, ∗) . . . . . . . .

A Bibliography

Chapter

A Sketch of Our Endeavour

Hilbert’s Tenth Problem has a beautiful and riveting history. In his 1900 ad-
dress to the Second International Congress of Mathematicians, David Hilbert
proposed a list of 23 mathematical problems. This list became a wonderfully
fruitful collection of conceptual seeds, dictating much of the mathematical de-
velopment of the century that followed. In this monograph, we are interested in
one of these problems in particular. It appears as tenth on the list:

10. Determination of the Solvability of a Diophantine Equation

Given a Diophantine equation with any number of unknown quan-
tities and with rational integral numerical coefficients: To devise a
process according to which it can be determined by a finite number
of operations whether the equation is solvable in rational integers.

In 1970, the existential fate of such a process was finally determined. Based

upon the work of Davis, Putnam, and Robinson, Yury Matiyasevich proved
that such an algorithm can not exist, and moreover, that the number-theoretic
notion of a Diophantine set corresponds precisely to the logical notion of a
recursively enumerable set. But the story need not end here. While there is no
such decision procedure for arbitrary Diophantine equations in Z[x

, . . . , x

m−1

we may specify restricted classes of Diophantine equations, such as monomial
equations with terms drawn from Z[x

, . . . , x

m−1

], and investigate questions

similar to Hilbert’s Tenth Problem relativised to these impoverished settings.

We shall examine the genesis and proof of the Davis-Putnam-Robinson-

Matiyasevich negative solution to Hilbert’s Tenth Problem, and then proceed
to prove a handful of elementary new results on definability and decidability in
(N, ∗).

CHAPTER 1. A SKETCH OF OUR ENDEAVOUR

Chapter

Diophantine Fundamentals and
Decisions

2.1

Decision Problems

In mathematics, a mechanical procedure or algorithm is often sought for solving
a particular set of problems. The informal notion of an algorithm is a very old
one, perhaps as old and fundamental as the notion of calculation itself. As an
example, when one learns to add, multiply, and divide arbitrary integers as a
child, one is effectively learning a mechanical procedure for simplifying a cer-
tain class of arithmetical terms. Similarly, Euclid’s celebrated G.C.D. algorithm
dates back over two millennia to the time of the ancient Greeks.

With the advent of symbolic logic, and in the wake of Hilbert’s program for

establishing a consistent finitary axiomatic foundation for higher mathematics,
an emphasis was placed on finding algorithms not just for outwardly arithmeti-
cal calculations, but for deciding the truth or falsity of certain mathematical
statements

. This study led to the notion of decision problems and decision

procedures, and at last, to an abstract mathematical theory of computability.

Without a grounding in the foundations of computability theory, the no-

tion of a decision problem must be broached in a necessarily informal manner.
The idea is this: A decision problem is a collection of countably many finitely-
specified

subproblems or instances, each of which may evaluate to true or false.

For a decision problem to have a solution, there must exist a general algorithm
that for any instance can compute its truth value in a finite amount of time.
When a decision problem in mathematics admits such a solution, we say the
problem is decidable and the algorithm is a decision procedure for the problem.
If a problem is not decidable, we say it is undecidable.

As it turns out, many imporant problems in mathematics are in fact un-

decidable. We now briefly examine one in particular, a historically important
undecidable component of Hilbert’s Second Problem known as the Entschei-

In retrospect, it is of course the fact that such decision procedures are essentially arith-

metical calculations that leads to the undecidability of elementary number theory.

That is, each instance can be specified by a finite amount of information. For Hilbert’s

Tenth Problem, this would be the specification of the polynomial D.

CHAPTER 2. DIOPHANTINE FUNDAMENTALS AND DECISIONS

dungsproblem.

2.1.1

Negative Solutions to Decision Problems

Consider the following decision problem:

Let L be a first-order language.
Let A be a set of axioms expressed in L.
Let C be a conjecture expressed in L.

Question: Does C follow logically from A ?

Through the work of Church and Turing [2] [16], it is known that this problem
does not admit a solution. That is, no decision procedure for provability in first-
order logic can exist.

Now, it seems obvious that if a decision procedure exists for a certain de-

cision problem, then this can be shown simply by exhibiting the procedure and
proving that it meets its specification. But what about proving that a problem
is undecidable? It is precisely this question that motivates the development of a
theory of computable functions. While showing that a decidable decision prob-
lem is indeed decidable requires merely the (possibly very difficult) exhibition
of an algorithm, to show that an undecidable problem is indeed undecidable,
one must in general have a mathematical theory of algorithms at hand. This,
as we shall see, is not a simple task.

2.1.2

Decision Problem Reductions

A note should be made on strategy. An essential method we shall use when
proving the undecidability of Hilbert’s Tenth Problem is one of reduction. The
idea is this:

Let P be a decision problem we know to be undecidable.
Let P

be another decision problem.

If we can prove that any instance of P may be solved by a sup-
posed decision procedure for P

, then clearly P

must be undecidable

as well.

This simple method of proving undecidability of a decision problem by reducing
a known undecidable decision problem to it is extremely useful. An important
property to note is that this type of reduction is transitive. This follows trivially
by the transitivity of logical implication.

In the remaining sections of this chapter, we follow closely the presentation
of Matiyasevich in [11].

2.2

Diophantine Equations

Recall that a Diophantine equation is an equation between polynomials with
integer coefficients. A general Diophantine equation is thus of the form:

2.3. SYSTEMS OF DIOPHANTINE EQUATIONS

, . . . , x

m−1

) = D

, . . . , x

m−1

)

where D

and D

are polynomials in Z[x

, . . . , x

m−1

2.2.1

LHS Form

With simple arithmetic, it is clear that any Diophantine equation of the general
form may be reduced to one in which the right hand side is zero. It is often more
convenient to work with Diophantine equations that have been reduced in this
way. Unless stated otherwise, a Diophantine equation in this text will have the
form:

D(x

, . . . , x

m−1

) = 0

where D ∈ Z[x

, . . . , x

m−1

2.3

Systems of Diophantine Equations

It is readily seen that a positive solution to Hilbert’s Tenth problem would
yield a method for deciding whether or not an arbitrary system of Diophantine
equations has a solution in the integers

Lemma 1. Let S be the system of Diophantine equations

, . . . , x

m−1

) = 0

, . . . , x

m−1

) = 0

k−1

, . . . , x

m−1

) = 0.

Then, there is a Diophantine equation D s.t. D has a solution in the integers if
and only if S does.

Proof. D = (D

, . . . , x

m−1

) + . . . + D

k−1

, . . . , x

n−1

) = 0).

The reader should convince herself that the new Diophantine equation D will in
fact have the exact same set of solution vectors V ∈ 2

as S.

2.4

Solutions in N

We now encounter our first decision problem reduction. We prove in this section
that the decision problem for the solubility of Diophantine equations by non-
negative integers may be reduced to Hilbert’s Tenth Problem.

Note that by a solution in the integers we really mean a solution vector whose elements

are integers.

CHAPTER 2. DIOPHANTINE FUNDAMENTALS AND DECISIONS

Lemma 2. Let D(x

, . . . , x

m−1

) = 0 be an arbitrary Diophantine equation.

Then there exists a Diophantine equation D(x

, . . . , x

n−1

) = 0 s.t. D(x

, . . . , x

n−1

) = 0

has solutions in N

if and only if D(x

, . . . , x

m−1

) = 0 has solutions in Z

Proof. Let S be the following system of Diophantine equations:

D(x

, . . . , x

m−1

) = 0

= y

0,0

+ y

0,1

+ y

0,2

+ y

0,3

m−1

= y

m−1,0

+ y

m−1,1

+ y

m−1,2

+ y

m−1,3

By Lemma 1, let D(x

, . . . , x

m−1

, y

0,0

, . . . , y

m−1,3

) = 0 be the Diophantine equa-

tion corresponding to the system S. Because the m auxiliary constraints on the
variables x

, . . . , x

m−1

yield that each element in a solution vector for S must

be non-negative, a solution of D(x

, . . . , x

m−1

, y

0,0

, . . . , y

m−1,3

) = 0 in Z

5∗m

includes a solution of the Diophantine equation in N

5∗m

. For the other direc-

tion, recall the nice theorem that every non-negative integer is a sum of four
squares.

It is prudent to reflect upon this accomplishment. Now, to prove the unde-

cidability of Hilbert’s Tenth Problem, it suffices to prove the nonexistence of an
algorithm for deciding whether or not an arbitrary Diophantine equation has
solutions in the non-negative integers. We shall call this the analog of Hilbert’s
Tenth Problem over the natural numbers. We shift our focus now to this analo-
gous problem, and unless stated otherwise, all solution vectors for Diophantine
equations in the text that follows will be assumed to consist of elements of N.

2.5

Families of Diophantine Equations

A family of Diophantine equations is a Diophantine equation with free param-
eters. Such families take the following form:

D(a

, . . . , a

n−1

, x

, . . . , x

m−1

) = 0.

In this context, the n+m variables are separated into two sets: {x

, . . . x

m−1

}

are the unknowns, and {a

, . . . a

n−1

} are the parameters. By varying the instan-

tiations of the parameters, one obtains all members of the family. It is important
to note that such families are not in general systems of equations, as a solution
vector for the unknowns does not need to satisfy all members of the family si-
multaneously. Such families are also called parametric Diophantine equations.
One is careful to distinguish the degree of the parametric equation in terms of
its unknowns and the degree of the parametric equation in terms of all of its
variables.

2.6. DIOPHANTINE SETS AND REPRESENTATIONS

2.6

Diophantine Sets and Representations

Let

D(a

, . . . , a

n−1

, x

, . . . , x

m−1

) = 0

be a parametric Diophantine equation. This equation defines a set M ∈ 2

consisting of the n-tuples of values of a

, . . . , a

n−1

for which there exist solution

vectors for the unknowns, x

, . . . , x

m−1

We thus have M defined through D(a

, . . . , a

n−1

, x

, . . . , x

m−1

) = 0 as fol-

lows:

, . . . , a

n−1

i ∈ M ⇐⇒ ∃x

. . . ∃x

m−1

(D(a

, . . . , a

n−1

, x

, . . . , x

m−1

) = 0).

Such a set M defined in this way is called, not surprisingly, a Diophantine set,
and the equivalence above is called a Diophantine representation for M .

We are now able to state the motivating questions for Chapter 2:

Let M be a given set of n-tuples of natural numbers. Is this set M
Diophantine? If so, is there an algorithm that can effectively find a
Diophantine representation for M ?

CHAPTER 2. DIOPHANTINE FUNDAMENTALS AND DECISIONS

Chapter

Algebra of Diophantine Sets

Having defined the notion of a Diophantine set of n-tuples of natural numbers,
we now build an algebra of Diophantine sets by introducing some, but not all

of the familiar set-theoretic operations in terms of the manipulation of their
defining polynomials. Moreover, we will exhibit a simple polynomial manipula-
tion that will yield a useful equivalent characterization of Diophantine sets as
the set of all natural number values assumed by a polynomial in Z[x

, . . . , x

m−1

]

when it is evaluated with natural number values in place of its variables. From
this foundation, we will see that many interesting sets of natural numbers are
easily observed to be Diophantine.

3.1

Union and Intersection

We first prove that both the union and intersection of two Diophantine sets of
the same dimension are indeed Diophantine.

Lemma 3. Let S and S

be two Diophantine sets represented respectively by

, . . . , a

n−1

, x

, . . . , x

−1

) = 0,

, . . . , a

n−1

, x

, . . . , x

−1

) = 0.

Then S ∪ S

and S ∩ S

are both Diophantine.

Proof.

, . . . , a

n−1

, x

, . . . , x

−1

) ∗ D

, . . . , a

n−1

, x

, . . . , x

−1

)) = 0

is a representation of their union, and

, . . . , a

n−1

, x

, . . . , x

−1

) + D

, . . . , a

n−1

, y

, . . . , y

−1

)) = 0

is a representation of their intersection. Note also that in the case of intersection,
we renamed the unknowns of the second equation.

In particular, Diophantine sets are not closed under complementation, but this an early

result of Martin Davis that we will not approach directly. Once we have proved the DPRM
Theorem, this fact will follow from the fact that there exist non-recursive recursively enumer-
able sets.

CHAPTER 3. ALGEBRA OF DIOPHANTINE SETS

3.2

Assumed Values Characterization

We first make the following simple observation:

Lemma 4. The Diophantine equation

D(a, x

, . . . , x

m−1

) = 0.

in m unknowns has a solution in x

, . . . , x

m−1

iff the equation

∗

+ 1)(1 − D

∗

, x

, . . . , x

m−1

)) − 1 = a

has a solution in the m + 1 unknowns x

∗

, x

, . . . , x

m−1

Proof. (⇒) Let a be such that D(a, x

, . . . , x

m−1

) has a solution in x

, . . . , x

m−1

Now, consider the equation

∗

+ 1)(1 − D

∗

, x

, . . . , x

)) − 1 = a

with x

∗

= a. That is, as we have

D(a, x

, . . . , x

m−1

) = 0

by assumption (for some fixed values of the unknowns), we have

(a, x

, . . . , x

) = 0

and thus

(a + 1)(1 − D

(a, x

, . . . , x

)) − 1

= (a + 1)(1 − 0) − 1

= a + 1 − 1

= a

as desired.

(⇐) On the other hand, consider a solution to the equation

∗

+ 1)(1 − D

∗

, x

, . . . , x

m−1

)) − 1 = a.

Clearly, the factor 1 − D

∗

, x

, . . . , x

m−1

) must be positive, as all unknowns

and parameters are assumed to be non-negative by Lemma 2. But, this is pos-
sible only when D(x

∗

, x

, . . . , x

m−1

) = 0. So, we have:

∗

+ 1)(1 − 0) − 1 = a

yielding

∗

+ 1 − 1 = a

and thus x

∗

= a.

Let us reflect upon this wonderful lemma. We restate the result as follows

(in the words of Matiyasevich [11]):

A set of natural numbers is Diophantine iff it is the set of all natural
number values assumed by some polynomial with integer coefficients
for natural number values of its parameters.

In the remaining sections of this chapter, we follow closely the presentation

of Matiyasevich in [11].

3.3. DIOPHANTINE PREDICATES AND LOGIC

3.3

Diophantine Predicates and Logic

It is now instructive to examine Diophantine representations for some important
(albeit very simple) predicates on the natural numbers. Consider, for instance,
the following polynomial equation:

− a

)

= x + 1.

In this case, we use the technique in the previous chapter and define the Dio-
phantine set M characterized by this polynomial as

, a

i ∈ M ⇐⇒ ∃x[(a

− a

)

= x + 1],

and we see quickly that

, a

i ∈ M ⇐⇒ (a

6= a

Thus, the property of two natural numbers being nonequal to each other is
Diophantine. To aid the clarity of our expression, we will often rewrite the
set membership statement above as one involving a predicate symbol that we
introduce as being defined by the existentially quantified Diophantine equation.
For instance, we might simply write:

R(a

, a

) ⇐⇒ ∃x[(a

− a

)

= x + 1].

Noting that R(a

, a

) ⇐⇒ (a

6= a

), we express this even more clearly as:

6= a

) ⇐⇒ ∃x[(a

− a

)

= x + 1].

For many very basic properties of natural numbers, finding Diophantine rep-
resentations for them is a simple task. Moreover, some simple properties are
ostensibly already given by Diophantine representations, though we may not
have realized it before undertaking this study. Consider the property of be-
ing an even number. A Diophantine representation for this property just the
canonical

Even(a) ⇐⇒ ∃x[2x = a]

that we already knew from childhood. We will see, however, that there are
many other Diophantine properties and relations for natural numbers that, while
natural in their descriptions (such as primality and exponentiation), are quite
difficult to describe in terms of Diophantine relations.

3.4

Diophantine Representations of Predicates

Being a bit more precise, a property P of natural numbers is a Diophantine
property if the set of natural numbers having that property is Diophantine (in
the sense of Section 1.6). An equivalence of the form

CHAPTER 3. ALGEBRA OF DIOPHANTINE SETS

P (a) ⇐⇒ ∃x

. . . x

m−1

[D(a, x

, . . . x

m−1

) = 0]

is called a Diophantine representation for the property P .

Likewise, given a relation R between n natural numbers, we say R is a

Diophantine relation if the set of all n-tuples for which the relation holds is
Diophantine. As above, a logical equivalence of the form

R(a

, . . . , a

n−1

) ⇐⇒ ∃x

. . . x

m−1

[D(a

, . . . , a

n−1

, x

, . . . x

m−1

) = 0]

is called a Diophantine representation for the relation R. We make the conven-
tion that both properties and relations are to be called predicates distinguished
by the fact that a property of natural numbers is a unary predicate, while a
relation is an n-ary predicate on natural numbers with n > 1.

We may now reformulate the set-theoretic union and intersection operations

for which we showed closure within Diophantine sets in Section 2.1 in terms of
logical connectives and and or between predicates. This takes shape in the
following lemma, which is essentially just a rewriting of Lemma 3.

Lemma 5. Let R

, R

be two Diophantine predicates. Then, the predicates R

and R

given by

R(a

, . . . , a

n−1

) ⇐⇒ R

, . . . , a

n−1

) ∨ R

, . . . , a

n−1

)

, . . . , a

n−1

) ⇐⇒ R

, . . . , a

n−1

) ∧ R

, . . . , a

n−1

)

are both Diophantine predicates.

Proof. Unfold the Diophantine representations for R

and R

and then apply

Lemma 3, with ∩ for ∧ and ∪ for ∨.

3.5

Generalized Diophantine Representations

We may continue in this direction and accept any formula constructed from
parametric Diophantine equations by using, in any order, disjunction, conjunc-
tion, and existential quantification as constituting a generalized Diophantine
representation

. The following notions will be helpful as we work to prove that

certain sets are in fact Diophantine:

1. A Diophantine function is a function whose graph is a Diophantine set.

2. A Diophantine representation of a function F is a logical equivalence of

the form:

a = F (b

, . . . , b

n−1

) ⇐⇒ ∃x

. . . x

m−1

[D(a, b

, . . . , b

n−1

, x

, . . . , x

m−1

) = 0]

where D is a polynomial with integer coefficients.

For the readers versed a bit in logic, this follows easily from the Prenex Normal Form

Theorem.

3.6. SOME SIMPLE DIOPHANTINE REPRESENTATIONS

Along with Diophantine equations, we may also examine equations of the

form

P (t

, . . . , t

k−1

) = 0

where P is a polynomial with integer coefficients and t

, . . . , t

k−1

are Diophan-

tine terms, that is expressions constructed in the standard way from particular
natural numbers, variables ranging over N, the operations +, −, ∗ : N × N → N,
and, importantly, symbols for previously defined (generalized) Diophantine func-
tions. Similar to the technique used in the proof of Lemma 1, we may transform
an equation of the form

P (t

, . . . , t

k−1

) = 0

into an equivalent Diophantine system consisting of equations of the form

α = β + γ,

(3.1)

α = β ∗ γ,

(3.2)

α = F (β

, . . . , β

n−1

)

(3.3)

where α, β, γ are either particular natural numbers or certain unknowns, and F
is a Diophantine function. Moreover, we may rewrite each equation of the form

α = F (β

, . . . , β

n−1

)

with a copy of the equation

a = F (b

, . . . , b

n−1

) ⇐⇒ ∃x

. . . x

m−1

[D(a, b

, . . . , b

n−1

, x

, . . . , x

m−1

) = 0]

with a replaced by α, b

, . . . , b

n−1

replaced by β

, . . . , β

n−1

, and the variables

, . . . , x

m−1

replaced by ones that have not yet been used. The system may

then be compressed into a single equation using Lemma 1.

3.6

Some Simple Diophantine Representations

Recall the representation we saw for 6=:

6= a

) ⇐⇒ ∃x[(a

− a

)

= x + 1].

Similarly, we may prove that the inequalities ≤ and < are Diophantine as follows:

a ≤ b ⇐⇒ ∃x[a + x = b],

a < b ⇐⇒ ∃[a + x + 1 = b].

Divisibility is also very simple:

CHAPTER 3. ALGEBRA OF DIOPHANTINE SETS

a|b ⇐⇒ ∃x[a ∗ x = b].

With < and | defined, we may now give the following generalized Diophan-
tine representation for the function remainder on dividing b by c, written as
rem(b, c):

a = rem(b, c) ⇐⇒ a < c ∧ c|(b − a).

When proving exponentiation to be Diophantine, we will see the need for the
function arem(b, c) defined to be the least absolute value |X| among all numbers
X congruent to b with respect to the modulus c:

(arem(b, c) ≡ ±b (mod c)) ∧ (0 ≤ arem(b, c) ≤

c
2

This function is seen to be Diophantine as follows:

a = arem(b, c) ⇐⇒ 2 ∗ a ≤ c ∧ [c|(b − a) ∨ c|(b + a)].

It will also be convenient to have the relation of non-divisibility in our Diophan-
tine arsenal:

a 6 | b ⇐⇒ rem(b, a) > 0.

It is useful to note that the relation of non-divisibility introduced here is not

the negation of the divisibility relation, because both relations are false when
a = 0 and b > 0. This could be avoided, but we will use this non-divisibility
relation only when we are sure that the first argument is non-zero. We may now
give a generalized Diophantine representation for the function integer part of
b/c, written b div c as:

a = (b div c) ⇐⇒ (a ∗ c + rem(b, c)) = b,

along with a generalized Diophantine representation of congruence with respect
to a positive modulus:

a ≡ b (mod c) ⇐⇒ rem(a, c) = rem(b, c).

We will make use of these Diophantine predicates and functions in the next

chapter.

Chapter

Exponential Diophantine
Equations

4.1

A Note on Our Historical Presentation

With some basic Diophantine machinery in hand, we may now work to prove
the Davis-Putnam-Robinson-Matiyasevich (DPRM) theorem. When this task is
complete, we will have established that Hilbert’s wish for a general algorithm
determining the existence of integer solutions for arbitrary Diophantine equa-
tions can never be fulfilled.

In presenting a proof of this important theorem, there are two approaches

that the author has considered. One approach is to embark upon a close follow-
ing of the historical genesis of the proof, beginning originally with the work of
Julia Robinson, Martin Davis, and Hilary Putnam in the 1950s and 1960s, and
culminating in the work of the young (22 year old) Yuri Matiyasevich in 1970.
This presentation involves much mathematical logic, especially recursion theory,
and while it is exhilerating to follow the historical development of such beauti-
ful ideas, it yields a somewhat indirect presentation compared to much shorter,
more outwardly number-theoretic proofs that have since been found. The other
approach, as alluded to, involves ignoring the historical development by present-
ing a slick modernization that is for the most part strictly number-theoretic.

The author believes that the wonders gained from the historical approach out-
weigh the merits of the other more economical one, at least for the purposes of
this monograph. Thus, we will begin this fascinating tale at (close to) the be-
ginning. Our story starts in the bustling hallways of the University of California
at Berkeley with a conjecture of Tarski on powers of two.

As some people say [13], we will have shown definitively a fact about which most mathe-

maticians will heartily agree: that number theory is hard!

As the DPRM theorem will establish, this choice is only a matter of taste, as a central

result of the theorem is that recursion theory is essentially number theory (in the sense that all
of the wonderful beasts of recursion theory such as recursively enumberable sets, immune sets,
creative sets, and so on, may be described fully using only existential Diophantine relations).

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

4.2

Foundational work of Robinson and Davis

As a Ph.D. student of Tarski at Berkeley in the 1940s, Julia Robinson grew to
mathematical maturity in an environment with a keen focus upon interactions
between logic and number theory, especially when it came to decision prob-
lems for algebraic structures prominent in mathematical practice. In Warsaw
in 1931 (though unpublished until 1948 [4]), Tarski proved the decidability of
the first-order theory of real numbers, T h(R, +, ∗). He did so by constructing
an algorithm for quantifier elimination, which systematically reduces any well-
formed formula of the first-order language of the theory of real numbers into
an equivalent statement that is quantifier free. In this way, any sentence in the
language can be reduced to a quantifier free statement that is readily seen to
be either true or false, and any formula with free variables can be reduced to an
equivalent quantifier free formula expressing a constraint upon the free variables
that would guarantee the truth of the original formula. In establishing quantifier
elimination, Tarski in fact showed that T h(R, +, ∗) is the same as the theory
of any real-closed field, including the countable field of real algebraic numbers.
Tarski also showed the somewhat less involved facts that the elementary theory
of the complex number field T h(C, +, ∗) is decidable, and that the theories of
all algebraically closed fields of characteristic zero are the same.

It is in this setting that Julia Robinson began to work under Tarski upon

the definability theory of T h(Q, +, ∗). In her dissertation, Robinson succeeded
in showing that, with a very clever use of Pell’s equation

, N is definable within

the elementary theory of the rational number field, and thus T h(Q, +, ∗) inher-
its the undecidability of T h(N, +, ∗) that had been established by G¨odel [8] in
the decade prior. Before returning to her work on Hilbert’s Tenth Problem, it
is worth a tiny bit of labor to enjoy the magical feeling a quick sketch of this
deep proof delivers to the contemplative reader.

In proving the undecidability of the rational number field, Robinson can be

said to have had her first breakthrough [9] when she realized that if r ∈ Q
and r = a/b where a, b ∈ Z and (a, b) = 1, then b is odd if and only if
∃x

, x

(7r

+ 2 = x

+ x

) is true in (Q, +, ∗). Thus, it follows

that this ternary quadratic form can be used to express that 2 is not a factor
of the denominator of a given rational number. Robinson then continued in this
way and found additional ternary quadratic forms that would “eliminate” one-
by-one all prime numbers from denominators. With these in hand, Robinson
then proved that this countably infinite collection of quadratic forms could be
combined into a finitely described class of forms which would exactly express
that a given rational number in lowest terms had no prime factors in its denom-
inator. Thus, she succeeded in showing that Z, and hence N, was expressible
as the set of rational numbers satisfying a first-order property within (Q, +, ∗).
An important corollary of this work is that the axiomatic theory of fields is
also undecidable, which she succeeded in showing by combining her results with
some results of Tarski

It is an incredible coincidence that Pell’s equation would later play in an important role

in Yuri Matiyasevich’s proof that a sequence of roughly exponential growth was Diophantine.

In fact, Robinson’s work on the definability of Z continued to be an oft-returned-to pursuit

throughout her lifetime. She later succeeded (in 1959) in extending her method of undecidabil-
ity to finite algebraic field extensions of (Q, +, ∗). She did this by showing N to be definable
within (A, +, ∗), the ring of algebraic integers, and then by showing A to be definable within
any algebraic field of finite degree over the rationals. The undecidability of T h(A, +, ∗) and

4.2. FOUNDATIONAL WORK OF ROBINSON AND DAVIS

With these results in hand, it is not altogether surprising that Robinson soon

began to work on Hilbert’s Tenth Problem. After all, the notion of a Diophan-
tine set of natural numbers as given in Chapter 1 is equivalent to the property
of being definable in purely existential form in the structure (N, +, ∗). Thus, the
study of Diophantine sets of natural numbers can be seen as a continuation of
Robinson’s work in the definability theory of discrete algebraic structures. Be-
fore diving into her result on exponential Diophantine equations, a note should
be made about the important, lovely foundational work on the problem under-
taken by Martin Davis a few years before Robinson began.

During the 1940s as an undergraduate at City College in New York, Martin

Davis read his teacher Emil Post’s writing on a hallway chalkboard stating that
Hilbert’s Tenth Problem “begs for an unsolvability proof.” This, according to
Davis, began his lifelong obsession with the problem [6]. It should be noted that
a strategy for proving the unsolvability of algorithmic problems had only recently
been ushered in with the foundations of recursion theory, while the notion of
unsolvability proofs had been around for quite some time, although in an ar-
guably somewhat shallow way. As remarked in Chapter 1, to prove in general
the nonexistence of a certain type of algorithm requires one to have a general
theory of algorithms in hand. But, even thirty years away from such a theory,
the ever optimistic Hilbert recognised the possibility of unsolvability and stated
the following in his famous 1900 address:

Occasionally it happens that we seek the solution under insufficient
hypotheses or in an incorrect sense, and for this reason do not suc-
ceed. The problem then arises: to show the impossibility of the solu-
tion under the given hypotheses, or in the sense contemplated. Such
proofs of impossibility were effected by the ancients, for instance
when they showed that the ratio of the hypotenuse to the side of an
isosceles triangle is irrational.

In later mathematics, the question as to the impossibility of cer-
tain solutions plays a preeminent part, and we perceive in this way
that old and difficult problems, such as the proof of the axiom of
parallels, the squaring of [a] circle, or the solution of equations of
the fifth degree by radicals have finally found fully satisfactory and
rigorous solutions, although in another sense than that originally in-
tended.

It is probably this important fact along with other philosophical
reasons that gives rise to [the] conviction (which every mathemati-
cian shares, but which no one has yet supported by a proof) that
every definite mathematical problem must necessarily be susceptible
of an exact settlement, either in the form of an actual answer to the
question asked, or by the proof of the impossibility of its solution
and therewith the necessary failure of all attempts.

In fact, there was already a related negative solution in the air at this time,

as shown by G¨

odel in his famous 1931 paper on the incompleteness of formal

T h(F, +, ∗) follows then in the same manner as T h(Q, +, ∗) above. She obtained even more
results in this direction in 1962 [14] and 1965 [15].

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

systems of arithmetic. It is important to introduce some basic details of this
proof now, as Davis’s foundational work on Diophantine expressability is built
upon them.

In his 1931 paper, G¨

odel showed that given a consistent axiom system T

containing enough arithmetic, one could find a true statement of T not provable
in T of the form ∀x(f (x) 6= 0), where f is a primitive recursive function. G¨

odel

then observed that the relation

f (x) = y

is definable over N through a statement of the following form:

f (x) = y ⇐⇒ (Q

) . . . (Q

m−1

)[P (x, y, z

, . . . , z

m−1

) = 0]

(4.1)

with each Q

being either the universal (∀) or existential (∃) quantifier, and P

a polynomial with integer coefficients

. In 1950 [5], Martin Davis proved that

one can replace the right-hand side of (5) with a definition in which all but one
of the quantifiers Q

are existential, and the one universal quantifier is bounded.

Thus, f in G¨

odel’s theorem is definable in the form:

f (x) = y ⇐⇒ ∃u∀w ≤ u∃z

. . . z

m−1

[P (x, y, u, w, z

, . . . , z

m−1

) = 0]

(4.2)

for a suitable polynomial P . Given this result, the following theorem is easily
shown with some basic recursion theory:

Theorem 1. If the universal quantifier in (6) can be eliminated, then Hilbert’s
Tenth Problem is unsolvable.

Proof. From the work of Church, Turing, and Kleene, we have:

1. Every non-empty recursively enumerable set A ∈ 2

is definable by a

logical equivalence of the form

x ∈ A ⇐⇒ ∃y[f (y) = x]

with f primitive recursive, and

2. One can construct a recursively enumerable set A which is not recursive,

so that the characteristic function of A is undecidable.

Therefore, elimination of the bounded universal quantifier in the form of (6)
would yield

x ∈ A ⇐⇒ ∃z

. . . z

m−1

[P (x, z

, . . . , z

m−1

) = 0]

(4.3)

for a suitable polynomial P , which we know to be exactly the form of a Dio-
phantine set of natural numbers. Thus, an algorithm for deciding the existence
of integer solutions for arbitrary Diophantine equations would yield an algo-
rithm for the characteristic function of A, contradicting the assumption that
membership in A was undecidable.

That is, P is the familiar D we are used to in the definition of a Diophantine equation.

4.3. THE ROBINSON RESULTS

The proof of this important theorem establishing the so-called Davis Nor-

mal Form as expressed by (6) will not be studied here (the interested reader
is referred to [5]). We are now sufficiently prepared to investigate Robinson’s
work on exponential Diophantine equations, as motivated by an enticing though
misguided conjecture of Tarski.

4.3

The Robinson Results

Julia Robinson’s work on Hilbert’s Tenth Problem proper began, like that of
Davis, with a fascinating and simply stated conjecture of her teacher.

Tarski’s Conjecture on Powers of Two
The set of powers of two, {2, 2

, 2

, . . . , 2

, . . .}, is not Diophantine.

Given this problem by Tarski, Robinson began by trying to prove this conjecture
in the affirmative. After failing in this endeavor, Robinson began to consider that
perhaps the opposite was true. Very quickly, she was led to the general problem
of the Diophantine definability of arbitrary recursively enumerable sets [7]. In
her 1952 paper, she proved that given any binary relation in the natural numbers
of roughly exponential growth, R : N × N → 2, the relation IsAP owerOf (x, y)
(meaning x is some non-negative power of y) is existentially definable in the
structure (N, +, ∗, R), where R is of roughly exponential growth means:

∃n∀x∀y[R(x, y) → y < x

] ∧ 6∃k∀x∀y[R(x, y) → y < x

]

(4.4)

where x

is a “supertower” of n x

s, also written x ∗ ∗n, and given by the

following primitive recursive recurrence:

x ∗∗ 0 = 1,
x ∗∗ (n + 1) = x

(x∗∗n)

In addition, she showed that the relations x

= z,

x
y

= z, and x! = y are all

existentially definable in terms of IsAP owerOf , and thus in terms of any R of
roughly exponential growth [7]. This result is a major step towards the negative
solution of Hilbert’s Tenth Problem, and thus we will work now to prove it in
careful detail.

After an interesting remark about Fermat’s Last Theorem, Robinson begins

with some lemmata establishing basic properties of Pell’s equation.

4.3.1

Some Results on Pell’s Equation

Recall that Pell’s equation is the following quadratic Diophantine equation:

− (a

− 1) ∗ y

= 1.

(4.5)

In the following lemmata, a is any natural number greater than 1 and the

other free variables are any natural numbers.

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

Lemma 6.

− (a

− 1) ∗ y

= 1 ⇐⇒ ∃n[x + y ∗

− 1 = (a +

− 1)

Proof. See Landau’s paper [8] for a proof of this theorem.

Lemma 7. If a

and a

are defined by the equation

+ a

0
n

∗

− 1 = (a +

− 1)

then

= 1,

= a,

n+2

= 2a ∗ a

n+1

− a

and

0
0

= 0,

0
1

= 1,

0
n+2

= 2a ∗ a

0
n+1

− a

0
n

Proof. Folklore.

It is useful to recognize that the recurrences from Lemma 7 constitute a

primitive recursive definition for both a

and a

. Note also that this results in

a complete characterization of the solutions of Pell’s equation.

Lemma 8. a

n+1

= a ∗ a

+ a

− 1).

Proof. Follows trivially with rewriting from Lemma 7.

Lemma 9. a

≤ a

≤ (2a)

Proof. Follows trivially with rewriting from Lemma 7.

Lemma 10. a

− a

(a − y) ≡ y

(mod 2ay − y

− 1).

Proof. Follows by induction from Lemma 7.

Lemma 11.

k=0,∃n∈N(k=2n)

n−k

− 1)

k/2

and

0
n

k=1,∃n∈N(k=2n+1)

n−k

− 1)

(k−1)/2

Proof. Follows trivially with rewriting from the Binomial Theorem and Lemmas
7 - 10.

4.3. THE ROBINSON RESULTS

Lemma 12.

≡ na

n−1

(mod a

− 1), hence a

≡ n (mod a − 1).

Proof. Follows immediately from Lemma 11.

Lemma 13. Let Ψ(a, u) be the Diophantine relation defined by the following
logical equivalence:

Ψ(a, u) ⇐⇒ ∃x, y[x

− (a

− 1)(a − 1)

= 1 ∧ x > 1 ∧ a > 1 ∧ u = ax].

Then

Ψ(a, u) ⇒ u ≥ a

and

a > 1 ⇒ ∃u(Ψ(a, u) ∧ u < a

Proof. By Lemma 12, u = ax ≥ a ∗ a

a−1

. Thus, we obtain the first conclusion

by Lemma 9. On the other hand, u = a × a

a−1

satisfies Ψ(a, u) and by Lemma

9 , a ∗ a

a−1

≤ a ∗ (2a)

a−1

< a

Lemma 14. If x > 1 and a > x

, then

≤ (ax)

< a

+ 1).

Proof. By Lemma 11,

k=0,∃n∈N(k=2n)

(ax)

n−k

− x

)

k/2

and

(ax)

k=0,∃n∈N(k=2n)

(ax)

n−k

− 1)

k/2

Hence a

≤ (ax)

. Observe that

(ax)

/(a

) ≤ {(a

− 1)/(a

− x

)}

n/2

≤ (1 − 1/a

)

−n

and

(1 − 1/a

)

> 1 − n/a

> 1 − 1/a ≥ 1 − 1/(x

+ 1).

Therefore,

≤ (ax)

< a

+ 1).

Lemma 15. If x > 1 and a > x

, then

≤ (ax)

≤ a ∗ a

⇐⇒ m = n.

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

Proof. From Lemma 14 and the assumption that a > x

, we have

≤ (ax)

≤ a ∗ a

Since (ax)

is an increasing function of m, it is sufficient to show that

(ax)

n−1

< a

and

(ax)

n+1

> a ∗ a

By applying Lemma 14 with n replaced by n − 1, we obtain

(ax)

n−1

< a ∗ a

n−1

≤ a

Also,

(ax)

n+1

> ax ∗ (ax)

> a ∗ a

4.3.2

Exponentiation

We will now show that the relation, Expt(x, y, z), meaning x = y

, is exis-

tentially Diophantine definable in terms of any relation of roughly exponential
growth.

Lemma 16. There is an existential Diophantine definition of a relation σ(x, y)
satisfying

σ(x, y) → y < x

(4.6)

and

6 ∃n∀xy(σ(x, y) ⇒ y < x

(4.7)

that is definable in terms of any relation φ(v, u) of roughly exponential growth.

Proof. We reason by cases. Case I: There is k s.t. φ(u, v) ⇒ v < u

. We let

σ(x, y) be defined by the equivalence

σ(x, y) ⇐⇒ ∃v(φ(x, v) ∧ y

≤ v),

and thus σ(x, y) satisfies (9) and (10).

Case II: φ(u, v) ⇒ v < (u ∗∗ n) and there is no k s.t. φ(u, v) ⇒ v < u

. We

show that given φ(u, v), we can existentially define a relation φ

(u, v) s.t. the

following both hold:

(u, v) ⇒ v < u∗∗(n − 1),

(4.8)

6 ∃m(φ

(u, v) ⇒ v < u

(4.9)

Then, either φ

satisfies the condition of Case I, or by Case II, we can define φ

s.t. the following both hold:

(u, v) ⇒ v < u∗∗(n − 2),

(4.10)

6 ∃m(φ

(u, v) ⇒ v < u

(4.11)

4.3. THE ROBINSON RESULTS

By iterating this process, we must eventually reach some n ∈ N s.t. φ

satisfies the condition of Case I. Hence, a relation σ(x, y) satisfying (9) and (10)
can be existentially Diophantine defined in terms of a relation φ(u, v) of roughly
exponential growth.

It suffices now to prove that given a relation φ(u, v) of roughly exponential

growth satisfying the conditions of Case II, we can define existentially in terms
of φ(u, v) a relation φ

(u, v) satisfying (9) and (10).

Let φ

(u, v) be defined by the following logical equivalence:

(u, v) ⇐⇒ ∃a(Ψ(a, u) ∧ φ(a, v)),

where Ψ is the relation of Lemma 13. Clearly,

(u, v) ⇒ v < (u∗∗(n − 1)),

Ψ(a, u) ⇒ u ≥ a

and

φ(a, v) ⇒ v < (a ∗ ∗n) < ((a

) ∗ ∗(n − 1)) ≤ (u ∗ ∗(n − 1)).

Also, there is no m s.t. φ

(u, v) ⇒ v < u

, as for each m, there exists a, u, v

s.t. the following both hold:

φ(a, v) ∧ v ≥ a

2ma

Ψ(a, u) ∧ u < a

so that v ≥ (a

)

> u

With the existence of the relation σ(x, y) as governed by rules (9) and (10)

existentially Diophantine definable in terms of any φ(u, v) of roughly exponential
growth, we may now turn to proving the main result.

Theorem 2. The relation Expt(x, y, z) governed by the logical equivalence

Expt(x, y, z) ⇐⇒ x = y

is existentially Diophantine definable in terms of any relation φ(u, v) of roughly
exponential growth.

Proof. By Lemma 14,

(y > 1 ∧ a > y

) ⇒ (x = y ⇐⇒ a

x ≤ (ay)

< a

(x + 1)).

(4.12)

By Lemma 10,

(y > 1 ∧ a > y

) ⇒ (u = (ay)

⇐⇒ Ω(v))

(4.13)

where Ω(u) is the formula

∃v(u

− (a

− 1)v

= 1 ∧ a

≤ u ≤ a ∗ a

(4.14)

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

Hence,

(1 < x < a ∧ y > 1 ∧ a > y

) ⇒ [x = y

⇐⇒ χ(u, v)]

(4.15)

where χ(u, v) is the formula

∃u, v(u

− (a

− 1)v

= 1 ∧ a

x ≤ u < a

(x + 1)).

(4.16)

The requirement that a > y

in the hypothesis of (15) may be replaced by the

stronger condition

∃b, c(b > y ∧ b > z ∧ a > c ∧ Ψ(b, c)),

(4.17)

where Ψ is the existentially Diophantine definable relation of Lemma 13. Hence
from (18) we may obtain an existential Diophantine definition of Expt(x, y, z)
in terms of the relation r = a

. Precisely,

x = y

⇐⇒

((z = 0 ∧ x = 1) ∨ (z > 0 ∧ y < 2 ∧ x = y)

∨(y > 1 ∧ x > 1 ∧ z > 0 ∧ β(a, b, c, u, v)))

where β(a, b, c, u, v) is the formula

∃a, b, c, u, v(x < a ∧ b > y ∧ b > z ∧ a > c ∧ Ψ(b, c)

∧u

− (a

− 1)v

= 1 ∧ a

x ≤ u < a

(x + 1)).

It would therefore suffice to find an existential Diophantine definition of the
relation r = a

in order to obtain an existential Diophantine definition of

Expt(x, y, z). Robinson however did not do this. Instead, she proceeded to work
via an application of Lemma 12.

By Lemma 12,

(1 < r < a

∧ 0 < z < a) ⇒

(r = a

⇐⇒ ∃s(r

− (a

− 1)(z + s(a − 1))

= 1)).

And so we see that we can make use of σ(x, y). To utilize the previous implication
to define r = a

, we must limit the size of r. For some values of a, this can be

done with σ(x, y). Namely,

[r ≤ d ∧ σ(a, d)] ⇒ r < a

< a

Conversely,

|{a|∃d(σ(a, d))}| = ω.

Fortunately, we need only define a

for a sufficiently large value of a. We thus

obtain

(x > 1 ∧ y > 1 ∧ z > 0) ⇒ (x = y

⇐⇒ ∆(a, b, c, d, u, v, r, s))

where ∆(a, b, c, d, u, v, r, s) is the formula

∃a, b, c, d, u, v, r, s{x < a ∧ b < y ∧ b > z ∧ Ψ(b, c)

∧r > 1 ∧ a > c ∧ r ≤ d ∧ σ(a, d) ∧ u

− (a

− 1)v

= 1

∧rx ≤ u < r(x + 1) ∧ r

− (a

− 1)(z + s(a − 1))

= 1}.

4.3. THE ROBINSON RESULTS

Therefore, Expt(x, y, z) is existentially Diophantine definable in terms of any
relation σ(x, y) satisfying (9) and (10). Thus it follows that x = y

is existentially

Diophantine definable in terms of any relation φ of roughly exponential growth.

Robinson then proves the following two theorems, whose proofs we shall

omit.

Theorem 3. Expt(x, y, z) is existentially Diophantine definable in terms of the
relation IsAP owerOf (x, y).

Theorem 4. The relations r =

n
k

, y = x!, |x| = y, x|y, and P rime(p) (“p

is prime”) are all existentially Diophantine definable in terms of Expt(x, y, z).

Robinson’s paper culminates in the following result, inching mathematics one

very important step closer to the negative solution of Hilbert’s Tenth Problem:

Theorem 5. Given a recursively enumerable relation Φ(x

, . . . , x

n−1

) expressed

in Davis Normal Form,

∃u∀v ≤ u(σ(x

, . . . , x

n−1

, u, v))

where σ is an existentially Diophantine relation, σ may also be taken to be
primitive recursive.

Proof. Expand the Davis Normal Form of Φ(x

, . . . , x

n−1

), eliminating σ, yield-

ing

Φ(x

, . . . , x

n−1

) ⇐⇒

∃u∀v ≤ u∃y

, . . . , y

k−1

(D(x

, . . . , x

n−1

, u, v, y

, . . . , y

k−1

) = 0).

Observe that this version of Davis Normal Form is equivalent to the form intro-
duced in (6) of Section 3.2. Thus it follows that

Φ(x

, . . . , x

n−1

) ⇐⇒

∃u, s∀v ≤ u∃y

, . . . , y

k−1

≤ s(D = 0).

The relation

∃y

, . . . , y

≤ s(D = 0)

is primitive recursive in addition to being existential Diophantine definable,
since G¨

odel [7] proved that in an arithmetical definition of a relation, if all

of the bound variables are bounded by primitive recursive functions, then the
relation being defined is also primitive recursive. Also,

∃u, v∀v ≤ u∃y

, . . . , y

≤ s(D = 0) ⇐⇒

∃z∀v ≤ z{∃u, s ≤ z∃y

, . . . , y

k−1

≤ s[z = (u + s)

+ u ∧ (D = 0 ∨ v > u)]}.

This is easily verified by noting that (u + s)

+ u is univalent. The expression

immediately above is both primitive recursive and existentially Diophantine
definable. Hence it follows that every recursively enumerable relation can be
expressed in a modified version of Davis Normal Form, where the purely ex-
istential Diophantine fragment of the definition is taken to be an existentially
Diophantine definable primitive recursive relation.

We write D to mean D(x

, . . . , x

n−1

, u, v, y

, . . . , y

k−1

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

4.4

Every R.E. Set is Exponential Diophantine

As Feferman [7] notes, the full significance of these results Robinson published in
1952 was not to emerge for close to a decade. Sometime around 1960, Robinson
received a draft of a paper by Davis and Putnam in which they proved the
following beautiful theorem.

Theorem 6. If there exist arbitrarily long arithmetic progressions consisting
only of primes, then every recursively enumerable set is definable as an exis-
tential exponential Diophantine relation. That is, if arbitrarily long arithmetic
progressions of primes exists, then every r.e. set is existentially definable in
(N, +, ∗, Expt).

Robinson succeeded in eliminating the hypothesis involving arithmetic pro-

gressions of primes (which would remain unproved for decades), and simplified
the results in many ways [7]. This resulted in the 1962 paper of Davis, Put-
nam, and Robinson titled The Decision Problem for Exponential Diophantine
Equations [7]. It is instructive to work through the proof of their main result,
beginning with a preliminary lemma establishing the existential exponential
Diophantine definability of a useful relation.

Lemma 17.

k≤K

(a + bk) is exponential Diophantine.

Proof.

k≤K

(a + bk) =

a/b+K

K!. Recall Theorem 4.

Lemma 18. Let D(x, y, k, z

, . . . , z

m−1

) be any polynomial with integer coeffi-

cients. Let G(x, y) be any polynomial

s.t. G(x, y) ≥ y and

∀k ≤ y∃z

≤ y, . . . , z

m−1

≤ y(|D(x, y, k, z

, . . . , z

m−1

)| ≤ G(x, y)).

Then,

[∀k ≤ y∃z

≤ y, . . . , z

m−1

≤ y(D(x, y, k, z

, . . . , z

m−1

) = 0)]

⇐⇒

{∃c, t, a

, . . . , a

m−1

(t = G(x, y)! ∧ 1 + ct =

k≤y

(1 + kt)

∧(1 + ct)|D(x, y, c, a

, . . . , a

m−1

) ∧ ∀i ≤ m[(1 + ct)|

j≤y

− j)])}.

Proof. (⇐) Let k ∈ N s.t. 0 ≤ k ≤ y ∧ ∃p

(P rime(p

) ∧ p

|(1 + kt)). Then, let

Rem(a

, p

) = z

for i = 1, . . . , m. It is sufficient to show that

D(x, y, k, z

, . . . , z

) = 0

and

0 < z

≤ y

As Davis, Putnam, and Robinson note, if deg(D) = n s.t. n > 0, then one can take, for

example, G(x, y) = cx

where c is the sum of the absolute values of the coefficients of D.

4.4. EVERY R.E. SET IS EXPONENTIAL DIOPHANTINE

for all i ≤ m. Since p

j≤y

− j), it follows that p

− j for some j with

1 ≤ j ≤ y. Thus, 1 ≤ z

= Rem(a

, p

) ≤ y. Furthermore, (p

, t) = 1 and

t = G(x, y)!, so p

> G(x, y) ≥ y. Hence, as 1 ≤ z

≤ y, it follows that

|D(x, y, k, z

, . . . , z

)| ≤ G(x, y) < p

From the equation which determines c, we have 1 + ct ≡ 0 (mod 1 + kt). Hence,
c ≡ k (mod 1 + kt), and finally, c ≡ k (mod p

). Therefore

D(x, y, k, z

, . . . , z

) ≡ F (x, y, c, a

, . . . , a

) (mod p

) ≡ 0( mod

Hence D(x, y, k, z

, . . . , z

) = 0 as was to be proved.

(⇒) Suppose that for every k ≤ y, there are z

, . . . , z

≤ y s.t.

D(x, y, k, z

, . . . , z

) = 0.

We show that the right side of the equivalence can be satisfied. Let t and c be
determined by

{∃c, t, a

, . . . , a

m−1

(t = G(x, y)! ∧ 1 + ct =

k≤y

(1 + kt)

∧(1 + ct)|D(x, y, c, a

, . . . , a

m−1

) ∧ ∀i ≤ m[(1 + ct)|

j≤y

− j)])}.

Then, for every k, j ≤ y s.t. k 6= j, (1+kt, 1+jt) = 1. This is verified by observing
that if a prime p divides both (1 + kt) and (1 + jt), then p divides (k − j)t.
But, any prime dividing k − j also divides t, as t = G(x, y)! and G(x, y) ≥ y
by assumption. Hence p|t, yielding p 6 |(1 + kt), a contradiction. Thus, 1 + kt
and 1 + jt are relatively prime. Therefore, by the Chinese Remainder Theorem,
there are a

, . . . , a

m−1

s.t.

≡ z

(mod 1 + kt)

for k ≤ y and i ≤ m. We will show that these a

, . . . , a

m−1

satisfy the RHS of

the equivalence. As before, c ≡ k (mod 1 + kt), and so

D(x, y, c, a

, . . . , a

m−1

) ≡ D(x, y, k, z

, . . . , z

) (mod 1 + kt) ≡ 0

(mod 1 + kt)

for k ≤ y. Since all of the moduli are relatively prime, it follows that

k≤y

(1 + kt)|D(x, y, c, a

, . . . , a

m−1

But it then follows that

1 + kt|a

− z

where z

≤ y. Hence,

1 + kt|

j≤y

− j)

CHAPTER 4. EXPONENTIAL DIOPHANTINE EQUATIONS

for every k ≤ y. But since these divisors are all relatively prime, we obtain

k≤y

(1 + kt)|

j≤y

− j)

for every i ≤ m. Thus, the RHS of the equivalence holds, and the lemma follows
by Theorem 4.

And at last, we are now prepared to prove the main D-P-R result.

Theorem 7. Every recursively enumerable set is existentially exponential Dio-
phantine definable.

Proof. Recall that every recursively enumerable set S may be expressed in the
form

x ∈ S ⇐⇒ ∃y∀k ≤ y∃z

≤ y, . . . , z

m−1

≤ y(D(x, y, k, z

, . . . , z

m−1

) = 0)

where D is a polynomial with integer coefficients. From this we see that to prove
the main theorem, it suffices only show that every relation of the form

∀k ≤ y∃z

≤ y, . . . , z

m−1

≤ y(D(x, y, k, z

, . . . , z

m−1

) = 0)

is exponential Diophantine. But this follows from Lemma 17 and Lemma 18.
Therefore, every recursively enumerable set is existentially exponential Diophan-
tine definable.

This result extends readily to arbitrary recursively enumerable relations

straightforwardly.

Theorem 8. Every recursively enumerable relation σ(x

, . . . , x

n−1

) is existen-

tially exponential Diophantine definable.

Proof. Let the set R be defined by the equivalence:

r ∈ R ⇐⇒ ∃x

, . . . , x

n−1

(r = 2

· · · p

n−1

∧ σ(x

, . . . , x

n−1

))

where p

is the ith prime. If σ is a recursively enumerable relation, then R is

a recursively enumerable set. Hence R is existenially exponential Diophantine
definable. But, by the Fundamental Theorem of Arithmetic, we have

σ(x

, . . . , x

n−1

) ⇐⇒ 2

· · · p

n−1

∈ R.

And so it follows that σ is also an existentially exponential Diophantine relation.

Chapter

Hilbert’s Tenth Problem is
Unsolvable

It is with Theorems 7 and 8 that work towards the negative solution of Hilbert’s
Tenth Problem essentially rested for nearly a decade. Let us recapitulate the
state of things thus far, so as to better appreciate the role Matiyasevich’s final
piece was soon to play.

5.1

Rough Exponentiation as the Missing Link

With Theorem 1, it was established that if every recursively enumerable set is
Diophantine, then Hilbert’s Tenth Problem is unsolvable. With Theorems 7 and
8, it has been shown that every recursively enumerable set is existentially defin-
able via an exponential Diophantine equation. Thus, to prove Hilbert’s Tenth
Problem unsolvable, it suffices to prove that exponentiation is Diophantine. By
Theorem 2, this would follow from the existence of any Diophantine relation of
roughly exponential growth, and thus the unsolvability of Hilbert’s Tenth Prob-
lem could be established by exhibiting such an equation. This is exactly what
Yuri Matiyasevich was soon to do in 1970.

5.2

Historical Interlude: Spirit of the Time

Before arriving at Matiyasevich’s proof, it is a wonderful experiece to read some
notes of Martin Davis as to the spirit of work around the problem in the 1950s
and early 1960s, before the relative lull from 1962-1970 as the world, unbe-
knownst to most of its inhabitants, waited patiently for Matiyasevich to prove
his theorem. The following is quoted directly from Martin Davis [5].

During the 1960s I often had the occasion to lecture on Hilbert’s
Tenth Problem. At that time it was known that the unsolvability
would follow from the existence of a single Diophantine equation

CHAPTER 5. HILBERT’S TENTH PROBLEM IS UNSOLVABLE

that satisfied a condition that had been formulated by Julia Robin-
son. However, it seemed extraordinarily difficult to produce such an
equation, and indeed, the prevailing opinion was that one was un-
likely to exist. [...] Inevitably, during the question period I would
often be asked for my own opinion as to how matters would turn
out, and I had my reply ready:

“I think that Julia Robinson’s hypothesis is true, and it
will be proved by a clever young Russian.”

[...] I met Julia Robinson at the 1950 International Congress of Math-
ematicians in Cambridge, Massachusetts, immediately after complet-
ing my doctorate. She had approached Hilbert’s Tenth Problem from
a direction opposite to mine. Where I had tried to simplify the arith-
metic representation of arbitrary recursively enumerable sets, she
had been trying to produce Diophantine definitions for various spe-
cific sets and especially for the exponential function. She had intro-
duced what was to become her famous “hypothesis” and shown that
under that assumption the exponential function is in fact Diophan-
tine. It’s been said that I told her that I doubted that her approach
would get very far, surely one of the more foolish statements I’ve
made in my life.

During the summer of 1957, there was an intensive five week “Insti-
tute for Logic” at Cornell University attended by almost all Ameri-
can logicians. Hilary Putnam and I together with our families were
sharing a house in Ithaca, and he and I began collaborating, al-
most without thinking about it. Hilary proposed the idea of using
the Chinese Remainder Theorem coding one more time to code the
sequences whose existence was asserted by the bounded universal
quantifier in the Davis Normal Form. My first reaction was skepti-
cal. But, as pointed out (in [7]), the Chinese Remainder Theorem
provides a “unique opportunity” because of the fact that polynomials
preserve congruences. In fact, we were able to obtain two particular
sets with quite simple definitions concerning which we were able to
show that their being Diophantine would imply the same for all re-
cursively enumerable sets.

Hilary and I resolved to seek other opportunities to work together,
and we were able to obtain support for our research during the three
summerts of 1958, 1959, and 1960. We had a wonderful time. We
talked constantly about everything under the sun. Hilary gave me a
quick course in classical European philosophy, and I gave him one
in functional analysis. We talked about Freudian psychology, about
the current political situation, about the foundations of quantum
mechanics, but mainly we talked mathematics. It was during the
summer of 1959 that we did our main work together on Hilbert’s
Tenth Problem. In a recent letter, Hilary wrote:

What I remember from that summer is not so much the
mathematical details as the sheer intensity with which we

5.2. HISTORICAL INTERLUDE: SPIRIT OF THE TIME

worked. I have never in my life been so absorbed in a
mathematical problem, and I’m sure the same was true
of you. Our method, as I remember it, was that one of
us would propose an attack and we would both work on
it together, writing on the board and arguing with each
other, making suggestions, etc., until something came of it
or we reached a dead end. I could not let go of the problem
even at night; this is the only time when I regularly stayed
up to four in the morning... I think we felt in our bones
that the problem would yield to our approach; otherwise,
I can’t explain the sense of mounting excitement.

Our “approach” was still to apply the Chinese Remainder Theorem
to Davis Normal Form. But this time, we were combining this attack
with Julia Robinson’s methods, attempting to see if by permitting
exponentiation in our Diophantine definitions we could eliminate the
troublesome bounded universal quantifier. The problem in using the
Chinese Remainder Theorem was the need for suitable moduli, rel-
atively prime in pairs. G¨

odel’s method was to obtain such moduli

in an arithmetic progression, and hence definable in Diophantine
terms. We found ourselves with the need to find exponential Dio-
phantine definitions for sums of the reciprocals of the terms of a
finite arithmetic progression as well as of the product of such terms.
To deal with the second problem, we used binomial coefficients with
rational numerators, for which we could find exponential Diophan-
tine definitions extending Julia Robinson’s methods, but requiring
the binomial theorem with rational exponents, an infinite power se-
ries expansion. For the first, we used a rather elaborate (as it turned
out, quite unnecessary) bit of elementary analysis, involving the Tay-
lor expansion of the Gamma function. Even with all that, we still
couldn’t get the full result we wanted. We needed to be able to assert
that if one of our moduli was a divisor of a product that it had to
necessarily divide one of the factors. And this seemed to require that
the moduli be not only relatively prime in pairs, but actual prime
numbers. In the end, we were forced to assume the hypothesis that
there are arbitrarily long arithmetic progressions of prime numbers,
in order to prove that every recursively enumerable set has an expo-
nential Diophantine definition.

We sent our results to Julia Robinson, and she responded shortly
thereafter saying:

I am very pleased, surprised, and impressed with your re-
sults on Hilbert’s Tenth Problem. Quite frankly, I did not
think that your methods could be pushed further...

I believe I have succeeded in eliminating the need for [the
assumption about primes in arithmetic progression] by ex-
tending and modifying your proof. I have this written out
for my own satisfaction, but it is not yet in shape for any-

CHAPTER 5. HILBERT’S TENTH PROBLEM IS UNSOLVABLE

one else.

[...] With the result that every recursively enumerable set has an
exponential Diophantine definition combined with Julia Robinson’s
earlier work on Diophantine definitions of the exponential function,
it was now clear that my “daring hypothesis” of the equivalence of
the two notions, recursively enumerable set and Diophantine set,
was entirely equivalent to the much weaker hypothesis (now called
JR) that Julia Robinson had proposed ten years earlier that one sin-
gle Diophantine equation could be found whose solutions satisfied a
simple condition

. [...]

At this time [mid-1960s], Julia had become rather pessimistic about
JR and, for a brief period, she actually worked towards a positive
solution of Hilbert’s Tenth Problem. A letter from her dated April
1968 responding to my report [on a certain Diophantine equation]
said:

I have enjoyed studying it, but my faith in JR still hasn’t
been restored. However, for the first time. I can see how
it might be proved. Indeed, maybe your equation works,
but it seems to need an infinite amount of good luck!

Early in 1970, a telephone call from my old friend Jack Schwartz in-
formed me that the “clever young Russian” I had predicted had ac-
tually appeared. Julia Robinson sent me a copy of John McCarthy’s
notes on a talk that Grisha Tseitin had given in Novosibirsk on
the proof by the twenty-two-year-old Yuri Matiyasevich of the Julia
Robinson hypothesis...

With the stage now set, let us commence to examining Matiyasevich’s proof

that a Diophantine equation of roughly exponential growth exist, and thus prove
the unsolvability of Hilbert’s Tenth Problem.

5.3

Exponentiation is Diophantine

Recall the well-known Fibonacci sequence, F (n), given by the following recur-
rence:

F (0) = 1,

F (1) = 1,

F (n + 2) = F (n + 1) + F (n).

Now, for technical convenience that will become apparent, we define an “off-

set by one” variant of F (n), Φ(n), as follows:

Φ(0) = 0,

That is, the property of being of roughly exponential growth.

5.3. EXPONENTIATION IS DIOPHANTINE

Φ(1) = 1,

Φ(n + 2) = Φ(n + 1) + Φ(n).

Matiyasevich considers the predicate P(u, v) governed by the following equiv-

alence:

P(u, v) ⇐⇒ v = Φ(2u).

(5.1)

He used for his conditions of roughly exponential growth the following:

1. P(u, v) ⇒ v ≤ u

2. ∀k∃u, v(P(u, v) ∧ u

< v).

It is readily seen that 1 and 2 imply the conditions Julia Robinson required

for a function to be of roughly exponential growth. It remains then to show that

P(u, v) indeed meets conditions 1 and 2, and then P(u, v) must be shown to be
existential Diophantine definable. That 1 and 2 hold of P(u, v) is readily seen
from a rather elementary property of Φ(n). It is amazing that this property of
the Fibonacci sequence - a very well studied function - was not discovered until
Matiyasevich made the leap [10].

Lemma 19. The following property holds of Φ(n):

∀n > 2(Φ(n) ≡ 0 (mod Φ

(n)) ⇐⇒ (m ≡ 0 (mod n· Φ(n)))).

Proof. The reader should first become convinced of the following list of propo-
sitions, the most difficult of which requires a somewhat tricky double induction:

gcd(Φ(n), Φ(n + 1)) = 1,

gcd(Φ(n), Φ(m)) = Φ(gcd(a, b)),

k > 0 ⇒ Φ(kn) = Φ(n)· Φ(n(k − 1) + 1) + Φ(n − 1)· Φ(n(k − 1)),

and

Φ(xy) ≡ 0 (mod Φ(x)),
k > 1 ⇒ {Φ(kn) ≡ k(Φ(n)Φ

k−1

(n + 1) (mod Φ

(n)))

∧

(∀N ∈ N Φ(kn + 1) ≡ N (mod Φ

(n))

⇐⇒

(n + 1) ≡ N (mod Φ

(n)))}.

That P(u, v) is of roughly exponential growth is thus seen to follow.

With Lemma 19, it now suffices to show that P(u, v) is existentially Diophan-

tine definable. Matiyasevich does so by exhibiting a Diophantine representation
for P(u, v) explicitly.

Theorem 9. P(u, v) is existentially Diophantine definable.

CHAPTER 5. HILBERT’S TENTH PROBLEM IS UNSOLVABLE

Proof. In order for P(u, v) to hold, it is necessary and sufficient that there exist
numbers g, h, l, m, x, y, z s.t.

u ≤ v ≤ 1,

(5.2)

− lx − z

= 1,

(5.3)

− gh − h

= 1,

(5.4)

|g,

(5.5)

1|(m − 2),

(5.6)

(2h + g)|(m − 3),

(5.7)

− mxy + y

= 1,

(5.8)

l|(x − u),

(5.9)

(2h + g)|(x − v).

(5.10)

By Theorem 4, we see that (23)-(31) are all existentially Diophantine definable
properties, and by Lemma 1 they may all be combined into a single Diophantine
equation. Thus, a relation of roughly exponential growth is Diophantine, and
therefore exponentiation is Diophantine as well.

This leads us at last to the following result:

5.4

Unsolvability of Hilbert’s Tenth Problem

Theorem 10. Every recursively enumerable set is Diophantine, and Hilbert’s
Tenth Problem is unsolvable.

Proof. Follows from Theorems 8, Lemma 19, and Theorem 9.

And thus we see that one can never find an algorithm that will correctly state

whether or not an arbitrary Diophantine equation has solutions in the integers.
In addition to this negative solution, a miraculous positive event has occurred
- we have in fact shown that the notion of a recursively enumerable set from
logic and the notion of a Diophantine set from number theory are one and the
same. Thus, any set of natural numbers that could be listed by an algorithm is
Diophantine, and it then follows from recursion theory that there exists, among
many other interesting things, a universal Diophantine equation of a fixed de-
gree that can simulate every other Diophantine equation of arbitrary degree.
This is identical to the notion of a universal Turing machine from computability
theory. In fact, such a Diophantine equation has been constructed by Chaitin
by encoding as a Diophantine equation a Turing-complete interpreter for a frag-
ment of the programming language LISP [3]. Chaitin’s equation has around
17,000 variables and takes up around 200 pages of modern teletype print, but it
can be “executed” on modern computer hardware. Recently, Matiyasevich has
proved that there exists such an equation in only nine variables. It is quite mov-
ing to reflect upon the fact that, in principle, one could understand everything
knowable about the entire world of Diophantine equations by only studying a
particular universal Diophantine equation in nine unknowns. What a marvel.

Chapter

New Results on Multiplicative
Definability

We now prove two new very elementary results on multiplicative definability
obtained by the author. By the phrase “multiplicative definability,” the author
is referring to a class of arithmetic definitions expressed with function symbols
that do not explicitly contain the addition function, ‘+’. Whereas Diophan-
tine sets are existentially definable in (N, +, ∗), one may ask instead about the
sets definable in (N, ∗), and see if any meaningful separation theorems might
be proved. This problem is intriguing from a Diophantine perspective, as sets
existentially definable in (N, ∗) have a close relationship to those recursively
enumerable sets which happen to be definable by a Diophantine monomial. It
would be quite nice to understand these.

6.1

Results on Definability Theory of (N, ∗, !)

Our three main results are:

1. Every recursively enumerable set is first-order definable in (N, ∗, !).

2. If factorial is first-order definable purely in terms of multiplication and

divisibility (which we will prove is equivalent to factorial being first-order
definable in (N, ∗)), then every recursively enumerable set is arithmetically
definable in the form:

) . . . (Q

i−1

)

((M

0,0

≈ M

0,0

∨ . . . ∨ M

0,d(0)

≈ M

0,d(0)

)∧

.
.
.
∧(M

j−1,0

≈ M

j−1,0

∨ . . . ∨ M

j−1,d(j−1)

≈ M

j−1,d(j−1)

))

where each M

x,d(x)

, M

x,d(x)

is a monomial in Z[x

, . . . , x

k−1

], each ≈

is either = or 6=, each Q

is either ∀ or ∃, each v

is a variable, and

d : N → N determines the number of disjuncts in each of the j conjuncts of

42 CHAPTER 6. NEW RESULTS ON MULTIPLICATIVE DEFINABILITY

the quantifier-free matrix. We say such a formula is in MCNF, or monomial
conjunctive normal form.

3. If factorial is definable in (N, ∗), then (N, ∗) is undecidable.

6.2

Every R.E. Set is F.O. Definable in (N, ∗, !)

Theorem 11. Every recursively enumerable set is first-order definable in (N, ∗, !).

Proof. By a result of Boolos and Jeffrey [1], it suffices to show that the successor
relation, x = y + 1, is first-order definable in terms of ∗ and !. Consider the
following first-order equivalence:

(x = y + 1)
⇐⇒
∃k∀l(k ∗ l = k)∧
[(y 6= x ∧ x 6= k ∧ (y = k ∨ (∃z(y! ∗ z = x!)))) ∧
6 ∃w((y 6= w ∧ w 6= k ∧ (y = k ∨ (∃u(y! ∗ u = w!)))) ∧
(w 6= x ∧ x 6= k ∧ (w = k ∨ (∃v(w! ∗ v = x!)))))].

That this is a necessary and sufficient condition for x = y + 1 to hold is

verified by observing that this first-order formula in (N, ∗, !) is equivalent to the
sentence

(x = y + 1) ⇐⇒ [(y < x)∧ 6 ∃z(y < z ∧ z < x)].

where < and 1 are given by the following lemmata:

Lemma 20. 1 is definable in (N, ∗).

Proof. ∀x(x = 1 ⇐⇒ ∀y(x ∗ y = y)).

Lemma 21. x < y is definable in (N, ∗, !).

Proof. Consider

(x < y) ⇐⇒ [(x 6= y) ∧ (y 6= 0) ∧ ((x = 0) ∨ (x!|y!))],

where 0 and | are given by the following lemmata:

Lemma 22. 0 is definable in (N, ∗).

Proof. ∀x(x = 0 ⇐⇒ ∀y(x ∗ y = x)).

Lemma 23. x|y is definable in (N, ∗).

Proof. ∀x, y(x|y ⇐⇒ ∃z(x ∗ z = y)).

Thus x < y is definable in (N, ∗).

Thus, x = y + 1 is definable in (N, ∗, !).

6.3. MULTIPLICATIVE CONJUNCTIVE NORMAL FORM

6.3

Multiplicative Conjunctive Normal Form

And now our second theorem:

Theorem 12. If factorial is first-order definable purely in terms of multipli-
cation and divisibility, then every recursively enumerable set is arithmetically
definable in the form:

) . . . (Q

i−1

)

((M

0,0

≈ M

0,0

∨ . . . ∨ M

0,d(0)

≈ M

0,d(0)

)∧

.
.
.
∧(M

j−1,0

≈ M

j−1,0

∨ . . . ∨ M

j−1,d(j−1)

≈ M

j−1,d(j−1)

))

where each M

x,d(x)

, M

x,d(x)

is a monomial in Z[x

, . . . , x

k−1

], each ≈ is either

= or 6=, each Q

is either ∀ or ∃, each v

is a variable, and d : N → N determines

the number of disjuncts in each of the j conjuncts of the quantifier-free matrix.
We say such a formula is in MCNF, or monomial conjunctive normal form.

Proof. We first note that it suffices to show that every primitive recursive func-
tion can be arithmetically defined in MCNF. By G¨

odel’s well-known result, ev-

ery primitive recursive function f (x) is arithmetically definable in the following
form:

f (x) = y ⇐⇒ (Q

) . . . (Q

m−1

)[P (x, y, z

, . . . , z

m−1

) = 0]

where P is a polynomial with integer coefficients. By Theorem 11, we may
rewrite the quantifer-free Diophantine equation

P (x, y, z

, . . . , z

m−1

) = 0

into an equivalent quantified formula, F, s.t. F only contains ∗ and ! as its non-
logical symbols. By assumption, ! is arithmetically definable in (N, ∗), and thus
a new formula G equivalent to F may be obtained by replacing each occurence of
! with its multiplicative definition. Then, by the Prenex Normal Form Theorem,
the resulting formula

) . . . (Q

m−1

)[G]

may be rewritten into the form

) . . . (Q

i−1

)[K]

where K is quantifier free. Note that each literal in K is either a monomial
equation or a monomial inequation. Finally, by the Conjunctive Normal Form
Theorem, this formula may be rewritten into an equivalent formula of the fol-
lowing form:

) . . . (Q

i−1

)

((M

0,0

≈ M

0,0

∨ . . . ∨ M

0,d(0)

≈ M

0,d(0)

)∧

.
.
.
∧(M

j−1,0

≈ M

j−1,0

∨ . . . ∨ M

j−1,d(j−1)

≈ M

j−1,d(j−1)

))

44 CHAPTER 6. NEW RESULTS ON MULTIPLICATIVE DEFINABILITY

where each M

x,d(x)

, M

x,d(x)

is a monomial in Z[x

, . . . , x

k−1

], each ≈ is either

= or 6=, each Q

is either ∀ or ∃, each v

is a variable, and d : N → N determines

the number of disjuncts in each of the j conjuncts of the quantifier-free matrix.

6.4

Sufficient Condition for Undecidability of T h(N, ∗)

And our final result follows as a trivial corollary to Theorem 11:

Theorem 13. If factorial is definable in (N, ∗), then (N, ∗) is undecidable.

Proof. By Theorem 11 and the fact that non-recursive recursively enumerable
sets exist.

Appendix

Bibliography

1. G.S. Boolos and R.C. Jeffrey, “Computability and Logic,” Third Edition.

Cambridge University Press, 1989. ISBN 0-521-38923-2

2. Alonzo Church, “An unsolvable problem of elementary number theory.”

American Journal of Mathematics, Vol. 58 (1936), pp 345 - 363,

3. G. J. Chaitin, “The limits of mathematics,” chao-dyn/9407003, IBM Re-

search Report RC-19646, July 1994, 270 pp.

4. G. E. Collins “Quantifier Elimination for the Elementary Theory of Real

Closed Fields by Cylindrical Algebraic Decomposition.” Lect. Notes Com-
put. Sci. 33 (1975), pp 134-183.

5. Martin Davis, “Arithmetical problems and recursively enumerable predi-

cates, ” Journal of Symbolic Logic, 1953, vol.18, N1, pp.33-41

6. Martin Davis, Forward to: Yuri Matiyasevich, “Hilbert’s 10th Problem,”

The MIT Press. ISBN-10: 0-262-13295-8

7. Martin Davis, Hilary Putnam, and Julia Robinson, “The Decision Problem

for Exponential Diophantine Equations,” Annals of Mathematics, 1961,
vol.74, N3, pp.425-436

8. Kurt G¨

odel, “ ¨

Uber formal unentscheidbare der Principia Mathematica

und verwandter Systeme, I.”, Monatshefte fr Mathematik und Physik 38
(1931), pp 173-98

9. Solomon Feferman, “Collected Works of Julia Robinson,” ISBN-13: 978-0-

8218-0575-6 Publication date: 28 November 1996, American Mathematical
Society

10. Edmund Landau, “Vorlesungen ¨

uber Zahlentheorie,” vol. 1, pp. 47-64

11. Yuri Matiyasevich, “Hilbert’s 10th Problem,” The MIT Press. ISBN-10:

0-262-13295-8

APPENDIX A. BIBLIOGRAPHY

12. Yuri Matiyasevich, “Enumerable sets are Diophantine,” Doklady Akademii

Nauk SSSR, 191, pp. 279-282, 1970. English translation in Soviet Mathe-
matics. Doklady, vol. 11, no. 2, 1970

13. Bjorn Poonen, “Why number theory is hard,” Lecture at Univ. Califor-

nia at Berkeley, March 15, 2007, URL: http://math.berkeley.edu/ poo-
nen/nt is hard.pdf

14. Julia Robinson, “On the decision problem for algebraic rings,” Studies

in Mathematical Analysis and Related Topics, (D. Gilbarg et al, eds.),
Stanford Univ. Press, Stanford, 1962, pp. 297-304

15. Julia Robinson, “The decision problem for fields,” The Theory of Mod-

els: Proceedings of the 1963 International Symposium at Berkeley (J. W.
Addison et al., eds.), North-Holland, Amsterdam, 1965, pp. 299-311

16. Alan Turing, “On computable numbers, with an application to the Entschei-

dungsproblem.” Proceedings of the London Mathematical Society, Series
2, 42 (1936), pp 230 - 265. Online version. Errata appeared in Series 2, 43
(1937), pp 544 - 546.

Wyszukiwarka

Podobne podstrony:
U S Soldiers Returning From World War II and Their Problems
19 Old people and their problems
Foucault Discourse and Truth The Problematization of Parrhesia (Berkeley,1983)
Herbs And Their Magickal Properties
MoS2 Preparation and their characterization
54 767 780 Numerical Models and Their Validity in the Prediction of Heat Checking in Die
Copyright Laws and their Downfalls Relating to?nada
Clothes and their Descriptions Worksheet
Medieval Writers and Their Work
German Converts to Islam and Their Ambivalent Relations with Immigrant Muslims
charged and rotating ADS black holes and their CFT duals
Cigarettes and Their?struction of the Brain
Analysis of?rm Subsidies and their?fects
MICROACTUATORS AND THEIR TECHNOLOGIES
grades of timber and their use
A comparison?tween English and German and their ancestors
HUMAN RIGHTS AND THEIR IMPORTANCE goood
Dane Rudhyar The Planets and their Symbols

więcej podobnych podstron