Which groups are isomorphic to automorphism groups of models of Peano Arithmetic? It will be shown here that any group that has half a chance of being isomorphic to the automorphism group of some model of Peano Arithmetic actually is.

For any structure , let Aut() be its automorphism group. There are groups which are not isomorphic to any model = (N, +, ·, 0, 1, ≤) of PA. For example, it is clear that Aut(N), being a subgroup of Aut((, <)), must be torsion-free. However, as will be proved in this paper, if (A, <) is a linearly ordered set and G is a subgroup of Aut((A, <)), then there are models of PA such that Aut() ≅ G.

If is a structure, then its automorphism group can be considered as a topological group by letting the stabilizers of finite subsets of A be the basic open subgroups. If ′ is an expansion of , then Aut(′) is a closed subgroup of Aut(). Conversely, for any closed subgroup G ≤ Aut() there is an expansion ′ of such that Aut(′) = G. Thus, if is a model of PA, then Aut() is not only a subgroup of Aut((N, <)), but it is even a closed subgroup of Aut((N, ′)).

There is a characterization, due to Cohn [2] and to Conrad [3], of those groups G which are isomorphic to closed subgroups of automorphism groups of linearly ordered sets.

Various results have been proved about growth rates of certain sequences of integers associated with infinite permutation groups. Most of these concern the number of orbits of the automorphism group of an ℵ0-categorical structure on the set of unordered n-subsets or on the set of n-tuples of elements of . (Recall that by the Ryll-Nardzewski Theorem, if is countable and ℵ0-categorical, the number of the orbits of its automorphism group Aut() on the set of n-tuples from is finite and equals the number of complete n-types consistent with the theory of .) The book [Ca90] is a convenient reference for these results. One of the oldest (in the realms of ‘folklore’) is that for any sequence (Kn)n∈ℕ of natural numbers there is a countable ℵ0-categorical structure such that the number of orbits of Aut() on the set of n-tuples from is greater than kn for all n.

These investigations suggested the study of the growth rate of another sequence. Let be an ℵ0-categorical structure and X be a finite subset of . Let acl(X) be the algebraic closure of X, that is, the union of the finite X-definable subsets of . Equivalently, this is the union of the finite orbits on of Aut()(X), the pointwise stabiliser of X in Aut(). Define

This paper introduces valuation structures associated with preferential models. Based on KLM valuation structures, we present a canonical approach to obtain injective preferential models for any preferential relation satisfying the property INJ, and give uniform proofs of representation theorems for injective preferential relations appeared in the literature. In particular, we show that, in any propositional language (finite or infinite), a preferential inference relation satisfies INJ if and only if it can be represented by a standard preferential model. This conclusion generalizes the result obtained by Freund. In addition, we prove that, when the language is finite, our framework is sufficient to establish a representation theorem for any injective relation.

Let {We}e∈ω be a standard enumeration of the recursively enumerable (r. e.) subsets of ω = {0, 1, 2, …}. The lattice of recursively enumerable sets, is the structure ({We}e∈ω, ∪, ∩). is the sublattice of consisting of the recursive sets.

Suppose is a lattice of subsets of ω. ≡ is said to be a congruence relation on if ≡ is an equivalence relation on and if for all U, U′ ∈ and V, V ∈ , if U ≡ U′ and V ≡ V′ then U ∪ U′ ≡ V ∪ V′ and U ∩ U′ ≡ V ∩ V′. [U] = {V ∈ | V ≡ U} is the equivalence class of U. If ≡ is a congruence relation on , the elements of the quotient lattice / ≡ are the equivalence classes of ≡. [U] ∪ [V] is defined as [U ∪ V], and [U] ∩ [V] is defined as [U ∩ V].

The quotient lattices of (or of some sublattice ) correspond naturally with the congruence relations which give rise to them, and in turn the congruence relations of sublattices of can be characterized in part by their computational complexity. The aim of the present paper is to characterize congruence relations in some of the most important complexity classes.

Some highly saturated models of Peano Arithmetic are constructed in this paper, which consists of two independent sections. In § 1 we answer a question raised in [10] by constructing some highly saturated, rather classless models of PA. A question raised in [7], [3], ]4] is answered in §2, where highly saturated, nonstandard universes having no bad cuts are constructed.

Highly saturated, rather classless models of Peano Arithmetic were constructed in [10]. The main result proved there is the following theorem. If λ is a regular cardinal and is a λ-saturated model of PA such that ∣M∣ > λ, then has an elementary extension of the same cardinality which is also λ-saturated and which, in addition, is rather classless. The construction in [10] produced a model for which cf() = λ+. We asked in Question 5.1 of [10] what other cofinalities could such a model have. This question is answered here in Theorem 1.1 of §1 by showing that any cofinality not immediately excluded is possible. Its proof does not depend on the theorem from [10]; in fact, the proof presented here gives a proof of that theorem which is much simpler and shorter than the one in [10].

