WORK
PROGRAMME
WEAK
ARITHMETICS
2.1
Objectives
· To construct Nonstandard Models of Buss
Arithmetic to establish some bounds on the class NP inter co-NP.
· To solve the problem of existence of
end extensions of countable models of bounded collection.
· To explore further the additive theory
of infinite sets of prime numbers, both with absolute results and its links
with number theory via the Schinzel's hypothesis.
· To code natural numbers, complex
numbers, and quadratic integers by automata accepting numbers (written in
non-classical systems).
· To prove results for ultra-linear unary
recursive schemata (with individual constants).
· To obtain decidability results for S2S[P] theories.
· To build formal constructive theories (from
Grzegorczyk hierarchy) with applications to databases. To investigate the power
of counting in very small complexity classes and in the corresponding logical
or arithmetical settings.
· To explore the relation between
Infinite games, automata, and arithmetic.
· To study the fine structure of the BSS
recursive enumerable sets.
· To investigate concurrent processes in
distributed conveyer systems and their relation with corresponding weak
arithmetics.
· To construct Diophantine
representations of recursively enumerable sets of particular interest.
· To show the cofinality of primes in D0
(P), where P is the
function which counts the primes below x.
· To study subsystems of Goodstein’s Arithmetic (without
quantifiers).
· To develop families of formalized languages
for presenting arithmetical texts.
2.2
Background
Weak
arithmetic is the study
of problems of Number theory and Computer Science using methods of mathematical
logic, just as Algebraic Number Theory or Analytic Number Theory use Algebra
and Analysis.
Weak arithmetic was born in the
1930’s, then really emerged with a famous paper of Julia Robinson in
1949 ; Weak arithmetic has known its most famous result with the
(negative) solution of Hilbert’s tenth problem in 1970 by Yuri Matiyasevich,
and is involving more and more topics.
Works in weak arithmetic are 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ödel Theorems, works or has been working on decision
problems, on algorithms and their complexities, and uses all kinds of abstract
machines.
****
Five of the main sources of results
in weaks arithmetics are :
·
undecidability of the field of rational numbers (Julia Robinson, 1949),
·
Matiyasevich-Davis-Robinson-Putnam theorem (1970), solving Hilbert’s
tenth problem (there is no algorithm to determine whether a given diophantine
equation has a solution),
·
Erdös-Woods conjecture (1981) :
there is an integer k such that for every pair (x,y) of integers, the equality x
= y holds if and only if x+i
and y+i have the same prime divisors for 0 £ i £ k,
·
Buss arithmetic (1985): a first-order logical language L(BA) which contains symbols for
arithmetical operations and a special
induction-schema on certain subset of formulas providing a Weak Arithmetical
theory S such that a subset A of the set N of natural integer is in the complexity class P (we may determine wether an integer
belongs to A in polynomial time) if and only if it is S-provably in NP Ç co-NP.
·
study of the real exponential field : Tarski has proved in the
1920’s than the first-order theory of the structure (R,+,x,=), where R is
the set of real numbers, is decidable, hence the elementary geometry is
decidable. He asks the question of the status of (R,+,x,exp,=), where exp
is the exponential. In the 90’s very substantial results about this structure
and this question have been obtained by Wilkie, Macintyre and others :
decidability assuming Shammel’s conjecture, quantifier elimination and
« o-minimality ».
Table
1 Summary of task involvement
|
TASKS |
ITEMS |
Responsible
Partner |
Involved Partners |
|
TASK
1 |
Construction
of Nonstandard Models of first-order Arithmetics |
P1 |
P1,P9 |
|
TASK
2 |
Definability
and decidability of weak substructures of the Standard Model of Peano |
P1 |
P1,P2,P3,P5,P7,P8 |
|
TASK
3 |
Abstract
Machines, Automata, and Words |
P2 |
P1,P2,P4,P5,P7,P8 |
|
TASK
4 |
Elementary proofs of classical Number Theory results |
P9 |
P4,P6,P8,P9 |
|
TASK
5 |
Weak
arithmetics, Pure and Computational Logic |
P5 |
P1,P5,P8 |
Every task is 36 months long
|
TASK 1 |
Construction of
Nonstandard Models |
Partners 1,9 |
|
Objectives: To investigate
which functions and sets cannot be defined in the Arithmetic axiomatizations
of subtheories of Peano Arithmetic and what is the algorithmic complexity of
those who can be defined. T1.1 nonstandard
models of Buss Arithmetic (P1) T1.2 to investigate whether bounded induction
proves MDRP theorem (P9) |
||
|
TASK 2 |
Definability and decidability of weak substructures |
Partners
1,2,3,5,7,8 |
|
Objectives: To prove that
either the whole arithmetical standard model is definable in such a structure
or to prove decidability and determine its complexity. T2.1 to explore the additive theory of primes
(P1,P2,P7,P8) T2.2 to explore expansions of <N,+> (P7) T2.3 systems
of Diophantine Linear Equations and Applications (P5) T2.4 decidability
results for S2S[P] theories (P5) T2.5 formal
constructive theories (P3,P8) |
||
|
TASK 3 |
Abstract Machines, Automata, and Words |
Partners
1,2,4,5,7,8 |
|
Objectives: to study
abstract models of computation T3.1 to explore the relation between infinite
games, automata, and arithmetic (P1) T3.2 BSS
model of computation (P7) T3.3 concurrent
processes in distributed conveyer systems (P4) T3.4 verification
of real-time distributed systems (P1) T3.5 classification
of real functions (P5) T3.6 counting
classes (P1,P8) T3.7 fusion
theory and multihead automata (P8) T3.8 diophantine
representations (P2) |
||
|
TASK 4 |
Elementary proofs of classical Number Theory results |
Partners
4,6,8,9 |
|
Objectives: to determine
whether a given theorem of Number Theory is provable in a subsystem of Peano
Arithmetic T4.1 to show the cofinality of primes in D0(P)
(P6,P9) T4.2 subsystems of Goodstein’s Arithmetics (P4,P8) |
||
|
TASK 5 |
Weak arithmetics, Pure and Computational Logic |
Partners 1,5,8 |
|
Objectives: to apply
general methods of Pure Logic and automated theorem proving to arithmetic T5.1 Nezondet’s p-destinies (P8) T5.2 Computtional Logic (P1,P5) |
||
Deliverables are related to the tasks mentioned in the section above and shall be listed accordingly
Every task is 36 months
long, but partial results will be presented at the following meetings:
·
D1 : June 2001 Presentation of every tasks at Fontainebleau (France)
·
D2 : June 2002 Presentation of first results at the first meeting in
Saint-Petersburg
·
D3 : June 2003 Presentation of
results at the second meeting
·
D4 : May 2004 Presentation of conclusion at the third meeting
Normal
discussions from distant members of different teams will be by e-mail but we
expect a workshop every year (JAF,
for Journées sur les Arithmétiques
Faibles; the name exists since ten years, perhaps now WAD for Weak Arithmetics Days) to present results and, mainly, lively discussions. Normal
dissemination will consist of papers in reviews (Journal of Symbolic Logic, Theoretical
Computer Science, Annals of Pure and
Applied Logic…). Also we expect to publish communications either in a
special issue of a review or as a Lecture
Note in Mathematics (Springer).
Report Schedule
Reports must be
submitted to the INTAS Secretariat as set out in Article 9 of the General
Conditions (Annex II) in the format specified in the INTAS Reporting
Guidelines, which are updated regularly on the internet site
http://www.intas.be
4 MANAGEMENT
The project will
last 36 months with the activities as indicated
in the table below.
Tasks
|
Teams
|
Months
1-6
|
Months
7-12
|
Months
13-18
|
Month
19-24
|
Months
25-30
|
Months
31-36
|
||||
|
|
|
|
|
|
|
|
|
||||
T1.1
|
Team 1
|
|
|
|
|
|
|
||||
T1.2
|
Team 9
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
T2.1
|
Team 7,1,2,8
|
|
|
|
|
|
|
||||
T2.2
|
Team 7
|
|
|
|
|
|
|
||||
T2.3
|
Team 5
|
|
|
|
|
|
|
||||
T2.4
|
Team 5
|
|
|
|
|
|
|
|
|||
T2.5
|
Team 3,8
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
||||
T3.1
|
Team 1
|
|
|
|
|
|
|
||||
T3.2
|
Team 7
|
|
|
|
|
|
|
||||
T3.3
|
Team 4
|
|
|
|
|
|
|
||||
T3.4
|
Team 1
|
|
|
|
|
|
|
||||
T3.5
|
Team 5
|
|
|
|
|
|
|
||||
T3.6
|
Team 1,8
|
|
|
|
|
|
|
||||
T3.7
|
Team 8
|
|
|
|
|
|
|
||||
T3.8
|
Team 2
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
||||
T4.1
|
Team 6,9
|
|
|
|
|
|
|
|
|||
T4.2
|
Team 4,8
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|||
T5.1
|
Team 8
|
|
|
|
|
|
|
|
|||
T5.2
|
Team 5,1
|
|
|
|
|
|
|
|
|||
CO Professor Patrick Cegielski
Université
Paris XII, IUT de Fontainebleau, France
CR1 Professor Yuri Matiyasevich
Steklov Institute of Mathematics at Saint-Petersburg, Russia
CR2 Professor Anatoly Beltiukov
Udmurt University, mathematics faculty, Russia
CR3 Professor Yuri Shoukourian
Institute for Informatics and Automation Problems, Yerevan, Armenia
CR4 Senior research scientist Alexander Lyaletski
Kiev University, Ukraine
CR5 Senior researcher Paola D’Aquino
University of Naples II, Italy
CR6 Professor Véronique Bruyère
Université de Mons-Hainaut,
Belgium
CR7 Professor Denis Richard
Université de Clermond-Ferrand
1, France
CR8 Professor Constantinos
Dimitracopoulos
University
of Athens, Greece
Weak arithmetic is the study of problems of Number theory and
Computer Science using methods of mathematical logic, just as Algebraic Number
Theory or Analytic Number Theory use Algebra and Analysis. Five of the main
sources of results in weaks arithmetics are undecidability of the field of
rational numbers, Matiyasevich-Davis-Robinson-Putnam theorem, solving Hilbert’s
tenth problem, Erdös-Woods conjecture, Buss arithmetic and study of the real
exponential field.
The proposed project is constituted of nine teams from
university of Paris, Steklov Institute of Mathematics at Saint-Petersburg
(Russia), Udmurt University (Russia), Institute for Informatics and Automaton
Problems at Yerevan (Armenia), Kiev University (Ukraine), University of Naples
(Italy), university of Mons-Hainaut (Belgium), university of Clermont-Ferrand
(France), and University of Athens (Greece).
Objectives for the three years were : to construct
Nonstandard Models of Buss Arithmetic to establish some bounds on the class NP
inter co-NP ; to solve the problem of existence of end extensions of
countable models of bounded collection ; to explore further the additive
theory of infinite sets of prime numbers, both with absolute results and its
links with number theory via the Schinzel's hypothesis ; to code natural
numbers, complex numbers, and quadratic integers by automata accepting numbers
(written in non-classical systems) ; to prove results for ultra-linear
unary recursive schemata (with individual constants); to obtain decidability
results for S2S[P] theories ; to build formal constructive
theories with (from Grzegorczyk hierarchy) with applications to
databases ; to investigate the power of counting in very small complexity
classes and in the corresponding logical or arithmetical settings ; to
explore the relation between Infinite games, automata, and arithmetic ; to
study the fine structure of the BSS recursive enumerable sets ; to
investigate concurrent processes in distributed conveyer systems and their
relation with corresponding weak arithmetics; to construct Diophantine
representations of recursively enumerable sets of particular interest ; to
show the cofinality of primes in D0 (P), where P is the
function which counts the primes below x ; to study subsystems of
Goodstein’s Arithmetic (without quantifiers) ; to develop families of
formalized languages for presenting arithmetical texts.
Main exchanges are by e-mail but it is planning two workshops (a local
one and a general) by year, two co-ordination meeting and exchanges of
scientists.