Abstract Answering a question of Cifú Lopes, we give a syntactic characterization of those continuous sentences that are preserved under reduced products of metric structures. In fact, we settle this question in the wider context of general structures as introduced by the second author.

Abstract Every complete first order theory has a corresponding complete theory in continuous logic, called the randomization theory. It has two sorts, a sort for random elements of models of the first order theory, and a sort for events. In this paper we establish connections between properties of countable models of a first order theory and corresponding properties of separable models of the randomization theory. We show that the randomization theory has a prime model if and only if the first order theory has a prime model. And the randomization theory has the same number of separable homogeneous models as the first order theory has countable homogeneous models. We also show that when T has at most countably many countable models, each separable model of TR is uniquely characterized by a probability density function on the set of isomorphism types of countable models of T. This yields an analogue for randomizations of the results of Baldwin and Lachlan on countable models of ω1-categorical first order theories.

We show that for each n and m, there is an existential first order sentence that is NOT logically equivalent to a sentence of quantifier rank at most m in infinitary logic augmented with all generalized quantifiers of arity at most n. We use this to show the strictness of the quantifier rank hierarchies for various logics ranging from existential (or universal) fragments of first-order logic to infinitary logics augmented with arbitrary classes of generalized quantifiers of bounded arity. The sentence above is also shown to be equivalent to a first-order sentence with at most n+2 variables (free and bound). This gives the strictness of the quantifier rank hierarchies for various logics with only n+2 variables. The proofs use the bijective Ehrenfeucht–Fraïsse game and a modification of the building blocks of Hella.

Abstract We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like ∃≥3/4y which says that “for at least 3/4 of all y”. These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are: 1. We deal with the quantifier ∃≥ry, where y is a tuple of variables. 2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope. 3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities PR for each predicate symbol R. 4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs). 5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers. 6. We allow each PR, as well as each r in the probability quantifier (∃≥ry), to depend on the size of the universe.

Abstract This paper studies the expressive power that an extra first order quantifier adds to a fragment of monadic second order logic, extending the toolkit of Janin and Marcinkowski [JM01]. We introduce an operation existsn (S) on properties S that says “there are n components having S”. We use this operation to show that under natural strictness conditions, adding a first order quantifier word u to the beginning of a prefix class V increases the expressive power monotonically in u. As a corollary, if the first order quantifiers are not already absorbed in V, then both the quantifier alternation hierarchy and the existential quantifier hierarchy in the positive first order closure of V are strict. We generalize and simplify methods from Marcinkowski [Mar99] to uncover limitations of the expressive power of an additional first order quantifier, and show that for a wide class of properties S, S cannot belong to the positive first order closure of a monadic prefix class W unless it already belongs to W. We introduce another operation alt(S) on properties which has the same relationship with the Circuit Value Problem as reach(S) (defined in [JM01]) has with the Directed Reachability Problem. We use alt(S) to show that Πn ⊈ FO(Σn), Σn ⊈ FO(∆n). and ∆n+1 ⊈ FOB(Σn), solving some open problems raised in [Mat98].

Abstract We settle a number of questions concerning definability in first order logic with an extra predicate symbol ranging over semi-linear sets. We give new results both on the positive and negative side: we show that in first-order logic one cannot query a semi-linear set as to whether or not it contains a line, or whether or not it contains the line segment between two given points. However, we show that some of these queries become definable if one makes small restrictions on the semi-linear sets considered.

Abstract We characterize Maharam spectra of Loeb probability spaces and give some applications of the results.

Abstract We shall prove quantifier elimination theorems for neocompact formulas, which define neocompact sets and are built from atomic formulas using finite disjunctions, infinite conjunctions, existential quantifiers, and bounded universal quantifiers. The neocompact sets were first introduced to provide an easy alternative to nonstandard methods of proving existence theorems in probability theory, where they behave like compact sets. The quantifier elimination theorems in this paper can be applied in a general setting to show that the family of neocompact sets is countably compact. To provide the necessary setting we introduce the notion of a law structure. This notion was motivated by the probability law of a random variable. However, in this paper we discuss a variety of model theoretic examples of the notion in the light of our quantifier elimination results.

