We prove a theorem about models with indiscernibles that are cofinal in a given linear order. We apply this theorem to obtain new independence results for Quine's set theory New Foundations, thus solving two open problems in this field.

In this paper, we define some consequence relations based on supervaluation semantics for partial models, and we investigate their properties. For our main consequence relation, we show that natural versions of the following fail: upwards and downwards Lowenheim-Skolem, axiomatizability, and compactness. We also consider an alternate version for supervaluation semantics, and show both axiomatizability and compactness for the resulting consequence relation.

Our theme is that not every interesting question in set theory is independent of ZFC. We give an example of a first order theory T with countable D(T) which cannot have a universal model at ℵ1 without CH; we prove in ZFC a covering theorem from the hypothesis of the existence of a universal model for some theory; and we prove--again in ZFC--that for a large class of cardinals there is no universal linear order (e.g. in every regular $\aleph_1 < (...) \lambda < 2^{\aleph_0}$). In fact, what we show is that if there is a universal linear order at a regular λ and its existence is not a result of a trivial cardinal arithmetical reason, then λ "resembles" ℵ1--a cardinal for which the consistency of having a universal order is known. As for singular cardinals, we show that for many singular cardinals, if they are not strong limits then they have no universal linear order. As a result of the nonexistence of a universal linear order, we show the nonexistence of universal models for all theories possessing the strict order property (for example, ordered fields and groups, Boolean algebras, p-adic rings and fields, partial orders, models of PA and so on). (shrink)

Many authors have noted that there are types of English modal sentences cannot be formalized in the language of basic first-order modal logic. Some widely discussed examples include “There could have been things other than there actually are” and “Everyone who is actually rich could have been poor.” In response to this lack of expressive power, many authors have discussed extensions of first-order modal logic with two-dimensional operators. But claims about the relative expressive power of these extensions are often justified (...) only by example rather than by rigorous proof. In this paper, we provide proofs of many of these claims and present a more complete picture of the expressive landscape for such languages. (shrink)

Assume $\langle \aleph_0, \aleph_1 \rangle \rightarrow \langle \lambda, \lambda^+ \rangle$ . Assume M is a model of a first order theory T of cardinality at most λ+ in a language L(T) of cardinality $\leq \lambda$ . Let N be a model with the same language. Let Δ be a set of first order formulas in L(T) and let D be a regular filter on λ. Then M is $\Delta-embeddable$ into the reduced power $N^\lambda/D$ , provided that every $\Delta-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 $\lambda, M^\lambda/D$ is $\lambda^{++}-universal$ . Our second result is as follows: For $i < \mu$ let Mi and Ni be elementarily equivalent models of a language which has cardinality $\leq \lambda$ . Suppose D is a regular filter on λ and $\langle \aleph_0, \aleph_1 \rangle \rightarrow \langle \lambda, \lambda^+ \rangle$ holds. We show that then the second player has a winning strategy in the $Ehrenfeucht-Fra\ddot{i}ss\acute{e}$ game of length λ+ on $\prod_i M_i/D$ and $\prod_i N_i/D$ . This yields the following corollary: Assume GCH and λ regular (or just $\langle \aleph_0, \aleph_1 \rangle \rightarrow \langle \lambda, \lambda^+ \rangle$ and 2λ = λ+). For L, Mi and Ni be as above, if D is a regular filter on λ, then $\prod_i M_i/D \cong \prod_i N_i/D$. (shrink)

Let T be a complete theory with infinite models in a countable language. The stability function g T (κ) 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 $\kappa, \kappa + 2^\omega, \kappa^\omega, \operatorname{ded} \kappa, (\operatorname{ded} \kappa)^\omega, 2^\kappa$.

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.

§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)

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)

A dialectical contradiction can be appropriately described within the framework of classical formal logic. It is in harmony with the law of noncontradiction. According to our definition, two theories make up a dialectical contradiction if each of them is consistent and their union is inconsistent. It can happen that each of these two theories has an intended model. Plenty of examples are to be found in the history of science.

Set theory is an autonomous and sophisticated field of mathematics, enormously successful not only at its continuing development of its historical heritage but also at analyzing mathematical propositions cast in set-theoretic terms and gauging their consistency strength. But set theory is also distinguished by having begun intertwined with pronounced metaphysical attitudes, and these have even been regarded as crucial by some of its great developers. This has encouraged the exaggeration of crises in foundations and of metaphysical doctrines in general. However, (...) set theory has proceeded in the opposite direction, from a web of intensions to a theory of extensionpar excellence, and like other fields of mathematics its vitality and progress have depended on a steadily growing core of mathematical structures and methods, problems and results. There is also the stronger contention that from the beginning set theory actually developed through a progression ofmathematicalmoves, whatever and sometimes in spite of what has been claimed on its behalf.What follows is an account of the development of set theory from its beginnings through the creation of forcing based on these contentions, with an avowedly Whiggish emphasis on the heritage that has been retained and developed by current set theory. The whole transfinite landscape can be viewed as the result of Cantor's attempt to articulate and solve the Continuum Problem. (shrink)

