GILA SHERTRUTH, LOGICAL STRUCTURE, AND COMPOSITIONALITYABSTRACT. In this paper I examine a cluster of concepts relevant to the methodologyof truth theories: ‘informative definition’, ‘recursive method’, ‘semantic structure’, ‘logicalform’, ‘compositionality’, etc. The interrelations between these concepts, I will try to show,are more intricate and multi-dimensional than commonly assumed.1. TRUTH AND RECURSIONIn his 1933 paper, “The Concept of Truth in Formalized Languages”,Tarski drew a tentative connection between the definition of truth (for agiven language) and the recursive method:If the language investigated only contained a finite number of sentences fixed from thebeginning, and if we could enumerate all these sentences, then the problem of the con-struction of a correct definition of truth would present no difficulties. For this purpose itwould suffice to complete the following scheme: x ∈ Tr if and only if either x = x1andp1, or x = x2and p2,...or x = xnand pn, the symbols ‘x1’, ‘x2’,...,‘xn’ being replacedby structural-descriptive names of all the sentences of the language investigated and ‘p1’,‘p2’,...,‘pn’ by the corresponding translation of these sentences into the metalanguage.But the situation is not like this. Whenever a language contains infinitely many sentences,the definition constructed automatically according to the above scheme would have toconsist of infinitely many words, and such sentences cannot be formulated either in themetalanguage or in any other language. Our task is thus greatly complicated.The idea of using the recursive method suggests itself. [188–189]Tarski’s idea involves, however, an indirect use of the recursive method:Among the sentences of a language we find expressions of rather varied kinds from thepoint of view of logical structure, some quite elementary, others more or less complicated.It would thus be a question of first giving all the operations by which simple sentences arecombined into composite ones and then determining the way in which the truth or falsity ofcomposite sentences depends on the truth or falsity of the simpler ones contained in them.Moreover, certain elementary sentences could be selected, from which, with the help ofthe operations mentioned, all the sentences of the language could be constructed; theseselected sentences could be explicitly divided into true and false, by means, for example,of partial definitions of the type described above. In attempting to realize this idea we arehowever confronted with a serious obstacle. Even a superficial analysis of Defs. 10–12 ofSynthese 126: 195–219, 2001.© 2001 Kluwer Academic Publishers. Printed in the Netherlands.196 GILA SHERSection 2 shows that in general composite sentences are in no way compounds of simplesentences. Sentential functions do in fact arise in this way from elementary functions ...;sentences on the contrary are certain special cases of sentential functions. In view of thisfact, no method can be given which would enable us to define the required concept directlyby recursive means. The possibility suggests itself, however, of introducing a more generalconcept which is applicable to any sentential function, can be recursively defined, and,when applied to sentences, leads us directly to the concept of truth. These requirements aremet by the notion of satisfaction of a given sentential function by given objects ...[189]Referring to the special language of the calculus of classes, Tarskispecifies:We shall use a recursive method in order to formulate a general definition of satisfaction ofa sentential function by a sequence of classes, which will include as special cases all partialdefinitions of this notion that are obtained from the given scheme in the way describedabove. For this purpose it will suffice, bearing in mind the definition of sentential function,to indicate which sequences satisfy the inclusions ‘xk⊆ xl’ and then to specify howthe notion we are defining behaves when the three fundamental operations of negation,disjunction, and universal quantification are performed on sentential functions. [192]I will not repeat Tarski’s formal account of the definition of truth forthe language of the calculus of classes here, but assuming familiarity withthis account, I will encapsulate it in the following way:1.1. Definition of Truth for LcLet Lcbe the formalized language of the calculus of classes whose prim-itive symbols are the individual variables ‘x1’, ‘x2’, ..., the non-logicalconstant ‘⊆’, the logical constants ‘∼’, ‘V ’, ‘∀’, and the auxiliary symbols‘(’ and ‘)’.Let the well-formed formulas and sentences of Lcbe defined in theusual way, and let the meta-language of Lc, MLc, be such that if s is asymbol of Lc,thens is a canonical name of s in MLcand s is a designatedsymbol of MLchaving the same meaning (or function) as s.11.1.1. Recursive Definition of SatisfactionLet g be an assignment function for Lc, i.e., g assigns to each individualvariable xiof Lca class, xi, in the “universe” of classes. Then:(a) If xiand xjare variables of Lc,thenxi⊆ xjis satisfied by g iffxi⊆ xj.(b) If 8 is a sentential function of Lc,then∼8 is satisfied by g iff ∼ [8is satisfied by g].(c) If 8 and 9 are sentential functions of Lc,then8V 9 is satisfied by giff [8 is satisfied by g] V[9 is satisfied by g].TRUTH, LOGICAL STRUCTURE, AND COMPOSITIONALITY 197(d) If 8 is a sentential function and xa variable of Lc,then∀x8 is satis-fied by g iff ∀g0[g0differs from g at most in its assignment to x → 8is satisfied by g0].1.1.2. Definition of Truthσ is a true sentence of Lciff σ is a sentence of Lcand every assignment gfor the variables of Lcsatisfies σ .2. RECURSION AND EXPLANATIONThe recursive method makes two important contributions to the theory oftruth: (A) It solves the technical problem of defining truth for a languagewith infinitely many sentences by finite means (once semantic values areassigned to the atomic elements). (B) It provides a template for an in-formative definition of truth. The informative, or explanatory, power ofthe recursive method was passed over by Tarski, but even a superficialcomparison of his recursive definition of truth for Lcand a non-recursivealternative based on his suggestion in the first citation –The sentence σ of Lcis true iff [[σ =∀x1(x1⊆ x1) and ∀x1(x1⊆ x1)]or[σ =∼∀x1(x1⊆ x1) and ∼∀x1(x1⊆ x1)] or [σ