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

1. 1.

$\exists(0)=0$,

2. 2.

$a\leq\exists(a)$, where $a\in B$, and

3. 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. 1.

A statement $\varphi(x)$ is false iff $\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, $\exists\varphi(x)$ is always false too.

2. 2.

$\varphi(x)$ implies $\exists x\varphi(x)$; in other words, if $\exists x\varphi(x)$ is false, then so is $\varphi(x)$. For example, let $\varphi(x)$ be the statement $1, where $x\in\mathbb{R}$. By itself, $\varphi(x)$ is neither true nor false. However $\exists x\varphi(x)$ is always true.

3. 3.

$\exists x(\varphi(x)\wedge\exists x\psi(x))$ iff $\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 $\exists x\psi(x)$ and $\exists x\varphi(x)$ are true. It is easy to verify the equivalence of the two sentences in this example. Notice that, however, $\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. (a)

$\exists(\exists(a))=\exists(a)$

2. (b)

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

3. (c)

$\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\leq 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. 1.

$\forall(1)=1$,

2. 2.

$\forall(a)\leq a$, where $a\in B$, and

3. 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.

## References

Title monadic algebra MonadicAlgebra 2013-03-22 17:48:57 2013-03-22 17:48:57 CWoo (3771) CWoo (3771) 9 CWoo (3771) Definition msc 03G15 msc 06E25 QuantifierAlgebra PolyadicAlgebra existential quantifier operator universal quantifier operator