Recursively saturated, rather classless κ-like models of PA were constructed in [9]. In the case of singular κ such models were constructed whenever cf(κ) > ℵ0; no additional set-theoretic hypothesis was needed.

We extend Morley's Theorem to show that if a theory is κ-p-categorical for some uncountable cardinal κ, it is uncountably categorical. We then discuss ω-p-categoricity and provide examples to show that similar extensions for the Baldwin-Lachlan and Lachlan Theorems are not possible.

Each Girard quantale (i.e., commutative quantale with a selected dualizing element) provides a support for a semantics for linear propositional formulas (but not for linear derivations). Several constructions of Girard quantales are known. We give two more constructions, one using an arbitrary partially ordered monoid and one using a partially ordered group (both commutative). In both cases the semantics can be controlled be a relation between pairs of elements of the support and formulas. This gives us a neat way of handling duality.

We prove some results related to the problem of blowing up the power set of the least measurable cardinal. Our forcing results improve those of [1] by using the optimal hypothesis.

We study smooth classes without the algebraic closure property. For such smooth classes we investigate the simplicity of the class of generic structures, in the context of Robinson theories.

The logical flow graphs of sequent calculus proofs might contain oriented cycles. For the predicate calculus the elimination of cycles might be non-elementary and this was shown in [Car96]. For the propositional calculus, we prove that if a proof of k lines contains n cycles then there exists an acyclic proof with (kn+1) lines. In particular, there is a polynomial time algorithm which eliminates cycles from a proof. These results are motivated by the search for general methods on proving lower bounds on proof size and by the design of more efficient heuristic algorithms for proof search.

In this paper we examine the cardinal structure of inner models that satisfy GCH but do not contain 0#. We show, assuming that 0# exists, that such models necessarily contain Mahlo cardinals of high order, but without further assumptions need not contain a cardinal κ which is κ-Mahlo. The principal tools are the Covering Theorem for L and the technique of reverse Easton iteration.

Let I denote the class of Silver indiscernibles for L and 〈iα ∣ α ϵ ORD〉 its increasing enumeration. Also fix an inner model M of GCH not containing 0# and let ωα denote the ωα of the model M[0#], the least inner model containing M as a submodel and 0# as an element.

It is proved that if 1 < m < 2p ≤ n for some integer p then the elementary theories of posets of m-c.e. and n-c.e. e-degrees are distinct. It is proved also that the structures 〈2n, ≤, 〉 and 〈2n, ≤. P〉 are not elementary equivalent where P is the predicate P(a) = “a is a e-degree”.

There has been increasing interest in intuitionistic methods over the years. Still, there has been relatively little work on intuitionistic set theory, and most of that has been on intuitionistic ZF. This investigation is about intuitionistic admissibility and theories of similar strength.

There are several more particular goals for this paper. One is just to get some more Kripke models of various set theories out there. Those papers that have dealt with IZF usually were more proof-theoretic in nature, and did not provide models. Furthermore, the inspirations for many of the constructions here are classical forcing arguments. Although the correspondence between the forcing and the Kripke constructions is not made tight, the relationship between these two methods is of interest (see [6] for instance) and some examples, even if only suggestive, should help us better understand the relationship between forcing and Kripke constructions. Along different lines, the subject of least and greatest fixed points of inductive definitions, while of interest to computer scientists, has yet to be studied constructively, and probably holds some surprises. Admissibility is of course the proper set-theoretic context for this study. Finally, while most of the classical material referred to here has long been standard, some of it has not been well codified and may even be unknown, so along the way we'll even fill in a gap in the classical literature.

The next section develops the basics of IKP, including some remarks on fixed points of inductive definitions.

By a classifiable theory we shall mean a theory which is superstable, without the dimensional order property, which has prime models over pairs. In order to define what we mean by unique decomposition, we remind the reader of several definitions and results. We adopt the usual conventions of stability theory and work inside a large saturated model of a fixed classifiable theory T; for instance, if we write M ⊆ N for models of T, M and N we are thinking of these models as elementary submodels of this fixed saturated models; so, in particular, M is an elementary submodel of N. Although the results will not depend on it, we will assume that T is countable to ease notation.

We do adopt one piece of notation which is not completely standard: if T is classifiable, M0 ⊆ Mi for i = 1, 2 are models of T and M1 is independent from M2 over M0 then we write M1M2 for the prime model over M1 ∪ M2.

It is proved that free dynamic algebras superamalgamate. Craig interpolation for propositional dynamic logic and superamalgamation for the variety of dynamic algebras follow.

In the paper we introduce and study regular enumerations for arbitrary recursive ordinals. Several applications of the technique are presented.

We show that every finite lattice is embeddable into the Σ20 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

We prove the following theorems:

1. If X ⊆ 2ω is a γ-set and Y ⊆2ω is a strongly meager set, then X + Y is Ramsey null.

2. If X ⊆2ω is a γ-set and Y belongs to the class of sets, then the algebraic sum X + Y is an set as well.

3. Under CH there exists a set X ∈ MGR* which is not Ramsey null.