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

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.

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.

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 free dynamic algebras superamalgamate. Craig interpolation for propositional dynamic logic and superamalgamation for the variety of dynamic algebras follow.

Given any field K, there is a function field F/K in one variable containing definable transcendental over K, i.e., elements in F / K first-order definable in the language of fields with parameters from K. Hence, the model-theoretic and the field-theoretic relative algebraic closure of K in F do not coincide. E.g., if K is finite, the model-theoretic algebraic closure of K in the rational function field K(t) is K(t).

For the proof, diophantine ∅-definability ofK in F is established for any function field F/K in one variable, provided K is large, or K× /(K×)n is finite for some integer n > 1 coprime to char K.

The study of pseudo-algebraically closed fields (henceforth called PAC) started with the work of J. Ax on finite and pseudo-finite fields [1]. He showed that the infinite models of the theory of finite fields are exactly the perfect PAC fields with absolute Galois group isomorphic to , and gave elementary invariants for their first order theory, thereby proving the decidability of the theory of finite fields. Ax's results were then extended to a larger class of PAC fields by M. Jarden and U. Kiehne [21], and Jarden [19]. The final word on theories of PAC fields was given by G. Cherlin, L. van den Dries and A. Macintyre [10], see also results by Ju. Ershov [13], [14]. Let K be a PAC field. Then the elementary theory of K is entirely determined by the following data:

• The isomorphism type of the field of absolute numbers of K (the subfield of K of elements algebraic over the prime field).

• The degree of imperfection of K.

• The first-order theory, in a suitable ω-sorted language, of the inverse system of Galois groups al(L/K) where L runs over all finite Galois extensions of K.

They also showed that the theory of PAC fields is undecidable, by showing that any graph can be encoded in the absolute Galois group of some PAC field. It turns out that the absolute Galois group controls much of the behaviour of the PAC fields. I will give below some examples illustrating this phenomenon.

We consider separably closed fields of characteristic p > 0 and fixed imperfection degree as modules over a skew polynomial ring. We axiomatize the corresponding theory and we show that it is complete and that it admits quantifier elimination in the usual module language augmented with additive functions which are the analog of the p-component functions.

We show that if p is a real type which is almost internal in a formula φ in a simple theory, then there is a type p′ interalgebraic with a finite tuple of realizations of p, which is generated over φ. Moreover, the group of elementary permutations of p′ over all realizations of φ is type-definable.

Let T be a model-complete theory that eliminates the quantifier ∃∞x For T we construct a theory T+ such that any element in a model of T+ determines a model of T. We show that T+ has a model companion T1. We can iterate the construction. The produced theories are investigated.

A propositional system of modal logic is second-order if it contains quantifiers ∀p and ∃p which, in the standard interpretation, are construed as ranging over sets of possible worlds (propositions). Most second-order systems of modal logic are highly intractable; for instance, when augmented with propositional quantifiers, K, B, T, K4 and S4 all become effectively equivalent to full second-order logic. An exception is S5, which, being interpretable in monadic second-order logic, is decidable.

In this paper we generalize this framework by allowing multiple modalities. While this does not affect the undecidability of K, B, T, K4 and S4, poly-modal second-order S5 is dramatically more expressive than its mono-modal counterpart. As an example, we establish the definability of the transitive closure of finitely many modal operators. We also take up the decidability issue, and, using a novel encoding of sets of unordered pairs by partitions of the leaves of certain graphs, we show that the second-order propositional logic of two S5 modalitities is also equivalent to full second-order logic.

Say that (a, d) is an isolation pair if a is a c.e. degree, d is a d.c.e. degree, a < d and a bounds all c.e. degrees below d. We prove that there are an isolation pair (a, d) and a c.e. degree c such that c is incomparable with a, d, and c cups d to o′, caps a to o. Thus, {o, c, d, o′} is a diamond embedding, which was first proved by Downey in [9]. Furthermore, combined with Harrington-Soare continuity of capping degrees, our result gives an alternative proof of N5 embedding.

The Logic of Partial Terms LPT is a strict negative free logic that provides an economical framework for developing many traditional mathematical theories having partial functions. In these traditional theories, all functions and predicates are strict. For example, if a unary function (predicate) is applied to an undefined argument, the result is undefined (respectively, false). On the other hand, every practical programming language incorporates at least one nonstrict or lazy construct, such as the if-then-else, but nonstrict functions cannot be either primitive or introduced in definitional extensions in LPT. Consequently, lazy programming language constructs do not fit the traditional mathematical mold inherent in LPT. A nonstrict (positive free) logic is required to handle nonstrict functions and predicates.

