You are here
Homemonadic algebra
Primary tabs
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\leq\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 $\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. 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:
(a) $\exists(\exists(a))=\exists(a)$
(b) $\exists(a\vee b)=\exists(a)\vee\exists(b)$
(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. $\forall(1)=1$,
2. $\forall(a)\leq 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.
References
 1 P. Halmos, S. Givant, Logic as Algebra, The Mathematical Association of America (1998).
Mathematics Subject Classification
03G15 no label found06E25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections