Adequacy theorem

From Encyclopedia of Mathematics
Jump to: navigation, search

for senses

A theorem from the theories of sense and synonymy. This theory provides a solution for the treatment of hyperintensional predications.

The statement of the theorem is as follows. Assume that:

i) $ \Delta $ and $ \Phi $ are well-formed expressions of an interpreted theory $ ( {\mathcal T},D, {\mathcal I} ) $, where $ {\mathcal T} $ is a theory based on the modal calculus (cf. modal logic) $ { \mathop{\rm MC} } ^ \nu $ and $ {\mathcal I} $ is a model for the definition system $ D $;

ii) $ I $ is a valuation of the constants, $ V $ and $ W $ are $ {\mathcal I} $- valuations of the variables, and the set-theoretical unions $ I \cup V $ and $ I \cup W $ are injective functions on the elementary expressions (i.e., the primitive constants and free variables) of $ \Delta $ and $ \Phi $, respectively. Then $ \Delta $ has (with respect to $ I $ and $ V $) the same sense as $ \Phi $( with respect to $ I $ and $ W $) if and only if $ \Phi $( respectively, $ \Delta $) can be obtained from $ \Delta $( respectively, $ \Phi $) by replacing the elementary expressions (i.e., the primitive constants and free variables) occurring in $ \Delta $( respectively, $ \Phi $) with those of $ \Phi $( respectively, $ \Delta $) suitably rearranged.

Hyperintensional predication.

By hyperintensional predication one understands a predication which can assume different truth values on terms having equal intensions but different senses. This happens, for instance, when propositional attitudes are involved: if one assumes that mathematical equality implies equi-intensionality, then "3" has the same intension as "log28" , even if the assertions "Peter knows that 3= 3" and "Peters knows that 3=log28" may have different truth values. The treatment of hyperintensional predications has important applications, for example in artificial intelligence. Various approaches for constructing a general and systematic theory of propositional attitudes were proposed, starting with work by A. Church [a8] and R. Carnap [a6], [a7]. Those based on Church's view use extensional languages (see [a10], [a12]); others use categorial or quotational languages (see [a11], [a9]; in the latter the literature and the situation with respect to the solution of the problem are surveyed). The approach to sense presented in [a3], [a5] is based on a very different point of view, in which uniformity and generality features are taken into account. This approach deals explicitly with Church's $ \lambda $- operator, the $ \iota $- operator for descriptions, general operator forms and synonymy, and propositional attitudes of transfinite order. It is modal, but not in an essential way.

Senses and synonymy.

The formulation of the adequacy theorem for the senses (or quasi-senses) considered here refers to an approach to sense presented in [a3]. Senses are closely connected with the notion of synonymy. This notion has been studied in itself, independently of its relation to senses, in connection with an extensional and a modal language (see, e.g., [a13], [a14]).

In order to obtain a unified theory for the various synonymy notions, C. Bonotto and A. Bressan [a3] have introduced a general rigorous definition of synonymy as a binary relation between well-formed expressions of a theory $ {\mathcal T} $ endowed with a definition system $ D $. $ {\mathcal T} $ is a theory based on the modal calculus $ { \mathop{\rm MC} } ^ \nu $( see [a4]). In [a3], four particular synonymy notions, $ \approx _ {0} $, $ \approx _ {1} $, $ \approx _ {2} $, and $ \approx _ {3} $, were first introduced by conditions only on the forms of well-formed expressions among which they hold. Among them, $ \approx _ {0} $ and $ \approx _ {1} $ are defined, first, only for empty $ D $, because the principles of $ \lambda $- conversion are not meaning-preserving in connection with them. Therefore, they may appear too weak (not extended enough) or too rich in content. On the other hand, $ \approx _ {0} $ also has a basic role in treating quasi-senses connected with any other synonymy notion. Moreover, the definitions of $ \approx _ {0} $ and $ \approx _ {1} $ can be extended to a certain theory $ {\mathcal T} ^ {*} $ endowed with the definition system $ D $ of $ {\mathcal T} $, provided that $ D $ is of a suitable kind. Finally, in [a3] a general rigorous definition of synonymy is introduced. For any synonymy notion $ \approx $ one has $ \approx _ {0} \subseteq \approx $.

A formal theory of senses.

Let $ ( {\mathcal T},D,I ) $ be an interpreted theory based on the modal calculus $ { \mathop{\rm MC} } ^ \nu $ introduced in [a4], where $ D $ is a definition system and $ I $ is an interpretation, i.e. a model (in logic) for $ D $. In the semantics adopted by [a3], every expression of a theory $ {\mathcal T} $ has both an intension and a sense, depending on the notion of synonymy chosen.

The basic idea for the construction of senses is a generalization of the idea of intensional isomorphism according to [a6]. Senses of complex expressions are suitable equivalence classes, modulo the chosen synonymy, of sequences constructed starting with intensions. These sequences correspond to the weakest synonymy notion, $ \approx _ {0} $. Senses of expressions are determined in an essentially unique way and depend on the formal aspect of the expression and on valuation of the constants and variables occurring in it. Therefore, for every choice of synonymy notion the sense must fullfill certain natural adequacy requirements. The first of these is:

