In this paper we establish the following theorems.

Theorem A. Let T be a complete first-order theory which is uncountable, Then:

(i) I(∣T∣, T) ≥ ℵ0

(ii) If T is not unidimensional, then for any λ ≥ ∣T∣, I(λ, T) ≥ ℵ0.

Theorem B. Let T be superstable, not totally transcendental and nonmultidimensional. Let θ(x) be a formula of least R∞ rank which does not have Morley rank, and let p be any stationary completion of θ which also fails to have Morley rank. Then p is regular and locally modular.

We show that the ℵ0-categorical structures produced by Hrushovski's predimension construction with a control function fit neatly into Shelah's SOPn hierarchy: if they are not simple, then they have SOP3 and NSOP4. We also show that structures produced without using a control function can be undecidable and have SOP.

In this paper a general method of proving the undecidability of a property P, for finite sets Σ of equations of a countable algebraic language, is presented. The method is subsequently applied to establish the undecidability of the following properties, in almost all nontrivial such languages:

1. 1. The first-order theory generated by the infinite models of Σ is complete.

2. 2. The first-order theory generated by the infinite models of Σ is model-complete.

3. 3. Σ has the joint-embedding property.

4. 4. The first-order theory generated by the models of Σ with more than one element has the joint-embedding property.

5. 5. The first-order theory generated by the infinite models of Σ has the joint-embedding property.

A countable algebraic language ℒ is a first-order language with equality, with countably many nonlogical symbols but without relation symbols, ℒ is trivial if it has at most one operation symbol, and this is of rank one. Otherwise, ℒ is nontrivial. An ℒ-equation is a sentence of the form , where φ and ψ are ℒ-terms. The set of ℒ-equations is denoted by Eqℒ. A set of sentences is said to have the joint-embedding property if any two models of it are embeddable in a third model of it.

If P is a property of sets of ℒ-equations, the decision problem of P for finite sets of ℒ-equations is the problem of the existence or not of an algorithm for deciding whether, given a finite Σ ⊂ Eqℒ, Σ has P or not.

Here we consider some problems concerning regular types. In the first place we consider a strongly minimal set D. One can ask what is the strength of the assumption that D has (full) elimination of imaginaries (namely, every definable set X over D has as canonical parameter some tuple from D). We show that D cannot be locally modular. Nontriviality of D is immediate. However, to exclude the locally modular nontrivial case one has to understand structures of the form G/E, where G is a modular strongly minimal group and E is a definable equivalence relation on G with finite classes. We show that the quotient structure G/E can be obtained in two steps. First quotient by a finite subgroup K of G to obtain a strongly minimal group H. Now let Γ be a finite subgroup of the group Aff(H) of definable affine automorphisms of H (namely maps of the form x → αx + a, where α is a definable automorphism of H and a ∈ H), and quotient H by Γ (namely form the orbit space of H under Γ). It can clearly be arranged that Γ contains no nontrivial subgroup of translations.

In the second place we look at a nontrivial modular regular type p whose pregeometry is actually a geometry. The geometry is then known to be (infinite-dimensional) projective geometry over a division ring F. We ask whether F is definable (internally to p). If F is finite, this is clear. In fact in this case p must have U-rank 1. So we assume F to be infinite. We are only able to show definability of F in the case where F is a field, using some results on 2-transitive subgroups of PGL [V]. Moreover in the superstable case we also observe that p is isolated.

In [1] S. Buss introduced systems of bounded arithmetic , , , (i = 1, 2, 3, …). and are first order systems and and are second order systems. and are closely related to and respectively in the polynomial hierarchy, and and are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether = or = for some i, or whether = , or whether is a conservative extension of S 2 = ⋃i . These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that = implies and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.

It is proved that the (2p)-c. e. e-degrees are not elementarily equivalent to the (2p + 1)-c. e. e-degrees for each nonzero p ∈ ω. It follows that m-c. e. e-degrees are not elementarily equivalent to the n-c e. e-degrees if 1 <m < n.

