Interpretability degrees of finitely axiomatized sequential theories

In this paper we show that the degrees of interpretability of finitely axiomatized extensions-in-the-same-language of a finitely axiomatized sequential theory—like Elementary Arithmetic EA, IΣ₁, or the Gödel–Bernays theory of sets and classes GB—have suprema. This partially answers a question posed by ?vejdar in his paper (Commentationes Mathematicae Universitatis Carolinae 19:789–813, 1978). The partial solution of ?vejdar’s problem follows from a stronger fact: the convexity of the degree structure of finitely axiomatized extensions-in-the-same-language of a finitely axiomatized sequential theory in the degree structure of the degrees of all finitely axiomatized sequential theories. In the paper we also study a related question: the comparison of structures for interpretability and derivability. In how far can derivability mimic interpretability? We provide two positive results and one negative result.     

Faith & falsity

A theory T is trustworthy iff, whenever a theory U is interpretable in T, then it is faithfully interpretable. In this paper we give a characterization of trustworthiness. We provide a simple proof of Friedman’s Theorem that finitely axiomatized, sequential, consistent theories are trustworthy. We provide an example of a theory whose schematic predicate logic is complete Π₂⁰.     

The complete finitely axiomatized theories of order are dense

We prove a conjecture of Lauchli and Leonard that every sentence of the theory of linear order which has a model, has a model with a finitely axiomatized theory.     

The small‐is‐very‐small principle

The central result of this paper is the small‐is‐very‐small principle for restricted sequential theories. The principle says roughly that whenever the given theory shows that a definable property has a small witness, i.e., a witness in a sufficiently small definable cut, then it shows that the property has a very small witness: i.e., a witness below a given standard number. Which cuts are sufficiently small will depend on the complexity of the formula defining the property. We draw various consequences from the central result. E.g., roughly speaking, (i) every restricted, recursively enumerable sequential theory has a finitely axiomatized extension that is conservative with respect to formulas of complexity $\le n$; (ii) every sequential model has, for any n, an extension that is elementary for formulas of complexity $\le n$, in which the intersection of all definable cuts is the natural numbers; (iii) we have reflection for ${\mathrm{\Sigma }}_2^0$‐sentences with sufficiently small witness in any consistent restricted theory U; (iv) suppose U is recursively enumerable and sequential. Suppose further that every recursively enumerable and sequential V that locally inteprets U, globally interprets U. Then, U is mutually globally interpretable with a finitely axiomatized sequential theory. The paper contains some careful groundwork developing partial satisfaction predicates in sequential theories for the complexity measure depth of quantifier alternations.     

Sequence encoding without induction

We show that the universally axiomatized, induction‐free theory $\mathsf {PA}^-$ is a sequential theory in the sense of Pudlák's 5 , in contrast to the closely related Robinson's arithmetic.     

On extensions of Nelson’s logic satisfying Dummett’s axiom

The class of extensions is completely described of the logic obtained by adding Dummett’s axiom to the paraconsistent Nelson logic. Moreover, we prove that every extension of this logic is finitely axiomatizable and decidable and, given a formula, it is possible to determine which extension is axiomatized by this formula.     

Axiomatization of modal logic squares with distinguished diagonal

Modal logics of squared Kripke frames with distinguished diagonal are considered. It is shown that many such logics, unlike ordinary two-dimensional products, cannot be axiomatized by formulas with finitely many variables. The method resembles that used to obtain a similar result for ≥ 3-dimensional products of modal logics. The proof uses, in particular, generalized Sahlquist formulas.     

A finitely axiomatizable undecidable equational theory with recursively solvable word problems

In this paper we construct a finitely based variety, whose equational theory is undecidable, yet whose word problems are recursively solvable, which solves a problem stated by G. McNulty (1992). The construction produces a discriminator variety with the aforementioned properties starting from a class of structures in some multisorted language (which may include relations), axiomatized by a finite set of universal sentences in the given multisorted signature. This result also presents a common generalization of the earlier results obtained by B. Wells (1982) and A. Mekler, E. Nelson, and S. Shelah (1993).

     

Finitely generated varieties of distributive effect algebras

Lattice-ordered effect algebras generalize both MV-algebras and orthomodular lattices. In this paper, finitely generated varieties of distributive lattice effect algebras are axiomatized, and for any positive integer n, the free n-generator algebras in these varieties are described.     

