The cofinality quantifiers were introduced by Shelah as an example of a compact logic stronger than first-order logic. We show that the classes of models axiomatized by these quantifiers can be turned into an Abstract Elementary Class by restricting to positive and deliberate uses. Rather than using an ad hoc proof, we give a general framework of abstract Skolemizations. This method gives a uniform proof that a wide rang of classes are Abstract Elementary Classes.

We present in this paper an abstract categorical logic based on an abstraction of quantifier. More precisely, the proposed logic is abstract because no structural constraints are imposed on models (semantics free). By contrast, formulas are inductively defined from an abstraction both of atomic formulas and of quantifiers. In this sense, the proposed approach differs from other works interested in formalizing the notion of abstract logic and of which the closest to our approach are the institutions, which in addition to (...) be semantics free do not also impose any syntactic contingencies on the structure of formulas. To define the semantical framework in which formulas will be interpreted, we propose to follow the idea from categorical logic which defines the semantical interpretation of formulas from context and as subobjects of an object of a given category. In the spirit of Lawvere’s hyperdoctrines, we use a more abstract notion which generalizes the notion of subobject, standard in category theory: Pitt’s prop-categories. Always in the spirit of categorical logic, we propose a sequent calculus of which we show correctness and completeness for all semantical frameworks defined over any prop-categories. We then study some conditions which allow us to get this completeness result for particular classes of prop-categories. (shrink)

This paper is a step toward showing what is achievable using non-classical metatheory—particularly, a substructural paraconsistent framework. What standard results, or analogues thereof, from the classical metatheory of first order logic can be obtained? We reconstruct some of the originals proofs for Completeness, Löwenheim-Skolem and Compactness theorems in the context of a substructural logic with the naive comprehension schema. The main result is that paraconsistent metatheory can ‘re-capture’ versions of standard theorems, given suitable restrictions and background assumptions; but the shift (...) to non-classical logic may recast the meanings of these apparently ‘absolute’ theorems. (shrink)

If we replace first-order logic by second-order logic in the original definition of Gödel’s inner model L, we obtain the inner model of hereditarily ordinal definable sets [33]. In this paper...

By utilizing the topological concept of pseudocompactness, we simplify and improve a proof of Caicedo, Dueñez, and Iovino concerning Terence Tao's metastability. We also pinpoint the exact relationship between the Omitting Types Theorem and the Baire Category Theorem by developing a machine that turns topological spaces into abstract logics.

Often philosophers, logicians, and mathematicians employ a notion of intended structure when talking about a branch of mathematics. In addition, we know that there are foundational mathematical theories that can find representatives for the objects of informal mathematics. In this paper, we examine how faithfully foundational theories can represent intended structures, and show that this question is closely linked to the decidability of the theory of the intended structure. We argue that this sheds light on the trade-off between expressive power (...) and meta-theoretic properties when comparing first-order and second-order logic. (shrink)

I will give a brief overview of Saharon Shelah’s work in mathematical logic. I will focus on three transformative contributions Shelah has made: stability theory, proper forcing and PCF theory. The first is in model theory and the other two are in set theory.

In the paper the following questions are discussed: What is logical consequence? What are logical constants? What is a logical system? What is logical pluralism? What is logic? In the conclusion, the main tendencies of development of modern logic are pointed out.

Bob Hale’s distinguished record of research places him among the most important and influential contemporary analytic metaphysicians. In his deep, wide ranging, yet highly readable book Necessary Beings, Hale draws upon, but substantially integrates and extends, a good deal his past research to produce a sustained and richly textured essay on — as promised in the subtitle — ontology, modality, and the relations between them. I’ve set myself two tasks in this review: first, to provide a reasonably thorough (if not (...) exactly comprehensive) overview of the structure and content of Hale’s book and, second, to a limited extent, to engage Hale’s book philosophically. I approach these tasks more or less sequentially: Parts I and 2 of the review are primarily expository; in Part 3 I adopt a somewhat more critical stance and raise several issues concerning one of the central elements of Hale’s account, his essentialist theory of modality. (shrink)

The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability and (...) definability theory. Here we give a unified presentation, including some new results, of how to use the Feferman–Vaught Theorem, and some new variations thereof, algorithmically in the case of Monadic Second Order Logic MSOL . We then extend the technique to graph polynomials where the range of the summation of the monomials is definable in MSOL . Here the Feferman–Vaught Theorem for these polynomials generalizes well known splitting theorems for graph polynomials. Again, these can be used algorithmically. Finally, we discuss extensions of MSOL for which the Feferman–Vaught Theorem holds as well. (shrink)

