Shelah's theory of forking is generalized in a way which deals with measures instead of complete types. This allows us to extend the method of forking from the class of stable theories to the larger class of theories which do not have the independence property. When restricted to the special case of stable theories, this paper reduces to a reformulation of the classical approach. However, it goes beyond the classical approach in the case of unstable theories. Methods from ordinary (...) forking theory and the Loeb measure construction from nonstandard analysis are used. (shrink)

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 $\exists ^{ \ge 3/4} y$ 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 $\exists ^{ \ge r} y$ , 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 $(\exists ^{ \ge r} y)$ , to depend on the size of the universe. (shrink)

We study generically stable measures in the local, NIP context. We show that in this setting, a measure is generically stable if and only if it admits a natural finite approximation.

We give examples of (i) a simple theory with a formula (with parameters) which does not fork over [Formula: see text] but has [Formula: see text]-measure 0 for every automorphism invariant Keisler measure [Formula: see text] and (ii) a definable group [Formula: see text] in a simple theory such that [Formula: see text] is not definably amenable, i.e. there is no translation invariant Keisler measure on [Formula: see text]. We also discuss paradoxical decompositions both in the setting of (...) discrete groups and of definable groups, and prove some positive results about small theories, including the definable amenability of definable groups. (shrink)

This work builds on previous papers by Hrushovski, Pillay and the author where Keisler measures over NIP theories are studied. We discuss two constructions for obtaining generically stable measures in this context. First, we show how to symmetrize an arbitrary invariant measure to obtain a generically stable one from it. Next, we show that suitable sigma-additive probability measures give rise to generically stable Keisler measures. Also included is a proof that generically stable measures (...) over o-minimal theories and the p-adics are smooth. (shrink)

We prove (Proposition 2.1) that if $\mu$ is a generically stable measure in an NIP (no independence property) theory, and $\mu(\phi(x,b))=0$ for all $b$ , then for some $n$ , $\mu^{(n)}(\exists y(\phi(x_{1},y)\wedge \cdots \wedge\phi(x_{n},y)))=0$ . As a consequence we show (Proposition 3.2) that if $G$ is a definable group with fsg (finitely satisfiable generics) in an NIP theory, and $X$ is a definable subset of $G$ , then $X$ is generic if and only if every translate of $X$ does not (...) fork over $\emptyset$ , precisely as in stable groups, answering positively an earlier problem posed by the first two authors. (shrink)

We initiate an account of Shelah’s notion of “strong dependence” in terms of generically stable measures, proving a measure analogue of the fact that a stable theory $T$ is “strongly dependent” if and only if all types have almost finite weight.

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

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. (shrink)

Provability, Computability and Reflection.

The language $L_A(\Finv)$ is formed by adding the quantifier $\Finv x$ , "few x", to the infinitary logic L A on an admissible set A. A complete axiomatization is obtained for models whose universe is the set of ordinals of A and where $\Finv 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 $L_A(\Finv)$.

We prove a local normal form theorem of the Gaifman type for the infinitary logic L∞ωω whose formulas involve arbitrary unary quantifiers but finite quantifier rank. We use a local Ehrenfeucht-Fraïssé type game similar to the one in [9]. A consequence is that every sentence of L∞ωω of quantifier rank n is equivalent to an infinite Boolean combination of sentences of the form ψ, where ψ has counting quantifiers restricted to the -neighborhood of y.

In this paper we continue our study, begun in [5], of the connection between ultraproducts and saturated structures. IfDis an ultrafilter over a setI, andis a structure, the ultrapower ofmoduloDis denoted byD-prod. The ultrapower is important because it is a method of constructing structures which are elementarily equivalent to a given structure. 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, for (...) each cardinalαthere is an ultrafilterDover a set of powerαsuch that for all structures,D-prodisα+-saturated. (shrink)

First order reasoning about hyperintegers can prove things about sets of integers. In the author’s paper Nonstandard Arithmetic and Reverse Mathematics, Bulletin of Symbolic Logic 12 100–125, it was shown that each of the “big five” theories in reverse mathematics, including the base theory , has a natural nonstandard counterpart. But the counterpart of has a defect: it does not imply the Standard Part Principle that a set exists if and only if it is coded by a hyperinteger. In this (...) paper we find another nonstandard counterpart, *RCA0′, that does imply the Standard Part Principle. (shrink)

We show that each of the five basic theories of second order arithmetic that play a central role in reverse mathematics has a natural counterpart in the language of nonstandard arithmetic. In the earlier paper [3] we introduced saturation principles in nonstandard arithmetic which are equivalent in strength to strong choice axioms in second order arithmetic. This paper studies principles which are equivalent in strength to weaker theories in second order arithmetic.

A paradox of self-reference in beliefs in games is identified, which yields a game-theoretic impossibility theorem akin to Russell’s Paradox. An informal version of the paradox is that the following configuration of beliefs is impossible:Ann believes that Bob assumes that.

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 equivalent to some universal sentence ; φ is preserved under homomorphic images if and only if φ is equivalent to some positive sentence. 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]. (shrink)

We characterize some large cardinal properties, such as $\mu$-measurability and $P^2(\kappa)$-measurability, in terms of ultrafilters, and then explore the Rudin-Keisler (RK) relations between these ultrafilters and supercompact measures on $P_\kappa(2^\kappa)$. This leads to the characterization of $2^\kappa$-supercompactness in terms of a measure on measure sequences, and also to the study of a certain natural subset, $\mathrm{Full}_\kappa$, of $P_\kappa(2^\kappa)$, whose elements code measures on cardinals less than $\kappa$. The hypothesis that $\mathrm{Full}_\kappa$ is stationary (a weaker assumption than $2^\kappa$-supercompactness) (...) is equivalent to a higher order Lowenheim-Skolem property, and settles a question about directed versus chain-type unions on $P_\kappa\lambda$. (shrink)

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 $\kappa < \lambda$ are uncountable regular cardinals and $\beta^\alpha < \lambda$ whenever $\alpha < \kappa$ and $\beta < \lambda$, 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. (shrink)

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46], and that of Platek [58], at Stanford, on admissible sets.Barwise's work on infinitary logic and admissible sets is described (...) in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L. (shrink)

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.

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. (shrink)