Patrick CÉGIELSKI
Denis RICHARD
I. An attempt to define Weak Arithmetics from the
Journées sur les Arithmétiques
Faibles
Theme 1: Construction of Nonstandard Models of first-order
Arithmetics in order to investigate:
1) axiomatizations of subtheories of PEANO Arithmetic in
which induction
schemata are restricted to special subset of formulas;
2) complexities of the considered subtheories, especially for
getting algorithms of polynomial time.
Theme 2: Definability and decidability of weak substructures
of the
Standard Model of PEANO
Theme 3: Abstract Machines, Automata and
Words
Other Themes:
a) Graphs, Spectra and RUD;
b) Elementary proofs of classical Number Theory results,
Arithmetical Proof Theory;
c) Functional Programming and Recursivity;
d) General Logic;
e) Applied Algorithmics.
II. An illustration of definability problem in Weak Arithmetics:
the WOODS-
ERDÖS conjecture
II-1 The Number Theoretical approach to WE
II-2 Logical approach to WE
Conclusion.
I. - An attempt to define Weak Arithmetics from the
Journées sur les Arithmétiques Faibles
It is amusing, indeed astonishing, that no-one among a community of about one
hundred computer scientists, logicians and mathematicians organizing
meetings twice a year for almost ten years has thought it advisable properly and precisely to
define the
field of research one usually calls Weak Arithmetics. In my opinion,
everybody,
within this group, brought to it his own interest and wondered at not
having to justify
the relevance of Weak Arithmetics.
In discussions by ourselves, it appears that this relevance is intuitively
founded on a
common field of mathematical interest, a common set of questions and
logical methods to
investigate problems, and a general culture within computer science.
Basically, a scientist interested in Weak Arithmetics knows some
mathematical logic,
likes PEANO Arithmetic and the two G¨ODEL Theorems, works or
has been working
on decision problems, on algorithms and their complexities, and uses all
kinds of
abstract machines. Through these machines Weak Arithmetics are strongly
influenced by
the computer-dominated modern world. The Weak Arithmetics scientist is not a
professional mathematician who studies numbers (using such tools as
algebraic methods,
complex analysis and algebraic geometry) but is often (or always in some
areas) in
contact with Number Theory. Therefore it is difficult to give a precise
definition of
Weak Arithmetics as a discipline in the same way as - say - Model Theory.
Nevertheless we can nowadays consider the list of lectures and talks given
from JAF1 to
JAF17, in order to determine the main directions and themes provided by the
participants at those events. One can distinguish four groups of lectures
which the
reader can find in the Annex.
Theme 1.- Construction of Nonstandard Models of first-order
Arithmetics in order to investigate:
1) axiomatizations of subtheories of PEANO Arithmetic
(denoted PA)
in which induction schemata are restricted to a special subset of formulas;
2) complexities of the considered subtheories, especially for
developing polynomial time algorithms.
This theme is closely linked, on the one hand, to the study of induction
schemata which
are respectively called logarithmic, open, parameter free,
-induction, etc.,
and, on the other hand, to the BUSS Arithmetic. In this theme,
logicians try to
construct (nonstandard) models having specific properties (for example an
ordered field
without an integer part (BOUGHATTAS)). One tries also to prove (or
disprove) some
axiomatizability properties such as the fact that open-induction in
normal rings is
not finitely axiomatisable (BOUGHATTAS). Algorithmic and Complexity
theories are
also connected to this theme because computability in polynomial time
corresponds to some
specific axiomatisations one can characterize: for instance P. PUDLAK, TAKEUTI and KRAJICEK proved the equivalence between the provability
in bounded
arithmetic of the collaps of the
strict polynomial time hierarchy and the finite axiomatizability of the
arithmetical theory in the language of addition, multiplication and
with induction schemata restricted to -formulas.
The lively style of the preface
by J.P. RESSAYRE provides a precise and well-documented
presentation, the
deep links between nonstandard models, axiomatizability and algorithmic
complexity. So on
this matter, we refer to his text.
Another illustration of this theme is bounded arithmetics, which were
introduced by BUSS within a first-order logical language which we
denote .
This language contains the symbols of successor, addition, multiplication, 0,
, length of , that is to say
,
the function , identity and natural order. In this
language, BUSS
defines a special induction-schemata on certain subset of formulas
providing a Weak
Arithmetical theory such that a subset of is if and only if
it is -provably
. In so doing, BUSS provides a
promising method
to prove a set is since, according to this result, it is sufficient
to prove it
is both and in some explicitly known and specific (weak)
theory. About this
result, P. CEGIELSKI wrote: Practically, if we know it is both
and
, then the method used to prove this result certainly is not too
complex and the
demonstration can be formalized in such a theory. However, up to now, no
set has been
shown in P by such a method. The reason is that bounded arithmetics are
still not widely
developed. For instance we do not know which classical theorems of Number
Theory are
true in these Weak Arithmetics. The length of proof of any classical
theorem increases
greatly with weakness of the arithmetical theory in which this proof takes
place. For
instance, a proof of DIRICHLET theorem on (infinity of) primes in
arithmetical
sequences in primitive recursive arithmetic is one hundred pages
long. Such
results would help to apply BUSS'(results).
Theme 2.- Definability and decidability of weak substructures of
the Standard
Model of PEANO.
The general framework of definability is presented in a detailed way in the
survey carried out by P. CEGIELSKI in the ANNALS of MATHEMATICS and
ARTIFICIAL INTELLIGENCE, vol. 16 n1.4 (1996). For a
structure , we
denote by DEF the set of constants, functions and relations which are
first-order
definable within . Following CHURCH and TURING's proof in
1936 that
the theory of natural integers equipped with addition and multiplication
and identity is
not decidable, we obtain a method for proving the undecidability of the
theory of a
structure which consists in showing DEF = DEF
.
The set
DEF
is well-known and K. G¨ODEL proved it
contains any relation
we can define by recursion (with some particular set of natural functions as
primitives) so that , if is a sub-structure of the standard model, then the
inclusion of DEF into DEF
is trivial. One of the
most famous
questions to have been solved in the framework of arithmetical definability
is HILBERT's tenth problem; It asks for an algorithm to determine whether a given
diophantine equation has a solution or, in other words whether there exists
a program
such that given a polynomial
with integer
coefficients as input,
we can obtain as output the set, possibly empty, of integer solutions of
. In 1970, I. MATIASSEVITCH proved the key-results
leading to a
negative answer to this problem: exponentiation is definable by a
diophantine equation, i.e. by a -formula within PEANO
Arithmetic. Of
course, this result was obtained after years of research and collaboration
with M. DAVIS, H. PUTNAM, J. ROBINSON who provide many classical
theorems and
conjectures. Due to this cooperation, in the definability area we refer to
as the MDRP
(for MATIASSEVITCH-DAVIS-ROBINSON-PUTNAM) theorem the fact that every
-formula is equivalent to a Diophantine formula.
The key-points of this famous proof of the negative solution of the
tenth-HILBERT
problem belong to arithmetical coding and definability:
- It is possible to code the process of register machines by the
masking relation
between the integers and given in their binary
expansion; more precisely, we say that masks if and only if when
appears
as a digit in the binary expansion of then also appears as the
digit of the
same rank in the binary expansion of ;
- (A corollary of LUCAS' Theorem) the miracle is that
if
and only if
, which means that one can
completely
describe in the language of first-order arithmetic not only the operation of
a register machine, but also that of a normal computer as well;
- the description, via first-order arithmetical formulas describing the
operating cycles, of a register machine, can finally be rewritten as a
conjunction of
diophantine equations; this is due to arithmetical properties such as, for
instance,
the exponential growth of the sequence of the solutions and
to
the PELL-FERMAT equation
.
A by-product of this is the possibility of
first-order defining the set of prime as the set of positive value
of
a certain polynomial due to J.P. JONES and al...
In the present theme, usually we consider an arithmetical
substructure of the standard model and we try to prove that either the
whole
arithmetical standard model is definable within , or is
decidable and in
this case we investigate the complexity of the considered structure. This
is not an
alternative: there are undecidable weak substructure of PEANO
where addition
and multiplication are not simulteneously definable and which are
undecidable. The
problem of definability which is the main topic of theme 2 goes back to
Number Theory
questions raised a long time ago, as we shall show in part II below.
Arithmetical
definability is closely related to Number Theory and, in a sense, sheds new
light
on its classical results. In part II of the present preface, we intend to
develop on an
example having historical roots going back a century before the second main
theme of
Weak Arithmetics, namely the problem of mutual definability of
arithmetical relations
within first-order Number Theory. Undecidability is a corollary of
definability of
addition and multiplication in the framework of PEANO Arithmetic.
Weak Arithmetics
therefore also include arithmetical decision problems such as decidable
extensions of
PRESBURGER (additive) arithmetic and SKOLEM (multiplicative)
arithmetic. The
decision problem for additive prime number theory is adressed both within
Number Theory and the Theory of Automata. There are conditional results in
this field
(mostly due to A. WOODS) under SHINZEL's Hypothesis on primes, and
absolute results recently proved by CEGIELSKI, RICHARD and VSMIRNOV.
The study of the set RUD of rudimentary predicates (GRZEGORCZYK and
ESBELIN)
is linked both to BUSS Arithmetics, and to algorithmic and Spectra
problems which
concern the set of cardinalities of the finite models of a given
first-order formula. It
is worth noting that rudimentary predicates extend to real analysis and to
the problem
of speeding up software used in computer science and numerical analysis. In
our somewhat arbitrary classification, we put RUD in a special theme with
the study of
the problem of spectra (finite models), arithmetisation of graphs and GRZEGORCZYK
hierarchy.
Theme 3.- Abstract Machines, Automata and Words.
Any program in a specified
language which we use in a computer has a corresponding abstract machine,
for instance a
TURING machine. Actually, we can formalize any program
because with addition and multiplication we can define (or simulate) all
recursive
schemata. Now if we consider only some Weak Arithmetic (for instance PRESBURGER
Arithmetic) then a corresponding abstract machine computing functions and
relations
definable in this theory, or in a model of this one, is of course weaker
than a TURING Machine (for instance it can be an automat on for PRESBURGER
Arithmetic).
In this way, it is natural to associate abstract machines (Automata, Push
Down Automata,
Cellular Automata, BELTIUKOV Machines, Alternating TURING
Machines, etc)
with different weak arithmetical theories and to the models we investigate.
During the JAF, many machines, algorithms and the objects they represent
were presented.
Of course, the words - arguments which these machines use - with the
different
meaning we give to this notion in computer science, were studied. To this
theme
also belong general coding theory and all problems of weak arithmetical
structures
consisting of the usual integers with pairing functions (such as CANTOR pairing
polynomial) or codings of -tuples (using for example the well-known
-function
of G¨ODEL). Machines as tools for solving problems of definability
or decidability
were used by I. KOREC, A. B`ES, V. BRUYÈRE, C. MICHAUX, J.E.
PIN, J. TOMASIK, etc. Machines are not only tools but are
themselves
the objects of investigation such as for instance the smallest universal
TURING
Machines (M. MARGENSTERN and PAVLOTSKAIA), or the MATIASSEVITCH
machines introduced to solve problems of trace monoid (A. MUSCHOLL,
Y. MATIASSEVITCH). Results on these machines are due to O. TEYTAUD and
A. B`ES.
The problem of determining whether counting is possible with a given
abstract machine is closely connected to question of complexity
hierarchies as
in the case of the GRZEGORCZYK hierarchy. Automata trees and modular
counting were
developed by H.A. ESBELIN and R. ESPEL LLIMA. In the framework
of infinite
games and particularly on Borelsets, J. DUPARC, J.P. RESSAYRE, O.
FINKEL refer to automata but this is considered to be on the boundary
between Weak
Arithmetics and Set Theory.
We have seen that Weak Arithmetics cover two main themes (Axiomatizibility
and Complexity
in Subtheories of PEANO Arithmetic on the one hand, and Arithmetical
Definability and Decidability on the other). We have also noted that Abstract
Machines underlie our investigations and thus become another theme of
studies within
the framework of Weak Arithmetics. Nevertheless these three areas do not
exhaust the
topics presented by participants of the JAF. We list some recurrent
questions and some new concepts in the last section of this part.
Other Themes.-
a) Graphs, Spectra and RUD;
b) Elementary proofs of classical Number Theory results, Arithmetical
Proof
Theory;
c) Functional Programing and Recursivity;
d) General Logic;
e) Applied Algorithmics.
Theme a) refers to Finite Models and to the FAGIN conjecture
which is also
linked to RUD according to some results of A. WOODS. The notion of
Graph is
central and its arithmetisation addresses this question within Weak
Arithmetics. In the
present issue there is an arithmetisation of the four-colour problem due to
Y. MATIASSEVITCH.
Theme b) stems from the work ERDÖS and SELFRIDGE who
were the first to
ask for what they called elementary proofs (i.e. in the framework of
real analysis
instead of complex analysis) of results such as the DIRICHELET
Theorem on the
infinity of primes in arithmetical sequences. Logicians such as TAKAEUTI, KREISEL and SIMPSON (with his reverse mathematics) have contributed
to the subject
but in a general way. P. CEGIELSKI and O. SUDAC have
constructed proofs for
specific classical theorems (such as the Prime Number Theorem of DE LA
VALLÉE
POUSSIN). They have also constructed some first order denumerable
structures modelling
a version of PEANO Analysis to provide proofs within PEANO
Arithmetic
models or even within the standard model of weaker arithmetical theories
(e.g.
, the Primitive Recursive Arithmetic). It is clear that this work
should be
continued in order to strengthen the tools developed by BUSS.
Theme c) is clearly within the scope of Weak Arithmetics wherein one
attempts to
reconstruct a missing induction or recursive schemata. In Functional
Programming also
attempts to avoid recursion and recursive definition. For example
L. COLSON demonstrates that roughly speaking primitive recursive
algorithms are
not optimal in terms of complexity.
Theme d) is mainly concerned with NEZONDET's -destinies
which are a
general tool founded on trees for deciding closed sentences when applied to
theories
consisting of a set of sentences in a relational language which have a
bounded number of
quantifiers. This a promising new method which, for example gives rise
to many
interesting questions in Number Theory (GUILLAUME, JELEI YIN,
RICHARD).
Theme e) could be considered to be the future of Weak
Arithmetics in Informatics. A considerable proportion of software relies on
algorithms
which derive from numerical analysis however, due to the undecidability of
the real zero,
many of these programs have to be written within the framework of the
standard model
of integers. This is particularly the case in discrete geometry, computer
imagery and
artificial vision where faster computation with increasing precision is
constantly
demanded. Some structure such as the natural integers with the mappings
ceiling and floor
is necessary to describe digital planes and their algorithms of
connectivity, or to
perform ray tracing and so on. Here the blend of Number Theory, Logical
Arithmetic and
Computer Science (automata and chips) which make up Weak Arithmetics has
been applied
effectively and will become more and more useful.
The question of whether first-order arithmetic on the set of
nonnegative
integers is definable in terms of the successor function and the
coprimeness
predicate is a typical problem of Weak Arithmetics and perhaps,
historically speaking, one of the first to be posed in this modern
framework. It was
raised in 1949 by Julia ROBINSON in her thesis, when she
investigated the
axiomatizability of different theories of elementary structures on numbers.
More
precisely, Julia ROBINSON stated: We might also try to improve
the theorem by
replacing divisibility by the relation of relative primeness. However I
have not been
able to determine whether is arithmetically definable in terms of
and
or even in terms of and . This question, and some others
of the same
nature such as the definability of all arithmetical relations in terms of
addition and
coprimeness, were neglected for decades. In the eighties, Alan WOODS,
returned
to these problems. He was the first to realize that the question of
definability within mathematical logic is equivalent to the following
conjecture of
Number Theory: there is an integer such that for every pair
of
integers, the equality holds if and only if and have
the same prime
divisors for
. This number-theoretical form of Julia ROBINSON's question is itself very closely linked to some open
questions proposed by
Paul ERDÖS and for which he had conjectured a positive answer. In
the book by Richard GUY entilted Unsolved Problems of Number
Theory,
the question is attributed to Alan WOODS, but due to
its close relation with conjectures of ERDÖS
which were known to A. WOODS, this conjecture is known as the
WOODS-ERDÖS conjecture, or WE or WE if it is necessary to
state the
parameter .
Indeed, WE is a weakening of the following conjecture of P. ERDÖS:
ERDÖS asks if there are infinitely many -tuples such
that
and
with
can
contain the same prime factors. For example
2.3.4.5.6.7.8.9.10 and 14.15.16 or 48.49.50, also
2.3.4.5.6.7.8.9.10.11 and 98.99.100. For he
conjectures that
there are only finitely many. ERDÖS' interest is the
relationship between prime divisors and consecutive integers is supported
by many
other papers. Weak Arithmetic, combines a Number-Theoretoc pointof view with
approchies based on mathematical Logic and concept of definability in a fashion
particulary appropriate to the investigation of the WE-conjecture.
II-1 The Number Theoretical approach to WE.
The problem of finding a local characterization of an integer by its
prime divisors
and by the prime divisors of (or ) - which actually is a problem of
definability - was raised by famous mathematicians many years ago. The
fundamental
result on this question is due to ZSIGMONDY and was rediscovered and
generalized by BIRKHOFF and VANDIVER twelve years
later.
They showed that, except for 2 and 8, each power of a prime
number is
characterized by and the prime divisors of .
An analogue of the previous result dealing with has been proved by
LUCAS and generalized by CARMICHAEL.
Another Classical result closely related to WE is due to C. STøRMER
who showed the following:
Let
be distinct prime
numbers and ,
be nonnegative
integers. For
, let us put
if is odd,
if is even and set
.
If
then is the
fundamental solution of the PELL-FERMAT equation
;
If
then is the
fundamental solution of the PELL-FERMAT equation
.
Now, we define as the set of the prime divisors of . From this
result,
the following:
(i) If E is a set of n distinct prime integers, there
are at most nonnegative integers satisfying the condition
SUPP(x(x + 1))
E, so that, for any nonnegative integer a, the set
ST(a) of
nonnegative integers b such that
(ii) The nonnegative
integers x and y are equal if and only if the following
conditions are
simultaneously satisfied:
1) SUPP(x - 1) = SUPP(y - 1) and SUPP(x + 1)=SUPP(y + 1);
2) for all prime numbers p
in SUPP( (or in SUPP() the
exponent of
p in the factorisation of x + 1 (resp. x - 1) has the same
parity as in the
factorisation of y + 1 (resp. y - 1).
Recently, number theoretists such as M. LANGEVIN, R. BALASUBRAMANIAN,
T.N. SHOREY and M. WALDSCHMIDT have investigated bounds and
inequalities
which permit the location of integers in according to the relationship
of their
supports. In this direction, LANGEVIN provides a fundamental
result he calls the reduction lemma. To present it, we introduce his
notation:
SUPP
is prime and ?
is the product of the primes in SUPP(n);
is the greatest prime in SUPP(n);
is the cardinality of SUPP(n);
is the product of all primes in
SUPP
;
Reduction Lemma. (LANGEVIN). Let x and y be
positive
integers. In each group labelled (i), (ii), (iii), (iv), the
conditions given are
equivalent:
We note that condition is the very hypothesis of WE. These
conditions
show how close the links are between the languages of successor and
coprimeness on one
hand and successor and divisibility on the other hand.
Beginning with the results on inequalities, we first mention a fundamental
result
of M. LANGEVIN who proved that for ,
if
then
This inequality
was improved upon by R. BALASUBRAMANIAN, T.N. SHOREY and M. WALDSCHMIDT who proved that for
x, y, k being nonnegative integers satisfying 0xy
and k
1 and (k) of the previous reduction lemma:
Importance of the Woods-Erdös conjecture
Beyond its intrinsic interest both to Mathematical Logic (more precisely
for arithmetical definability and axiomatizability) and Number Theory, the
attempt to
prove or disprove the questions of
J. ROBINSON, A. WOODS and P. ERDÖS, gains in
importance if we
realize how strong the links are between WE and other classical
conjectures of Number
Theory. In the same paper by LANGEVIN, the
following results were proved:
Let k be the parameter
appearing in the WOODS-ERDÖS conjecture WE(k).
1) If there is an absolute constant C such that for
any pair (x,y) of positive integers the condition
implies:
(HALL's conjecture).
then the answer to WE is positive.
2) Moreover, under the same hypothesis above, if
we can
prove
then the answer to WE(k) is positive with
modulo a
finite set of exceptions.
3) If for every positive real , there exists a
constant D
such that for any pair (a,b) of positive integers we have;
u(a + b)abD(a + b)(gcd(a,b)
((a-b-c)-conjecture),
then the answer to WE(k) is positive with
modulo a
finite set of exceptions.
We note that as a result of conclusions 2) and 3) the above theorem is
a negative answer to WE would refute both HALL 's conjecture, and the so-called OESTERLÉ-MASSER
's conjecture
(also called the ---conjecture).
There are still other relationships of WE to questions recently answered by
Capi
Corrales RODRIGÀNEZ and René SCHOOF about the
characterization of by supports of , for infinitely many
positive this
was also a question posed by ERDÖS. Maxim VSMIRNOV (unpublished)
has a proof of the characterization of integers by finitely many
supports. Ten years ago, we asked whether
for all
implies and
we gave a proof due to A. SCHINZEL of the fact
that the (--)-conjecture implies a positive answer to our question.
In the section devoted to the logical approach to WE, we present an
analogue of these results within the frame-work of definability, when we
prove that
.
II-2 Logical approach to WE.
To place the logical approach to WE in a more general and historical
setting, it is
worth pointing out that arithmetical definability goes back to Kurt G¨ODEL
who proved that the structure
is
closed under primitive recursion. In order to appreciate the power of
this result,
consider the effort required to obtain a direct first-order definition of
exponentiation, or of the natural enumeration of prime integers, from
equality,
addition and multiplication. Another interesting aspect of G¨ODEL's
result is
that there exist arithmetical structures which are not closed under
primitive
recursion:
- addition does not belong to
as shown by LANGFORD in
1926;
- multiplication does not belong to
as shown by PRESBURGER in 1929.
Defining addition and multiplication from some a priori weaker
languages of arithmetic is not always easy but is sometimes possible. A
classical
example is the language which defines all arithmetical
relations. A. TARSKI provided a first-order
-definition of addition from the following
equivalence:
if and only if or
Julia ROBINSON's results
In a sense, folling the G¨ODEL's works and the above relation due
to TARSKI, the first important and really difficult result was the
characterization
of definability within a Weak Arithmetic structure and was obtained
by J. ROBINSON:
Addition and multiplication are definable in the
structure
.
In the same paper, J. ROBINSON showed that the set
of
nonnegative integers
is definable in terms of addition and multiplication within the field
of rationals.
This result is central to the investigation of decidable and
undecidable theories.
In order to find other natural axiomatisations of arithmetic,
J. ROBINSON asked whether
There was first an unpublished positive solution by J. ROBINSON,
then a second
solution by A. WOODS proving that the -definability
of multiplication is a corollary of the SCHNIRELMANN Theorem (stating
that every integer is the sum of a finite bounded number of primes). Finally we
obtained a proof using coding devices.
It is worth observing that J. ROBINSON attempt to
propose a natural axiomatization of first-order PEANO
arithmetic in
terms of and , was in part completely realized by P. CEGIELSKI in
his thesis. Indeed CEGIELSKI has given a first-order natural
axiomatization of first-order PEANO Arithmetic in the language
. To obtain this axiomatization, he used the so-called ZBV-method of
coding which we describe below.
Alan WOODS' results.
Concerning the language , the first result is due to A. WOODS who
also proved that
.
In the sequel we call this question the ROBINSON problem
(namely: is
there an equality
between
and
). A. WOODS has
linked the ROBINSON problem to the WOODS-ERDÖS conjecture
by proving that the answer to the ROBINSON problem is
positive if and only if the WE conjecture is true.
More precisely, Alan WOODS proved that the following assertions are
all equivalent:
(i) The answer to the ROBINSON problem is positive,
namely one can
define addition and multiplication in terms of equality, coprimeness
predicate and
successor function; (and vice-versa)
(i') One can define natural order, or addition, or
multiplication in terms
of equality, coprimeness predicate and successor function;
(ii) One can define equality,
addition and multiplication in terms of coprimeness predicate and successor
function;
(ii') One can define natural order, or addition, or
multiplication in terms of
coprimeness predicate and successor function;
(iii) One can define equality in terms of
coprimeness predicate and successor
function;
(iv) The answer to the WOODS-ERDÖS
conjecture is positive, namely, there is an integer such that for
every
pair of integers, the equality holds if and only if
and have the same prime divisors for
.
Remark. It is worth pointing out the status of equality:
if we
consider successor and coprimeness without equality, then to define equality is
equivalent to a positive answer to WE; on the other hand, if we consider
equality,
successor and coprimeness together, then a success at definition equality
order (resp.
addition or multiplication) is still equivalent to a positive answer to WE.
At this step in the investigation of the ROBINSON problem, farther
results are
obtained via the so called ZBV-Method (for ZSIGMONDY-BIRKHOFF-VANDIVER)
which we have introduced. This method allows are to prove all the results
already
mentioned this section as well as providing new results.
ZBV-method of coding.
The ZBV-method consists in considering integers of the form or (where and are coprime) to be coded by
their respective
support or their respective set of primitive or characteristic divisors. This
method is most effective when is a
fixed prime and is 1, 2 or 3. By this method, one reduces
arithmetical questions
to an investigation of finite sets of primes and their
boolean combinatorics.
Moreover, every finite set of primes (or every function of
finite domain mapping primes to primes) is itself codable in
infinitely many ways by a single prime integer
using a combination of the Chineese Remainder Theorem and the DIRICHLET Theorem.
A prime which is a code plays the role of a memory in which we store a
finite set
of primes.
One can interpret the structure
as a set
theory on the supports of nonnegative integers. Any finite part of the
set of
primes is coded by the set of integers having as its support.
New -definable relations and undecidability of
via the ZBV-method.
It can be proved that an integer is a power of a prime (we say also
primary) if and only if the support of is included in the support
of any
integer not coprime to . As a consequence, the following relations are
-definable:
- the set
of powers of primes;
- the set
of powers of the same prime ;
- every finite relation on
;
- the equality
restricted to
;
- the successor function and the predecessor function
restricted to
;
every integer which is a constant (this is not obvious but is
a corollary of the
previous point).
A fundamental result derived from the ZBV-method is the
possibility of defining the set
of primes within the structure
.
This result can be extended to the structure
where
Pred denotes the
predecessor function on
. They are in both structures
and
, we
have all
set theoretical combinatorics exist on the supports.
For every pair of distinct primes the notation is by
definition the only power of such that is a primitive divisor
of . The
crucial fact is that the ternary relation
(ii) consequently, the theory
is undecidable;
(iii) moreover,
, NewAdd,
NewMult
What may be added to successor and coprimeness in order to define all
arithmetical relations?
At this step the logical approach consists in finding out what are the
relations we can
add to successor and coprimeness to obtain the definability of all
arithmetical
relations.
With this in mind, we consider the binary relations of
exponentiation and
power of the form
such that there
exists
which satisfies
(i) Every relation or function which is first-order definable
in
is actually first-order definable in
.
(ii) Every relation or function definable by a first-order
formula of
is also definable in the structure
by a first-order formula of the associated
language
It now follows that the structure
where
denotes the natural order on
restricted to primaries, allows the
first-order
definition all arithmetical relations on
, and verifies that
.
The last result we would like to mention, is due to Francis NEZONDET
who showed
the importance of
equality and, the difference between relational and
functional languages, to the investigation of arithmetical definability in
terms of
successor and exprimeness. Actually, there is a structure
which is elementarily equivalent to the standard model
and in which the identity relation
is not
definable. More precisely:
Let , be
respectively the functional symbols of addition and multiplication. There
exists an
arithmetical model
Here , are respectively the
functional symbols of addition and multiplication, will be
interpreted in
the usual way on
. The coprimeness predicate on
and on the domain is the interpreted as a first-order formula
meaning
(x and y are coprime) on
. By finite arithmetic, we denote
the
-axioms which characterize an ordered semi-ring. Of course, our finite
arithmetic (namely the RR system of Raphael ROBINSON) is
a purely relational theory which contains a symbol of equality and
does not contain
any schema of induction. The proof of this result, consists in first
building a
model of the finite arithmetic RR and of
and then demonstration, that equality is not
-definable. We emphasise that
here addition and multiplication are functions and not relations.
Finally, the theory of the standard model with the functions of
addition and multiplication, the coprimeness relation and the constants 0
and 1, does not decide the WOODS-ERDÖS conjecture.
Conclusion: Due to the new tools, the computers, and the new objects
of our investigation, the abstracts machines modelizing fragments of the
human reasoning, weak arithmetics have appeared. Perhaps weak arithmetics
precede weak real analysis which we can observe showing up against the
mist of the
complexity theory of reals.