Search

On the basis of recent work concerning the meaning of the term stoicheion (στοιχεῖον) in Aristotle’s Analytics, we strengthen the view that this treatise can be viewed as a precursor of Euclid’s Elements. © 2022, The Author(s), under exclusive licence to Springer Nature Switzerland AG.

In this paper, we prove results concerning the existence of proper end extensions of arbitrary models of fragments of Peano arithmetic (PA). In particular, we give alternative proofs that concern (a) a result of Clote (Fundam Math 127(2):163–170, 1986); (Fundam Math 158(3):301–302, 1998), on the end extendability of arbitrary models of Σ n-induction, for n≥ 2 , and (b) the fact that every model of Σ 1-induction has a proper end extension satisfying Δ -induction; although this fact was not explicitly stated before, it follows by earlier results of Enayat and Wong (Ann Pure Appl Log 168:1247–1252, 2017) and Wong (Proc Am Math Soc 144:4021–4024, 2016). © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.

Topological dynamics of cellular automata (CA), inherited from classical dynamical systems theory, has been essentially studied in dimension 1. This paper focuses on 2D CA and aims at showing that the situation is different and more complex. The main results are the existence of non sensitive CA without equicontinuous points, the non-recursivity of sensitivity constants and the existence of CA having only non-recursive equicontinuous points. They all show a difference between the 1D and the 2D case. Thanks to these new constructions, we also extend undecidability results concerning topological classification previously obtained in the 1D case.

We study problems of Clote and Paris, concerning the existence of end extensions of models of ∑ n -collection. We continue the study of the notion of 'Γ-fullness', begun by Wilkie and Paris (Logic, Methodology and Philosophy of Science VIII (Moscow, 1987). Stud. Logic Found. Math., vol. 126, pp. 143-161. North- Holland, Amsterdam, 1989) and introduce and study a generalization of it, to be used in connection with the existence of ∑ n -elementary end extensions (instead of plain end extensions). We obtain (a) alternative proofs of results (Adamowicz in Fund. Math. 136, 133-145, 1990) and (Wilkie and Paris in Logic, Methodology and Philosophy of Science VIII (Moscow, 1987). Stud. Logic Found. Math., vol. 126, pp. 143-161. North-Holland, Amsterdam, 1989) related to the problem of Paris and (b) a partial solution to the problem of Clote. © 2007 Springer-Verlag.

We give alternative proofs for results of T. Slaman and N. Thapen, concerning the problem whether or not | Δ1 implies B Σ1. Our proofs isolate structures that could disprove this implication.

We give an alternative proof of a result of T. Slaman, concerning the strength of I Delta(1), i.e. the theory of provably-Delta(1) induction.

We provide an alternative proof of a theorem of P. Clote concerning end extensions of models of Σn-induction, for n ≥ 2.

We work in a model M of I∆_0 +Ω_1, with fraction field K. For each prime p of M we consider the p-adic valuation v_p on K, and prove that K is dense in its Henselization K_p^h. This will be applied in our project of proving quadratic reciprocity law in M.

Inspired by recent work of Meduna on deep pushdown automata, we consider the computational power of a class of basic program schemes, $\mbox{NPSDS}_s$, based around assignments, while-loops and non- deterministic guessing but with access to a deep pushdown stack which, apart from having the usual push and pop instructions, also has deep-push instructions which allow elements to be pushed to stack locations deep within the stack. We syntactically define sub-classes of $\mbox{NPSDS}_s$ by restricting the occurrences of pops, pushes and deep-pushes and capture the complexity classes NP and PSPACE . Furthermore, we show that all problems accepted by program schemes of $\mbox{NPSDS}_s$ are in EXPTIME .