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].

In his thesis 'Para uma Teoria Geral dos Homomorfismos' (1944) the Portuguese mathematician José Sebastião e Silva constructed an abstract or generalized Galois theory, that is intimately linked to F. Klein’s Erlangen Program and that foreshadows some notions and results of today’s model theory; an analogous theory was independently worked out by M. Krasner in 1938. In this paper, we present a version of the theory making use of tools which were not at Silva’s disposal. At the same time, we (...) tried to keep in mind, so much as possible, the gist of his standpoint. (shrink)

The bounded arithmetic theories R2i, S2i, and T2i are closely connected with complexity theory. This paper is motivated by the questions: what are the Σi+1b-definable multifunctions of R2i? and when is one theory conservative over another? To answer these questions we consider theories , and where induction is restricted to prenex formulas. We also define which has induction up to the 0 or 1-ary L2-terms in the set τ. We show and and for . We show that the -multifunctions of (...) are FPΣip and that those of are FPΣip. For -definability we get FPΣi+k+1p for all these theories. Write for the set of terms 2min,t) where ℓ is a finite product of terms in τ and tL2. We prove and we show - INDτ provided τO2. This gives a proof theoretic proof that S2iΔi+1b-LIND and -LLIND solving an open problem. For τO2, we define using weak replacement axioms and show . We show if or if or if where τ′ has an unbounded term then PH=B. We separate PΣip from PΣip for behaved ℓ and deduce theory separations. We lastly introduce a notion of a model separating two theories and derive some consequences. (shrink)

In his Formalization of Logic (1943) Carnap pointed out that there are non-normal interpretations of classical logic: non-standard interpretations of the connectives and quantifiers that are consistent with the classical consequence relation of a language. Different ways around the problem have been proposed. In a recent paper, Bonnay and Westerståhl argue that the key to a solution is imposing restrictions on the type of interpretation we take into account. More precisely, they claim that if we restrict attention to interpretations that (...) are (a) compositional, (b) non-trivial and (c) in the case of the quantifiers, invariant under permutations of the domain, Carnap’s Problem is avoided. This paper has two goals. The first is to show that Bonnay and Westerståhl’s solution to Carnap’s Problem doesn’t work. The second is to argue that something similar to their proposal seems to do the job. The problems with Bonnay and Westerståhl’s approach trace back to issues concerning the (un)definability of subsets of the domain of first-order structures, as well as to the compositionality of first-order languages. After expanding on these problems, I’ll propose a way to modify Bonnay and Westerståhl’s account and solve Carnap’s Problem. (shrink)

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)

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)

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)

We point out how the "Fundamental Theorem of Stability Theory", namely the equivalence between the "non order property" and definability of types, proved by Shelah in the 1970s, is in fact an immediate consequence of Grothendieck's "Criteres de compacite" from 1952. The familiar forms for the defining formulae then follow using Mazur's Lemma regarding weak convergence in Banach spaces.

Combining two results from machine learning theory we prove that a formula is NIP if and only if it satisfies uniform definability of types over finite sets (UDTFS). This settles a conjecture of Laskowski.

In 1905, Richard discovered his paradox of definability, and in a letter written that year he presented both the paradox and a solution to it.Soon afterwards, Poincaré endorsed a variant of Richard?s solution.In this paper, I critically examine Richard?s and Poincaré?s ways out.I draw on an objection of Peano?s, and argue that their stated solutions do not work.But I also claim that their writings suggest another way out, different from their stated solutions, and different from the orthodox Tarskian approach.I (...) argue that this second solution does not prevent the return of the paradox. (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)

