Classical accounts of intertheoretic reduction involve two pieces: first, the new terms of the higher-level theory must be definable from the terms of the lower-level theory, and second, the claims of the higher-level theory must be deducible from the lower-level theory along with these definitions. The status of each of these pieces becomes controversial when the alleged reduction involves an infinite limit, as in statistical mechanics. Can one define features of or deduce the behavior of an infinite idealized system from (...) a theory describing only finite systems? In this paper, I change the subject in order to consider the motivations behind the definability and deducibility requirements. The classical accounts of intertheoretic reduction are appealing because when the definability and deducibility requirements are satisfied there is a sense in which the reduced theory is forced upon us by the reducing theory and the reduced theory contains no more information or structure than the reducing theory. I will show that, likewise, there is a precise sense in which in statistical mechanics the properties of infinite limiting systems are forced upon us by the properties of finite systems, and the properties of infinite systems contain no information beyond the properties of finite systems. (shrink)

Henkin quantifiers have been introduced in Henkin (1961). Walkoe (1970) studied basic model-theoretical properties of an extension $L_{*}^{1}$ (H) of ordinary first-order languages in which every sentence is a first-order sentence prefixed with a Henkin quantifier. In this paper we consider a generalization of Walkoe's languages: we close $L_{*}^{1}$ (H) with respect to Boolean operations, and obtain the language L¹(H). At the next level, we consider an extension $L_{*}^{2}$ (H) of L¹(H) in which every sentence is an L¹(H)-sentence prefixed with (...) a Henkin quantifier. We repeat this construction to infinity. Using the (un)definability of truth - in - N for these languages, we show that this hierarchy does not collapse. In addition, we compare some of the present results to the ones obtained by Kripke (1975), McGee (1991), and Hintikka (1996). (shrink)

The present paper suggests relative truth definability as a tool for comparing conceptual aspects of axiomatic theories of truth and gives an overview of recent developments of axiomatic theories of truth in the light of it. We also show several new proof-theoretic results via relative truth definability including a complete answer to the conjecture raised by Feferman in [13].

This paper studies definability within the theory of institutions, a version of abstract model theory that emerged in computing science studies of software specification and semantics. We generalise the concept of definability to arbitrary logics, formalised as institutions, and we develop three general definability results. One generalises the classical Beth theorem by relying on the interpolation properties of the institution. Another relies on a meta Birkhoff axiomatizability property of the institution and constitutes a source for many new (...) actual definability results, including definability in (fragments of) classical model theory. The third one gives a set of sufficient conditions for 'borrowing' definability properties from another institution via an 'adequate' encoding between institutions. The power of our general definability results is illustrated with several applications to (many-sorted) classical model theory and partial algebra, leading for example to definability results for (quasi-)varieties of models or partial algebras. Many other applications are expected for the multitude of logical systems formalised as institutions from computing science and logic. (shrink)

A central theme in the philosophy of sport literature is the definability of games. According to Thomas Hurka, and others, the argument presented by Bernard Suits in The Grasshopper refutes...

The Denjoy integral is an integral that extends the Lebesgue integral and can integrate any derivative. In this paper, it is shown that the graph of the indefinite Denjoy integral f↦∫xaf is a coanalytic non-Borel relation on the product space M[a,b]×C[a,b], where M[a,b] is the Polish space of real-valued measurable functions on [a,b] and where C[a,b] is the Polish space of real-valued continuous functions on [a,b]. Using the same methods, it is also shown that the class of indefinite Denjoy integrals, (...) called ACG∗[a,b], is a coanalytic but not Borel subclass of the space C[a,b], thus answering a question posed by Dougherty and Kechris. Some basic model theory of the associated spaces of integrable functions is also studied. Here the main result is that, when viewed as an ℝ[X]-module with the indeterminate X being interpreted as the indefinite integral, the space of continuous functions on the interval [a,b] is elementarily equivalent to the Lebesgue-integrable and Denjoy-integrable functions on this interval, and each is stable but not superstable, and that they all have a common decidable theory when viewed as ℚ[X]-modules. (shrink)

The idea of a property's being supervenient on a class of properties is familiar from much philosophical literature. We give this idea a linguistic turn by converting it into the idea of a predicate symbol's being supervenient on a set of predicate symbols relative to a (first order) theory. What this means is that according to the theory, any individuals differing in respect to whether the given predicate applies to them also differ in respect to the application of at least (...) one of the predicates in the set. The latter relationship we show turns out to coincide with something antecedently familiar from work on definability: with what is called the piecewise (or modelwise) definability, in the theory in question, of the given predicate in terms of those in the set. (shrink)

A few results generalizing well-known classical model theory ones have been obtained in institution theory these last two decades (e.g. Craig interpolation, ultraproduct, elementary diagrams). In this paper, we propose a generalized institution-independent version of the Beth definability theorem.

Among the main theorems obtained in mathematical logic in this century are the so called limitation theorems, i.e., the Löwenheim-Skolem theorem on the cardinality of models of first-order theories, Gödel’s incompleteness theorems and Tarski’s theorem on the undefinability of truth. Problems connected with the latter are the subject of this paper. In Section 1 we shall consider Tarski’s theorem. In particular the original formulation of it as well as some specifications will be provided. Next various meanings of the notion of (...) a satisfaction predicate will be studied. In Section 2 the problem of definability of the notion of truth, in particular of the notion of truth for the language of Peano arithmetic PA, will be discussed. It will be explicitly shown that the notion of satisfaction for the language of PA can be defined in a certain weak fragment of the second order arithmetic. Finally the axiomatic characterization of satisfaction and truth as well and its mathematical and philosophical meaning will be discussed. (shrink)

