abstract duality: opposite category,
|logic||category theory||type theory|
|true||terminal object/(-2)-truncated object||h-level 0-type/unit type|
|false||initial object||empty type|
|proposition||(-1)-truncated object||h-proposition, mere proposition|
|cut elimination for implication||counit for hom-tensor adjunction||beta reduction|
|introduction rule for implication||unit for hom-tensor adjunction||eta conversion|
|disjunction||coproduct ((-1)-truncation of)||sum type (bracket type of)|
|implication||internal hom||function type|
|negation||internal hom into initial object||function type into empty type|
|universal quantification||dependent product||dependent product type|
|existential quantification||dependent sum ((-1)-truncation of)||dependent sum type (bracket type of)|
|equivalence||path space object||identity type|
|equivalence class||quotient||quotient type|
|induction||colimit||inductive type, W-type, M-type|
|higher induction||higher colimit||higher inductive type|
|completely presented set||discrete object/0-truncated object||h-level 2-type/preset/h-set|
|set||internal 0-groupoid||Bishop set/setoid|
|universe||object classifier||type of types|
|modality||closure operator monad||modal type theory, monad (in computer science)|
|linear logic||(symmetric, closed) monoidal category||linear type theory/quantum computation|
|proof net||string diagram||quantum circuit|
|(absence of) contraction rule||(absence of) diagonal||no-cloning theorem|
In logic, de Morgan duality is a duality between intuitionistic logic and dual-intuitionistic paraconsistent logic. In classical logic and linear logic, it is a self-duality mediated by negation. Although it goes back to Aristotle (at least), its discovery is generally attributed to Augustus de Morgan.
More explicitly, de Morgan duality is the duality between logical operators as shown in the table below:
|Intuitionistic operator||Dual-intuitionistic operator|
|(universal quantification)||(existential quantification)|
The first two operators in each column exist in both intuitionistic and dual-intuitionistic propositional logic and the last two in each column exist in both forms of predicate logic and modal logic (respectively), but they are still dual as shown. All of these exist in classical logic (although some of the paraconsistent operators are not widely used), and the two forms of negation ( and ) are the same there.
In linear logic, this extends to a duality between conjunctive and disjunctive operators:
|Conjunctive operator||Disjunctive operator|
The first two rows of the intuitionistic/dual-intuitionistic/classical duality generalise to arbitrary lattices, including subobject lattices in coherent categories, and from there to the duality between limits and colimits in category theory:
|terminal object||initial object|
So in a way, all duality in category theory is a generalisation of de Morgan duality.
The de Morgan laws are the statements, valid in various forms of logic, that de Morgan duality is mediated by negation. For example, using the second line of the first table, we have
Traditionally, the term is reserved for this line.
since every other aspect of the first two lines is already constructively valid, the claim that negation mediates the de Morgan self-duality of negation already has a name (the double negation law, equivalent to the principle of excluded middle), and no other line involves only operators that appear in intuitionstic propositional calculus.