The paper starts with an examination and critique of Tarski’s wellknown proposed explication of the notion of logical operation in the type structure over a given domain of individuals as one which is invariant with respect to arbitrary permutations of the domain. The class of such operations has been characterized by McGee as exactly those definable in the language L∞,∞. Also characterized similarly is a natural generalization of Tarski’s thesis, due to Sher, in terms of bijections between domains. My main (...) objections are that on the one hand, the Tarski-Sher thesis thus assimilates logic to mathematics, and on the other hand fails to explain the notion of same logical operation across domains of different sizes. A new notion of homomorphism invariant operation over functional type structures (with domains M0 of individuals and {T, F} at their base) is introduced to accomplish the latter. The main result is that an operation is definable from.. (shrink)

We show how to build various models of first-order theories, which also have properties like: tree with only definable branches, atomic Boolean algebras or ordered fields with only definable automorphisms. For this we use a set-theoretic assertion, which may be interesting by itself on the existence of quite generic subsets of suitable partial orders of power λ + , which follows from ♦ λ and even weaker hypotheses . For a related assertion, which is equivalent to the morass see Shelah (...) and Stanley [16]. The various specific constructions serve also as examples of how to use this set-theoretic lemma. We apply the method to construct rigid ordered fields, rigid atomic Boolean algebras, trees with only definable branches; all in successors of regular cardinals under appropriate set- theoretic assumptions. So we are able to answer the following algebraic question. Saltzman's Question . Is there a rigid real closed field, which is not a subfield of the reals? (shrink)

We use some notions from computability in an uncountable setting to describe a difference between the “Zilber field” of size ℵ1ℵ1 and the “Zilber cover” of size ℵ1ℵ1.

We study classes of atomic models \ of a countable, complete first-order theory T. We prove that if \ is not \-small, i.e., there is an atomic model N that realizes uncountably many types over \\) for some finite \ from N, then there are \ non-isomorphic atomic models of T, each of size \.

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)

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.

§1. Introduction. After the pioneering work of Mostowski [29] and Lindström [23] it was Jon Barwise's papers [2] and [3] that brought abstract model theory and generalized quantifiers to the attention of logicians in the early seventies. These papers were greeted with enthusiasm at the prospect that model theory could be developed by introducing a multitude of extensions of first order logic, and by proving abstract results about relationships holding between properties of these logics. Examples of such properties areκ-compactness.Any set (...) of sentences of cardinality ≤ κ, every finite subset of which has a model, has itself a model.Löwenheim-Skolem Theorem down toκ.If a sentence of the logic has a model, it has a model of cardinality at most κ.Interpolation Property.If ϕ and ψ are sentences such that ⊨ ϕ → Ψ, then there is θ such that ⊨ ϕ → θ, ⊨ θ → Ψ and the vocabulary of θ is the intersection of the vocabularies of ϕ and Ψ.Lindstrom's famous theorem characterized first order logic as the maximal ℵ0-compact logic with Downward Löwenheim-Skolem Theorem down to ℵ0. With his new concept of absolute logics Barwise was able to get similar characterizations of infinitary languagesLκω. But hopes were quickly frustrated by difficulties arising left and right, and other areas of model theory came into focus, mainly stability theory. No new characterizations of logics comparable to the early characterization of first order logic given by Lindström and of infinitary logic by Barwise emerged. What was first called soft model theory turned out to be as hard as hard model theory. (shrink)

We define the concept of a logic frame , which extends the concept of an abstract logic by adding the concept of a syntax and an axiom system. In a recursive logic frame the syntax and the set of axioms are recursively coded. A recursive logic frame is called complete , if every finite consistent theory has a model. We show that for logic frames built from the cardinality quantifiers “there exists at least λ ” completeness always implies .0-compactness. On (...) the other hand we show that a recursively compact logic frame need not be ℵ0-compact. (shrink)

Universal Logic is not a new logic, but a general theory of logics, considered as mathematical structures. The name was introduced about ten years ago, but the subject is as old as the beginning of modern logic: Alfred Tarski and other Polish logicians such as Adolf Lindenbaum developed a general theory of logics at the end of the 1920s based on consequence operations and logical matrices. The subject was revived after the flowering of thousands of new logics during the last (...) thirty years: there was a need for a systematic theory of logics to put some order in this chaotic multiplicity. This bo. (shrink)

