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.

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 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.

We define notions of homomorphism, submodel, and sandwich of Kripke models, and we define two syntactic operators analogous to universal and existential closure. Then we prove an intuitionistic analogue of the generalized (dual of the) Lyndon-Łoś-Tarski Theorem, which characterizes the sentences preserved under inverse images of homomorphisms of Kripke models, an intuitionistic analogue of the generalized Łoś-Tarski Theorem, which characterizes the sentences preserved under submodels of Kripke models, and an intuitionistic analogue of the generalized Keisler (...) class='Hi'>Sandwich Theorem, which characterizes the sentences preserved under sandwiches of Kripke models. We also define several intuitionistic formula hierarchies analogous to the classical formula hierarchies $\forall_n (= \Pi^0_n)$ and $\exists_n (=\Sigma^0_n)$ , and we show how our generalized syntactic preservation theorems specialize to these hierarchies. Each of these theorems implies the corresponding classical theorem in the case where the Kripke models force classical logic. (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)

A general metatheorem is proved which reduces a wide class of statements about continuous time stochastic processes to statements about discrete time processes. We introduce a strong language for stochastic processes, and a concept of forcing for sequences of discrete time processes. The main theorem states that a sentence in the language is true if and only if it is forced. Although the stochastic process case is emphasized in order to motivate the results, they apply to a wider class (...) of random variables. At the end of the paper we illustrate how the theorem can be used with three applications involving submartingales. (shrink)

Gaifman's normal form theorem showed that every first-order sentence of quantifier rank n is equivalent to a Boolean combination of “scattered local sentences”, where the local neighborhoods have radius at most 7n−1. This bound was improved by Lifsches and Shelah to 3×4n−1. We use Ehrenfeucht–Fraïssé type games with a “shrinking horizon” to get a spectrum of normal form theorems of the Gaifman type, depending on the rate of shrinking. This spectrum includes the result of Lifsches and Shelah, with a (...) more easily understood proof and with the bound on the radius improved to 4n−1. We also obtain bounds for a normal form theorem of Schwentick and Barthelmann. (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)

We consider several variants of Keisler’s isomorphism theorem. We separate these variants by showing implications between them and cardinal invariants hypotheses. We characterize saturation hypotheses that are stronger than Keisler’s theorem with respect to models of size $\aleph _1$ and $\aleph _0$ by $\mathrm {CH}$ and $\operatorname {cov}(\mathsf {meager}) = \mathfrak {c} \land 2^{<\mathfrak {c}} = \mathfrak {c}$ respectively. We prove that Keisler’s theorem for models of size $\aleph _1$ and $\aleph _0$ implies $\mathfrak (...) {b} = \aleph _1$ and $\operatorname {cov}(\mathsf {null}) \le \mathfrak {d}$ respectively. As a consequence, Keisler’s theorem for models of size $\aleph _0$ fails in the random model. We also show that for Keisler’s theorem for models of size $\aleph _1$ to hold it is not necessary that $\operatorname {cov}(\mathsf {meager})$ equals $\mathfrak {c}$. (shrink)

In this paper, we consider some contributions to the model theory of the logic of formal inconsistency $\mathsf{QmbC}$ as a reply to Walter Carnielli, Marcelo Coniglio, Rodrigo Podiacki and Tarcísio Rodrigues’ call for a ‘wider model theory.’ This call demands that we align the practices and techniques of model theory for logics of formal inconsistency as closely as possible with those employed in classical model theory. The key result is a proof that the Keisler–Shelah isomorphism theorem holds for (...) $\mathsf{QmbC}$, i.e. that the strong elementary equivalence of two $\mathsf{QmbC}$ models $\mathfrak{A}$ and $\mathfrak{B}$ is equivalent to them having strongly isomorphic ultrapowers. As intermediate steps, we introduce some notions of model-theoretic equivalence between $\mathsf{QmbC}$ models, explicitly prove Łoś’ theorem and introduce a useful technique of model-theoretic ‘atomization’ in which the satisfaction sets of non-deterministically evaluated formulae are associated with new predicates. Finally, we consider some of the extensions of $\mathsf{QmbC}$, explicitly showing that Keisler–Shelah holds for $\mathsf{QCi}$ and suggesting that it holds of extensions like $\mathsf{QCila}$ and $\mathsf{QCia}$ as well. (shrink)

We prove a model theoretic generalization of an extension of the Keisler-Morley theorem for countable recursively saturated models of theories having a K-like model, where K is an inaccessible cardinal.