In this paper we study notions of a “meager subset” of a hyper-finite set. We work within an ω-saturated nonstandard universe and fix a hyperfinite natural number Є *N∖N. We shall consider subsets of the set = {1, 2, …,H}. By analogy with the meager subsets of the real interval [0, 1], a notion of meager subset of should have the following properties. 1. Finite sets, countable unions of meager sets, subsets of meager sets, and translates of meager sets should be meager. 2. The Baire Category Theorem should hold; that is, should not be meager. 3. The internal analogue of the Cantor set should be meager. 4. The notion of a meager set should be with respect to a natural topology on . 5. There should exist meager subsets of of Loeb measure one. 6. Sierpiński and Lusin sets should have hyperfinite counterparts with properties similar to the classical case. Property 5 is desirable so that, as with Lebesgue measure and Baire category on [0, 1], the topological and measure-theoretic notions of “large” and “small” sets are incomparable. Property 6, while not as necessary as the other five, is desirable because of the strong interplay between measure and category in the classical results about Lusin and Sierpinski sets. Our objective is to find notions of meager set which have a relationship to Loeb measure similar to the classical relationship between meager sets and Lebesgue measure.

Abstract In a nonstandard universe, the κ -saturation property states that any family of fewer than κ internal sets with the finite intersection property has a nonempty intersection. An ordered field F is said to have the λ -Bolzano-Weierstrass property iff F has cofinality λ and every bounded λ -sequence in F has a convergent λ -subsequence. We show that if κ < λ are uncountable regular cardinals and β α < λ whenever α < κ and β < λ then there is a κ -saturated nonstandard universe in which the hyperreal numbers have the λ -Bolzano-Weierstrass property. The result also applies to certain fragments of set theory and second order arithmetic.

Abstract The separation, uniformization, and other properties of the Borel and projective hierarchies over hyperfinite sets are investigated and compared to the corresponding properties in classical descriptive set theory. The techniques used in this investigation also provide some results about countably determined sets and functions, as well as an improvement of an earlier theorem of Kunen and Miller.

It is often asserted in the literature that any theorem which can be proved using nonstandard analysis can also be proved without it. The purpose of this paper is to show that this assertion is wrong, and in fact there are theorems which can be proved with nonstandard analysis but cannot be proved without it. There is currently a great deal of confusion among mathematicians because the above assertion can be interpreted in two different ways. First, there is the following correct statement: any theorem which can be proved using nonstandard analysis can be proved in Zermelo-Fraenkel set theory with choice, ZFC, and thus is acceptable by contemporary standards as a theorem in mathematics. Second, there is the erroneous conclusion drawn by skeptics: any theorem which can be proved using nonstandard analysis can be proved without it, and thus there is no need for nonstandard analysis. The reason for this confusion is that the set of principles which are accepted by current mathematics, namely ZFC, is much stronger than the set of principles which are actually used in mathematical practice. It has been observed (see [F] and [S]) that almost all results in classical mathematics use methods available in second order arithmetic with appropriate comprehension and choice axiom schemes.

Abstract We consider extensions of Peano arithmetic suitable for doing some of nonstandard analysis, in which there is a predicate N(x) for an elementary initial segment, along with axiom schemes approximating ω1-saturation. We prove that such systems have the same proof-theoretic strength as their natural analogues in second order arithmetic. We close by presenting an even stronger extension of Peano arithmetic, which is equivalent to ZF for arithmetic statements.

Abstract The language LA(Ⅎ) is formed by adding the quantifier Ⅎx, “few x”, to the infinitary logic LA on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where Ⅎx is interpreted as there exist A-finitely many x. For well-behaved A, every consistent sentence has a model with an A-recursive diagram. A principal tool is forcing for LA(Ⅎ).

