The field of Weak arithmetics is application of logical methods
to
Number Theory, developed by mathematicians, philosophers, and
Theoretical Computer Scientists. In this volume, after a general
presentation of weak arithmetics, the following topics are studied:
the properties of integers of a real closed field equipped
with exponentiation; conservation results for the induction
schema restricted to first-order formulas with a finite number
of alternations of quantifiers; a survey on a class of tools,
called pebble games, used in finite model theory; the fact
that
reals e and π have approximations expressed by first-order
formulas using bounded quantifiers; properties on infinite
pictures depending on the universe of sets used;
a language that simulates in a sufficiently nice manner
all algorithms of a certain restricted class; the logical
complexity of the axiom of infinity in some variants of set theory
without the axiom of foundation; and the complexity to determine
whether a trace is included in another one.
Patrick Cégielski
is professor at Université Paris-Est Créteil IUT de Sénart-Fontainebleau
Jointly published with Presses Universitaires
du Pôle de Recherche
et d'enseignement supérieur Paris-Est.
Other works associated with Patrick Cégielski:
- Foreword
by Simone Bonnafous vii
- Introduction
by Patrick Cégielski 1
- 1 On the Arithmetization of Real Fields with Exponentiation
by Sedki Boughattas and Jean-Pierre Ressayre 13
- 2 On Conservation Results for Parameter-Free Πn-Induction
by A. Cordón-Franco, A. Fernández-Margarit, and F.F. Lara-Martín 49
- 3 Pebble Games for Logics with Counting and Rank
by Anuj Dawar and Bjarki Holm 99
- 4 Rudimentary of Two Famous Real Numbers
by Henri-Alex Esbelin 121
- 5 Decision Problems for Recognizable Languages of Infinite Pictures
by Olivier Finkel 127
- 6 A Total Functional Programming Language Computing APRA
by David Michel and Pierre Valarcher 153
- 7 Statements of Ill-Founded Infinity in Set Theory
by Eugenio Omodeo, Alberto Policriti, and Alexandru Tomescu 173
- 8 On some Matching Problems in Trace Monoids
by Karine Shahbazyan and Yuri Shoukourian 201