monadic algebra
Let be a Boolean algebra. An existential quantifier operator on is a function such that
- 1.
,
- 2.
, where , and
- 3.
, where .
A monadic algebra is a pair , where 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 quantifier in a first order logic:
- 1.
A statement is false iff is false. For example, suppose is a real number. Let be the statement . Then is false no matter what is. Likewise, is always false too.
- 2.
implies ; in other words, if is false, then so is . For example, let be the statement , where . By itself, is neither true nor false. However is always true.
- 3.
iff . For example, suppose again is real. Let be the statement and the statement . Then both and are true. It is easy to verify the equivalence of the two sentences
in this example. Notice that, however, 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)
- (b)
- (c)
From this, it is easy to see that is a closure operator
on , and that and are both closed under .
- (a)
- •
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 , , or where 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 is a function such that
- 1.
,
- 2.
, where , and
- 3.
, where .
Every existential quantifier operator on a Boolean algebra induces a universal quantifier operator , given by
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
- 1 P. Halmos, S. Givant, Logic as Algebra, The Mathematical Association of America (1998).