a) the senses assigned to any two closed well-formed expressions $ \Delta $ and $ \Phi $ of an interpreted theory $ ( {\mathcal T},D,I ) $ coincide if and only if $ \Delta $ and $ \Phi $ are synonymous. Since open well-formed expressions are also used, e.g., within propositional attitudes, they, too, must have a sense. The requirement a) has been strengthened into one which involves a certain extension of the synonymy relation considered to $ v $- valued well-formed expressions, which are couples $ \langle {\Delta,V } \rangle $, where $ \Delta $ is a well-formed expression and $ V $ is a $ v $- valuation, i.e., an assignment of intensions to variables.

The adequacy theorem, basic to the sequel, has a uniqueness character, in that it substantially asserts that if both $ \langle {\Delta,V } \rangle $ and $ \langle {\Phi,W } \rangle $ are related to the same sense $ \sigma $, then a simple procedure transforms them into one another. This allows one to associate $ \sigma $ with a unique determination of $ \langle {\Delta,V } \rangle $ by a suitable convention. In [a3] a version of the adequacy theorem is proved when the well-formed expressions $ \Delta $ and $ \Phi $ are constant free. This proof holds only when the language is effectively modal, because the following assumption is used:

b) the class $ \Gamma $ of possible worlds is infinite.

Subsequently, in [a1] a version of the adequacy theorem has been presented which is applicable to every case, including the extensional case, since b) is not used.

The sense language $ { \mathop{\rm SL} } _ \alpha ^ \nu $.

On the basis of [a3], the modal language $ { \mathop{\rm ML} } ^ \nu $ has been extended in [a5] to the sense language $ { \mathop{\rm SL} } _ \alpha ^ \nu $( where $ \alpha $ may be a transfinite ordinal, cf. also Ordinal number; Transfinite number), which contains well-formed expressions of every (iteration) order $ \beta < \alpha $. Thus, $ { \mathop{\rm SL} } _ \alpha ^ \nu $ is capable of dealing with propositional attitudes whose iteration orders may be transfinite.

Any semantics for $ { \mathop{\rm SL} } _ \alpha ^ \nu $ must, on the basis of [a3], involve sense, hence it must be based on a synonymy relation. Every well-formed expression $ \Delta $ of order $ \beta $ has a hyper-quasi-intension (hyper-quasi-extension) of order less than or equal to $ \beta $ which represents its hyperintension (hyperextension). In addition, $ \Delta $ has as quasi-sense of order less than or equal to $ \beta $ which represents its sense.

Intuitively, every hyper-quasi-intension is a function from $ \Gamma $( the class of possible worlds) into a set of hyper-quasi-extensions. Hyper-quasi-extensions are constructed in the usual type-theoretical way except that, if a hyper-quasi-extension is a function, its domain is formed with hyper-quasi-intensions and quasi-senses. A relevant feature of this construction is that the quasi-senses must have an order (see below) lower than that of the function involved. The entities assignable to variables and constants of order $ \beta $ are hyper-quasi-intensions or quasi-senses of order less than $ \beta $. The $ v $- valuations (respectively, $ c $- valuations) assigning a hyper-quasi-intension to every variable (constant) will be called ostensive $ v $- valuations (respectively, ostensive $ c $- valuations).

Since expressions may contain both constants and variables, quasi-senses are relative to a valuation of the constants and variables. Roughly speaking, the senses of constants and variables are their valuations, whereas the quasi-sense of a compound expression $ \Delta $ is a sequence $ \langle {\chi,x _ {1} \dots x _ {n} } \rangle $, where $ \chi $ is a marker depending on the form of $ \Delta $ and $ x _ {1} \dots x _ {n} $ are senses (of the components of $ \Delta $) or functions (depending on the senses of the components of $ \Delta $).

Adequacy theorem for $ { \mathop{\rm SL} } _ \alpha ^ \nu $.

In [a2], a theory $ {\mathcal T} $ based on $ { \mathop{\rm SL} } _ \alpha ^ \nu $ and a definition system $ D $ is presented. Strong (weak) extensions of $ {\mathcal T} $ are defined in connection with a semantics for which the senses of well-formed expressions are (are not) preserved by the principles of $ \lambda $- conversion. In [a2] the designation rules for the senses, given in [a5] only for weak theories, have been given in a complete form for strong theories as well. In fact, by means of a suitable notion, every defined constant has a sense, and the synonymy relations, introduced in [a3] for theories based on $ { \mathop{\rm MC} } ^ \nu $, have been extended to strong and weak extensions of theories based on $ { \mathop{\rm SL} } _ \alpha ^ \nu $. In [a2] a strong version of the adequacy theorem is shown to hold, which is a new result also for $ { \mathop{\rm ML} } ^ \nu $, which is substantially $ { \mathop{\rm SL} } _ {1} ^ \nu $. The last version of the adequacy theorem does not involve the assumptions that $ I \cup V $ and $ I \cup W $ are injective functions and that no primitive constant or defined constants occur in $ \Delta $ and $ \Phi $. $ I $ is required to be an ostensive valuation of the constants, $ V $ and $ W $ are ostensive $ I $- valuations of the variables.

