Calculus

A part of the name of some branches of mathematics dealing with rules for the computation of and operation with objects of a definite type; e.g. differential calculus, variational calculus.

A deductive system, i.e. a method of specifying sets by way of indicating the initial elements (the axioms of the calculus) and the derivation rules (cf. Derivation rule), each of which describes how to construct new elements from the initial ones and the ones already constructed. A derivation in a calculus $\Xi$ is a totally ordered set such that every element $P$ in it is either an axiom of $\Xi$ or the conclusion of applying certain derivation rules in $\Xi$, where the premises of this application precede $P$ in the derivation. An element is called derivable in $\Xi$ if there is a derivation in $\Xi$ ending at it. Sometimes derivations are written as non-linear structures (cf. Derivation tree), which makes their study easier. Derivations may also be endowed with an analysis, i.e. additional information that makes the verification of the truth of the derivation easier (e.g., for each element in the derivation one writes down the codes of the rule and the preceding elements from which the given element is obtained).

Example. Consider the calculus $\Xi$ specified by the set $M$ of descriptions in the one-letter alphabet $\{|\}$ of all numbers of the form $2^n$ for $n=1,2,\dots$. The calculus $\Xi$ has one axiom, $\|$, and one derivation rule, "from a word P one can obtain PP". It is easy to convince oneself that the words in $M$, and only these, are derivable in $\Xi$.

Auxiliary elements may sometimes arise in a calculus; in these cases one specifies some algorithm by which one can distinguish between the basic and auxiliary elements. If there are no auxiliary elements, one has a strict interpretation of a set $M$ in a calculus $\Xi$. Such is, e.g., the previous example.

Other, more complicated, forms of specifying sets by calculi are used when instead of the elements of a set their codes are generated (i.e. one needs an auxiliary algorithm for decoding the basic elements). Thus, the coding of non-linear objects by words, the coding of words and $n$ digit numbers by natural numbers, etc., is extensively used. An important special case of a non-strict interpretation is a stepwise-constructed calculus. In it the derivable objects of the previous step have an auxiliary character in the formation of the next step (such constructions are especially characteristic for logico-mathematical theories, which are upper steps over the series of calculi that give the language of the theory).

The concept of a calculus is a formalization of the intuitive idea of an inductively-generated set. Such sets are extensively used in mathematics; in particular, the formalization of any extended theory leans on a large number of inductively-defined sets, starting with the simplest (the set of variables, terms, formulas, etc.) and ending with the set of theorems that can be derived from the axioms of the theory by corresponding logical transitions. It is not surprising then that calculi are one of the basic means in mathematical logic. The logical calculi (cf. Logical calculus) were the first examples of completely-formalized deductive systems (on the basis of these calculi one develops the basic notions and methods of the general theory of calculi and finds far-reaching generalizations of calculi; see, e.g., Carnap rule). Some special kinds of calculi are well-suited for the description of formal grammars (cf. Grammar, formal; this determines the role of calculi in mathematical linguistics) and for the specification of sets recognizable by finite automata (cf. Automaton, finite).

One of the fundamental areas of application of the general theory of calculi is the theory of algorithms (cf. Algorithms, theory of). This is clear from the fact that the notion of a calculus is as fundamental as that of an algorithm. In fact, the class of sets that can be specified by means of calculi coincides with the class of algorithmically-enumerable sets of words (if one remains within the framework of the generally accepted notion of a calculus, and does not consider generalizations violating the potential possibility of generating any derivable element). Hence follows the existence of a calculus for which the derivability problem is unsolvable, i.e. for which there is no algorithm that would end its processing with a definite answer (i.e., that would give $0$ on all derivable words and 1 otherwise) for all words (in the language of the calculus). The possibility of specifying arbitrarily complex enumerable sets implies the existence of calculi that are universal in some sense or another (i.e. calculi modelling all other calculi with a fixed language, see Creative set). These facts, in combination with the study of different modifications and specializations of the general notion of a calculus, open the possibility of obtaining interesting algorithmically-unsolvable problems. The work of E.L. Post, [1], was of fundamental importance in this direction. In it, the concept of a deductive system, suitable for generating arbitrary enumerable sets of words, was given for the first time (cf. Post canonical system). The wide possibilities in formulating the derivation rules in canonical calculi aid in the process of inductive generation of sets; the large majority of constructed concrete calculi can easily and naturally be formulated as particular cases of canonical calculi.

Associative calculi, also called Thue systems, are a convenient tool for specifying and studying groups and semi-groups (cf. Associative calculus).

References

[1]	E.L. Post, "Formal reductions of the general combinatorial decision problem" Amer. J. Math. , 65 (1943) pp. 197–215
[2]	A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))
[3a]	Trudy. Mat. Inst. Steklov. , 72 (1964) pp. 5–56
[3b]	Trudy. Mat. Inst. Steklov. , 93 (1967) pp. 3–42

Comments

Some specific calculi in the sense of a deductive system discussed elsewhere in this Encyclopaedia are the predicate calculus, the propositional calculus and the $\lambda$-calculus.

Besides the systems of computation (better, manipulating formulas) embodied in the differential calculus and variational calculus (or calculus of variations), which were already mentioned, there are e.g. the integral calculus and the Itô-calculus, which is a differential and integral calculus for stochastic differentials and integrals (cf. Stochastic differential; Stochastic integral, and Stochastic differential equation). There is also the Malliavin calculus, a stochastic calculus of variations. Further there is a calculus of fractional integrals, sometimes known as fractional calculus, based on the Riemann–Liouville integral, cf. Fractional integration and differentiation. The phrase fractional calculus is also used to describe a certain body of theory dealing with constructing categories of fractions in category theory, cf. Localization in categories.