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),(f^{\prime })(x):=f{(x)}^{\prime },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\text{ 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. $\bigvee 1(X)=\bigvee \{1\}=1$ and $\bigwedge 1(X)=\bigwedge \{1\}=1$ so $1\in B$

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. Suppose $f,g\in B$. Then

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

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

   $=$ ${\displaystyle \bigwedge f(X)}\wedge {\displaystyle \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 }\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}{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 }\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}\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 $\mathrm{\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\le \exists (f)$: $f(x)\le \bigvee f(X)=f^{\vee }=f^{\exists }(x)=\exists (f)(x)$.

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

  $\exists (f\wedge \exists (g))(x)$ $=$ ${\displaystyle \bigvee \left(f\wedge \exists (g)\right)(X)}={\displaystyle \bigvee \left(f(X)\wedge \exists (g)(X)\right)}$

  $=$ ${\displaystyle \bigvee \left(f(X)\wedge \exists (g)(x)\right)}={\displaystyle \bigvee \left(f(X)\wedge \bigvee g(X)\right)}$

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

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

$\forall (f)(x)$ $=$ ${\displaystyle \bigwedge \{f(x)\mid x\in X\}}={\displaystyle \bigwedge \{f{(x)}^{\prime \prime }\mid x\in X\}}$

$=$ ${\left({\displaystyle \bigvee \{f{(x)}^{\prime }\mid x\in X\}}\right)}^{\prime }={\left({\displaystyle \bigvee \{f^{\prime }(x)\mid x\in X\}}\right)}^{\prime }={\left(\exists (f^{\prime })\right)}^{\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
Canonical name	ExampleOfMonadicAlgebra
Date of creation	2013-03-22 17:51:55
Last modified on	2013-03-22 17:51:55
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	10
Author	CWoo (3771)
Entry type	Example
Classification	msc 03G15
Defines	functional monadic algebra