Abstract Let T be a complete theory with infinite models in a countable language. The stability function gT(κ) is defined as the supremum of the number of types over models of T of power κ. It is proved that there are only six possible stability functions, namely κ, κ + 2ω, κω, ded κ, (ded κ)ω, 2κ.

The cardinality problem for ultraproducts is as follows: Given an ultrafilter over a set I and cardinals αi, i ∈ I, what is the cardinality of the ultraproduct ? Although many special results are known, several problems remain open (see [5] for a survey). For example, consider a uniform ultrafilter over a set I of power κ (uniform means that all elements of have power κ). It is open whether every countably incomplete has the property that, for all infinite α, the ultra-power has power ακ. However, it is shown in [4] that certain countably incomplete , namely the κ-regular , have this property. This paper is about another cardinality property of ultrafilters which was introduced by Eklof [1] to study ultraproducts of abelian groups. It is open whether every countably incomplete ultrafilter has the Eklof property. We shall show that certain countably incomplete ultrafilters, the κ-good ultrafilters, do have this property. The κ-good ultrafilters are important in model theory because they are exactly the ultrafilters such that every ultraproduct modulo is κ-saturated (see [5]). Let be an ultrafilter on a set I. Let αi, n, i ∈ I, n ∈ ω, be cardinals and αi, n, ≥ αi, m if n < m. Let . Then ρn are nonincreasing and therefore there is some m and ρ such that ρn = ρ if n ≥ m. We call ρ the eventual value (abbreviated ev val) of ρn.

The Arithmetical Hierarchy Theorem of Kleene [1] states that in the complete theory of the standard model of arithmetic there is for each positive integer r a Σr0 formula which is not equivalent to any Πr0 formula, and a Πr0 formula which is not equivalent to any Πr0 formula. A Πr0 formula is a formula of the form where φ has only bounded quantifiers; Πr0 formulas are defined dually. The Linear Prefix Theorem in [3] is an analogous result for predicate logic. Consider the first order predicate logic L with identity symbol, countably many n-placed relation symbols for each n, and no constant or function symbols. A prefix is a finite sequence of quantifier symbols ∃ and ∀, for example ∀∃∀∀∀∃. By a Q formula we mean a formula of L of the form where v1, …, vr are distinct variables and φ has no quantifiers. A sentence is a formula with no free variables. The Linear Prefix Theorem is as follows. Linear Prefix Theorem. Let Q and q be two different prefixes of the same length r. Then there is a Q sentence which is not logically equivalent to any q sentence. Moreover, for each s there is a Q formula with s free variables which is not logically equivalent to any q formula with s free variables. For example, there is an ∀∃∀∀∀∃ sentence which is not logically equivalent to any ∀∃∃∀∀∃ sentence, and vice versa. Recall that in arithmetic two consecutive ∃'s or ∀'s can be collapsed; for instance all ∀∃∀∀∀∃ and ∀∃∃∀∀∃ formulas are logically equivalent to Π40 formulas. But the Linear Prefix Theorem shows that in predicate logic the number of quantifiers in each block, as well as the number of blocks, counts.

A theory T is said to be categorical in power κ iff T has a model of power κ and any two models of power κ are isomorphic. It was conjectured by Morley [4] that if T is a theory in a language with κ > ω symbols and T is categorical in power κ, then T has a model of power < κ. The aim of this paper is to prove the following theorem. Theorem A. Let κ be a regular cardinal such that ω < κ < 2ω. Let T be a theory in a language with κ symbols such that T is categorical in power κ. Then: (a) T has a model of power < κ. (b) T is categorical in all powers μ ≥ κ.

