Duality (mathematics) - Duality in Logic and Set Theory

Duality in Logic and Set Theory

In logic, functions or relations A and B are considered dual if A(¬x) = ¬B(x), where ¬ is logical negation. The basic duality of this type is the duality of the ∃ and ∀ quantifiers. These are dual because ∃x.¬P(x) and ¬∀x.P(x) are equivalent for all predicates P: if there exists an x for which P fails to hold, then it is false that P holds for all x. From this fundamental logical duality follow several others:

• A formula is said to be satisfiable in a certain model if there are assignments to its free variables that render it true; it is valid if every assignment to its free variables makes it true. Satisfiability and validity are dual because the invalid formulas are precisely those whose negations are satisfiable, and the unsatisfiable formulas are those whose negations are valid. This can be viewed as a special case of the previous item, with the quantifiers ranging over interpretations.

• In classical logic, the ∧ and ∨ operators are dual in this sense, because (¬x ∧ ¬y) and ¬(x ∨ y) are equivalent. This means that for every theorem of classical logic there is an equivalent dual theorem. De Morgan's laws are examples. More generally, . The left side is true if and only if ∀i.¬x_i, and the right side if and only if ¬∃i.x_i.

• In modal logic, □p means that the proposition p is "necessarily" true, and that p is "possibly" true. Most interpretations of modal logic assign dual meanings to these two operators. For example in Kripke semantics, "p is possibly true" means "there exists some world W in which p is true", while "p is necessarily true" means "for all worlds W, p is true". The duality of □ and then follows from the analogous duality of ∀ and ∃. Other dual modal operators behave similarly. For example, temporal logic has operators denoting "will be true at some time in the future" and "will be true at all times in the future" which are similarly dual.

Other analogous dualities follow from these:

• Set-theoretic union and intersection are dual under the set complement operator ⋅C. That is, AC ∩ BC = (A ∪ B)C, and more generally, . This follows from the duality of ∀ and ∃: an element x is a member of if and only if ∀α.¬x∈A_α, and is a member of if and only if ¬∃α.x∈A_α.

Topology inherits a duality between open and closed subsets of some fixed topological space X: a subset U of X is closed if and only if its complement in X is open. Because of this, many theorems about closed sets are dual to theorems about open sets. For example, any union of open sets is open, so dually, any intersection of closed sets is closed. The interior of a set is the largest open set contained in it, and the closure of the set is the smallest closed set that contains it. Because of the duality, the complement of the interior of any set U is equal to the closure of the complement of U.

The collection of all open subsets of a topological space X forms a complete Heyting algebra. There is a duality, known as Stone duality, connecting sober spaces and spatial locales.

• Birkhoff's representation theorem relating distributive lattices and partial orders