Keisler in [7] proved that for a strong limit cardinal κ and a singular cardinal λ, the transfer relation κ → λ holds. We analyze the λ -like models produced in the proof of Keisler's transfer theorem when κ is further assumed to be regular. Our main result shows that with this extra assumption, Keisler's proof can be modified to produce a λ -like model M with built-in Skolem functions that satisfies the following two properties: M (...) is generated by a subset C of order-type λ. M can be written as union of an elementary end extension chain 〈Ni: i < δ 〉 such that for each i < δ, there is an initial segment Ci of C with Ci ⊆ Ni, and Ni ∩ = ∅. (shrink)

Adam Brandenburger and H. Jerome Keisler have recently discovered a two person Russell-style paradox. They show that the following configurations of beliefs is impossible: Ann believes that Bob assumes that Ann believes that Bob’s assumption is wrong. In [7] a modal logic interpretation of this paradox is proposed. The idea is to introduce two modal operators intended to represent the agents’ beliefs and assumptions. The goal of this paper is to take this analysis further and study this paradox from (...) the point of view of a modal logician. In particular, we show that the paradox can be seen as a theorem of an appropriate hybrid logic. (shrink)

We review, and in the process unify two techniques , for proving results concerning amalgamation in several classes studied in algebraic logic. The logical counterpart of these results adress interpolation and definability properties in modal and algebraic logic. Presenting them in a functorial context as adjoint situations, we show that both techniques can indeed be seen as instances of the use of the Keisler-Shelah ultrapower Theorem in proving Robinson's Joint Consistency Theorem. Some new results are surveyed. The (...) results of this paper are presented in such a way that further establishes the hitherto existing well developed duality theory between boolean algebras with operators and modal logic. (shrink)

The ultraproduct construction is generalized to p‐ultramean constructions () by replacing ultrafilters with finitely additive measures. These constructions correspond to the linear fragments of continuous logic and are very close to the constructions in real analysis. A powermean variant of the Keisler‐Shelah isomorphism theorem is proved for. It is then proved that ‐sentences (and their approximations) are exactly those sentences of continuous logic which are preserved by such constructions. Some other applications are also given.

We give a completeness theorem for a logic with probability quantifiers which is equivalent to the logics described in a recent survey paper of Keisler [K]. This result improves on the completeness theorems in [K] in that it works for languages with function symbols and produces a model whose universe is an analytic subset of the real line, and whose relations and functions are Borel relative to this universe.

We extend the hierarchy of finite-dimensional Ellentuck spaces to infinite dimensions. Using uniform barriers [Formula: see text] on [Formula: see text] as the prototype structures, we construct a class of continuum many topological Ramsey spaces [Formula: see text] which are Ellentuck-like in nature, and form a linearly ordered hierarchy under projections. We prove new Ramsey-classification theorems for equivalence relations on fronts, and hence also on barriers, on the spaces [Formula: see text], extending the Pudlák–Rödl theorem for barriers on the (...) Ellentuck space. The inspiration for these spaces comes from continuing the iterative construction of the forcings [Formula: see text] to the countable transfinite. The [Formula: see text]-closed partial order [Formula: see text] is forcing equivalent to [Formula: see text], which forces a non-p-point ultrafilter [Formula: see text]. This work forms the basis for further work classifying the Rudin–Keisler and Tukey structures for the hierarchy of the generic ultrafilters [Formula: see text]. (shrink)

A general method for constructing a new class of topological Ramsey spaces is presented. Members of such spaces are infinite sequences of products of Fraïssé classes of finite relational structures satisfying the Ramsey property. The Product Ramsey Theorem of Sokič is extended to equivalence relations for finite products of structures from Fraïssé classes of finite relational structures satisfying the Ramsey property and the Order-Prescribed Free Amalgamation Property. This is essential to proving Ramsey-classification theorems for equivalence relations on fronts, generalizing (...) the Pudlák–Rödl Theorem to this class of topological Ramsey spaces. To each topological Ramsey space in this framework corresponds an associated ultrafilter satisfying some weak partition property. By using the correct Fraïssé classes, we construct topological Ramsey spaces which are dense in the partial orders of Baumgartner and Taylor generating p-points which are k-arrow but not \-arrow, and in a partial order of Blass producing a diamond shape in the Rudin-Keisler structure of p-points. Any space in our framework in which blocks are products of n many structures produces ultrafilters with initial Tukey structure exactly the Boolean algebra \\). If the number of Fraïssé classes on each block grows without bound, then the Tukey types of the p-points below the space’s associated ultrafilter have the structure exactly \. In contrast, the set of isomorphism types of any product of finitely many Fraïssé classes of finite relational structures satisfying the Ramsey property and the OPFAP, partially ordered by embedding, is realized as the initial Rudin-Keisler structure of some p-point generated by a space constructed from our template. (shrink)

Provability, Computability and Reflection.

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)

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)

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.

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)