Orders of hyperintensional predications in $ { \mathop{\rm SL} } _ \alpha ^ \nu $.

The basic notion of order is crucial in the sense language $ { \mathop{\rm SL} } _ \alpha ^ \nu $ presented in [a5]. It arises from the observation that, when propositional attitudes are involved, one faces a proposition containing subordinate clauses. In other words, the logical analysis of the proposition considered cannot ignore the recognition that there subsists a hierarchy among the components of the proposition itself. Orders are just the mathematical counterparts of this hierarchy: every expression of $ { \mathop{\rm SL} } _ \alpha ^ \nu $( as well as its interpretation) has an order, so that the hierarchy can be established by comparing the orders of the components of the formula. In this way, it is natural to translate the propositions considered above into two formulas like, e.g., $ K ( P,3 = 3 ) $ and $ K ( P,3 = { \mathop{\rm log} } _ {2} 8 ) $, where $ P $ denotes Peter, $ K $ is a binary relation representing knowledge and the order of $ K $ is greater than those of "3= 3" and "3=log28" .

The example considered above shows that operators like "knows that" seem to be sensitive to something more than the extension (or the intension) of the known assertion. According to the role of the orders pointed out above for the semantics of $ { \mathop{\rm SL} } _ \alpha ^ \nu $, the truth value of $ F ( \Delta ) $, for $ F $ a predicate term, in general depends on the sense of $ \Delta $, when the interpretation of $ F $ has order greater than that of $ \Delta $. Thus, the fact that the assertions considered above may have different truth values can be explained by accepting the translations $ K ( P,3 = 3 ) $ and $ K ( P,3 = { \mathop{\rm log} } _ {2} 8 ) $, with the order of $ K $ greater than those of "3= 3" and "3=log28" , and by holding that "3= 3" and "3=log28" have different senses.

This example shows that substitution of identicals fails to be valid in the semantics for $ { \mathop{\rm SL} } _ \alpha ^ \nu $. It is replaced with the substitutivity of synonymous expressions, which are expressions having the same sense. Synonymy can be expressed in the language and hence this also holds for the principle of substitutivity of synonymous expressions. Roughly speaking, the synonymy of two expressions $ \Delta $ and $ \Delta ^ \prime $, of order $ h $, is expressed by asserting that no predicate of order $ h + 1 $ can distinguish $ \Delta $ and $ \Delta ^ \prime $. This means, in particular, that the mutual substitutivity of two expressions of order $ h $ corresponds to an axiom of order $ h + 1 $.


[a1] C. Bonotto, "An adequacy theorem for the quasi-senses used in certain theories which are extensional, modal, or strongly intensional" Atti Ist. Veneto di Sci., Lettere ed Arti , CXLVII (1988–89) pp. 31–39
[a2] C. Bonotto, "A generalization of the adequacy theorem for the quasi-senses" Notre Dame J. Formal Logic , 31 (1990) pp. 560–575
[a3] C. Bonotto, A. Bressan, "On generalized synonymy notions and corresponding quasi-senses" Mem. Atti Accad. Naz. Lincei (VIII), Sect. I , 17 (1984) pp. 163–209
[a4] A. Bressan, "A general interpreted modal calculus" , Yale Univ. Press (1972)
[a5] A. Bressan, "On the interpreted sense calculus $SC_\alpha^{\nu}$" G. Dorn (ed.) P. Weingartner (ed.) , Foundations of Logic and Linguistic , Plenum (1985) pp. 427–463
[a6] R. Carnap, "Meaning and necessity" , Chicago Univ. Press (1947)
[a7] R. Carnap, "Meaning and synonymy in natural languages" Philosophical Studies , 6 (1955) pp. 33–47
[a8] A. Church, "A formulation of the logic of sense and denotation" , Structure, Method, and Meaning. Essays in honor of H. Sheffer , Liberal Art Press (1951)
[a9] M.J. Cresswell, "Structured meanings" , MIT (1985)
[a10] D. Kaplan, "How to Russell a Frege–Church" J. Philosophy , 72 (1975) pp. 716–729
[a11] D.K. Lewis, "General semantics" Synthese , 22 (1972) pp. 18–67
[a12] T. Parsons, "Intensional logic in extensional language" J. Symb. Logic , 47 (1982) pp. 289–328
[a13] C. Bonotto, "Synonymy for Bressan's modal calculus $MC^\nu$. Part I: A synonymy relation for $MC^\nu$" Atti Ist. Veneto di Sci., Lettere ed Arti , CXL (1982) pp. 11–24
[a14] C. Bonotto, "Synonymy for Bressan's modal calculus $MC^\nu$. Part II: A sufficient criterium" Atti Ist. Veneto di Sci., Lettere ed Arti , CXL (1982) pp. 85–99
How to Cite This Entry:
Adequacy theorem. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by C. Bonotto (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article