We investigate expressiveness and definability issues with respect to minimal models, particularly in the scope of Circumscription. First, we give a proof of the failure of the Löwenheim-Skolem Theorem for Circumscription. Then we show that, if the class of P; Z-minimal models of a first-order sentence is Δ-elementary, then it is elementary. That is, whenever the circumscription of a first-order sentence is equivalent to a first-order theory, then it is equivalent to a finitely axiomatizable one. This means that classes (...) of models of circumscribed theories are either elementary or not Δ-elementary. Finally, using the previous result, we prove that, whenever a relation Pi is defined in the class of P; Z-minimal models of a first-order sentence Φ and whenever such class of P; Z-minimal models is Δ-elementary, then there is an explicit definition ψ for Pi such that the class of P; Z-minimal models of Φ is the class of models of Φ ∧ ψ. In order words, the circumscription of P in Φ with Z varied can be replaced by Φ plus this explicit definition ψ for Pi. (shrink)

We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it does not have the strong Beth definability property.

We isolate a condition on a class A of ordinals sufficient to Δ1-code it by a real in a class-generic extension of L. We then apply this condition to show that the class of ordinals of L-cofinality ω is Δ1 in a real of L-degree strictly below O#.

In this paper we study the expressive power and definability for modal languages interpreted on topological spaces. We provide topological analogues of the van Benthem characterization theorem and the Goldblatt–Thomason definability theorem in terms of the well-established first-order topological language.

We investigate the definability in monadic ∑11 and monadic Π11 of the problems REGk, of whether there is a regular subgraph of degree k in some given graph, and XREGk, of whether, for a given rooted graph, there is a regular subgraph of degree k in which the root has degree k, and their restrictions to graphs in which every vertex has degree at most k, namely REGkk and XREGkk, respectively, for k ≥ 2 . Our motivation partly stems (...) from the fact that REGkk and XREGkk are logspace equivalent to CONN and REACH, respectively, for k ≥ 3, where CONN is the problem of whether a given graph is connected and REACH is the problem of whether a given graph has a path joining two given vertices. We use monadic first - order reductions, monadic ∑11 games and a recent technique due to Fagin, Stockmeyer and Vardi to almost completely classify whether these problems are definable in monadic ∑11 and monadic Π11, and we compare the definability of these problems. (shrink)

This paper investigates logical aspects of combining linear orders as semantics for modal and temporal logics, with modalities for possible paths, resulting in a variety of branching time logics over classes of trees. Here we adopt a unified approach to the Priorean, Peircean and Ockhamist semantics for branching time logics, by considering them all as fragments of the latter, obtained as combinations, in various degrees, of languages and semantics for linear time with a modality for possible paths. We then consider (...) a hierarchy of natural classes of trees and bundled trees arising from a given class of linear orders and show that in general they provide different semantics. We also discuss transfer of definability from linear orders to trees and introduce a uniform translation from Priorean to Peircean formulae which transfers definability of properties of linear orders to definability of properties of all paths in trees. (shrink)

The provability logic GL was in the field of interest of A.V. Kuznetsov, who had also formulated its intuitionistic analog—the intuitionisticprovability logic—and investigated these two logics and their extensions.In the present paper, different versions of interpolation and of the Bethproperty in normal extensions of the provability logic GL are considered. Itis proved that in a large class of extensions of GL almost all versions of interpolation and of the Beth propertyare equivalent. It follows that in finite slice logics over GL (...) the three versionsCIP, IPD and IPR of the interpolation property are equivalent. Also theyare equivalent to the Beth properties B1, PB1 and PB2. (shrink)

In this paper it will be shown that the Beth definability property corresponds to surjectiveness of epimorphisms in abstract algebraic logic. This generalizes a result by I. Németi (cf. [11, Theorem 5.6.10]). Moreover, an equally general characterization of the weak Beth property will be given. This gives a solution to Problem 14 in [20]. Finally, the characterization of the projective Beth property for varieties of modal algebras by L. Maksimova (see [15]) will be shown to hold for the larger (...) class of semantically algebraizable logics. (shrink)

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in (...) restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property. (shrink)

In this paper I am going to inquire to what extent the main requirements of a minimalist theory of truth and falsity (as formulated, for example, by Horwich and Field) can be consistently implemented in a formal theory. I will discuss several of the existing logical theories of truth, including Tarski-type (un)definability results, Kripke’s partial interpretation of truth and falsity, Barwise and Moss’ theory based upon non-well-founded sets, McGee’s treatment of truth as a vague predicate, and Hintikka’s languages of (...) imperfect information, to see which axioms of the minimalist theory they satisfy or fail to satisfy. Finally, I will discuss the relation between the minimalist program and compositionality. (shrink)

Let be a relational system whereby D is a nonempty set and P1 is an m1-ary relation on D. With we associate the (weak) monadic second-order theory consisting of the first-order predicate calculus with individual variables ranging over D; monadic predicate variables ranging over (finite) subsets of D; monadic predicate quantifiers; and constants corresponding to P1, P2, …. We will often use ambiguously to mean also the set of true sentences of.