The main results in the paper are the following. Theorem A. Suppose that T is superstable and M ⊂ N are distinct models of T eq . Then there is a c ϵ N⧹M such that t is regular. For M ⊂ N two models we say that M ⊂ na N if for all a ϵ M and θ such that θ ≠ θ , there is a b ∈ θ ⧹ acl . Theorem B Suppose that T is (...) superstable , M ⊂ na N are models of T eq , and p is a regular type non-orthogonal to t . Then there is a c ϵ N such that t is regular and non-orthogonal to p. Furthermore, there is a formula θ ∈ t such that a ∈ θ and t ⊥ ̷ p ⇒ t is regular. We used these results to obtain ‘good’ tree decompositions of models in superstable theories with NDOP. See Definition 5.1 for the undefined terms. Theorem C Suppose that T is superstable with NDOP and M ⊨ T eq . Then every ⊂ na - decomposition inside M extends to a ⊂ na -decomposition of M. Furthermore, if 〈N η , a η : η ∈ I〉 is any ⊂ na -decomposition of M, then M is minimal over ∪N η and for all η ∈ I. M is dominated by ∪N η over N η . Using some stable group theory we show that when Th is superstable with NDOP and 〈 N η : η ∈ I 〉 is a tree decomposition of M, then M is constructible over ∪ n η with respect to a very strong isolation relation. (shrink)

We succeed to say something on the identities of when μ > θ > cf with μ strong limit θ-compact or even μ is limit of compact cardinals.

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.

In paper [5] it was shown that a great part of model theory of logic with the generalized quantifier Q x = there exist uncountably many x is reducible to the model theory of first order logic with an extra binary relation symbol. In this paper we consider when the quantifier Q x can be syntactically defined in a first order theory T. That problem was raised by Kosta Doen when he asked if the quantifier Q x can be eliminated (...) in Peano arithmetic. We answer that question fully in this paper. (shrink)

This chapter offers a logical, linguistic, and philosophical account of modern quantification theory. Contrasting the standard approach to quantifiers (according to which logical quantifiers are defined by enumeration) with the generalized approach (according to which quantifiers are defined systematically), the chapter begins with a brief history of standard quantifier theory and identifies some of its logical, linguistic, and philosophical strengths and weaknesses. It then proceeds to a brief history of generalized quantifier theory and explains how it overcomes the weaknesses of (...) the standard theory. One of the main philosophical advantages of the generalized theory is its philosophically informative criterion of logicality. The chapter describes the work done so far in this theory, highlights some of its central logical results, offers an overview of its main linguistic contributions, and discusses its philosophical significance. (shrink)

This paper reviews current psychological theories of syllogistic inference and establishes that despite their various merits they all contain deficiencies as theories of performance. It presents the results of two experiments, one using syllogisms and the other using three-term series problems, designed to elucidate how the arrangement of terms within the premises affects performance. These data are used in the construction of a theory based on the hypothesis that reasoners construct mental models of the premises, formulate informative conclusions about the (...) relations in the model, and search for alternative models that are counterexamples to these conclusions. This theory, which has been implemented in several computer programs, predicts that two principal factors should affect performance: the figure of the premises, and the number of models that they call for. These predictions were confirmed by a third experiment. Dans cet article sont passées en revue les théories psychologiques du traitement des syllogismes. On établit qu'en dépit de leurs mérites variés toutes sont en défaut en tant que théories de la performance. On présente les résultats de deux expériences, une utilisant des syllogismes et l'autre des problémes avec des séries de trois termes conçues pour élucider comment l'arrangement des termes dans les premises affecte la performance. Ces données sont utilisées pour construire une théorie fondée sur l'hypothése que les gens construisent des modèles mentaux des premises, formulent des conclusions explicites sur les relations dans le modèle et cherchent des modèles qui seraient des contre-exemples pour leurs conclusions. Cette théorie, utilisée dans plusieurs programmes d'ordinateur, prédit que deux principaux facteurs affectent la performance: la figure des premises et le nombre de; modèles qu'ils mettent en jeu. Cette prédiction est confirmée dans les trois expériences. (shrink)