§1. Introduction. Natural sets that can be enumerated by a computable function always seem to be either actually computable or of the same complexity as the Halting Problem, the complete r.e. set K. The obvious question, first posed in Post [1944] and since then called Post's Problem is then just whether there are r.e. sets which are neither computable nor complete, i.e., neither recursive nor of the same Turing degree as K?Let be the r.e. degrees, i.e., the r.e. sets modulo (...) the equivalence relation of equicomputable with the partial order induced by Turing computability. This structure is a partial order with least element 0, the degree of the computable sets, and greatest element 1 or 0′, the degree of K. Post's problem then asks if there are any other elements of.The solution of Post's problem by Friedberg [1957] and Muchnik [1956] was followed by various algebraic or order theoretic results that were interpreted as saying that the structure was in some way well behaved:Theorem 1.1. Every countable partial ordering or even uppersemilattice can be embedded into.Theorem 1.2. For every nonrecursive r.e. degreeathere are r.e. degreesb, c < asuch thatb ∨ c = a.Theorem 1.3. For every pair of nonrecursive r.e. degreesa < bthere is an r.e. degreecsuch thata < c < b. (shrink)

Oikkonen, J. and J. Väänänen, Game-theoretic inductive definability, Annals of Pure and Applied Logic 65 265-306. We use game-theoretic ideas to define a generalization of the notion of inductive definability. This approach allows induction along non-well-founded trees. Our definition depends on an underlying partial ordering of the objects. In this ordering every countable ascending sequence is assumed to have a unique supremum which enables us to go over limits. We establish basic properties of this induction and examine examples (...) where it emerges naturally. In the main results we prove an abstract Kleene Theorem and restricted versions of the Stage-Comparison Theorem and the Reduction Theorem. (shrink)

In his new introduction to the 1925 second edition of Principia Mathematica, Russell maintained that by adopting Wittgenstein's idea that a logically perfect language should be extensional mathematical induction could be rectified for finite cardinals without the axiom of reducibility. In an Appendix B, Russell set forth a proof. Godel caught a defect in the proof at *89.16, so that the matter of rectification remained open. Myhill later arrived at a negative result: Principia with extensionality principles and without reducibility cannot (...) recover mathematical induction. The finite cardinals are indefinable in it. This paper shows that while Gödel and Myhill are correct, Russell was not wrong. The 1925 system employs a different grammar than the original Principia. A new proof for *89.16 is given and induction is recovered. (shrink)

Assuming the existence of a supercompact cardinal, we construct a model where, for some uncountable regular cardinal κ, there are no κ‐mad families.

A compact complex space X is viewed as a 1-st order structure by taking predicates for analytic subsets of X, X \times X, … as basic relations. Let f: X→ Y be a proper surjective holomorphic map between complex spaces and set Xy:=f-1(y). We show that the set Ak,d:={y∈ Y: the number of d-dimensional components of Xy is (...) holomorphic map. The analogous result in the context of algebraic geometry gives rise to the definability of Morley degree. (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)

Hilbert-style axiomatic systems are presented for versions of the modal logics K, where {D, 4, 5}, with noncontingency as the sole modal primitive. The classes of frames characterized by the axioms of these systems are shown to be first-order definable, though not equal to the classes of serial, transitive, or euclidean frames. The canonical frame of the noncontingency logic of any logic containing the seriality axiom is proved to be nonserial. It is also shown that any class of frames definable (...) in the noncontingency language contains the class of functional frames, and dually, there exists a greatest consistent normal noncontingency 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...

We formulate a certain subtheory of Ishimoto’s [1] quantifier-free fragment of Leśniewski’s ontology, and show that Ishimoto’s theory can be reconstructed in it. Using an epimorphism theorem we prove that our theory is complete with respect to a suitable set-theoretic interpretation. Furthermore, we introduce the name constant 1 and we prove its adequacy with respect to the set-theoretic interpretation. Ishimoto’s theory enriched by the constant 1 is also reconstructed in our formalism with into which 1 has been introduced. Finally we (...) examine for both our theories their quantifier extensions and their connections with Leśniewski’s classical quantified ontology. (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.

In this paper we see that the answer of this question is affirmative. We prove this for Dco-algebras and as special case we obtain the result for Positive Implication algebras. First we give, without proof, the properties of Dco-algebras and S-algebras and their connection with Positive Implication algebras and Implication algebras. These results can be found in [T] and [IT].