polyadic algebra with equality

Let $A=(B,V,\exists ,S)$ be a polyadic algebra. An equality predicate on $A$ is a function $E:V\times V\to B$ such that

1. $S(f)\circ E(x,y)=E(f(x),f(y))$ for any $f:V\to V$ and any $x,y\in V$

2. $E(x,x)=1$ for every $x\in V$, and

3. $E(x,y)\wedge a\le S(x/y)a$, where $a\in B$, and $(x/y)$ denotes the function $V\to 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 $x_1$, and $y$ by $y_1$, then $x_1=y_1$.

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)\le E(y,x)$

• (transitive property) $E(x,y)\wedge E(y,z)\le E(x,z)$

• $E(x,y)\wedge a=E(x,y)\wedge 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\in V$ is not in the support of $a\in A$, then $a=\exists (x)(E(x,y)\wedge S(y/x)a)$.

• $\exists (x)(E(x,y)\wedge a)\wedge \exists (x)(E(x,y)\wedge a^{\prime })=0$ for all $a\in A$ and all $x,y\in V$ whenever $x\ne y$.

• $\exists (x)(E(x,y)\wedge E(x,z))=E(y,z)$ for all $x,y,z\in V$ where $x\notin \{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.