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 algebraMathworldPlanetmath and X be a non-empty set. Then AX, the set of all functions from X into A, has a natural Boolean algebraic structurePlanetmathPlanetmath defined as follows:


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

For each f:XA, let f(X)A be the range of f. Let B be the subset of AX consisting of all functions f such that f(X) and f(X) exist, where and are the infinite join and infinite meet operationsMathworldPlanetmath on A. In other words,

B:={fAXf(X)A and f(X)A}.
Proposition 1.

B defined above is a Boolean subalgebra of AX.


We need to show that, (1): 1B, (2): for any fB, fB, and (3): for any f,gB, fgB.

  1. 1.

    1(X)={1}=1 and 1(X)={1}=1 so 1B

  2. 2.

    Suppose fB. Then f(X)={f(x)xX}={f(x)xX}. By de Morgan’s law on infinite joins, the last expression is ({f(x)xX}), which exists. Dually, f(X) exists by de Morgan’s law on infinite meets. Therefore, fB.

  3. 3.

    Suppose f,gB. Then

    (fg)(X) = {f(x)g(x)xX}
    = {f(x)xX}{g(x)xX}
    = f(X)g(X),

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


    The last equality stems from the distributive law of infinite meets over finite joins. Since the last expression exists, fgB.

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

Remark. Every constant function belongs to B.

For each fB, write f:=f(X) and f:=f(X). Define two functions f,fAX by

f(x):=f   and   f(x):=f.

Since these are constant functions, they belong to B.

Now, we define operators , on B by setting

(f):=f   and   (f):=f.

By the remark above, and are well-defined functions on B (f,fB).

Proposition 2.

is an existential quantifier operator on B and is its dual.


The following three conditions need to be verified:

  • (0)=0: (0)(x)=0(x)=0=0(X)=0=0.

  • f(f): f(x)f(X)=f=f(x)=(f)(x).

  • (f(g))=(f)(g):

    (f(g))(x) = (f(g))(X)=(f(X)(g)(X))
    = (f(X)(g)(x))=(f(X)g(X))
    = f(X)g(X)=(f)(x)(g)(x)=((f)(g))(x).

Finally, to see that is the dual of , we do the following computations:

(f)(x) = {f(x)xX}={f(x)′′xX}
= ({f(x)xX})=({f(x)xX})=((f))(x),

completing the proof. ∎

Based on PropositionsPlanetmathPlanetmath 1 and 2, (B,) 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