In this paper we continue our study, begun in [5], of the connection between ultraproducts and saturated structures. IfDis an ultrafilter over a setI, and is a structure (i.e., a model for a first order predicate logicℒ), the ultrapower of moduloDis denoted byD-prod . The ultrapower is important because it is a method of constructing structures which are elementarily equivalent to a given structure (see Frayne-Morel-Scott [3]). Our ultimate aim is to find out what kinds of structure are ultrapowers of . We made a beginning in [5] by proving that, assuming the generalized continuum hypothesis (GCH), for each cardinalαthere is an ultrafilterDover a set of powerαsuch that for all structures ,D-prod isα+-saturated.

It is shown in [1] that an ultraproduct of finite sets can be of arbitrarily large cardinality, but if it is infinite then it must have at least the power of the continuum. In this paper we shall take a closer look at the cardinality of ultraproducts of finite sets. Our results were announced without proof in [5]. A discussion of the cardinality of ultraproducts of infinite sets, and another theorem about ultraproducts of finite sets, can be found in [3].

This paper is a sequel to our earlier paper, “Limit Ultrapowers”, [6]. In that paper we introduced the limit ultrapower construction and proved that is isomorphic to a limit ultrapower of if and only if every PCΔ class which contains also contains . In Section 1 of this paper we introduce the more general limit ultraproduct construction, and in Section 2 we prove that, for any class K of relational systems, a relational system is isomorphic to a limit ultraproduct of members of K if and only if every PCΔ class which includes K also contains . As a consequence, the property of K being an intersection of PCΔ classes is characterized purely set-theoretically by the property of K being closed under isomorphisms and limit ultraproducts. In Section 3 we apply limit ultraproducts to obtain model-theoretic conditions equivalent to the set-theoretic condition that every α-complete ultrafilter is γ+-complete. The first result, Theorem 3.7, was announced in the abstract [8], and it is also closely related to a result which was stated without proof in [10], namely Theorem 2 of that paper. In Sections 4 and 5 we apply our results in order to improve a theorem of Craig in [2]. Craig considered the logic L(Q), where Q is a set of cardinals, obtained from ordinary first order logic by adding for each α ϵ Q the quantifier “there exist at least α”.

Introduction. This paper is a sequel to our paper [3]. In that paper we introduced the notion of a finite approximation to an infinitely long formula, in a language L with infinitely long expressions of the type considered by Henkin in [2]. The results of the paper [3] show relationships between the models of an infinitely long sentence and the models of its finite approximations. In the present paper we shall apply the main result of [3] to prove a number of theorems about ordinary finitely long sentences; these theorems are of a type which one might call “preservation theorems”. The following two known results are typical preservation theorems: A sentence φ is preserved under substructures if and only if φ is (logically) equivalent to some universal sentence (Łoś [7] and Tarski [11]); φ is preserved under homomorphic images if and only if φ is equivalent to some positive sentence (Lyndon [8]). An expository account of preservation theorems may be found in Lyndon [9]. We shall use freely all of the notation introduced in [3], and shall not attempt to make this paper selfcontained. However, the reader should have no difficulty following this paper after he has read [3]. In § 1 we cover some preliminary topics. In § 2 and § 3 we shall illustrate our method in familiar situations by proving anew the two preservation theorems mentioned above. We shall then obtain four new preservation theorems in §§ 4, 5, and 6, involving respectively direct powers and roots, strong homomorphisms and retracts, and direct factors. The result in § 6 was stated in the abstract [4], while the results in § 5 were stated in the abstract [5].

Let ℒ be the set of all formulas of a given first order predicate logic (with or without identity). For each positive integer n, let ℒn be the set of all formulas φ in ℒ logically equivalent to a formula of the form where Q is a (possibly empty) string of quantifiers, m is a positive integer, and each αij is either an atomic formula or the negation of an atomic formula.

Introduction We shall prove the following theorem, which gives a necessary and sufficient condition for an elementary class to be characterized by a set of sentences having a prescribed number of alternations of quantifiers. A finite sequence of relational systems is said to be a sandwich of order n if each is an elementary extension of (i ≦ n—2), and each is an extension of (i ≦ n—2). If K is an elementary class, then the statements (i) and (ii) are equivalent for each fixed natural number n.