It is known (see [1, 3.1.5]) that the order type of the nonstandard natural number system * N has the form ω + (ω * + ω) θ, where θ is a dense order type without first or last element and ω is the order type of N. Concerning this, Zakon [2] examined * N more closely and investigated the nonstandard real number system * R, as an ordered set, as an additive group and as a uniform space. He raised (...) five questions which remained unsolved. These questions are concerned with the cofinality and coinitiality of θ (which depend on the underlying nonstandard universe * U). In this paper, we shall treat nonstandard models where the cofinality and coinitiality of θ coincide with some appropriated cardinals. Using these nonstandard models, we shall give answers to three of these questions and partial answers to the other to questions in [2]. (shrink)

The authors show. by means of a finitary version $\square_{\lambda D}^{fin}$ of the combinatorial principle $\square_\lambda^{h*}$ of [7]. the consistency of the failure, relative to the consistency of supercompact cardinals, of the following: for all regular filters D on a cardinal A. if Mi and Ni are elementarily equivalent models of a language of size $\leq \lambda$ , then the second player has a winning strategy in the Ehrenfeucht- $Fra\uml{i}ss\acute{e}$ game of length $\lambda^{+}$ on $\pi_{i} M_{i}/D$ and $\pi_{i} N_{i}/D$ . (...) If in addition $2^{\lambda} = \labda^{+}$ and i < $\lambda$ implies | $M_{i}$ | +| $N_{i}$ | $\leq$ \lambda^{+} this means that the ultrapowers are isomorphic. This settles negatively conjecture 18 in [2]. (shrink)

Minimal predicates P satisfying a given first-order description φ(P) occur widely in mathematical logic and computer science. We give an explicit first-order syntax for special first-order ‘PIA conditions’ φ(P) which guarantees unique existence of such minimal predicates. Our main technical result is a preservation theorem showing PIA-conditions to be expressively complete for all those first-order formulas that are preserved under a natural model-theoretic operation of ‘predicate intersection’. Next, we show how iterated predicate minimization on PIA-conditions yields a language MIN(FO) equal (...) in expressive power to LFP(FO), first-order logic closed under smallest fixed-points for monotone operations. As a concrete illustration of these notions, we show how our sort of predicate minimization extends the usual frame correspondence theory of modal logic, leading to a proper hierarchy of modal axioms: first-order-definable, first-order fixed-point definable, and beyond. (shrink)

In § 1 of this paper, we characterize the isomorphism property of nonstandard universes in terms of the realization of some second-order types in model theory. In § 2, several applications are given. One of the applications answers a question of D. Ross in [this Journal, vol. 55 (1990), pp. 1233-1242] about infinite Loeb measure spaces.

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ∈ O there is a y greater than all the elements in U such that the interval $\lbrack x - y, x + y\rbrack \subseteq O$ . Let U be a cut in a hyperfinite time (...) line H, which is a hyperfinite initial segment of the hyperintegers. A subset B of H is called a U-Lusin set in H if B is uncountable and for any Loeb-Borel U-meager subset X of H, B ∩ X is countable. Here a Loeb-Borel set is an element of the σ-algebra generated by all internal subsets of H. In this paper we answer some questions of Keisler and Leth about the existence of U-Lusin sets by proving the following facts. (1) If $U = x/\mathbb{N} = \{y \in \mathscr{H}: \forall n \in \mathbb{N}(y < x/n)\}$ for some x ∈ H, then there exists a U-Lusin set of power κ if and only if there exists a Lusin set of the reals of power κ. (2) If U ≠ x/N but the coinitiality of U is ω, then there are no U-Lusin sets if CH fails. (3) Under ZFC there exists a nonstandard universe in which U-Lusin sets exist for every cut U with uncountable cofinality and coinitiality. (4) In any ω2-saturated nonstandard universe there are no U-Lusin sets for all cuts U except U = x/N. (shrink)

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ∈ O there is a y greater than all the elements in U such that the interval $\lbrack x - y, x + y\rbrack \subseteq O$ . Let U be a cut in a hyperfinite time (...) line H, which is a hyperfinite initial segment of the hyperintegers. The U-monad topology of H is the quotient topology of the U-topological space H modulo U. In this paper we answer a question of Keisler and Leth about the U-monad topologies by showing that when H is κ-saturated and has cardinality κ, (1) if the coinitiality of U1 is uncountable, then the U1-monad topology and the U2-monad topology are homeomorphic iff both U1 and U2 have the same coinitiality; and (2) H can produce exactly three different U-monad topologies (up to homeomorphism) for those U's with countable coinitiality. As a corollary H can produce exactly four different U-monad topologies if the cardinality of H is ω1. (shrink)

