A polyadic algebra is a quadruple $(B,V,\exists,S)$ , where $(B,V,\exists)$ is a quantifier algebra, and $S$ is a function from the set of functions on $V$ to the set of endomorphisms on the Boolean algebra $B$ , in other words $$S:V^V\to \operatorname{End}(B)$$ such that

1. $S(1_V)=1_B$ ,
2. $S(f\circ g)=S(f)\circ S(g)$ ,
3. $S(f)\circ \exists(I)=S(g)\circ \exists(I)$ if $f(V-I)=g(V-I)$ ,
4. $\exists(I)\circ S(f) = S(f)\circ \exists(f^{-1}(I))$ if $f$ is one-to-one when restricted to $f^{-1}(I)$ .

Explanation of notations: $1_V,1_B$ are identity functions on $V,B$ respectively; $f,g$ are functions on $V$ , and $I$ is a subset of $V$ . The circle $\circ$ represents functional compositions.

The degree and local finiteness of a polyadic algebra are defined as the degree and local finiteness of the underlying quantifier algebra.

Heuristically, the function $S$ can be thought of as changes to propositional functions due to a ``substitution'' of variables (elements of $V$ ). Let us see some examples. Let $V=\lbrace x_0,x_1,\ldots \rbrace$ be a countably indexed set of variables. For any propositional function $\varphi$ , define $S(f)(\varphi)$ to be the propositional function $\varphi_1$ obtained by replacing each variable $x$ that occurs in it by $f(x)$ . Below are two examples illustrating how $S(f)$ changes propositional functions:

• Let $f:V \to V$ be the function given by $f(x_0)=f(x_1)=x_0$ and $f(x_i)=x_{i+1}$ for all $i>1$ . If $\varphi$ is the propositional function $x_0^2-x_1+x_2/x_3$ , then $S(f)(\varphi)$ is the propositional function $x_0^2-x_0+x_3/x_4$ .
• Let $f:V\to V$ be the function given by $f(x_0)=x_2$ , and $f(x_i)=x_i$ for all $i\ne 0$ . Then the propositional function ``$\exists x_0,x_1,x_2 (x_0\ne x_1 \wedge x_1\ne x_2 \wedge x_2\ne x_0)$ '' becomes ``$\exists x_2,x_1,x_2 (x_2\ne x_1 \wedge x_1\ne x_2 \wedge x_2\ne x_2)$ '' under $S(f)$ .

1. if there are no substitutions of variables, then there should be no corresponding changes to the propositional functions
2. applying substitutions $f\circ g$ of varaibles in a propositional function $\varphi$ should have the same effect as applying substitutions $g$ of variables in $\varphi$ , followed by substitutions $f$ of variables in $S(g)(\varphi)$
3. a substitution $f$ of variables should have no effect to a propositional function beginning with $\exists$ if every variable bound by $\exists$ is fixed by $f$ . For example, if we replace $f$ in the second example above by $f(x_3)=x_2$ and $f(x_i)=x_i$ otherwise, then $$``\exists x_0,x_1,x_2 (x_0\ne x_1 \wedge x_1\ne x_2 \wedge x_2\ne x_0)"$$ is unchanged by $S(f)$ , since $x_0,x_1,x_2$ are all fixed by $f$ .
4. Let $\varphi=\exists I \psi(I,J)$ be a propositional function, where $I,J$ are sets of variables with $I$ bound by $\exists$ and $J$ free. If no two variables $I$ get mapped to the same variable, and no free variable (in $J$ ) becomes bound (in $f(I)$ ) under the substitution, then $\exists I \psi(f(I),f(J))$ and $\exists f(I) \psi(f(I),f(J))$ are semantically the same, which is exactly the statement in the condition.

Remarks.

• Paul Halmos first introduced the notion of polyadic algebras. In his Algebraic Logic, a compilation of articles on the subject, he called a function on the set $V$ of variables a transformation, and the triple $(B,V,S)$ satisfying the first two conditions above a transformation algebra. Therefore, a polyadic algebra is a quadruple $(B,V,\exists,S)$ where $(B,V,\exists)$ is a quantifier algebra and $(B,V,S)$ is a transformation algebra, such that conditions 3 and 4 above are satisfied.
• The notion of polyadic algebras generalizes the notion of monadic algebras. Indeed, a monadic algebra is a polyadic algebra where $V$ is a singleton.
• Just as a Lindenbaum-Tarski algebra is the algebraic counterpart of a classical propositional logic, a polyadic algebra is the algebraic counterpart of a classical first order logic without equality. A variant of the polyadic algebra is what is known as a cylindric algebra, which algebratizes a classical first order logic with equality.

Bibliography

1

P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).

2

B. Plotkin, Universal Algebra, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).