The Stoic “indemonstrables” were inference rules; a rule about rules was the synthetic theorem: if from certain premisses a conclusion follows and from that conclusion and certain further premisses a second conclusion follows, then the second conclusion follows from all the premisses together. Similar things occur as medieval “rules of consequence”, although not usually on a metametalevel; and (with the same proviso) the following might be deemed a contemporary avatar of that Stoic theorem.

If every formula which occurs once or more often in the list A1, A2, …, An, B1, B2, …, Bm occurs also at least once in the list C1, C2, …, Cr then:

This rule [Church: Introduction to Mathematical Logic, 1956, pp. 94, 165], which may be called the rule of modus ponens under hypotheses (MPH), is worthy of attention for the following reasons:

A. MPH and the axioms A ⊃ A yield precisely the positive implicative calculus (and very easily, too).

B. MPH and the axioms A ⊃ f ⊃ f ⊃ A yield a new formulation of the full classical propositional calculus (in terms of f and ⊃).

C. MPH and the axioms ∼A ⊃ A ⊃ A and A ⊃. ∼A ⊃ B yield the classical calculus in terms of ∼ and ⊃.

Necessary and sufficient conditions are presented for the (first-order) theory of a universal class of algebraic structures (algebras) to have a model completion, extending a characterization provided by Wheeler. For varieties of algebras that have equationally definable principal congruences and the compact intersection property, these conditions yield a more elegant characterization obtained (in a slightly more restricted setting) by Ghilardi and Zawadowski. Moreover, it is shown that under certain further assumptions on congruence lattices, the existence of a model completion implies that the variety has equationally definable principal congruences. This result is then used to provide necessary and sufficient conditions for the existence of a model completion for theories of Hamiltonian varieties of pointed residuated lattices, a broad family of varieties that includes lattice-ordered abelian groups and MV-algebras. Notably, if the theory of a Hamiltonian variety of pointed residuated lattices has a model completion, it must have equationally definable principal congruences. In particular, the theories of lattice-ordered abelian groups and MV-algebras do not have a model completion, as first proved by Glass and Pierce, and Lacava, respectively. Finally, it is shown that certain varieties of pointed residuated lattices generated by their linearly ordered members, including lattice-ordered abelian groups and MV-algebras, can be extended with a binary operation to obtain theories that do have a model completion.

In the present paper we use the theory of exact completions to study categorical properties of small setoids in Martin-Löf type theory and, more generally, of models of the Constructive Elementary Theory of the Category of Sets, in terms of properties of their subcategories of choice objects (i.e., objects satisfying the axiom of choice). Because of these intended applications, we deal with categories that lack equalisers and just have weak ones, but whose objects can be regarded as collections of global elements. In this context, we study the internal logic of the categories involved, and employ this analysis to give a sufficient condition for the local cartesian closure of an exact completion. Finally, we apply this result to show when an exact completion produces a model of CETCS.

We introduce type-theoretic algebraic weak factorisation systems and show how they give rise to homotopy-theoretic models of Martin-Löf type theory. This is done by showing that the comprehension category associated with a type-theoretic algebraic weak factorisation system satisfies the assumptions necessary to apply a right adjoint method for splitting comprehension categories. We then provide methods for constructing several examples of type-theoretic algebraic weak factorisation systems, encompassing the existing groupoid and cubical sets models, as well as new models based on normal fibrations.