We show that, assuming the consistency of a supercompact cardinal, the first inaccessible cardinal can satisfy a strong form of a Löwenheim–Skolem–Tarski theorem for the equicardinality logic L, a logic introduced in [5] strictly between first order logic and second order logic. On the other hand we show that in the light of present day inner model technology, nothing short of a supercompact cardinal suffices for this result. In particular, we show that the Löwenheim–Skolem–Tarski theorem for the equicardinality logic at (...) κ implies the Singular Cardinals Hypothesis above κ as well as Projective Determinacy. (shrink)

This is a survey of work on set-theoretical invariance criteria for logicality. It begins with a review of the Tarski-Sher thesis in terms, first, of permutation invariance over a given domain and then of isomorphism invariance across domains, both characterized by McGee in terms of definability in the language L∞,∞. It continues with a review of critiques of the Tarski-Sher thesis, and a proposal in response to one of those critiques via homomorphism invariance. That has quite divergent characterization results depending (...) on its formulation, one in terms of FOL, the other by Bonnay in terms of L∞,∞, both without equality. From that we move on to a survey of Bonnay’s work on similarity relations between structures and his results that single out invariance with respect to potential isomorphism among all such. Turning to the critique that calls for sameness of meaning of a logical operation across domains, the paper continues with a result showing that the isomorphism invariant operations that are absolutely definable with respect to KPU−Inf are exactly those definable in full FOL; this makes use of an old theorem of Manders. The concluding section is devoted to a critical discussion of the arguments for set-theoretical criteria for logicality. (shrink)

Though deceptively simple and plausible on the face of it, Craig's interpolation theorem (published 50 years ago) has proved to be a central logical property that has been used to reveal a deep harmony between the syntax and semantics of first order logic. Craig's theorem was generalized soon after by Lyndon, with application to the characterization of first order properties preserved under homomorphism. After retracing the early history, this article is mainly devoted to a survey of subsequent generalizations and applications, (...) especially of many-sorted interpolation theorems. Attention is also paid to methodological considerations, since the Craig theorem and its generalizations were initially obtained by proof-theoretic arguments while most of the applications are model-theoretic in nature. The article concludes with the role of the interpolation property in the quest for "reasonable" logics extending first-order logic within the framework of abstract model theory. (shrink)

We discuss the differences between first-order set theory and second-order logic as a foundation for mathematics. We analyse these languages in terms of two levels of formalization. The analysis shows that if second-order logic is understood in its full semantics capable of characterizing categorically central mathematical concepts, it relies entirely on informal reasoning. On the other hand, if it is given a weak semantics, it loses its power in expressing concepts categorically. First-order set theory and second-order logic are not radically (...) different: the latter is a major fragment of the former. (shrink)

The first section of this paper is concerned with the intrinsic properties of elementary monadic logic (EM), and characterizations in the spirit of Lindström [2] are given. His proofs do not apply to monadic logic since relations are used, and intrinsic properties of EM turn out to differ in certain ways from those of the elementary logic of relations (i.e., the predicate calculus), which we shall call EL. In the second section we investigate connections between higher-order monadic and polyadic logics.EM (...) is the subsystem of EL which results by the restriction to one-place predicate letters. We omit constants (for simplicity) but take EM to contain identity. Let atypebe any finite sequence (possibly empty) of one-place predicate letters. A modelMof typehas a nonempty universe ∣M∣ and assigns to each predicate letterPofa subsetPMof ∣M∣.Let us take a monadic logicLto be any collection of classes of models, calledL-classes, satisfying the following:1. All models in a givenL-class are of the same type (called the type of the class).2. Isomorphic models lie in the sameL-classes.3. IfandareL-classes of the same type, thenandareL-classes. (shrink)

We associate with any abstract logic L a family F(L) consisting, intuitively, of the limit ultrapowers which are complete extensions in the sense of L. For every countably generated [ω, ω]-compact logic L, our main applications are: (i) Elementary classes of L can be characterized in terms of $\equiv_L$ only. (ii) If U and B are countable models of a countable superstable theory without the finite cover property, then $\mathfrak{U} \equiv_L \mathfrak{B}$ . (iii) There exists the "largest" logic M such (...) that complete extensions in the sense of M and L are the same; moreover M is still [ω,ω]-compact and satisfies an interpolation property stronger than unrelativized ▵-closure. (iv) If L = L ωω(Q α ) , then $\operatorname{cf}(\omega_\alpha) > \omega$ and $\lambda^\omega for all $\lambda . We also prove that no proper extension of L ωω generated by monadic quantifiers is compact. This strengthens a theorem of Makowsky and Shelah. We solve a problem of Makowsky concerning L κλ -compact cardinals. We partially solve a problem of Makowsky and Shelah concerning the union of compact logics. (shrink)

