Polyadic algebra

Polyadic algebras were introduced by Paul Halmos in the 1950s as part of the program of algebraic logic, whose aim was to provide algebraic counterparts of logical systems. Another approach relating first-order logic to algebra is provided by categorical logic and Lawvere's functorial semantics.^{[3] [4]} They were developed as an alternative to cylindric algebras introduced earlier by Alfred Tarski and his collaborators. Polyadic algebras provide an algebraic formalism that reflects the behavior of quantifiers and substitutions in first-order logic. The theory was further developed in the work of Henkin, Monk, and Tarski on algebraic logic.^[5]

A polyadic algebra of dimension ${\displaystyle \alpha }$ is a Boolean algebra equipped with operations corresponding to substitutions of variables and existential quantification indexed by a set of variables of cardinality ${\displaystyle \alpha }$. The substitution operations correspond to transformations of the set of variables, while the quantifier operations correspond to existential quantification over individual variables. More precisely, besides the Boolean operations, a polyadic algebra includes:

• substitution operations corresponding to transformations of variables, and
• quantifier operations corresponding to existential quantification over variables.

These operations satisfy axioms reflecting the algebraic behavior of substitutions and quantifiers in first-order logic.

The axioms of polyadic algebras describe the interaction between Boolean operations, substitutions, and quantifiers. Among the basic principles are the following:

• substitution operations form a representation of transformations of the set of variables;
• substitutions preserve the Boolean structure;
• existential quantifier operations are additive and monotone;
• substitutions and quantifiers interact in a way corresponding to the renaming of bound variables.

These axioms capture the algebraic properties satisfied by logical formulas under substitution of variables and existential quantification. A detailed axiomatization is given in Halmos's monograph .^[4]

Representation theorems show that polyadic algebras can be represented as algebras of sets in which the operations are defined using relations and functions on sequences. Halmos proved representation theorems for both locally finite and infinite-dimensional polyadic algebras.^[4] A further representation theorem due to Daigneault and Monk establishes representation results for general polyadic algebras.^[6] Further developments in the representation theory of polyadic and related algebras are discussed in later literature on algebraic logic.^[7][8] These representation theorems establish a bridge between abstract algebraic structures and the semantics of first-order logic.

A natural class of examples of polyadic algebras arises from logic.

For an infinitary first-order language, the Lindenbaum–Tarski algebra of formulas modulo logical equivalence can be equipped with operations induced by substitution of variables and existential quantification. With these operations it forms a polyadic algebra. Such algebras provide an algebraic representation of the logical structure of formulas. ^[9]

A quasi-polyadic algebra is a variant of a polyadic algebra in which the system of substitution operations is restricted. In polyadic algebras substitutions corresponding to arbitrary transformations of the set of variables are available, while in quasi-polyadic algebras only finitely supported substitutions (typically finite permutations or finite transformations of variables) are included among the primitive operations. In many treatments the term quasi-polyadic algebra refers to quasi-polyadic equality algebras. These algebras were introduced in the development of algebraic logic as structures more closely related to cylindric algebras while retaining some of the substitution mechanisms characteristic of polyadic algebras. Quasi-polyadic algebras form an intermediate class between cylindric algebras and full polyadic algebras, that is they additionally contain distinguished diagonal elements corresponding to equality. These structures play an important role in the algebraic study of first-order logic with equality. As in the case of polyadic algebras, the operations of quasi-polyadic algebras are intended to model logical operations on formulas of first-order logic. The Boolean operations correspond to propositional connectives, cylindrification operations correspond to existential quantification, and the substitution operations represent the replacement of variables.

The theory of quasi-polyadic and related cylindric-like algebras has been developed extensively in the literature on algebraic logic. ^{[10][11][7] [8]} Such algebras provide an algebraic representation of the logical structure of formulas. Representation results show that quasy-polyadic algebras have stronger representation properties than cylindric algebras in .relativized settings ^[12][13] Quasi-polyadic and related cylindric-like algebras continue to play an important role in contemporary research in algebraic logic.

Polyadic algebras are closely related to cylindric algebras. Both structures provide algebraic frameworks for first-order logic. Polyadic algebras are closely related to cylindric algebras and include structures corresponding to cylindric algebras as special cases, but differs in the treatment of substitutions and quantifiers. While cylindric algebras emphasize cylindrification operations corresponding to quantifiers, polyadic algebras incorporate a richer system of substitution operations. The relationships between these algebraic systems form an important part of the theory of algebraic logic.

• Algebraic logic
• Cylindric algebra
• Relation algebra
• Lindenbaum–Tarski algebra