In this paper we ask the question: to what extent do basic set theoretic properties of Loeb measure depend on the nonstandard universe and on properties of the model of set theory in which it lies? We show that, assuming Martin's axiom and κ-saturation, the smallest cover by Loeb measure zero sets must have cardinality less than κ. In contrast to this we show that the additivity of Loeb measure cannot be greater than ω1. Define cof(H) as the smallest cardinality of a family of Loeb measure zero sets which cover every other Loeb measure zero set. We show that card(⌊log2(H)⌋) ≤ cof (H) ≤ card(2H), where card is the external cardinality. We answer a question of Paris and Mills concerning cuts in nonstandard models of number theory. We also present a pair of nonstandard universes M ≼ N and hyperfinite integer H ∈ M such that H is not enlarged by N, 2H contains new elements, but every new subset of H has Loeb measure zero. We show that it is consistent that there exists a Sierpiński set in the reals but no Loeb-Sierpiński set in any nonstandard universe. We also show that it is consistent with the failure of the continuum hypothesis that Loeb-Sierpiński sets can exist in some nonstandard universes and even in an ultrapower of a standard universe.

One of the simplest and yet most fruitful ideas in forcing was the notion of Karel Prikry in which he used a measure on a cardinal κ to change the cofinality of κ to ω without collapsing it. The idea has found connections to almost every branch of modern set theory, from large cardinals to small, from combinatorics to models, from Choice to Determinacy, and from consistency to inconsistency. The long list of generalizers and modifiers includes Apter, Gitik, Henle, Spector, Shelah, Mathias, Magidor, Radin, Blass and Kimchi.

This paper is about generalizing Prikry forcing and partition properties to “simple spaces”. The concept of a simple space is itself the generalization of those combinatorial objects upon which the notions of “measurable”, “compact”, “supercompact”, “huge”, etc. are based. Simple spaces were introduced in [ADHZ1] and [ADHZ2] together with a broader generalization, “filter spaces”. The definition provided here is a small simplification of earlier versions. The author is indebted to Mitchell Spector, whose careful reading turned up numerous errors, some subtle, some flagrant.

In this first section, we review simple spaces briefly, including a short introduction to the space Qκλ. In §2, we describe our generalizations of partition property and Prikry forcing, and discuss the relationship between them. In §3, we find a partition property for the huge space [λ]κ, but show that Prikry forcing here is impossible. We find partition properties for Qκλ and show that Prikry forcing can be done here.

We generalize the model theory of small profinite structures developed by Newelski to the case of compact metric spaces considered together with compact groups of homeomorphisms and satisfying the existence of m-independent extensions (we call them compact e-structures). We analyze the relationships between smallness and different versions of the assumption of the existence of m-independent extensions and we obtain some topological consequences of these assumptions. Using them, we adopt Newelski's proofs of various results about small profinite structures to compact e-structures. In particular, we notice that a variant of the group configuration theorem holds in this context.

A general construction of compact structures is described. Using it, a class of examples of compact e-structures which are not small is constructed.

It is also noticed that in an m-stable compact e-structure every orbit is equidominant with a product of m-regular orbits.

The present note suggests how the computation of complexity-values outlined in The logical simplicity of predicates may be so modified as to satisfy a more stringent requirement than was there imposed.

By the method of computation described in that article, a basis consisting of two two-place predicates has in general the value 6. Any such basis may be replaced by one four-place predicate that is self-complete with respect to two of its places and also with respect to the remaining two. Such a predicate has but one “joint,” and therefore a value of 5. The consolidation of the two predicates into one thus results in a basis having a lower complexity-value. This does not violate the cardinal rule laid down in that article for testing proposed ways of assigning complexity-values; for, conversely, a four-place predicate that is self-complete in the way described can always be replaced by two two-place prediates. The rule requires a four-place predicate of the kind described to have a higher value than two two-place predicates only if replacement of two two-place predicates by such a four-place predicate is always possible, while replacement of such a four-place predicate by two two-place predicates is not.

However, we might reasonably strengthen our cardinal rule for complexity-valuation by adding as a second requirement:

If each basis of kind A is always replaceable by some basis of kind B, and each basis of kind B is always replaceable by some basis of kind A, then a basis of kind A and a basis of kind B must, in the absence of contrary indications, have the same complexity-value.

We propose a simple notion of “extender” for coding large elementary embeddings of models of set theory. As an application we present a self-contained proof of the theorem by D. Martin and J. Steel that infinitely many Woodin cardinals imply the determinacy of every projective set.