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. 1.

$S(1_{V})=1_{B}$,

2. 2.

$S(f\circ g)=S(f)\circ S(g)$,

3. 3.

$S(f)\circ\exists(I)=S(g)\circ\exists(I)$ if $f(V-I)=g(V-I)$,

4. 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},\ldots\}$ 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\neq 0$. Then the propositional function “$\exists x_{0},x_{1},x_{2}(x_{0}\neq x_{1}\wedge x_{1}\neq x_{2}\wedge x_{2}% \neq x_{0})$” becomes “$\exists x_{2},x_{1},x_{2}(x_{2}\neq x_{1}\wedge x_{1}\neq x_{2}\wedge x_{2}% \neq 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. 1.

if there are no substitutions of variables, then there should be no corresponding changes to the propositional functions

2. 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. 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}\neq x_{1}\wedge x_{1}\neq x_{2}\wedge x_{2}% \neq x_{0})"$

is unchanged by $S(f)$, since $x_{0},x_{1},x_{2}$ are all fixed by $f$.

4. 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.

## References

• 1 P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
• 2
Title polyadic algebra PolyadicAlgebra 2013-03-22 17:50:39 2013-03-22 17:50:39 CWoo (3771) CWoo (3771) 13 CWoo (3771) Definition msc 03G15 QuantifierAlgebra MonadicAlgebra CylindricAlgebra transformation algebra