# example of monadic algebra

The canonical example of a monadic algebra is what is known as a functional monadic algebra, which is explained in this entry.

Let $A$ be a Boolean algebra and $X$ be a non-empty set. Then $A^{X}$, the set of all functions from $X$ into $A$, has a natural Boolean algebraic structure defined as follows:

 $(f\wedge g)(x):=f(x)\wedge g(x),\qquad(f^{\prime})(x):=f(x)^{\prime},\qquad 1(% x)=1$

where $f,g:X\to A$ are functions, and $1:X\to A$ is just the constant function mapping everything to $1\in A$ (the abuse of notation here is harmless).

For each $f:X\to A$, let $f(X)\subseteq A$ be the range of $f$. Let $B$ be the subset of $A^{X}$ consisting of all functions $f$ such that $\bigvee f(X)$ and $\bigwedge f(X)$ exist, where $\bigvee$ and $\bigwedge$ are the infinite join and infinite meet operations on $A$. In other words,

 $B:=\{f\in A^{X}\mid\bigvee f(X)\in A\mbox{ and }\bigwedge f(X)\in A\}.$
###### Proposition 1.

$B$ defined above is a Boolean subalgebra of $A^{X}$.

###### Proof.

We need to show that, (1): $1\in B$, (2): for any $f\in B$, $f^{\prime}\in B$, and (3): for any $f,g\in B$, $f\wedge g\in B$.

1. 1.

$\bigvee 1(X)=\bigvee\{1\}=1$ and $\bigwedge 1(X)=\bigwedge\{1\}=1$ so $1\in B$

2. 2.

Suppose $f\in B$. Then $\bigvee f^{\prime}(X)=\bigvee\{f^{\prime}(x)\mid x\in X\}=\bigvee\{f(x)^{% \prime}\mid x\in X\}$. By de Morgan’s law on infinite joins, the last expression is $(\bigwedge\{f(x)\mid x\in X\})^{\prime}$, which exists. Dually, $\bigwedge f^{\prime}(X)$ exists by de Morgan’s law on infinite meets. Therefore, $f^{\prime}\in B$.

3. 3.

Suppose $f,g\in B$. Then

 $\displaystyle\bigwedge(f\wedge g)(X)$ $\displaystyle=$ $\displaystyle\bigwedge\{f(x)\wedge g(x)\mid x\in X\}$ $\displaystyle=$ $\displaystyle\bigwedge\{f(x)\mid x\in X\}\wedge\bigwedge\{g(x)\mid x\in X\}$ $\displaystyle=$ $\displaystyle\bigwedge f(X)\wedge\bigwedge g(X),$

which exists because both $\bigwedge f(X)$ and $\bigwedge g(X)$ do. In addition,

 $\bigvee(f\wedge g)(X)=\bigvee\{f(x)\wedge g(x)\mid x\in X\}=\bigvee f(X)\wedge% \bigvee g(X).$

The last equality stems from the distributive law of infinite meets over finite joins. Since the last expression exists, $f\wedge g\in B$.

The three conditions are verified and the proof is complete. ∎

Remark. Every constant function belongs to $B$.

For each $f\in B$, write $f^{\vee}:=\bigvee f(X)$ and $f^{\wedge}:=\bigwedge f(X)$. Define two functions $f^{\exists},f^{\forall}\in A^{X}$ by

 $f^{\exists}(x):=f^{\vee}\qquad\mbox{ and }\qquad f^{\forall}(x):=f^{\wedge}.$

Since these are constant functions, they belong to $B$.

Now, we define operators $\exists,\forall$ on $B$ by setting

 $\exists(f):=f^{\exists}\qquad\mbox{ and }\qquad\forall(f):=f^{\forall}.$

By the remark above, $\exists$ and $\forall$ are well-defined functions on $B$ ($f^{\exists},f^{\forall}\in B$).

###### Proposition 2.

$\exists$ is an existential quantifier operator on $B$ and $\forall$ is its dual.

###### Proof.

The following three conditions need to be verified:

• $\exists(0)=0$: $\exists(0)(x)=0^{\exists}(x)=0^{\vee}=\bigvee 0(X)=\bigvee 0=0$.

• $f\leq\exists(f)$: $f(x)\leq\bigvee f(X)=f^{\vee}=f^{\exists}(x)=\exists(f)(x)$.

• $\exists(f\wedge\exists(g))=\exists(f)\wedge\exists(g)$:

 $\displaystyle\exists(f\wedge\exists(g))(x)$ $\displaystyle=$ $\displaystyle\bigvee\big{(}f\wedge\exists(g)\big{)}(X)=\bigvee\big{(}f(X)% \wedge\exists(g)(X)\big{)}$ $\displaystyle=$ $\displaystyle\bigvee\big{(}f(X)\wedge\exists(g)(x)\big{)}=\bigvee\big{(}f(X)% \wedge\bigvee g(X)\big{)}$ $\displaystyle=$ $\displaystyle\bigvee f(X)\wedge\bigvee g(X)=\exists(f)(x)\wedge\exists(g)(x)=% \big{(}\exists(f)\wedge\exists(g)\big{)}(x).$

Finally, to see that $\forall$ is the dual of $\exists$, we do the following computations:

 $\displaystyle\forall(f)(x)$ $\displaystyle=$ $\displaystyle\bigwedge\{f(x)\mid x\in X\}=\bigwedge\{f(x)^{\prime\prime}\mid x% \in X\}$ $\displaystyle=$ $\displaystyle\big{(}\bigvee\{f(x)^{\prime}\mid x\in X\}\big{)}^{\prime}=\big{(% }\bigvee\{f^{\prime}(x)\mid x\in X\}\big{)}^{\prime}=\big{(}\exists(f^{\prime}% )\big{)}^{\prime}(x),$

completing the proof. ∎

Based on Propositions 1 and 2, $(B,\exists)$ is a monadic algebra, and is called the functional monadic algebra for the pair $(A,X)$.

Title example of monadic algebra ExampleOfMonadicAlgebra 2013-03-22 17:51:55 2013-03-22 17:51:55 CWoo (3771) CWoo (3771) 10 CWoo (3771) Example msc 03G15 functional monadic algebra