polyadic algebra
A polyadic algebra is a quadruple , where is a quantifier algebra, and is a function from the set of functions on to the set of endomorphisms on the Boolean algebra , in other words
such that
-
1.
,
-
2.
,
-
3.
if ,
-
4.
if is one-to-one when restricted to .
Explanation of notations: are identity functions on respectively; are functions on , and is a subset of . The circle 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 can be thought of as changes to propositional functions due to a “substitution” of variables (elements of ). Let us see some examples. Let be a countably indexed set of variables. For any propositional function , define to be the propositional function obtained by replacing each variable that occurs in it by . Below are two examples illustrating how changes propositional functions:
-
•
Let be the function given by and for all . If is the propositional function , then is the propositional function .
-
•
Let be the function given by , and for all . Then the propositional function “” becomes “” under .
It is not hard to see from the examples above that respects Boolean operations and , which is why we want to make an endomorphism on . 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 of varaibles in a propositional function should have the same effect as applying substitutions of variables in , followed by substitutions of variables in
-
3.
a substitution of variables should have no effect to a propositional function beginning with if every variable bound by is fixed by . For example, if we replace in the second example above by and otherwise, then
is unchanged by , since are all fixed by .
-
4.
Let be a propositional function, where are sets of variables with bound by and free. If no two variables get mapped to the same variable, and no free variable (in ) becomes bound (in ) under the substitution, then and 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 of variables a transformation, and the triple satisfying the first two conditions above a transformation algebra. Therefore, a polyadic algebra is a quadruple where is a quantifier algebra and 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 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.
References
- 1 P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
- 2 B. Plotkin, Universal Algebra, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).
Title | polyadic algebra |
---|---|
Canonical name | PolyadicAlgebra |
Date of creation | 2013-03-22 17:50:39 |
Last modified on | 2013-03-22 17:50:39 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 13 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03G15 |
Related topic | QuantifierAlgebra |
Related topic | MonadicAlgebra |
Related topic | CylindricAlgebra |
Defines | transformation algebra |