Peano Corto and Peano Basso: A Study of Local Induction in the Context of Weak Theories

In this paper we study local induction w.r.t. Σ₁‐formulas over the weak arithmetic . The local induction scheme, which was introduced in 7 , says roughly this: for any virtual class that is progressive, i.e., is closed under zero and successor, and for any non‐empty virtual class that is definable by a Σ₁‐formula without parameters, the intersection of and is non‐empty. In other words, we have, for all Σ₁‐sentences S, that S implies , whenever is progressive. Since, in the weak context, we have (at least) two definitions of Σ₁, we obtain two minimal theories of local induction w.r.t. Σ₁‐formulas, which we call Peano Corto and Peano Basso. In the paper we give careful definitions of Peano Corto and Peano Basso. We establish their naturalness both by giving a model theoretic characterization and by providing an equivalent formulation in terms of a sentential reflection scheme. The theories Peano Corto and Peano Basso occupy a salient place among the sequential theories on the boundary between weak and strong theories. They bring together a powerful collection of principles that is locally interpretable in . Moreover, they have an important role as examples of various phenomena in the metamathematics of arithmetical (and, more generally, sequential) theories. We illustrate this by studying their behavior w.r.t. interpretability, model interpretability and local interpretability. In many ways the theories are more like Peano arithmetic or Zermelo Fraenkel set theory, than like finitely axiomatized theories as Elementary Arithmetic, and . On the one hand, Peano Corto and Peano Basso are very weak: they are locally cut‐interpretable in . On the other hand, they behave as if they were strong: they are not contained in any consistent finitely axiomatized arithmetical theory, however strong. Moreover, they extend , the theory of parameter‐free Π₁‐induction.     

The logic of π1-conservativity

We show that the modal prepositional logicILM (interpretability logic with Montagna's principle), which has been shown sound and complete as the interpretability logic of Peano arithmetic PA (by Berarducci and Savrukov), is sound and complete as the logic of ₁-conservativity over eachbE ₁-sound axiomatized theory containingI ₁ (PA with induction restricted tobE ₁-formulas). Furthermore, we extend this result to a systemILMR obtained fromILM by adding witness comparisons in the style of Guaspari's and Solovay's logicR (this will be done in a separate continuation of the present paper).     

Semigroup actions on posets and preimage quasi-orders

Structures consisting of a semigroup of (partial) functions on a set X, a?poset of subsets of X, and a preimage operation linking the two, arise commonly throughout mathematics. The poset may be equipped with one or more set operations, up to Boolean algebra structure. Such structures are finitely axiomatized here in terms of order-preserving semigroup actions on posets. This generalises Schein??s axiomatization of semigroups of partial functions equipped with the first projection quasi-order.     

Congruence distributive quasivarieties whose finitely subdirectly irreducible members form a universal class

By a congruence distributive quasivariety we mean any quasivarietyK of algebras having the property that the lattices of those congruences of members ofK which determine quotient algebras belonging toK are distributive. This paper is an attempt to study congruence distributive quasivarieties with the additional property that their classes of relatively finitely subdirectly irreducible members are axiomatized by sets of universal sentences. We deal with the problem of characterizing such quasivarieties and the problem of their finite axiomatizability.Presented by Joel Berman.To the memory of Basia Czelakowska.     

Interactions between party members and local party activists: A formal model and its empirical application*

Data taken from two surveys among party members and local party activists are used to test a formal theory of intra‐party interaction at a low regional level. For this purpose a miniature version of legitimation theory is axiomatized according to Joseph D. Sneed's proposals. A possible partial model for this miniature theory is defined, terms theoretical in this theory are introduced to make up a possible model of the theory, and several variants of the model of this theory are discussed together with their empirical claims. The axiomatized theory does not only allow the interpretation of empirical correlations among attitudinal variables as effects of interactions between persons bearing those attitudes, but also compels to consider nonlinear interactions as well.     

The Fraenkel‐Carnap question for Dedekind algebras

It is shown that the second‐order theory of a Dedekind algebra is categorical if it is finitely axiomatizable. This provides a partial answer to an old and neglected question of Fraenkel and Carnap: whether every finitely axiomatizable semantically complete second‐order theory is categorical. It follows that the second‐order theory of a Dedekind algebra is finitely axiomatizable iff the algebra is finitely characterizable. It is also shown that the second‐order theory of a Dedekind algebra is quasi‐finitely axiomatizable iff the algebra is quasi‐finitely characterizable.     

Robinson forcing is not absolute

Robinson (or infinite model theoretic) forcing is studied in the context of set theory. The major result is that infinite forcing, genericity, and related notions are not absolute relative to ZFC. This answers a question of G. Sacks and provides a non-trivial example of a non-absolute notion of model theory. This non-absoluteness phenomenon is shown to be intrinsic to the concept of infinite forcing in the sense that any ZFC-definable set theory, relative to which forcing is absolute, has the flavor of asserting self-inconsistency. More precisely: IfT is a ZFC-definable set theory such that the existence of a standard model ofT is consistent withT, then forcing is not absolute relative toT. For example, if it is consistent that ZFC+ “there is a measureable cardinal” has a standard model then forcing is not absolute relative to ZFC+ “there is a measureable cardinal.” Some consequences: 1) The resultants for infinite forcing may not be chosen “effectively” in general. This answers a question of A. Robinson. 2) If ZFC is consistent then it is consistent that the class of constructible division rings is disjoint from the class of generic division rings. 3) If ZFC is consistent then the generics may not be axiomatized by a single sentence ofL _w/w. In Memoriam: Abraham Robinson     