Previously developed nonstrict logics are not fully satisfactory because they are verbose in describing strict functions (which predominate in many programming languages), and some logicians find their semantics philosophically unpalatable. The newly developed Lazy Logic of Partial Terms LL is as concise as LPT in describing strict functions and predicates, and strict and nonstrict functions and predicates can be introduced in definitional extensions of traditional mathematical theories. LL is “built on top of” LPT. and, like LPT, admits only one domain in the semantics. In the semantics, for the case of a nonstrict unary function h in an LL theory T, we have ⊨Th(⊥) = y ↔ ∀x(h(x) = y), where ⊥ is a canonical undefined term. Correspondingly, in the axiomatization, the “indifference” (to the value of the argument) axiom h(⊥) = y ↔ ∀x(h(x) = y) guarantees a proper fit with the semantics. The price paid for LL's naturalness is that it is tailored for describing a specific area of computer science, program specification and verification, possibly limiting its role in explicating classical mathematical and philosophical subjects.

For X ⊆ ω, let [X]n denote the class of all n-element subsets of X. An infinite set A ⊆ ω is called n-r-cohesive if for each computable function f: [ω]n → {0, 1} there is a finite set F such that f is constant on [A − F]n. We show that for each n > 2 there is no Πn0 set A ⊆ ω which is n-r-cohesive. For n = 2 this refutes a result previously claimed by the authors, and for n ≥ 3 it answers a question raised by the authors.

In [9] we introduced a new framework for asymptotic probabilities, in which a σ-additive measure is defined on the sample space of all sequences of finite models, where the universe of , is {1,2,…,n}. In this framework we investigated the strong 0-1 law for sentences, which states that each sentence either holds in eventually almost surely or fails in eventually almost surely.

In this paper we define the strong convergence law for formulas, which carries over the ideas of the strong 0-1 law to formulas with free variables, and roughly states that for each formula ϕ(x), the fraction of tuples a in , which satisfy the formula ϕ(x), almost surely has a limit as n tends to infinity.

We show that the infinitary logic with finitely many variables has the strong convergence law for formulas for the uniform measure, and further characterize the measures on random graphs for which the strong convergence law holds.

This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting.

For every ring S with identity, the (right) Ziegler spectrum of S, Zgs, is the set of (isomorphism classes of) indecomposable pure injective (right) S-modules. The Ziegler topology equips Zgs with the structure of a topological space. A typical basic open set in this topology is of the form

where φ and ψ are pp-formulas (with at most one free variable) in the first order language Ls for S-modules; let [φ/ψ] denote the closed set Zgs - (φ/ψ). There is an alternative way to introduce the Ziegler topology on Zgs. For every choice of two f.p. (finitely presented) S-modules A, B and an S-module homomorphism f: A → B, consider the set (f) of the points N in Zgs such that some S-homomorphism h: A → N does not factor through f. Take (f) as a basic open set. The resulting topology on Zgs is, again, the Ziegler topology.

The algebraic and model-theoretic relevance of the Ziegler topology is discussed in [Z], [P] and in many subsequent papers, including [P1], [P2] and [P3], for instance. Here we are interested in the Ziegler spectrum ZgRG of a group ring RG, where R is a Dedekind domain of characteristic 0 (for example R could be the ring Z of integers) and G is a finite group. In particular we deal with the R-torsionfree points of ZgRG.

The main motivation for this is the study of RG-lattices (i.e., finitely generated R-torsionfree RG-modules).

We prove that a form of the Erdӧs property (consistent with V = L[Hω2] and strictly weaker than the Weak Chang's Conjecture at ω1), together with Bounded Martin's Maximum implies that Woodin's principle ψAC holds, and therefore . We also prove that ψAC implies that every function f: ω1 → ω1 is bounded by some canonical function on a club and use this to produce a model of the Bounded Semiproper Forcing Axiom in which Bounded Martin's Maximum fails.

In this paper we present some metapredicative subsystems of analysis. We deal with reflection principles, ω-model existence axioms (limit axioms) and axioms asserting the existence of hierarchies. We show several equivalences among the introduced subsystems. In particular we prove the equivalence of Σ11 transfinite dependent choice and Π21 reflection on ω-models of Σ11-DC.

Assume (ℵ0, ℵ1) → (λ, λ+). Assume M is a model of a first order theory T of cardinality at most λ+ in a language of cardinality ≤ λ. Let N be a model with the same language. Let Δ be a set of first order formulas in and let D be a regular filter on λ. Then M is Δ-embeddable into the reduced power Nλ/D, provided that every Δ-existential formula true in M is true also in N. We obtain the following corollary: for M as above and D a regular ultrafilter over λ, Mλ/D is λ++-universal. Our second result is as follows: For i < μ let Mi, and Ni, be elementarily equivalent models of a language which has cardinality ≤ λ. Suppose D is a regular filter on λ and (ℵ0, ℵ1) → (λ, λ+) holds. We show that then the second player has a winning strategy in the Ehrenfeucht-Fraïssé game of length λ+ on ΠiMi/D and ΠiNi/D. This yields the following corollary: Assume GCH and λ regular (or just (ℵ0, ℵ1) → (λ, λ+) and 2λ = λ+. For L, Mi and Ni be as above, if D is a regular filter on λ, then ΠiMi/D ≅ ΠiNi/D.