polyadic algebra with equality
Let A=(B,V,∃,S) be a polyadic algebra. An equality predicate on A is a function E:V×V→B such that
-
1.
S(f)∘E(x,y)=E(f(x),f(y)) for any f:V→V and any x,y∈V
-
2.
E(x,x)=1 for every x∈V, and
-
3.
E(x,y)∧a≤S(x/y)a, where a∈B, and (x/y) denotes the function V→V that maps x to y, and constant everywhere else.
Heuristically, we can interpret the conditions above as follows:
-
1.
if x=y and if we replace x by, say x1, and y by y1, then x1=y1.
-
2.
x=x for every variable
x
-
3.
if we have a propositional function a that is true, and x=y, then the proposition
obtained from a by replacing all occurrences of x by y is also true.
The second condition is also known as the reflexive property of the equality predicate E, and the third is known as the substitutive property of E
A polyadic algebra with equality is a pair (A,E) where A is a polyadic algebra and E is an equality predicate on A. Paul Halmos introduced this concept and called this simply an equality algebra.
Below are some basic properties of the equality predicate E in an equality algebra (A,E):
-
•
(symmetric property) E(x,y)≤E(y,x)
-
•
(transitive property) E(x,y)∧E(y,z)≤E(x,z)
-
•
E(x,y)∧a=E(x,y)∧S(x,y)a, where (x,y) in the S is the transposition on V that swaps x and y and leaves everything else fixed.
-
•
if a variable x∈V is not in the support
of a∈A, then a=∃(x)(E(x,y)∧S(y/x)a).
-
•
∃(x)(E(x,y)∧a)∧∃(x)(E(x,y)∧a′)=0 for all a∈A and all x,y∈V whenever x≠y.
-
•
∃(x)(E(x,y)∧E(x,z))=E(y,z) for all x,y,z∈V where x∉{y,z}.
Remarks
-
•
The degree and local finiteness of a polyadic algebra (A,E) are defined as the degree and the local finiteness and degree of its underlying polyadic algebra A.
-
•
It can be shown that every locally finite
polyadic algebra of infinite
degree can be embedded (as a polyadic subalgebra
) in a locally finite polyadic algebra with equality of infinite degree.
-
•
Like cylindric algebras, polyadic algebras with equality is an attempt at “converting” a first order logic (with equality) into algebraic form, so that the logic can be studied using algebraic means.
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 with equality |
Canonical name | PolyadicAlgebraWithEquality |
Date of creation | 2013-03-22 17:51:37 |
Last modified on | 2013-03-22 17:51:37 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 10 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03G15 |
Synonym | equality algebra |
Related topic | CylindricAlgebra |
Defines | equality predicate |
Defines | substitutive |
Defines | reflexive![]() |
Defines | symmetric |
Defines | transitive![]() |