A LOGICAL CALCULUS OF MEANING AND SYNONYMY
YIANNIS N. MOSCHOVAKIS
date: December 13, 2004
Linguistics and Philosophy
source: A logical calculus of meaning and synonymy , Linguistics and Philosophy, v. 29 (2006), pp. 27 -- 89.
Montague: meaning (= Frege: sense) of term A is its Carnap Intension or denotation(A)(a) for each state a (= possible world, time, context of use). Too coarse for synonyms.
Other extreme: "structural" approaches to the modeling of meaning (like Russell's propositions,[n3] Church [1946], Church [1974] and Cresswell [1985]) basically tell us no more than that "the sense of a complex term A can be determined from the syntactic structure of A and the senses or denotations of the basic constituent parts of A", without explaining how this "determination" is to take place.
Judy Pelham and Alasdair Urquhart [1994], Russellian propositions, Logic, Methodology and Philosophy of Science IX (D. Prawitz et al., editors), Elsevier Science.
Alonzo Church [1946], A formulation of the logic of sense and denotation, abstract, The Journal of
Symbolic Logic, vol. 11, p. 31.
Alonzo Church [1974], Outline of a revised formulation of the logic of sense and denotation, part II,
Nous, vol. 8, pp. 135-156.
M. J. Cresswell [1985], Structured meanings: The semantics of propositional attitudes, The MIT
Press, Cambridge, Mass.
- This is bottom-up compositional, does not allow the construction to contribute to meaning. The syntactic structures are empty combinatorial rules, without any meaning beyond what is determined by its constituents (deductively determined, not abductively-probabilistically inferred).
- but if the method constructs an algorithm (semantic contribution) before getting to the denotation (the explicit core of pragmatic interpretation), could that algorithm be construction-dependent rather that language-wide and uniform? Would it be enough to have every sense license a particular construction that triggers that sense for the wordform?
Davidson's eloquent criticism in Davidson [1967],
Theaetetus and the property of flying do not (by themselves) amount to the meaning of "Theaetetus flies"
Donald Davidson [1967], Truth and meaning, Synthese, vol. 17, pp. 304-333, reprinted in Martinich
[1990] and in Davidson [1984].
- the meaning of the verb in use is not the (property of) the action but a situation type involving the participants dependent on the predicative verb; or better, it is both an antecedent situation-type involving the particiapants and a related consequent situation-type where the action is realized with participant-role relationships between the instantiated action-type and each mentioned or implicit participant). This verb-meaning situation type exists in the discourse situation cognitively shared by speaker and hearer, their shared information state.
In Moschovakis [1994] I argued that the meaning of a term A can be faithfully modeled by its referential intension int(A), an (abstract, idealized, not necessarily implementable) algorithm which computes the denotation of A. The basic technical tool in that paper was the Formal language of recursion FLR, [for rendering NL as formal]
Yiannis N. Moschovakis [1994], Sense and denotation as algorithm and value, Logic colloquium '90
[note4] full rendering operation is of the form
natural language expression + context -- render--> formal expression + state
where the (informally understood) context determines not only the state (as we will make it precise in Subsection x2.2), but also which precise reading of the expression is appropriate and what formal transformations should be made (e.g., co-indexing), depending on information about "what the speaker meant", intonation, if the expression was spoken, punctuation and capitalization, if it was written, etc.
- I take this to mean:
NL expr + partly-construed situation --render-->
formal semantic contribution
+ anchoring situation (concrete or discourse) as construed in a verbal scheme (= parameter-resolved psoa + location + context of use (Wittg aspect))
I will not specify with any precision the all-important rendering (or translation) operation... I think that the theory of what-happens-next proposed here may be of some value, primarily because of two reasons.
> First, the modeling of meanings by referential intensions goes far beyond the imagery and analogy with computation often used to explain the relation between Frege's sense and denotation, especially by Dummett.5
M. A. Dummett [1978], Frege's distinction between sense and reference, Truth and other enigmas, Harvard Univ.ersity Press, Cambridge, pp. 116-144.
G. Evans [1982], The varieties of reference, Clarendon Press, Oxford, Edited by J. N. McDowell.
> Second, the formal processing of L^{lambda}_ar-terms (the "calculus" of the title) sets conditions and limitations on the rendering operation, it provides new ways to implement some syntactic transformations which affect meaning (like co-indexing and co-ordination), and for some English phrases, it suggests some plausible, novel renderings directly in L^{lambda}_ar which are not referentially synonymous with any terms of the typed {lambda}-calculus.
x1. The typed {lambda}-calculus with acyclic recursion, L^{lambda}_ar. The language L^{lambda}_ar is a typed calculus of terms, an extension of the two-sorted type theory Ty_2 of Gallin [1975][sec.8]
into which the language of intensional logic LIL of Montague [1973] can be interpreted by Gallin's Theorem 8.2.[note6]
Daniel Gallin [1975], Intensional and higher-order modal logic, North-Holland Mathematical Studies, no. 19, North-Holland, Elsevier, Amsterdam, Oxford, New York.
- Moschovakis builds on the theory of typed functions, typed substitution-evaluable relations. Russell originally made a (ramified) theory of typed sets. What are typed situations? The are set like collections of individuals_s, properties_s on individuals and relations_s on pairs and sequences of individuals, where properties_s, relations_s and situations can also be individuated (reification in a cognitive schema?).
- can we make a typed calculus of terms for rendering natural language sentence in the scheme of a constructicon? A Natural Semantic Rendering Formalism, that is not truth-conditional but considers conditions of information flow and conditions of satisfaction up to a shared semantic contribution of (only) the expression. Instead of just types e~ and t~, we can have entities (individuals) e~, properties and relations r~_i for i=1..n (where n is the number of participants in the largest frame, let us call it less than 7, Miller's number for working memory), situations s, and j~ for information flow values (whether a concrete or discourse situation supports a situation-type or basic infon). Going beyond Russellian propositions, we consider that verbs have many senses, and that constructions also contribute sense-like meanings. We want our representation to support not simply deductive inference but abductive sense extension, so we can infer not only information that is already there in the expression, but can learn about the world and acquire extended schemas for classifying it.
- We would like to build on DRS, but again at the sense level rather than the proposition level. Perhaps we can refer to each signalled sense as a microsign, and we are interested in its semantic contribution to pragmatic construal.
- in SBCG, every verb is taken to have one _rel. If we model at the granularity of senses, one _rel per sense. However, in Sowa's conceptual graphs, a verb is a relational concept that has (labelled) relations with each participant mentioned in the expression. Using FrameNet, but at the level of senses + constructions, we can have a small set of participant-relations that identify how the mentioned individuals relate to the event-situation of the verb, call them _prel. We may want to classify each _prel in a way local to the frame, or using a language-wide or universal collection of generic _prels (agent, accessory, goal, location, instrument, beneficiary). We can have grammatically-compulsory _prels and optional (adjunct) _prels.
the set of types is the smallest set which includes the distinct "symbols" e; t; s
and is closed under the pairing operation ({sigma}-->{sigma}). A type is pure (or state-free) if the state type s does not occur in it.
- Moschovakis only has a single pairing operation to generate his types, perhaps we need several.
- M uses the Curry-Howard isomorphism to handle multiple arguments to a function. We may instead shift to a finer grain level of _prels relation a verb's event-situation and its participants.
- in DRS we resolve referential indexes by equating i=j. But for events, we may need to place them in a partial order of a consistent discourse situation (one channel) and be prepared to shift channels. This is done pragmatically so we can abductively infer the best shared information state for information to flow in a successful communication context. Within this broad contingent pragmatic field, the semantic contribution is more predictable across similar and distinguished situations.
Constants, variables, terms
We assume given a (finite) set K of typed constants, the "vocabulary", and we write c : {sigma} to indicate that c has type {sigma}
For each type {sigma}, L^{lambda}_ar has two infnite sequences of variables,
- the pure variables v^{sigma}_0, v^{sigma}_1, ... and
- the recursion variables or locations p^{sigma}_0, p^{sigma}_1, ...
Syntactically, pure variables are quantified, while locations are assigned-to.
Terms are defined recursively, starting with the variables and the constants and using application, {lambda}-abstraction and (mutual) acyclic recursion. The definition also assigns a type to every term and specifies the free and bound occurrences of variables in it.
- locations are used for referential indexes
"referentially synonymous"
Formally, congruence is the smallest equivalence relation =_c between terms which respects alphabetic replacement of bound
variables (of both kinds), application, {lambda}-abstraction and acyclic recursion, and permuting the indexes of locations (so the system of assignments is a set, not a sequence)
Both the denotational and intensional semantics of L^{lambda}_ar(K) will respect congruence, and so we will sometimes tacitly identify congruent terms.
- we can model the acquisition of new vocabulary in a known wordsense group as associating a new constant with some idiosyncratic meaning to a wordsense group existing in the constructicon. If the new vocabulary item (a new form, or a new sense of an existing form) fits into the pattern and makes sense in terms of semantic analysis and pragmatic construal, it supports abduction to a particular semantic and pragmatic meaning, and the constructicon is (defeasibly) incremented with the new vocabulary item.
{beta}-conversion almost never preserves meaning, just as logical deduction does not--otherwise all theorems would be synonymous, which is absurd
States. To be specific,we will assume in this paper that a state is a quadruple
a = <>
which speciÞes a possible world i , a moment of time j, a point in space k, a speaker (or "agent") A, and a function ä which assigns values to all possible occurrences of proper names and demonstratives, indexed by the order in which they appear in
terms
More interesting for the natural language examples are the state-depended versions of these [logical] operations, [where t evaluates to 1, 0, or er] summarized in Table 3.
We assume the language has a constant [] for the basic ne-
cessity operator, Montague's "full necessity", or "necessarily always", as Thomason calls it.
Kaplan [1978b] argues convincingly that this interpretation is inappropriate for terms which contain demonstratives, but in our determination to avoid philosophical commitments, it is best to allow his interpretation as a de re reading of the modality, without forbidding the de dicto reading.
David Kaplan [1978b], On the logic of demonstratives, Journal of Philosophical Logic, pp. 81-98, reprinted in Salmon and Soames [1988].
The natural definition of the description operator returns an
error if the existence and uniqueness conditions are not fulfilled
Local, modal
An object is local[n16] if each value p(x; a) depends only on x(a) and not on any other values x(b).
[16] See Montague [1973][Section 4]. Montague and Gallin use extensional and intensional for our local and modal, but this adds one more use to the already overloaded extension-intension distinction and suggests a connection between modality and meaning which is not in the spirit of this article.
What seems (at first) surprising is that some common nouns and verbs are also modal, in this abstract sense, and that the
distinction is worth noting.
e.g. the temperature is rising
then rises cannot be reasonably interpreted by a local object: because we cannot tell whether the temperature is rising in state a from the mere knowledge of its value in state a.
For another example, consider the sentence
the color of the sky ranged from light pink to deep, brooding red;
the verb "ranges" is modal in this usage since to determine whether ranges(color; a) we must evaluate color(b) for various states b which differ in "observed location" from the current state a--assuming, for the example, that "observed location" is
part of the state.
Roughly speaking, co-indexing occurs when the references of one or more indexical expressions in a term are identified with that of a subterm by the introduction of a bound variable which refers to all of them.
Co-indexing is part of the rendering operation, since whether and how it should be done is determined by the informal context
One of the most original innovations in Montague [1973] is the interpretation of "John", "I" and "the blond" by quantifiers, of type ~q = (~e -> ~t) -> ~t (in the present system). I will not adopt it,
however, because the Montague renderings produce the wrong logical form for the syntactical expressions that they purport to formalize, and thus lose the intended meaning.
The evening star is the morning star (should be synonymous to) The morning star is the evening star
It is not hard to formulate rules for rendering which avoid unnecessary type-raising and give plausible results for (at least) simple expressions which involve singular terms or quantifiers (or both). The basic technique is known as type-driven rendering (or translation), cf. Klein and Sag [1985] or the more recent textbook Heim and Kratzer [1998][Chapter 3], where it is applied using phrase structure trees to represent meanings.
Ewan Klein and Ivan A. Sag [1985], Type-driven translation, Linguistics and Philosophy, vol. 8, pp. 163-201.
Irene Heim and Angelika Kratzer [1998], Semantics in generative grammar, Blackwell.
For our purposes here, the main lesson is that meaning (intuitively understood) must be seriously considered in the rendering process--simply "getting the right denotation" is not enough; and that the subsequent, formal computation of referential intensions and synonymies provides some clues as to whether the informal meaning
was captured by the proposed rendering.
We call cf(A) the canonical form of A and we write
A =>_cf B () <=> cf(A) ==_c B:
The terms A0,A1,...,An are the parts of A, and A0 is its head. It will be convenient to employ the notational convention
A where { } == A
introduced in (4), which allows us to assume that all canonical forms look like
recursive termsÑperhaps with an empty body:
10 reduction rules
We claim that it preserves meaning, so it had better preserve at least denotations: Thm 3.11
Proof is simple, by induction on the definition of the reduction relation.
Main Conjecture. If the set of constants K is finite, then the relation of referential synonymy between closed terms of L^{lambda}_ar(K) is decidable.
Still open.
For a satisfactory development of a theory of belief in which the belief carriers are utterances, we would also need to establish the decidability of synonymy between the parts of utterances in which the parameter a occurs. see:
Eleni Kalyvianaki and Yiannis N. Moschovakis [], Two aspects of local meaning, in preparation.
This is because, intuitively: if you mention an individual concept,
then that (full) concept is part of the meaning of your utterance.34 In the two puzzles above, Los Angeles, LA, He and Scott are all parts of the relevant terms, but Los Angeles = LA, which dooms poor Petros, while He 6= Scott, which saves the King.
We have already discussed in x4.2 the technical fact behind this claim: the state parameter a occurs only in the head of the canonical form of an utterance A(a) and not in its body.
5. English as a programming language.
(50) program P |--> algorithm(P) |--> den(P):
It is not hard to work out the mathematical theory of a suitably abstract notion of algorithm which makes this work; and once this is done, then it is hard to miss the similarity of (50) with the basic Fregean scheme for the interpretation of a natural language,
(51) term A |--> meaning(A) |--> den(A):
Aside from the relation between algorithms and meanings, programming languages resemble natural languages more than they resemble the classical, formal languages of logic, both in their complexity and also because they exhibit some natural language phenomena which are absent from formal languages.
I will also not try to explain my take on basic philosophical questions like what it means to "define", "represent faithfully" or "explicate" meaning (or any other notion) in set-theoretic terms; I tried my best to be as clear on these issues as I can in Moschovakis [1998]
Yiannis N. Moschovakis [1998], On founding the theory of algorithms, Truth in mathematics (H. G. Dales and G. Oliveri, editors), Clarendon Press, Oxford, pp. 71-104.
Denotational semantics for programming languages.
Scott's theory is peculiarly incomplete in that it makes no room for the notion of algorithm which (one would think) is at the heart of the matter. Consider, for example, the problem of "sorting" (putting in alphabetical order) a long list of words u. There are many algorithms which will do this--the bubble sort, the merge sort, the quick sort etc.-- and they differ greatly in many ways, for example their efficiency. They can all be "programmed" (expressed) in every sufficently rich programming language L, but the denotational semantics of L cannot distinguish between them, as they all have the same denotation, the function which assigns to each u its alphabetized rearrangement.
And so it seemed to me that Scott semantics should be refined by the introduction of algorithms as the primary semantics values of programs, which then determine their denotations, i.e., by adopting the basic interpretation scheme (50).
5.2. What is an algorithm?
recursive equations, e.g. for Euclidean Algo for gcd
gcd(x; y) = p(x; y) where fp := {lambda}(x){lambda}(y)C(q1(x; y); y; r(x; y));
q1 := {lambda}(x){lambda}(y)rem(x; y);
r := {lambda}(x){lambda}(y)p(y; q2(x; y));
q2 := {lambda}(x){lambda}(y)rem(x; y)g
where the conditional construct
C(u; s; t) = if (u = 0) then s else t
Notice that these algorithms are always relative to the givens, and so they do not determine "absolutely computable" functions unless the givens are absolutely computable.
intended interpretation of L^{lambda}_ar(K) in x1.4 includes higher-type givens,
and the simpler, acyclic recursors sufficed.
---------------
Alonzo Church [1951a], A formulation of the logic of sense and denotation, Structure, method and meaning (P. Henle, H. M. Kallen, and S. K. Langer, editors), Liberal Arts Press, New York, pp. 3-24.
Alonzo Church [1951b], The need for abstract entities, American Academy of Arts and Sciences Proceedings, vol. 80, pp. 100-113, reprinted in Martinich [1990] under the title Intensional Semantics.
Alonzo Church [1962], A remark conerning QuineÕs paradox about modality, Spanish version in Analisis Filos«oÞco, pp. 25-32, reprinted in English in Salmon and Soames [1988].
Alonzo Church [1973], Outline of a revised formulation of the logic of sense and denotation, part I, Nous, vol. 7, pp. 24-33.
Donald Davidson [1984], Truth and interpretation, Clarendon Press, Oxford.
G. Frege [1952], Translations from the philosophical writings of Gottlob Frege, Blackwell, Oxford,
edited by P. Geach and M. Black.
Gottlob Frege [1892], On sense and denotation, Zeitschrift f ¬ur Philosophie und Philosophische Kri-
tik, vol. 100, Translated by Max Black Frege [1952] and also by Herbert Feigl Martinich [1990]. I have
used ÒdenotationÓ to render Frege's ÒBedeutung,Ó instead of BlackÕs ÒmeaningÓ or FeiglÕs ÒnominatumÓ.
David Kaplan [1978a], Dthat, Syntax and semantics (Peter Cole, editor), vol. 9, Academic Press, New York, reprinted in Martinich [1990].
Saul A. Kripke [1979], A puzzle about belief, Meaning and use (A. Margalit, editor), Reidel, pp. 239-283, reprinted in Salmon and Soames [1988].
Leonard Linsky (editor) [1971], Reference and modality, Oxford University Press.
A. P. Martinich (editor) [1990], The philosophy of language, second ed., Oxford University Press, New York, Oxford.
R. Montague [1970a], English as a formal language, Linguaggi nella Societ `a e nella Tecnica (Milan) (Bruno Visentini et al., editors), Edizioni di Comunit`a, pp. 189-284, reprinted in Montague [1974].
R. Montague [1970b], Pragmatics and intensional logic, Synth`ese, vol. 22, pp. 68-94, reprinted in Montague [1974].
R. Montague [1970c], Universal grammar, Theoria, vol. 36, pp. 373-398, reprinted in Montague [1974].
R. Montague [1973], The Proper Treatment of Quantification in Ordinary English, Approaches to Natural Language: Proceedings of the 1970 Stanford Workshop on Grammar and Semantics (J. Hintikka et al., editors), D. Reidel Publishing Co, Dordrecht, pp. 221-224, reprinted in Montague [1974].
R. Montague [1974], Formal philosophy, Yale University Press, New Haven and London, Selected papers of Richard Montague, edited by Richmond H. Thomason.
Yiannis N. Moschovakis [1994], Sense and denotation as algorithm and value, Logic colloquium '90 (J. V¬a¬an¬anen and J. Oikkonen, editors), vol. 2, Association for Symbolic Logic, Lecture Notes in Logic, pp. 210-249.
Jamal Ouhalla [1994], Introducing transformational grammar, Arnold and Oxford University Press.
G. Plotkin [1977], LCF considered as a programming language, Theoretical Computer Science, vol. 5, pp. 223-255.
Nathan Salmon and Scott Soames [1988], Propositions and attitudes, Oxford University Press.
D. S. Scott and C. Strachey [1971], Towards a mathematical semantics for computer languages, Proceedings of the symposium on computers and automata (New York) (J. Fox, editor), Polytechnic Institute of Brooklyn Press, pp. 19-46.
J. van Heijenoort [1985], Frege on sense identity, Selected essays, Bibliopolis, Napoli, pp. 65-70.
