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 (21)
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
polyadic algebra (Definition)

A polyadic algebra is a quadruple % latex2html id marker 394 $ (B,V,\exists,S)$, where % latex2html id marker 396 $ (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

$\displaystyle S:V^V\to \operatorname{End}(B)$
such that
  1. $ S(1_V)=1_B$,
  2. $ S(f\circ g)=S(f)\circ S(g)$,
  3. % latex2html id marker 410 $ S(f)\circ \exists(I)=S(g)\circ \exists(I)$ if $ f(V-I)=g(V-I)$,
  4. % latex2html id marker 414 $ \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=\lbrace x_0,x_1,\ldots \rbrace$ 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\ne 0$. Then the propositional function “ % latex2html id marker 476 $ \exists x_0,x_1,x_2 (x_0\ne x_1 \wedge x_1\ne x_2 \wedge x_2\ne x_0)$” becomes “ % latex2html id marker 478 $ \exists x_2,x_1,x_2 (x_2\ne x_1 \wedge x_1\ne x_2 \wedge x_2\ne x_2)$” under $ S(f)$.
It is not hard to see from the examples above that $ S(f)$ respects Boolean operations $ \wedge$ and $ '$, which is why we want to make $ S(f)$ an endomorphism on $ B$. 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 $ 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. a substitution $ f$ of variables should have no effect to a propositional function beginning with % latex2html id marker 506 $ \exists$ if every variable bound by % latex2html id marker 508 $ \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
    % latex2html id marker 518 $\displaystyle \lq\lq \exists x_0,x_1,x_2 (x_0\ne x_1 \wedge x_1\ne x_2 \wedge x_2\ne x_0)''$
    is unchanged by $ S(f)$, since $ x_0,x_1,x_2$ are all fixed by $ f$.
  4. Let % latex2html id marker 526 $ \varphi=\exists I \psi(I,J)$ be a propositional function, where $ I,J$ are sets of variables with $ I$ bound by % latex2html id marker 532 $ \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 % latex2html id marker 542 $ \exists I \psi(f(I),f(J))$ and % latex2html id marker 544 $ \exists f(I) \psi(f(I),f(J))$ 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 $ V$ of variables a transformation, and the triple $ (B,V,S)$ satisfying the first two conditions above a transformation algebra. Therefore, a polyadic algebra is a quadruple % latex2html id marker 550 $ (B,V,\exists,S)$ where % latex2html id marker 552 $ (B,V,\exists)$ is a quantifier algebra and $ (B,V,S)$ 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 $ V$ 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.

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" is owned by CWoo.
(view preamble | get metadata)

View style:

See Also: quantifier algebra, monadic algebra, cylindric algebra

Also defines:  transformation algebra

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

Cross-references: cylindric algebra, equality, classical first order logic, propositional logic, Lindenbaum-Tarski algebra, singleton, monadic algebras, transformation, logic, algebraic, free variable, fixed, bound, operations, Boolean, occur ins, variables, propositional functions, degree, compositions, functional, represents, circle, subset, identity functions, restricted, one-to-one, Boolean algebra, endomorphisms, function, quantifier algebra
There are 5 references to this entry.

This is version 10 of polyadic algebra, born on 2008-02-22, modified 2008-02-26.
Object id is 10315, canonical name is PolyadicAlgebra.
Accessed 619 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)