This paper ties together much of the model theory of the last 50 years. Shelah's attempts to generalize the Morley theorem beyond first order logic led to the notion of excellence, which is a key to the structure theory of uncountable models. The notion of Abstract Elementary Class arose naturally in attempting to prove the categoricity theorem for L ω 1 ,ω (Q). More recently, Zilber has attempted to identify canonical mathematical structures as those whose theory (in an appropriate logic) (...) is categorical in all powers. Zilber's trichotomy conjecture for first order categorical structures was refuted by Hrushovski, by the introducion of a special kind of Abstract Elementary Class. Zilber uses a powerful and essentailly infinitary variant on these techniques to investigate complex exponentiation. This not only demonstrates the relevance of Shelah's model theoretic investigations to mainstream mathematics but produces new results and conjectures in algebraic geometry. (shrink)

A Kaufmann model is an \(\omega _1\) -like, recursively saturated, rather classless model of \({{\mathsf {P}}}{{\mathsf {A}}}\) (or \({{\mathsf {Z}}}{{\mathsf {F}}} \) ). Such models were constructed by Kaufmann under the combinatorial principle \(\diamondsuit _{\omega _1}\) and Shelah showed they exist in \(\mathsf {ZFC}\) by an absoluteness argument. Kaufmann models are an important witness to the incompactness of \(\omega _1\) similar to Aronszajn trees. In this paper we look at some set theoretic issues related to this motivated by the seemingly (...) naïve question of whether such a model can be “killed” by forcing without collapsing \(\omega _1\). We show that the answer to this question is independent of \(\mathsf {ZFC}\) and closely related to similar questions about Aronszajn trees. As an application of these methods we also show that it is independent of \(\mathsf {ZFC}\) whether or not Kaufmann models can be axiomatized in the logic \(L_{\omega _1, \omega } (Q)\) where _Q_ is the quantifier “there exists uncountably many”. (shrink)

The principal result of this paper answers a long-standing question in the model theory of arithmetic [R. Kossak, J. Schmerl, The Structure of Models of Peano Arithmetic, Oxford University Press, 2006, Question 7] by showing that there exists an uncountable arithmetically closed family of subsets of the set ω of natural numbers such that the expansion of the standard model of Peano arithmetic has no conservative elementary extension, i.e., for any elementary extension of , there is a subset of ω* (...) that is parametrically definable in but whose intersection with ω is not a member of . We also establish other results that highlight the role of countability in the model theory of arithmetic. Inspired by a recent question of Gitman and Hamkins, we furthermore show that the aforementioned family can be arranged to further satisfy the curious property that forcing with the quotient Boolean algebra collapses 1 when viewed as a notion of forcing. (shrink)

A condition, in two variants, is given such that if a property P satisfies this condition, then every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The result is used to prove that for a number of natural properties P speaking about automorphism groups or connectivity, every logic which is at least as strong as first-order logic and can express P fails to have the compactness property. The basic (...) idea underlying the results and examples presented here is that it is possible to construct a countable first-order theory T such that every model of T has a very rich automorphism group, but every finite subset T′ of T has a model which is rigid. (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)

Context is essential in virtually all human activities. Yet some logical notions seem to be context-free. For example, the nature of the universal quantifier, the very meaning of “all”, seems to be independent of the context. At the same time, there are many quantifier expressions, and some are context-independent, while others are not. Similarly, purely logical consequence seems to be context-independent. Yet often we encounter strong inferences, good enough for practical purposes, but not valid. The two types of examples suggest (...) a general problem: how to characterise the context-free logical concepts in their natural environment, that is, in the field of their context-dependent associates. A general Thesis on Quantifiers is formulated: among all quantifiers, the context-free ones are just those definable by the universal quantifier. The issue of inferences is treated following the approach introduced by Richard L. Epstein: valid ones are an extreme case, the result of the disappearance of context-dependence. This idea can be applied to an analysis of a form of abduction, called “reductive inference” in Polish literature on logic. A tentative Thesis on Inferences identifies the validity of a strong inference that is context-independent. (shrink)

It is proved, under Martin's Axiom, that all gaps in are indestructible in any forcing extension by a separable measure algebra. This naturally leads to a new type of gap, a summable gap. The results of these investigations have applications in Descriptive Set Theory. For example, it is shown that under Martin's Axiom the Baire categoricity of all Δ31 non-Δ31-complete sets of reals requires a weakly compact cardinal.

