Noson S. Yanofsky
2003 · arXiv
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.
Metadata: arXiv. Abstracts retain their original authors’ rights.
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
6 selected excerpts · 6 total mentions
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 generalization too. https://arxiv.org/abs/math/0305282v1
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.
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 shows that the paradoxes of self-reference arise from our interpretations. https://arxiv.org/abs/math/0305282v1 explains with many examples. Hi downvoters: Use your words when somebody is wrong. Your downvotes aren't helpful here for finding the truth.
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 with resource dependencies that either deadlock or not -- is there a partial order on resource acquisition so that eventually some operation is unblocked? * garbage collection of memory references -- is there a partial order on resource ownership such that some element is eventually unowned? * Russell's paradox -- presumably something like: is there a partial order on the definitions of some sets such…
that all of the definitions can be resolved? * Godel's Incompleteness theorem and Liar's paradox, etc -- presumably something like: is there a partial order on statements that allows their truth values to be resolved? In every case it seems like the solution is some form of diagonal argument. I really like the version I just found in this paper[1]: if Y is a set and there's a function a(Y): Y that doesn't have a fixed point, then for any function f(T, T): Y there's a function g(T): Y that can't be written as g(s) = f(s,t) for all t. Namely, set g(t) = a(f(t,t)); clearly f(s,s) = g(s) = a(f(s,s)) != f(s,s). For the Liar Paradox ("this sentence is false") and Godel ("this statement cannot be proved in G") the set Y is (True/Proven, False/Disproven) and the function a() just takes False <-> True and so has no fixed point. The function f(s, t) tries to assign a truth value to a statement 's' and also to the _claim_ made by 's'. The function g(s) tries to assign a truth value to 's' alone, but for 'this sentence is false' the definition is g(s) = a(f(s,s)), and the definition of f(s,s) = g(s), so g(s) = a(g(s)) and there's no solution -- just like a recursive function that says f(x) = !f(x) never terminates! The connection to partial orders is: there must be a partial order on the possible states of the system such that there isn't an infinite loop. The states can be the truth values of statements, the input to a function, the states of a Turing machine's tape, the state of the condition a thread is waiting on, or the state of whether an object has been freed. Etc. Of course I have never really thought through this before and I'm making it up as I go, but this is grand and delightful to sort-of hand-wavingly understand. [1]: https://arxiv.org/pdf/math/0305282.pdf
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] https://arxiv.org/abs/math/0305282
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 anywhere. It's a paper by Noson Yanofsky entitled "A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points" (http://arxiv.org/abs/math/0305282) I think you'll enjoy reading it. I read the paper on a long train ride loved working out how given "Ann believes that Bob believes that Ann believes that Bob has a false belief about Ann" asking "does Ann believe that Bob has a false belief about Ann?" results in a paradox. This is supposedly called Brandenburger’s Epistemic Paradox. Anyway, thanks again for your reference.
More from the same topics.
William P. Thurston
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan +11
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.
Martin Kleppmann
The CAP Theorem is a frequently cited impossibility result in distributed systems, especially among NoSQL distributed databases.
Eric Chisolm
This is an introduction to geometric algebra, an alternative to traditional vector algebra that expands on it in two ways: 1.