monadic algebra


Let B be a Boolean algebraMathworldPlanetmath. An existential quantifier operator on B is a function :BB such that

  1. 1.

    (0)=0,

  2. 2.

    a(a), where aB, and

  3. 3.

    (a(b))=(a)(b), where a,bB.

A monadic algebra is a pair (B,), where B is a Boolean algebra and is an existential quantifier operator.

There is an obvious connection between an existential quantifier operator on a Boolean algebra and an existential quantifierMathworldPlanetmath in a first order logic:

  1. 1.

    A statement φ(x) is false iff xφ(x) is false. For example, suppose x is a real number. Let φ(x) be the statement x=x+1. Then φ(x) is false no matter what x is. Likewise, φ(x) is always false too.

  2. 2.

    φ(x) implies xφ(x); in other words, if xφ(x) is false, then so is φ(x). For example, let φ(x) be the statement 1<x, where x. By itself, φ(x) is neither true nor false. However xφ(x) is always true.

  3. 3.

    x(φ(x)xψ(x)) iff xφ(x)xψ(x). For example, suppose again x is real. Let φ(x) be the statement x<1 and ψ(x) the statement x>1. Then both xψ(x) and xφ(x) are true. It is easy to verify the equivalence of the two sentencesMathworldPlanetmath in this example. Notice that, however, x(φ(x)ψ(x)) is false.

Remarks

  • One may replace condition 3. above with the following three conditions to get an equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath definition of an existential quantifier operator:

    1. (a)

      ((a))=(a)

    2. (b)

      (ab)=(a)(b)

    3. (c)

      ((a))=(a)

    From this, it is easy to see that is a closure operatorPlanetmathPlanetmathPlanetmath on B, and that a and (a) are both closed under .

  • Like the Lindenbaum algebra of propositional logicPlanetmathPlanetmath, 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 formulasMathworldPlanetmathPlanetmath with only one variable (hence the name monadic). Formulas with multiple variables, such as x2+y2=1, xy+z, or xi=xi+1+xi+2 where i=0,1,2, require further generalizationsPlanetmathPlanetmath 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 :BB such that

  1. 1.

    (1)=1,

  2. 2.

    (a)a, where aB, and

  3. 3.

    (a(b))=(a)(b), where a,bB.

Every existential quantifier operator on a Boolean algebra B induces a universal quantifier operator , given by

(a):=((a)).

Conversely, every universal quantifier operator induces an existential quantifier by exchanging and in the definition above. This shows that the two operations are dual to one another.

References

Title monadic algebra
Canonical name MonadicAlgebra
Date of creation 2013-03-22 17:48:57
Last modified on 2013-03-22 17:48:57
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 9
Author CWoo (3771)
Entry type Definition
Classification msc 03G15
Classification msc 06E25
Related topic QuantifierAlgebra
Related topic PolyadicAlgebra
Defines existential quantifier operator
Defines universal quantifier operator