PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (22)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] polyadic algebra with equality (Definition)

Let % latex2html id marker 312 $ 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 % latex2html id marker 402 $ a=\exists(x) (E(x,y)\wedge S(y/x)a)$.
  • % latex2html id marker 404 $ \exists(x)(E(x,y)\wedge a)\wedge \exists(x)(E(x,y)\wedge a')=0$ for all $ a\in A$ and all $ x,y\in V$ whenever $ x\ne y$.
  • % latex2html id marker 412 $ \exists(x)(E(x,y)\wedge E(x,z))=E(y,z)$ for all $ x,y,z\in V$ where $ x\notin \lbrace y,z\rbrace$.

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.

Bibliography

1
P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
2
B. Plotkin, Universal Algebra, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).



"polyadic algebra with equality" is owned by CWoo.
(view preamble | get metadata)

View style:

See Also: cylindric algebra

Other names:  equality algebra
Also defines:  equality predicate, substitutive, reflexive, symmetric, transitive

This object's parent.

Attachments:
example of polyadic algebra with equality (Example) by CWoo
Log in to rate this entry.
(view current ratings)

Cross-references: logic, algebraic, first order logic, equality, cylindric algebras, subalgebra, polyadic, infinite, locally finite, degree, support, fixed, transposition, Reflexive, occurrences, proposition, propositional function, variable, function, polyadic algebra
There are 25 references to this entry.

This is version 7 of polyadic algebra with equality, born on 2008-02-26, modified 2008-03-18.
Object id is 10337, canonical name is PolyadicAlgebraWithEquality.
Accessed 1557 times total.

Classification:
AMS MSC: 03G15 (Mathematical logic and foundations :: Algebraic logic :: Cylindric and polyadic algebras; relation algebras)
Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)