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

Let $ B$ be a Boolean algebra. An existential quantifier operator on $ B$ is a function % latex2html id marker 351 $ \exists: B\to B$ such that

  1. % latex2html id marker 353 $ \exists(0)=0$,
  2. % latex2html id marker 355 $ a\le \exists(a)$, where $ a\in B$, and
  3. % latex2html id marker 359 $ \exists(a\wedge \exists(b))=\exists(a)\wedge \exists(b)$, where $ a,b\in B$.
A monadic algebra is a pair % latex2html id marker 363 $ (B,\exists)$, where $ B$ is a Boolean algebra and % latex2html id marker 367 $ \exists$ is an existential quantifier operator.

There is an obvious connection between an existential quantifier operator on a Boolean algebra and an existential quantifier in a first order logic:

  1. A statement $ \varphi(x)$ is false iff % latex2html id marker 371 $ \exists x \varphi(x)$ is false. For example, suppose $ x$ is a real number. Let $ \varphi(x)$ be the statement $ x=x+1$. Then $ \varphi(x)$ is false no matter what $ x$ is. Likewise, % latex2html id marker 383 $ \exists \varphi(x)$ is always false too.
  2. $ \varphi(x)$ implies % latex2html id marker 387 $ \exists x\varphi(x)$; in other words, if % latex2html id marker 389 $ \exists x\varphi(x)$ is false, then so is $ \varphi(x)$. For example, let $ \varphi(x)$ be the statement $ 1<x$, where $ x\in \mathbb{R}$. By itself, $ \varphi(x)$ is neither true nor false. However % latex2html id marker 401 $ \exists x\varphi(x)$ is always true.
  3. % latex2html id marker 403 $ \exists x (\varphi(x) \wedge \exists x \psi(x))$ iff % latex2html id marker 405 $ \exists x \varphi(x) \wedge \exists x \psi(x)$. For example, suppose again $ x$ is real. Let $ \varphi(x)$ be the statement $ x<1$ and $ \psi(x)$ the statement $ x>1$. Then both % latex2html id marker 417 $ \exists x \psi(x)$ and % latex2html id marker 419 $ \exists x \varphi(x)$ are true. It is easy to verify the equivalence of the two sentences in this example. Notice that, however, % latex2html id marker 421 $ \exists x (\varphi(x) \wedge \psi(x))$ is false.

Remarks

  • One may replace condition 3. above with the following three conditions to get an equivalent definition of an existential quantifier operator:
    1. % latex2html id marker 423 $ \exists(\exists(a)) = \exists(a)$
    2. % latex2html id marker 425 $ \exists (a\vee b)=\exists(a) \vee \exists(b)$
    3. % latex2html id marker 427 $ \exists ((\exists a)')=(\exists a)'$
    From this, it is easy to see that % latex2html id marker 429 $ \exists$ is a closure operator on $ B$, and that % latex2html id marker 433 $ \exists a$ and % latex2html id marker 435 $ (\exists a)'$ are both closed under % latex2html id marker 437 $ \exists$.
  • Like the Lindenbaum algebra of propositional logic, monadic algebra is an attempt at converting first order logic into an algebra so that a logical question may be turned into an algebraic one. However, the existential quantifier operator in a monadic algebra corresponds to existential quantifier applied to formulas with only one variable (hence the name monadic). Formulas with multiple variables, such as $ x^2+y^2=1$, $ x\le y+z$, or $ x_i=x_{i+1}+x_{i+2}$ where $ i=0,1,2,\ldots$ require further generalizations to what is known as a polyadic algebra. The notions of monadic and polyadic algebras were introduced by Paul Halmos.

Dual to the notion of an existential quantifier is that of a universal quantifier. Likewise, there is a dual of an existential quantifier operator on a Boolean algebra, a universal quantifier operator. Formally, a universal quantifier operator on a Boolean algebra $ B$ is a function $ \forall : B\to B$ such that

  1. $ \forall (1) = 1$,
  2. $ \forall (a) \le a$, where $ a\in B$, and
  3. $ \forall(a \vee \forall(b)) = \forall(a) \vee \forall(b)$, where $ a,b\in B$.

Every existential quantifier operator % latex2html id marker 461 $ \exists$ on a Boolean algebra $ B$ induces a universal quantifier operator $ \forall$, given by

% latex2html id marker 467 $\displaystyle \forall (a) := (\exists (a'))'.$
Conversely, every universal quantifier operator induces an existential quantifier by exchanging $ \forall$ and % latex2html id marker 471 $ \exists$ in the definition above. This shows that the two operations are dual to one another.

Bibliography

1
P. Halmos, S. Givant, Logic as Algebra, The Mathematical Association of America (1998).



"monadic algebra" is owned by CWoo.
(view preamble | get metadata)

View style:

See Also: quantifier algebra, polyadic algebra

Also defines:  existential quantifier operator, universal quantifier operator

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

Cross-references: operations, induces, universal quantifier, polyadic algebra, multiple, monadic, variable, formulas, algebraic, algebra, propositional logic, Lindenbaum algebra, closed under, closure operator, sentences, equivalence, NOR, implies, real number, iff, first order logic, existential quantifier, connection, obvious, function, Boolean algebra
There are 6 references to this entry.

This is version 5 of monadic algebra, born on 2008-02-16, modified 2008-02-24.
Object id is 10279, canonical name is MonadicAlgebra.
Accessed 729 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)