A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points

Abstract

Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the same simple scheme. We demonstrate these similarities by showing how this simple scheme encompasses the semantic paradoxes, and how they arise as diagonal arguments and fixed point theorems in logic, computability theory, complexity theory and formal language theory.

References in corpus (1)

• Classical computing, quantum computing, and Shor's factoring algorithm

Cited by in corpus (12)

• Impossibility Results in AI: A Survey
• Quantum Hocus Pocus
• Epistemic Horizons and the Foundations of Quantum Mechanics
• Formalizing common sense for scalable inconsistency-robust information integration using Direct Logic(TM) reasoning and the Actor Model
• Substructural fixed-point theorems and the diagonal argument: theme and variations
• Martingale drift of Langevin dynamics and classical canonical spin statistics
• A Framework for Universality in Physics, Computer Science, and Beyond
• Diagonalizing by Fixed-Points
• A Compositional Coalgebraic Semantics of Strategic Games
• The Emergence of Cognition and Computation: A Physicalistic Perspective
• Epistemic Horizons: This Sentence is $\frac{1}{\sqrt{2}}(|True⟩+|False⟩)$
• From Unitarity to Irreversibility: The Role of Infinite Tensor Products and Nested Wigner's Friends