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 this paper we show that the compactness of a Loeb space depends on its cardinality, the nonstandard universe it belongs to and the underlying model of set theory we live in. In $\S1$ we prove that Loeb spaces are compact under various assumptions, and in $\S2$ we prove that Loeb spaces are not compact under various other assumptions. The results in $\S1$ and $\S2$ give a quite complete answer to a question of D. Ross in [9], [11] and [12].

We construct a decidable first-order theory T such that the theory of its finite models is undecidable. Moreover, T will be equationally axiomatizable and of finite type.

We study the following conjecture. Conjecture. Let T be an ω-stable theory with continuum many countable models. Then either i) T has continuum many complete extensions in L1(T), or ii) some complete extension of T in L1 has continuum many L1-types without parameters. By Shelah's proof of Vaught's conjecture for ω-stable theories, we know that there are seven types of ω-stable theory with continuum many countable models. We show that the conjecture is true for all but one of these seven (...) cases. In the last case we show the existence of continuum many L2-types. (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 consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finite relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an (...) algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable. An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras. Other instances of this approach are looked at, and include the step by step method. (shrink)

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.

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.

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.

This is a survey of some possible extensions of ZF to a larger universe, closer to the “naive set theory” (the universes discussed here concern, roughly speaking : stratified sets, partial sets, positive sets, paradoxical sets and double sets).

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.

Computable model theory, also called effective or recursive model theory, studies algorithmic properties of mathematical structures, their relations, and isomorphisms. These properties can be described syntactically or semantically. One of the major tasks of computable model theory is to obtain, whenever possible, computability-theoretic versions of various classical model-theoretic notions and results. For example, in the 1950's, Fröhlich and Shepherdson realized that the concept of a computable function can make van der Waerden's intuitive notion of an explicit field precise. This led (...) to the notion of a computable structure. In 1960, Rabin proved that every computable field has a computable algebraic closure. However, not every classical result “effectivizes”. Unlike Vaught's theorem that no complete theory has exactly two nonisomorphic countable models, Millar's and Kudaibergenov's result establishes that there is a complete decidable theory that has exactly two nonisomorphic countable models with computable elementary diagrams. In the 1970's, Metakides and Nerode [58], [59] and Remmel [71], [72], [73] used more advanced methods of computability theory to investigate algorithmic properties of fields, vector spaces, and other mathematical structures. (shrink)

Our concern is the axiomatisation problem for modal and algebraic logics that correspond to various fragments of two-variable first-order logic with counting quantifiers. In particular, we consider modal products with Diff, the propositional unimodal logic of the difference operator. We show that the two-dimensional product logic $Diff \times Diff$ is non-finitely axiomatisable, but can be axiomatised by infinitely many Sahlqvist axioms. We also show that its ‘square’ version (the modal counterpart of the substitution and equality free fragment of two-variable first-order (...) logic with counting to two) is non-finitely axiomatisable over $Diff \times Diff$ , but can be axiomatised by adding infinitely many Sahlqvist axioms. These are the first examples of products of finitely axiomatisable modal logics that are not finitely axiomatisable, but axiomatisable by explicit infinite sets of canonical axioms. (shrink)

The fact that Gödel's famous incompleteness theorem and the archetype of all logical paradoxes, that of the Liar, are related closely is, of course, not only well known, but is a part of the common knowledge of the community of logicians. Indeed, almost every more or less formal treatment of the theorem makes a reference to this connection. Gödel himself remarked in the paper announcing his celebrated result :The analogy between this result and Richard's antinomy leaps to the eye;there is (...) also a close relationship with the ‘liar’ antinomy, since … we are… confronted with a proposition which asserts its own unprovability.In the light of the fact that the existence of this connection is commonplace it is all the more surprising that very little can be learnt about its exact nature except perhaps that it is some kind of similarity or analogy. There is, however, a lot more to it than that. Indeed, as we shall try to show below, the general ideas underlying the three central theorems concerning internal limitations of formal deductive systems can be taken as different ways to resolve the Liar paradox. More precisely, it will turn out that an abstract formal variant of the Liar paradox, which can almost straightforwardly inferred from its original ordinary language version, is a possible common generalization of Gödel's incompleteness theorem, the theorem of Tarski on the undefinability of truth, and that of Church concerning the undecidability of provability. (shrink)

I present solutions to several questions of Paul Bankston [2] by means of another version of the ultracoproduct construction, and explain the relation of ultracoproduct of compact Hausdorff spaces to other constructions combining topology, algebra and logic.

The Logic of Partial Terms LPT is a strict negative free logic that provides an economical framework for developing many traditional mathematical theories having partial functions. In these traditional theories, all functions and predicates are strict. For example, if a unary function (predicate) is applied to an undefined argument, the result is undefined (respectively, false). On the other hand, every practical programming language incorporates at least one nonstrict or lazy construct, such as the if-then-else, but nonstrict functions cannot be either (...) primitive or introduced in definitional extensions in LPT. Consequently, lazy programming language constructs do not fit the traditional mathematical mold inherent in LPT. A nonstrict (positive free) logic is required to handle nonstrict functions and predicates. Previously developed nonstrict logics are not fully satisfactory because they are verbose in describing strict functions (which predominate in many programming languages), and some logicians find their semantics philosophically unpalatable. The newly developed Lazy Logic of Partial Terms LL is as concise as LPT in describing strict functions and predicates, and strict and nonstrict functions and predicates can be introduced in definitional extensions of traditional mathematical theories. LL is "built on top of" LPT, and, like LPT, admits only one domain in the semantics. In the semantics, for the case of a nonstrict unary function h in an LL theory T, we have $\models_T h(\perp) = y \longleftrightarrow \forall x(h(x) = y)$ , where $\perp$ is a canonical undefined term. Correspondingly, in the axiomatization, the "indifference" (to the value of the argument) axiom $h(\perp) = y \longleftrightarrow \forall x(h(x) = y)$ guarantees a proper fit with the semantics. The price paid for LL's naturalness is that it is tailored for describing a specific area of computer science, program specification and verification, possibly limiting its role in explicating classical mathematical and philosophical subjects. (shrink)

Let κ and λ be infinite cardinals such that κ ≤ λ (we have new information for the case when $\kappa ). Let T be a theory in L κ +, ω of cardinality at most κ, let φ(x̄, ȳ) ∈ L λ +, ω . Now define $\mu^\ast_\varphi (\lambda, T) = \operatorname{Min} \{\mu^\ast:$ If T satisfies $(\forall\mu \kappa)(\exists M_\chi \models T)(\exists \{a_i: i Our main concept in this paper is $\mu^\ast_\varphi (\lambda, \kappa) = \operatorname{Sup}\{\mu^\ast(\lambda, T): T$ is a theory (...) in L κ +, ω of cardinality κ at most, and φ (x, y) ∈ L λ +, ω }. This concept is interesting because of THEOREM 1. Let $T \subseteq L_{\kappa^+,\omega}$ of cardinality ≤ κ, and φ (x̄, ȳ) ∈ L λ +, ω . If $(\forall\mu then $(\forall_\chi > \kappa) I(\chi, T) = 2^\chi$ (where I(χ, T) stands for the number of isomorphism types of models of T of cardinality χ). Many years ago the second author proved that $\mu^\ast (\lambda, \kappa) \leq \beth_{(2^\lambda)^+}$ . Here we continue that work by proving. THEOREM 2. $\mu^\ast (\lambda, \aleph_0) = \beth_{\lambda^+}$ . THEOREM 3. For every κ ≤ λ we have $\mu^\ast (\lambda, \kappa) \leq \beth)_{(\lambda^\kappa)}^+$ . For some κ or λ we have better bounds than in Theorem 3, and this is proved via a new two cardinal theorem. THEOREM 4. For every $\kappa \leq \lambda, T \subseteq L_{\kappa^+,\omega}$ , and any set of formulas $\Lambda \subseteq L_{\lambda^+,\omega}$ such that $\Lambda \subseteq L_{\kappa^+,\omega}$ , if T is (Λ,μ)-unstable for μ satisfying μ μ * (λ, κ) = μ then T is Λ-unstable (i.e. for every χ ≥ λ, T is (Λ, χ)-unstable). Moreover, T is L κ +, ω -unstable. In the second part of the paper, we show that always in the applications it is possible to replace the function I(χ, T) by the function IE(χ, T), and we give an application of the theorems to Boolean powers. (shrink)

Let L(Q) be first order logic with Keisler's quantifier, in the λ + interpretation (= the satisfaction is defined as follows: $M \models (\mathbf{Q}x)\varphi(x)$ means there are λ + many elements in M satisfying the formula φ(x)). Theorem 1. Let λ be a singular cardinal; assume □ λ and GCH. If T is a complete theory in L(Q) of cardinality at most λ, and p is an L(Q) 1-type so that T strongly omits $p (= p$ has no support, to (...) be defined in $\S1$ ), then T has a model of cardinality λ + in the λ + interpretation which omits p. Theorem 2. Let λ be a singular cardinal, and let T be a complete first order theory of cardinality λ at most. Assume □ λ and GCH. If Γ is a smallness notion then T has a model of cardinality λ + such that a formula φ(x) is realized by λ + elements of M iff φ(x) is not Γ-small. The theorem is proved also when λ is regular assuming $\lambda = \lambda^{ . It is new when λ is singular or when |T| = λ is regular. Theorem 3. Let λ be singular. If $\operatorname{Con}(ZFC + GCH + (\exists\kappa)$ [κ is a strongly compact cardinal]), then the following in consistent: ZFC + GCH + the conclusions of all above theorems are false. (shrink)

A theoretical development is carried to establish fundamental results about rank-initial embeddings and automorphisms of countable non-standard models of set theory, with a keen eye for their sets of fixed points. These results are then combined into a “geometric technique” used to prove several results about countable non-standard models of set theory. In particular, back-and-forth constructions are carried out to establish various generalizations and refinements of Friedman’s theorem on the existence of rank-initial embeddings between countable non-standard models of the fragment (...) \ + \-Separation of \; and Gaifman’s technique of iterated ultrapowers is employed to show that any countable model of \ can be elementarily rank-end-extended to models with well-behaved automorphisms whose sets of fixed points equal the original model. These theoretical developments are then utilized to prove various results relating self-embeddings, automorphisms, their sets of fixed points, strong rank-cuts, and set theories of different strengths. Two examples: The notion of “strong rank-cut” is characterized in terms of the theory \, and in terms of fixed-point sets of self-embeddings. (shrink)

A fundamental result from Boolean modal logic states that a first-order definable class of Kripke frames defines a logic that is validated by all of its canonical frames. We generalise this to the level of non-distributive logics that have a relational semantics provided by structures based on polarities. Such structures have associated complete lattices of stable subsets, and these have been used to construct canonical extensions of lattice-based algebras. We study classes of structures that are closed under ultraproducts and whose (...) stable set lattices have additional operators that are first-order definable in the underlying structure. We show that such classes generate varieties of algebras that are closed under canonical extensions. The proof makes use of a relationship between canonical extensions and MacNeille completions. (shrink)

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.

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.

We develop a method for showing that various modal logics that are valid in their countably generated canonical Kripke frames must also be valid in their uncountably generated ones. This is applied to many systems, including the logics of finite width, and a broader class of multimodal logics of ‘finite achronal width’ that are introduced here.

We show that there is a restriction, or modification of the finite-variable fragments of First Order Logic in which a weak form of Craig's Interpolation Theorem holds but a strong form of this theorem does not hold. Translating these results into Algebraic Logic we obtain a finitely axiomatizable subvariety of finite dimensional Representable Cylindric Algebras that has the Strong Amalgamation Property but does not have the Superamalgamation Property. This settles a conjecture of Pigozzi [12].

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe that the theories without induction (...) tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

The complete characterisation of order types of non-standard models of Peano arithmetic and its extensions is a famous open problem. In this paper, we consider subtheories of Peano arithmetic (both with and without induction), in particular, theories formulated in proper fragments of the full language of arithmetic. We study the order types of their non-standard models and separate all considered theories via their possible order types. We compare the theories with and without induction and observe that the theories without induction (...) tend to have an algebraic character that allows model constructions by closing a model under the relevant algebraic operations. (shrink)

I consider the first-order modal logic which counts as valid those sentences which are true on every interpretation of the non-logical constants. Based on the assumptions that it is necessary what individuals there are and that it is necessary which propositions are necessary, Timothy Williamson has tentatively suggested an argument for the claim that this logic is determined by a possible world structure consisting of an infinite set of individuals and an infinite set of worlds. He notes that only the (...) cardinalities of these sets matters, and that not all pairs of infinite sets determine the same logic. I use so-called two-cardinal theorems from model theory to investigate the space of logics and consequence relations determined by pairs of infinite sets, and show how to eliminate the assumption that worlds are individuals from Williamson’s argument. (shrink)

We discuss saturating ultrafilters on N, relating them to other types of nonprincipal ultrafilter. (a) There is an (ω,c)-saturating ultrafilter on $\mathbf{N} \operatorname{iff} 2^\lambda \leq \mathfrak{c}$ for every $\lambda and there is no cover of R by fewer than c nowhere dense sets. (b) Assume Martin's axiom. Then, for any cardinal κ, a nonprincipal ultrafilter on N is (ω,κ)-saturating iff it is almost κ-good. In particular, (i) p(κ)-point ultrafilters are (ω,κ)-saturating, and (ii) the set of (ω,κ)-saturating ultrafilters is invariant under (...) homeomorphisms of $\beta\mathbf{N\backslash N}$ . (c) It is relatively consistent with ZFC to suppose that there is a Ramsey p(c)-point ultrafilter which is not (ω,c)-saturating. (shrink)