monadic algebra

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

1. $\exists (0)=0$,

2. $a\le \exists (a)$, where $a\in B$, and

3. $\exists (a\wedge \exists (b))=\exists (a)\wedge \exists (b)$, where $a,b\in B$.

A monadic algebra is a pair $(B,\exists )$, where $B$ is a Boolean algebra and $\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 $\phi (x)$ is false iff $\exists x\phi (x)$ is false. For example, suppose $x$ is a real number. Let $\phi (x)$ be the statement $x=x+1$. Then $\phi (x)$ is false no matter what $x$ is. Likewise, $\exists \phi (x)$ is always false too.

2. $\phi (x)$ implies $\exists x\phi (x)$; in other words, if $\exists x\phi (x)$ is false, then so is $\phi (x)$. For example, let $\phi (x)$ be the statement , where $x\in ℝ$. By itself, $\phi (x)$ is neither true nor false. However $\exists x\phi (x)$ is always true.

3. $\exists x(\phi (x)\wedge \exists x\psi (x))$ iff $\exists x\phi (x)\wedge \exists x\psi (x)$. For example, suppose again $x$ is real. Let $\phi (x)$ be the statement and $\psi (x)$ the statement $x>1$. Then both $\exists x\psi (x)$ and $\exists x\phi (x)$ are true. It is easy to verify the equivalence of the two sentences in this example. Notice that, however, $\exists x(\phi (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. $\exists (\exists (a))=\exists (a)$

  2. $\exists (a\vee b)=\exists (a)\vee \exists (b)$

  3. $\exists ({(\exists a)}^{\prime })={(\exists a)}^{\prime }$

  From this, it is easy to see that $\exists$ is a closure operator on $B$, and that $\exists a$ and ${(\exists a)}^{\prime }$ are both closed under $\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,\mathrm{\dots }$ 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 $\exists$ on a Boolean algebra $B$ induces a universal quantifier operator $\forall$, given by

$$\forall (a):={(\exists (a^{\prime }))}^{\prime }.$$

Conversely, every universal quantifier operator induces an existential quantifier by exchanging $\forall$ and $\exists$ in the definition above. This shows that the two operations are dual to one another.

Title	monadic algebra
Canonical name	MonadicAlgebra
Date of creation	2013-03-22 17:48:57
Last modified on	2013-03-22 17:48:57
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	9
Author	CWoo (3771)
Entry type	Definition
Classification	msc 03G15
Classification	msc 06E25
Related topic	QuantifierAlgebra
Related topic	PolyadicAlgebra
Defines	existential quantifier operator
Defines	universal quantifier operator