nLab compositionality




Ordo et connexio idearum idem est ac ordo et connexio rerum.1

The principle of compositionality asserts that the nature of complex structures is entirely determined by that of their simpler parts and the way these are composed.

In the context of the semantics of languages, this is sometimes called Frege’s principle after Gottlob Frege, although it was arguably assumed in Boole 1854, decades before Frege’s work, and possibly not even embraced by Frege (see Pelletier 01).

Taking up Alfred Tarski's work on the theory of truth in object languages with respect to metalanguages (Tarski 35), the concept became popular in linguistics with the formalization of semantics of formal and informal languages via Montague semantics (Montague 70a, Montague 70b, Montague 73), where the principle asserts that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them.

In computation

From Compositionality 16:

The compositional description of complex objects is a fundamental feature of the logical structure of computation. The use of logical languages in database theory and in algorithmic and finite model theory provides a basic level of compositionality, but establishing systematic relationships between compositional descriptions and complexity remains elusive. Compositional models of probabilistic systems and languages have been developed, but inferring probabilistic properties of systems in a compositional fashion is an important challenge. In quantum computation, the phenomenon of entanglement poses a challenge at a fundamental level to the scope of compositional descriptions. At the same time, compositionally has been proposed as a fundamental principle for the development of physical theories.

In linguistics:



The principle is regarded as originating, at least implicitly, in

The common attribution to Gottlob Frege has been called into question:

  • Francis Jeffry Pelletier, Did Frege Believe Frege’s Principle?, Journal of Logic, Language and Information, 10, 87–114 (2001) (doi:10.1023/A:1026594023292)

The principle was promoted in linguistics via Montague semantics:

Montague relied on

  • Alfred Tarski, 1935, The Concept of Truth in Formalized Languages, in Logic, Semantics, Metamathematics, Indianapolis: Hackett 1983, 2nd edition, 152–278.

A concise and formal discussion of this tradition is

  • Theo Janssen, Compositionality , ch.7 of van Benthem/ter Meulen (eds.), Handbook of Logic and Language , North-Holland Amsterdam 1997.

A somewhat critical reassessment of the concept from a mathematical POV is the monograph

  • Marcus Kracht, Interpreted Languages and Compositionality , Springer Heidelberg 2011.

See also


  • Compositionality, workshop hosted at UC Berkeley in 2016.

  • Compositionality is also the name of a journal whose aim is to publish papers about compositional phenomena, construed broadly.

  1. Baruch de Spinoza, Ethices Pars Secunda, propositio VII: “The order and connection of the thought is identical to with the order and connection of the things.” (buboquote)

Last revised on October 11, 2020 at 13:26:02. See the history of this page for a list of all contributions to it.