We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Combinatorial Isols and the Arithmetic of Dekker Semirings.
- Authors
Mclaughlin, Thomas G.
- Abstract
In his long and illuminating paper [1] Joe Barback defined and showed to be non-vacuous a class of infinite regressive isols he has termed “complete y torre” (CT) isols. These particular isols a enjoy a property that Barback has since labelled combinatoriality. In [2], he provides a list of properties characterizing the combinatoria isols. In Section 2 of our paper, we extend this list of characterizations to include the fact that an infinite regressive isol X is combinatorial if and only if its associated Dekker semiring D (X) satisfies all those Π2 sentences of the anguage LN for isol theory that are true in the set ω of natural numbers. (Moreover, with X combinatorial, the interpretations in D(X)of the various function and relation symbols of LN via the “lifting ” to D(X) of their Σ1 definitions in ω coincide with their interpretations via isolic extension.) We also note in Section 2 that Π2(L)-correctness, for semirings D(X), cannot be improved to Π 3(L)-correctness, no matter how many additional properties we succeed in attaching to a combinatoria isol; there is a fixed <UEQN>${\vec \forall} {\vec \exists} {\vec \forall}$</UEQN>(L) sentence that blocks such extension. (Here L is the usual basic first-order language for arithmetic.) In Section 3, we provide a proof of the existence of combinatorial isols that does not involve verification of the extremely strong properties that characterize Barback's CT isols.
- Subjects
RECURSION theory; ISOLS; RECURSIVE functions; MATHEMATICS; COMBINATORIAL group theory; GROUP theory
- Publication
Mathematical Logic Quarterly, 2002, Vol 48, Issue 3, p323
- ISSN
0942-5616
- Publication type
Article
- DOI
10.1002/1521-3870(200204)48:3<323::AID-MALQ323>3.0.CO;2-C