Ultrafilters play a significant role in model theory to characterize logics having various compactness and interpolation properties. They also provide a general method to construct extensions of first-order logic having these properties. A main result of this paper is that every class $\Omega $ of uniform ultrafilters generates a $\Delta $ -closed logic ${\mathcal {L}}_\Omega $. ${\mathcal {L}}_\Omega $ is $\omega $ -relatively compact iff some $D\in \Omega $ fails to be $\omega _1$ -complete iff ${\mathcal {L}}_\Omega $ does not (...) contain the quantifier “there are uncountably many.” If $\Omega $ is a set, or if it contains a countably incomplete ultrafilter, then ${\mathcal {L}}_\Omega $ is not generated by Mostowski cardinality quantifiers. Assuming $\neg 0^\sharp $ or $\neg L^{\mu }$, if $D\in \Omega $ is a uniform ultrafilter over a regular cardinal $\nu $, then every family $\Psi $ of formulas in ${\mathcal {L}}_\Omega $ with $|\Phi |\leq \nu $ satisfies the compactness theorem. In particular, if $\Omega $ is a proper class of uniform ultrafilters over regular cardinals, ${\mathcal {L}}_\Omega $ is compact. (shrink)

Lindström’s theorem obviously fails as a characterization of first-order logic without identity ( $\mathcal {L}_{\omega \omega }^{-} $ ). In this note, we provide a fix: we show that $\mathcal {L}_{\omega \omega }^{-} $ is a maximal abstract logic satisfying a weak form of the isomorphism property (suitable for identity-free languages and studied in [11]), the Löwenheim–Skolem property, and compactness. Furthermore, we show that compactness can be replaced by being recursively enumerable for validity under certain conditions. In the proofs, we (...) use a form of strong upwards Löwenheim–Skolem theorem not available in the framework with identity. (shrink)

The Ehrenfeucht–Fraïsse game for a logic usually provides an intuitive characterizarion of its expressive power while in abstract model theory, logics are compared by their expressive powers. In this paper, I explore this connection in details by proving a general Lindström theorem for logics which have certain types of Ehrenfeucht–Fraïsse games. The results generalize and uniform some known results and may be applied to get new Lindström theorems for logics.

In this paper I discuss Ernst Zermelo’s ideas concerning the possibility of developing a system of infinitary logic that, in his opinion, should be suitable for mathematical inferences. The presentation of Zermelo’s ideas is accompanied with some remarks concerning the development of infinitary logic. I also stress the fact that the second axiomatization of set theory provided by Zermelo in 1930 involved the use of extremal axioms of a very specific sort.1.

We generalize two well-known model-theoretic characterization theorems from propositional modal logic to first-order modal logic. We first study FML-definable frames and give a version of the Goldblatt–Thomason theorem for this logic. The advantage of this result, compared with the original Goldblatt–Thomason theorem, is that it does not need the condition of ultrafilter reflection and uses only closure under bounded morphic images, generated subframes and disjoint unions. We then investigate Lindström type theorems for first-order modal logic. We show that FML has (...) the maximal expressive power among the logics extending FML which satisfy compactness, bisimulation invariance and the Tarski union property. (shrink)

This volume is about abstract objects and the ways we refer to them in natural language. Asher develops a semantical and metaphysical analysis of these entities in two stages. The first reflects the rich ontology of abstract objects necessitated by the forms of language in which we think and speak. A second level of analysis maps the ontology of natural language metaphysics onto a sparser domain--a more systematic realm of abstract objects that are fully analyzed. This second level reflects the (...) commitments of real metaphysics. The models for these commitments assign truth conditions to natural language discourse. Annotation copyright by Book News, Inc., Portland, OR. (shrink)

We introduce a natural principleStrong Chang Reflectionstrengthening the classical Chang Conjectures. This principle is between a huge and a two huge cardinal in consistency strength. In this note we prove that it implies the existence of an inner model with a huge cardinal. The technique we explore for building inner models with huge cardinals adapts to show thatdecisiveideals imply the existence of inner models with supercompact cardinals. Proofs for all of these claims can be found in [10].1,2.

The Craig Interpolation Theorem is intimately connected with the emergence of abstract logic and continues to be the driving force of the field. I will argue in this paper that the interpolation property is an important litmus test in abstract model theory for identifying “natural,” robust extensions of first order logic. My argument is supported by the observation that logics which satisfy the interpolation property usually also satisfy a Lindström type maximality theorem. Admittedly, the range of such logics is small.

In this paper we isolate a notion that we call “formalism freeness” from Gödel's 1946 Princeton Bicentennial Lecture, which asks for a transfer of the Turing analysis of computability to the cases of definability and provability. We suggest an implementation of Gödel's idea in the case of definability, via versions of the constructible hierarchy based on fragments of second order logic. We also trace the notion of formalism freeness in the very wide context of developments in mathematical logic in the (...) 20th century. (shrink)

