HackerPapers

arXiv:math/0305282math.LO

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

Noson S. Yanofsky

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.

arXiv comments
Journal reference
The Bulletin of Symbolic Logic, Vol 9, 2003, NUMBER = 3, PAGES = 362--386
DOI
doi:10.2178/bsl/1058448677
Subjects
math.LOLogic

On Hacker News

Linked by 6 identifiable commenters in 6 comments across 6 threads, from Nov 2015 to Sep 2023. Found in 2 HN submissions from Mar 2025 to May 2026. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments6 threads

  1. Proofs based on diagonalization help reveal the limits of algorithms 1 comment

    • It turns out that these are all kind of the same, the Liar's Paradox, Russell's Paradox, the Halting Problem, etc. And indeed the they rely on a "diagonal map" i.e., a map x -> (x, x) in the construction. This was a great read, if you want a mathematical take on it, and some…

      doomroboView on HNParent context

  2. Basics of Proofs (2017) [pdf] 1 comment

    • It is a formalization of Cantor's diagonal argument - in fact, of "diagonal arguments" more generally. See http://arxiv.org/abs/math/0305282 for an expository treatment.

      zozbot234View on HNParent context

  3. How many real numbers exist? New proof moves closer to an answer 1 comment

    • Hi, Lawvere pummelled your position into the ground a while ago: http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf Your critique involves repeatedly crossing the boundary between the inside and outside of the system in question; Lawvere works entirely inside the system, and…

      myWindoonnView on HNParent context

  4. Weakening Cycles So That Turing Can Halt 1 comment

    • Oh, wow, this is a very stimulating comparison. My summary is that all of these are structurally the same: * programs with recursion that either halts or not -- is there a partial order on states of a recursive algorithm such that some state is eventually terminal? * threads…

      ajkjkView on HNParent context

  5. John Conway – The Free Will Lectures (2009) [video] 1 comment

    • It isn't what you're looking for, but perhaps Lawvere's generalization of Gödel's work is sufficiently geometric for you [0][1][2]. [0] https://ncatlab.org/nlab/show/Lawvere's+fixed+point+theorem [1] http://tac.mta.ca/tac/reprints/articles/15/tr15.pdf [2]…

      lidHanteykView on HNParent context

  6. The Hardest Logic Puzzle: A step-by-step guide to true, false, and random 1 comment

    • Wow Peter, thanks for that. I like their analysis. It reminded me of a great article I read years ago that dealt with the issue of self-referential paradox. In fact, at the time I tried applying the techniques therein towards the surprise examination, however I didn't get…

      throwaway000002View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.