polyadic algebra

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 \mathrm{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=\{x_0,x_1,\mathrm{\dots }\}$ be a countably indexed set of variables. For any propositional function $\phi$, define $S(f)(\phi )$ to be the propositional function ${\phi }_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 $\phi$ is the propositional function $x_0^2-x_1+x_2/x_3$, then $S(f)(\phi )$ 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)$.

It is not hard to see from the examples above that $S(f)$ respects Boolean operations $\wedge$ and ${}^{\prime }$, which is why we want to make $S(f)$ an endomorphism on $B$. Furthermore, the four conditions above can be interpreted as

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 $\phi$ should have the same effect as applying substitutions $g$ of variables in $\phi$, followed by substitutions $f$ of variables in $S(g)(\phi )$

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

   is unchanged by $S(f)$, since $x_0,x_1,x_2$ are all fixed by $f$.

4. Let $\phi =\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.