Math 2.0

Mathematical logic and foundations Counterexample

Girard's paradox

Builds on System FCalculus of constructionsBurali-Forti paradoxType theoryNormalization propertyIntuitionistic type theory

Counterexample

System U is the pure type system with sorts ∗*, □\square and △\triangle, axioms ∗:□* : \square and □:△\square : \triangle, and rules (∗,∗)(*, *), (□,∗)(\square, *), (□,□)(\square, \square), (△,∗)(\triangle, *) and (△,□)(\triangle, \square). It extends the higher-order form of System F by allowing quantification over all kinds, such as ∀κ:□. …\forall \kappa{:}\square.\, \dots. Girard's paradox is the construction, in System U, of a closed term of type ⊥=∀α:∗. α\bot = \forall \alpha{:}{*}.\, \alpha. Applying this term to any type τ\tau of sort ∗* gives a closed term of τ\tau. So every proposition has a proof, and System U is inconsistent as a logic. It follows that System U does not have the normalization property. Indeed, a closed normal term of type ∀α:∗. α\forall \alpha{:}{*}.\, \alpha would have the form λα:∗. t\lambda \alpha{:}{*}.\, t. Here tt would be a normal term of type α\alpha whose only free variable is α\alpha, and no such tt exists.

Remarks

The construction is a type-theoretic form of the Burali-Forti paradox. It builds a type that behaves like the collection of all well-founded orders, and derives a contradiction from it. Girard found the paradox in his 1972 thesis. It also applies to any system with a type of all types, ∗:∗* : *, such as the first version of Martin-Löf's type theory. Antonius Hurkens later gave a much shorter version. The paradox shows that a type theory used as a logic cannot have a type of all types. For this reason the calculus of constructions has no sort above □\square, so it cannot quantify over all kinds. Martin-Löf type theory instead uses a hierarchy of universes, each in the next.

Reading path

To understand this page from the ground up, read these 38 pages in order. The foundations come first.

Show the path as a graph
Element, definition, no evidence levelElementdefinitionIntuitionistic logic, concept, no evidence levelIntuitionistic logicconceptLambda calculus, concept, no evidence levelLambda calculusconceptLambda cube, concept, no evidence levelLambda cubeconceptNormalization property, concept, no evidence levelNormalization propertyconceptOrdinal number, concept, no evidence levelOrdinal numberconceptProposition, concept, no evidence levelPropositionconceptSet, concept, no evidence levelSetconceptWell-order, concept, no evidence levelWell-orderconceptSet, definition, no evidence levelSetdefinitionConjunction, definition, no evidence levelConjunctiondefinitionDisjunction, definition, no evidence levelDisjunctiondefinitionImplication, definition, no evidence levelImplicationdefinitionNegation, definition, no evidence levelNegationdefinitionPredicate, definition, no evidence levelPredicatedefinitionBiconditional, definition, no evidence levelBiconditionaldefinitionTruth table, concept, no evidence levelTruth tableconceptModus ponens, concept, no evidence levelModus ponensconceptUniversal quantifier, definition, no evidence levelUniversal quantifierdefinitionAxiom of extensionality, statement, no evidence levelAxiom of extensionali…statementMathematical proof, concept, no evidence levelMathematical proofconceptPropositional logic, concept, no evidence levelPropositional logicconceptTautology, definition, no evidence levelTautologydefinitionPredicate logic, concept, no evidence levelPredicate logicconceptLogical equivalence, definition, no evidence levelLogical equivalencedefinitionZermelo–Fraenkel set theory, concept, no evidence levelZermelo–Fraenkel set …conceptDouble negation law, statement, no evidence levelDouble negation lawstatementBurali-Forti paradox, counterexample, no evidence levelBurali-Forti paradoxcounterexampleProof by contradiction, concept, no evidence levelProof by contradictionconceptRussell's paradox, statement, no evidence levelRussell's paradoxstatementType theory, concept, no evidence levelType theoryconceptCurry–Howard correspondence, concept, no evidence levelCurry–Howard correspo…conceptDependent type, concept, no evidence levelDependent typeconceptIntuitionistic type theory, concept, no evidence levelIntuitionistic type t…conceptSimply typed lambda calculus, concept, no evidence levelSimply typed lambda c…conceptSystem F, concept, no evidence levelSystem FconceptCalculus of constructions, concept, no evidence levelCalculus of construct…conceptGirard's paradox, counterexample, no evidence levelGirard's paradoxcounterexample
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Element definition
  2. Intuitionistic logic concept
  3. Lambda calculus concept
  4. Lambda cube concept
  5. Normalization property concept
  6. Ordinal number concept
  7. Proposition concept
  8. Set concept
  9. Well-order concept
  10. Set definition
  11. Conjunction definition
  12. Disjunction definition
  13. Implication definition
  14. Negation definition
  15. Predicate definition
  16. Biconditional definition
  17. Truth table concept
  18. Modus ponens concept
  19. Universal quantifier definition
  20. Axiom of extensionality statement
  21. Mathematical proof concept
  22. Propositional logic concept
  23. Tautology definition
  24. Predicate logic concept
  25. Logical equivalence definition
  26. Zermelo–Fraenkel set theory concept
  27. Double negation law statement
  28. Burali-Forti paradox counterexample
  29. Proof by contradiction concept
  30. Russell's paradox statement
  31. Type theory concept
  32. Curry–Howard correspondence concept
  33. Dependent type concept
  34. Intuitionistic type theory concept
  35. Simply typed lambda calculus concept
  36. System F concept
  37. Calculus of constructions concept
  38. Girard's paradox counterexample

Further reading

  1. Web https://en.wikipedia.org/wiki/System_U
About this page
TagDK5CE74C06
URIm2://DK5CE74C06
Kindcounterexample
WritingW0 stub
MSC03B38, 03B40
UsesSystem F, Calculus of constructions, Burali-Forti paradox, Type theory, Normalization property, Intuitionistic type theory
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)
  • edge refutes or not_instance_of out (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.