For an infinite cardinal K a stronger version of K-distributivity for Boolean algebras, called k-partition completeness, is defined and investigated . It is shown that every k-partition complete Boolean algebra is K-weakly representable, and for strongly inaccessible K these concepts coincide. For regular K ≥ u, it is proved that an atomless K-partition complete Boolean algebra is an updirected union of basic K-tree algebras. Using K-partition completeness, the concept of γ-almost compactness is introduced for γ ≥ K. For strongly inaccessible (...) K we show that K is K-almost compact iff K is weakly compact, and if K is 2K-almost compact, then K is measurable. Further K is strongly compact iff it is γ-almost compact for all γ ≥ K. (shrink)

This paper answers some questions of D. Ross in [R]. In § 1, we show that some consequences of the ℵ0- or ℵ1-special model axiom in [R] cannot be proved by the κ-isomorphism property for any cardinal κ. In § 2, we show that with one exception, the ℵ0-isomorphism property does imply the remaining consequences of the special model axiom in [R]. In § 3, we improve a result in [R] by showing that the κ-special model axiom is equivalent to (...) the ℵ0-special model axiom plus κ-saturation. (shrink)

An L-structure is called internally presented in a nonstandard universe if its base set and interpretation of every symbol in L are internal. A nonstandard universe is said to satisfy the κ-isomorphism property if for any two internally presented L-structures U and B, where L has less than κ many symbols, U is elementarily equivalent to B implies that U is isomorphic to B. In this paper we prove that the ℵ1-isomorphism property is equivalent to the ℵ0-isomorphism property plus ℵ1-saturation.

In an ω1-saturated nonstandard universe a cut is an initial segment of the hyperintegers which is closed under addition. Keisler and Leth in [KL] introduced, for each given cut U, a corresponding U-topology on the hyperintegers by letting O be U-open if for any x ∈ O there is a y greater than all the elements in U such that the interval $\lbrack x - y, x + y\rbrack \subseteq O$ . Let U be a cut in a hyperfinite time (...) line H, which is a hyperfinite initial segment of the hyperintegers. U is called a good cut if there exists a U-meager subset of H of Loeb measure one. Otherwise U is bad. In this paper we discuss the questions of Keisler and Leth about the existence of bad cuts and related cuts. We show that assuming $\mathbf{b} > \omega_1$, every hyperfinite time line has a cut with both cofinality and coinitiality uncountable. We construct bad cuts in a nonstandard universe under ZFC. We also give two results about the existence of other kinds of cuts. (shrink)

In various theories of truth, people have set forth many definitions to clarify in what sense a set of sentences is paradoxical. But what, exactly, is _a_ paradox per se? It has not yet been realized that there is a gap between ‘being paradoxical’ and ‘being a paradox’. This paper proposes that a paradox is a minimally paradoxical set meeting some closure property. Along this line of thought, we give five tentative definitions based upon the folk notion of paradoxicality implied (...) in Tarski’s undefinability theorem of truth and the dependence relation proposed by Leitgeb (J Philos Log 34(2):155–192, 2005). A definition of ‘being a paradox’ is acceptable if its extension must be sufficiently comprehensive to include all known paradoxes on the one hand, and its standard must also be high enough to exclude those that are evidently not paradoxes on the other hand. It turns out that only the last attempt is acceptable: a set of sentences is a paradox if it is paradoxical and self-dependent, and at the same time, it and any of its paradoxical and self-dependent subsets bisimulate each other. In this way, we articulate in what sense a set of sentences is a paradox, and so establish a connection between the notion of a paradox and the notion of paradoxicality. (shrink)

We achieve several results. First, we develop a variant of the theory of absolute Galois groups in the context of many sorted structures. Second, we provide a method for coding absolute Galois groups of structures, so they can be interpreted in some monster model with an additional predicate. Third, we prove the “Weak Independence Theorem” for pseudo-algebraically closed (PAC) substructures of an ambient structure with no finite cover property (nfcp) and the property [Formula: see text]. Fourth, we describe Kim-dividing in (...) these PAC substructures and show several results related to the SOPnhierarchy. Fifth, we characterize the algebraic closure in PAC structures. (shrink)

Relative to any reasonable frame, satisfiability of modal quantificational formulae in which “= ” is the sole predicate is undecidable; but if we restrict attention to satisfiability in structures with the expanding domain property, satisfiability relative to the familiar frames (K, K4, T, S4, B, S5) is decidable. Furthermore, relative to any reasonable frame, satisfiability for modal quantificational formulae with a single monadic predicate is undecidable ; this improves the result of Kripke concerning formulae with two monadic predicates.

A countably infinite relational structure M is called absolutely ubiquitous if the following holds: whenever N is a countably infinite structure, and M and N have the same isomorphism types of finite induced substructures, there is an isomorphism from M to N. Here a characterisation is given of absolutely ubiquitous structures over languages with finitely many relation symbols. A corresponding result is proved for uncountable structures.

We use the spaces T n and E n of complete types and of existential types to investigate various notions which appear in the theory of the algebraic structure of models.

This is a study of the set of the Malitz-completions of a given infinite first-order structure, put in relation with properties of directed sets.