Axiomatizing Provable <Emphasis Type="Italic">n</Emphasis>-Provability

The set of all formulas whose n-provability in a given arithmetical theory S is provable in another arithmetical theory T is a recursively enumerable extension of S. We prove that such extensions can be naturally axiomatized in terms of transfinite progressions of iterated local reflection schemata over S. Specifically, the set of all provably 1-provable sentences in Peano arithmetic PA can be axiomatized by an ε₀-times iterated local reflection schema over PA. The resulting characterizations provide additional information on the proof-theoretic strength of these theories and on the complexity of their axiomatization.     

Axiomatizability of reducts of algebras of relations

In this paper, we prove that any subreduct of the class of representable relation algebras whose similarity type includes intersection, relation composition and converse is a non-finitely axiomatizable quasivariety and that its equational theory is not finitely based. We show the same result for subreducts of the class of representable cylindric algebras of dimension at least three whose similarity types include intersection and cylindrifications. A similar result is proved for subreducts of the class of representable sequential algebras. Received October 7, 1998; accepted in final form September 10, 1999.     

Friedman-reflexivity

In the present paper, we explore an idea of Harvey Friedman to obtain a coordinate-free presentation of consistency. For some range of theories, Friedman's idea delivers actual consistency statements (modulo provable equivalence). For a wider range, it delivers consistency-like statements.We say that a sentence C is an interpreter of a finitely axiomatised A over U iff it is the weakest statement C over U, with respect to U-provability, such that $U+C$ interprets A. A theory U is Friedman-reflexive iff every finitely axiomatised A has an interpreter over U. Friedman shows that Peano Arithmetic, PA, is Friedman-reflexive.We study the question which theories are Friedman-reflexive. We show that a very weak theory, Peano Corto, is Friedman-reflexive. We do not get the usual consistency statements here, but bounded, cut-free, or Herbrand consistency statements. We illustrate that Peano Corto as a base theory has additional desirable properties.We prove a characterisation theorem for the Friedman-reflexivity of sequential theories. We provide an example of a Friedman-reflexive sequential theory that substantially differs from the paradigm cases of Peano Arithmetic and Peano Corto.Interpreters over a Friedman-reflexive U can be used to define a provability-like notion for any finitely axiomatised A that interprets U. We explore what modal logics this idea gives rise to. We call such logics interpreter logics. We show that, generally, these logics satisfy the Löb Conditions, aka K4. We provide conditions for when interpreter logics extend S4, K45, and Löb's Logic. We show that, if either U or A is sequential, then the condition for extending Löb's Logic is fulfilled. Moreover, if our base theory U is sequential and if, in addition, its interpreters can be effectively found, we prove Solovay's Theorem. This holds even if the provability-like operator is not necessarily representable by a predicate of Gödel numbers.At the end of the paper, we briefly discuss how successful the coordinate-free approach is.