First-order logic is known to have a severely limited expressive power on finite structures. As a result, several different extensions have been investigated, including fragments of second-order logic, fixpoint logic, and the infinitary logic L∞ωω in which every formula has only a finite number of variables. In this paper, we study generalized quantifiers in the realm of finite structures and combine them with the infinitary logic L∞ωω to obtain the logics L∞ωω, where Q = {Qi: iε I} is a family (...) of generalized quantifiers on finite structures. Using the logics L∞ωω, we can express polynomial-time properties that are not definable in L∞ωω, such as “there is an even number of x” and “there exists at least n/2 x” , without going to second-order logic. We show that equivalence of finite structures relative to L∞ωω can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht—Fraïssé games. We combine this game-theoretic characterization with sophisticated combinatorial tools from Ramsey theory, such as van der Waerden's Theorem and Folkman's Theorem, in order to investigate the scope and limits of generalized quantifiers in finite model theory. We obtain sharp lower bounds for expressibility in the logics L∞ωω and discover an intrinsic difference between adding finitely many simple unary generalized quantifiers to L∞ωω adding infinitely many. In particular, we show that if Qis a finite sequence of simple unary generalized quantifiers, then the equicardinality, or Härtig, quantifier is not definable in L∞ωω. We also show that the query “does the equivalence relation E have an even number of equivalence classes” is not definable in the extension L∞ωω of L∞ωω by the Härtig quantifier I and any finite sequence Q of simple unary generalized quantifiers. (shrink)

There are several known Lindström-style characterization results for basic modal logic. This paper proves a generic Lindström theorem that covers any normal modal logic corresponding to a class of Kripke frames definable by a set of formulas called strict universal Horn formulas. The result is a generalization of a recent characterization of modal logic with the global modality. A negative result is also proved in an appendix showing that the result cannot be strengthened to cover every first-order elementary class of (...) frames. This is shown by constructing an explicit counterexample. (shrink)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 BASIC MODAL LOGIC . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.

Given an abstract logic L = L(Q i ) i ∈ I generated by a set of quantifiers Q i , one can construct for each type τ a topological space S τ exactly as one constructs the Stone space for τ in first-order logic. Letting T be an arbitrary directed set of types, the set $S_T = \{(S_\tau, \pi^\tau_\sigma)\mid\sigma, \tau \in T, \sigma \subset \tau\}$ is an inverse topological system whose bonding mappings π τ σ are naturally determined by (...) the reduct operation on structures. We relate the compactness of L to the topological properties of S T . For example, if I is countable then L is compact iff for every τ each clopen subset of S τ is of finite type and S τ is homeomorphic to $\underset{lim}S_T$ , where T is the set of finite subtypes of τ. We finally apply our results to concrete logics. (shrink)

We study generalized quantifiers on finite structures.With every function : we associate a quantifier Q by letting Q x say there are at least (n) elementsx satisfying , where n is the sizeof the universe. This is the general form ofwhat is known as a monotone quantifier of type .We study so called polyadic liftsof such quantifiers. The particular lifts we considerare Ramseyfication, branching and resumption.In each case we get exact criteria fordefinability of the lift in terms of simpler quantifiers.

Though deceptively simple and plausible on the face of it, Craig's interpolation theorem has proved to be a central logical property that has been used to reveal a deep harmony between the syntax and semantics of first order logic. Craig's theorem was generalized soon after by Lyndon, with application to the characterization of first order properties preserved under homomorphism. After retracing the early history, this article is mainly devoted to a survey of subsequent generalizations and applications, especially of many-sorted interpolation (...) theorems. Attention is also paid to methodological considerations, since the Craig theorem and its generalizations were initially obtained by proof-theoretic arguments while most of the applications are model-theoretic in nature. The article concludes with the role of the interpolation property in the quest for "reasonable" logics extending first-order logic within the framework of abstract model theory. (shrink)

A semantical definition of abstract logics is given. It is shown that the Craig interpolation property implies the Beth definability property, and that the Souslin-Kleene interpolation property implies the weak Beth definability property. An example is given, showing that Beth does not imply Souslin-Kleene.

Carnap's philosophy is examined from new viewpoints, including three important distinctions: (i) language as calculus vs language as universal medium; (ii) different senses of completeness: (iii) standard vs nonstandard interpretations of (higher-order) logic. (i) Carnap favored in 1930-34 the "formal mode of speech," a corollary to the universality assumption. He later gave it up partially but retained some of its ingredients, e.g., the one-domain assumption. (ii) Carnap's project of creating a universal self-referential language is encouraged by (ii) and by the (...) author's recent work. (iii) Carnap was aware of (iii) and occasionally used the standard interpretation, but was not entirely clear of the nature of the contrast. (shrink)