3 ms·
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"
by doomrobo 3y ago
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 https://arxiv.org/abs/math/0305282v1
- hgsgm 3y agoSure, if you create a larger object it can contain two smaller objects. But that construction is so general that it contains all proofs of the from "There exists X that does not have not property Y" that proceed by constructing something that lacks the property, and stuffs the proof into the diagram.
- abdullahkhalids 3y agoIts not fully general. Many different types of undecidability proofs are basically proofs by diagonalization, but not all are. See some counter examples: https://mathoverflow.net/q/454105 https://mathoverflow.net/q/454105
- srcreigh 3y ago“I genuinely don’t have an operational definition for what it means to use diagonalization” - Terry Tao