Simple formula should contain only few quantifiers. In the paper the methods to estimate quantity and quality of quantifiers needed to express a sentence equivalent to given one.

Mancosu, P., Generalizing classical and effective model theory in theories of operations and classes, Annas of Pure and Applied Logic 52 249-308 . In this paper I propose a family of theories of operations and classes with the aim of developing abstract versions of model-theoretic results. The systems are closely related to those introduced and already used by Feferman for developing his program of ‘explicit mathematics’. The theories in question are two-sorted, with one kind of variable for individuals and the (...) other for classes. The individual variables range over a domain closed under pairing and containing, among other things, natural numbers and operations.All the theories used assume a common group of axioms that insure that the individuals in the domain satisfy the conditions for a partial combinatory algebra with pairing. We also assume a class of natural numbers and a class induction axiom on . Finally there are various class existence axioms. I work mainly with three theories, FMT0, FMT and FMTΩ, which differ from each other both in their class existence axioms as well as in some further applicative axioms.These theories have various interpretations in which every object is explicitly presented by some means of definition as well as classical, or ‘standard’, set-theoretical interpretation. The systems are formulated in a flexible general language which can be used to prove abstract theorems of mathematics , thereby generalizing recursive, hyperarithmetic and admissible versions of classical mathematics.The aim of my work is to give an abstract development of portions of model theory in the afore-mentioned theories, in a way to look as much as possible like classical mathematics. Thus, FMT0 generalizes portions of countable and recursive model theory; FMT further generalizes portions of countable and hyperarithmetical model theory and finally FMTΩ provides a generalization of the classical L-completeness theorem and of an admissible version of L-completeness due to Bruce and Keisler. This continues the development of the program mentioned above, originating with Feferman. (shrink)

We introduce the notion of effective Axiom A and use it to show that some popular tree forcings are Suslin+. We introduce transitive nep and present a simplified version of Shelah’s “preserving a little implies preserving much”: If I is a Suslin ccc ideal (e.g. Lebesgue-null or meager) and P is a transitive nep forcing (e.g. P is Suslin+) and P does not make any I-positive Borel set small, then P does not make any I-positive set small.

In his 1936 paper,On the Concept of Logical Consequence, Tarski introduced the celebrated definition oflogical consequence: “The sentenceσfollows logicallyfrom the sentences of the class Γ if and only if every model of the class Γ is also a model of the sentenceσ.” [55, p. 417] This definition, Tarski said, is based on two very basic intuitions, “essential for the proper concept of consequence” [55, p. 415] and reflecting common linguistic usage: “Consider any class Γ of sentences and a sentence which (...) follows from the sentences of this class. From an intuitive standpoint it can never happen that both the class Γ consists only of true sentences and the sentenceσis false. Moreover, … we are concerned here with the concept of logical, i.e.,formal, consequence.” [55, p. 414] Tarski believed his definition of logical consequence captured the intuitive notion: “It seems to me that everyone who understands the content of the above definition must admit that it agrees quite well with common usage. … In particular, it can be proved, on the basis of this definition, that every consequence of true sentences must be true.” [55, p. 417] The formality of Tarskian consequences can also be proven. Tarski's definition of logical consequence had a key role in the development of the model-theoretic semantics of modern logic and has stayed at its center ever since. (shrink)

We investigate the existence of perfect homogeneous sets for analytic colorings. An analytic coloring of X is an analytic subset of [X]N, where N>1 is a natural number. We define an absolute rank function on trees representing analytic colorings, which gives an upper bound for possible cardinalities of homogeneous sets and which decides whether there exists a perfect homogeneous set. We construct universal σ-compact colorings of any prescribed rank γ<ω1. These colorings consistently contain homogeneous sets of cardinality γ but they (...) do not contain perfect homogeneous sets. As an application, we discuss the so-called defectedness coloring of subsets of Polish linear spaces. (shrink)

Numerical probabilities are eliminated in favor of qualitative notions, with an eye to isolating what it is about probabilities that is essential to judgements of acceptability. A basic choice point is whether the conjunction of two propositions, each acceptable, must be deemed acceptable. Concepts of acceptability closed under conjunction are analyzed within Keisler's weak logic for generalized quantifiers — or more specifically, filter quantifiers. In a different direction, the notion of a filter is generalized so as to allow sets with (...) probability non-infinitesimally below 1 to be acceptable. (shrink)