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 (192)
Orphanage
Unclass'd
Unproven (496)
Corrections (23)
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
cylindric algebra (Definition)

A cylindric algebra is a quadruple % latex2html id marker 407 $ (B,V,\exists,d)$, where $ B$ is a Boolean algebra, $ V$ is a set whose elements we call variables, % latex2html id marker 413 $ \exists$ and $ d$ are functions

% latex2html id marker 417 $\displaystyle \exists:V\to B^B$    and $\displaystyle \qquad d:V\times V\to B$
such that
  1. % latex2html id marker 420 $ (B,\exists x)$ is a monadic algebra for each $ x\in V$,
  2. % latex2html id marker 424 $ \exists x\circ \exists y = \exists y\circ \exists x$ for any $ x,y\in V$,
  3. $ d_{xx}=1$ for all $ x\in V$,
  4. for any $ x,y\in V$ with $ x\ne y$, and any $ a \in B$, we have the equality
    % latex2html id marker 438 $\displaystyle \exists x(a\wedge d_{xy})\wedge \exists x\big(a'\wedge d_{xy}\big)=0$
  5. for any $ x,y,z\in V$ with $ x\ne y$ and $ x\ne z$, we have the equality
    % latex2html id marker 446 $\displaystyle \exists x (d_{xy}\wedge d_{xz})=d_{yz}.$
where % latex2html id marker 448 $ \exists x$ and $ d_{xy}$ are the abbreviations for % latex2html id marker 452 $ \exists(x)$ and $ d(x,y)$ respectively.

Basically, the first two conditions say that the % latex2html id marker 456 $ (B,V,\exists)$ portion of the cylindric algebra is very similar to a quantifier algebra, except the domain is no longer the subsets of $ V$, but the elements of $ V$ instead. The function $ d$ is the algebraic abstraction of equality. Condition 3 says that $ x=x$ is always true, condition 4 says that the proposition $ a$ and its complement $ a'$, where any occurrences of the variable $ x$ are replaced by the variable $ y$, distinct from $ x$, is always false, while condition 5 says $ y=z$ iff there is an $ x$ such that $ x=y$ and $ x=z$.

Below are some elementary properties of $ d$:

Remarks

  1. The dimension of a cylindric algebra % latex2html id marker 502 $ (B,V,\exists,d)$ is the cardinality of $ V$.
  2. From the definition above, a cylindric algebra is a two-sorted structure, with $ B$ and $ V$ as the two distinct universes. However, it is often useful to view a cylindric algebra as a one-sorted structure. The way to do this is to dispense with $ V$ and identify each % latex2html id marker 512 $ \exists x$ as a unary operator on $ B$, and each $ d_{xy}$ as a constant in $ B$. As a result, the cylindric algebra % latex2html id marker 520 $ (B,V,\exists,d)$ becomes a Boolean algebra with possibly infinitely many operators:
    % latex2html id marker 522 $\displaystyle (B,\exists x,d_{xy})_{x,y\in V}.$
  3. Let $ L$ be a the language of a first order logic, and $ S$ a set of sentences in $ L$. Define $ \equiv$ on $ L$ so that
    $\displaystyle \varphi \equiv \psi$    iff $\displaystyle \quad S \vdash (\varphi\leftrightarrow \psi).$
    Then $ \equiv$ is an equivalence relation on $ L$. For each formula $ \varphi\in L$, let $ [\varphi]$ be the equivalence class containing $ \varphi$. Let $ V$ be a countably infinite set of variables available to $ L$. Now, define operations % latex2html id marker 551 $ \vee,\wedge,',\exists x,d_{xy}$ as follows:

    $\displaystyle [\varphi] \vee [\psi]$ $\displaystyle :=$ $\displaystyle [\varphi \vee \psi],$ (1)
    $\displaystyle \left[ \varphi \right] \wedge [\psi]$ $\displaystyle :=$ $\displaystyle [\varphi \wedge \psi],$ (2)
    $\displaystyle \left[ \varphi \right]'$ $\displaystyle :=$ $\displaystyle [\neg \varphi],$ (3)
    0 $\displaystyle :=$ $\displaystyle [\neg x=x],$ (4)
    $\displaystyle 1$ $\displaystyle :=$ $\displaystyle [x=x],$ (5)
    % latex2html id marker 583 $\displaystyle \exists x[\varphi]$ $\displaystyle :=$ % latex2html id marker 587 $\displaystyle [\exists x \varphi],$ (6)
    $\displaystyle d_{xy}$ $\displaystyle :=$ $\displaystyle [x=y].$ (7)

    Then it can be shown that % latex2html id marker 595 $ (L/\equiv, V,\exists,d)$ is a cylindric algebra. Thus a cylindric algebra can be thought of as an “algebraization” of first order logic (with equality), much the same way as a Boolean algebra (Lindenbaum-Tarski algebra) as the algebraic counterpart of propositional logic.

Bibliography

1
P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
2
L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, Part I., North-Holland, Amsterdam (1971).
3
J. D. Monk, Mathematical Logic, Springer, New York (1976).
4
B. Plotkin, Universal Algebra, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).



"cylindric algebra" is owned by CWoo.
(view preamble)

View style:

See Also: polyadic algebra, polyadic algebra with equality


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

Cross-references: propositional logic, Lindenbaum-Tarski algebra, operations, countably infinite, equivalence class, formula, equivalence relation, sentences, first order logic, language, operator, unary, universes, structure, cardinality, dimension, transitive property, symmetric, properties, iff, occurrences, complement, proposition, algebraic, subsets, domain, quantifier algebra, similar, equality, monadic algebra, functions, variables, Boolean algebra
There are 3 references to this entry.

This is version 6 of cylindric algebra, born on 2008-02-24, modified 2008-03-16.
Object id is 10331, canonical name is CylindricAlgebra.
Accessed 285 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)