I highly recommend getting Godel's proof[1] and reading it. It's an amazing journey and quite understandable from the start (the first half of the book is introduction), and I've never been able to read proofs very well. It takes concentration, but once you get it (at '17 GenR') it's almost like a symphony going off. The crystalline brilliance of the "System P" decomposition is worth it just to see how math as a process could be reduced to a such simple, clear and concise set of symbol manipulations...and then the rest shows how that could be used topple itself. Incredibly philosophically insightful.
I can't speak for Godel's original proof since I haven't seen it before, but I certainly found Computability and Logic [1] to be pretty approachable. It's the textbook used for UC Berkeley's "Intermediate Logic" philosophy course (in other words, it's so easy even philosophy majors can understand it! :P).
From my understanding, C&L diverges from Godel's original proof technique in order to make it easier to follow, but it's much more rigorous and explicit than what you'd find in Godel, Escher, Bach or something. It's still a textbook.
I try to read Godel's Proof once a year or so. You might also be interested in Gregory Chaitin's Meta Math! The Quest For Omega, which relates the halting problem (among other things) to Godel. A word of warning though, the book is rather idiosyncratic, as you might have seen from the title.
Regarding [1], "circularity" in an uncountably infinite context seems different than "self-referential", though the latter is usually geometrically analogized as the former. I tentatively consider Yablo's Paradox to demonstrate that an ineradicable cycle of alternating truth-assignments is equivalent to an infinite (>= aleph-one) regression of alternating truth-assignments, and thus that circularity does not map coherently to self-reference in all logic systems.
Imagine an infinite sequence of sentences S1, S2, S3, ...,
(S1) for all k >1, Sk is untrue
(S2) for all k >2, Sk is untrue
(S3) for all k >3, Sk is untrue
...
Perhaps another argument in favor of regarding infinites as a logical fallacy. Assuming our universe is finite, all objects in the universe are finite, including sets. Yablo's set chain ends at some N, possibly very very very large. Sentence N is true [there are no further sequences], all other sentences are untrue, as there exists a true sentence with k > i: the Nth sentence.
Infinities can be handled safely in logic. You just have to be careful about them.
There may not be physically real infinities. But there are no physically real perfect squares either (assuming an analogue universe). It's a simplified model.
> But there are no physically real perfect squares either (assuming an analogue universe).
How does analogue vs digital (assuming you mean that analogue) matter here? You'd also want to specify which "digital physics" you want to rely on.
We don't need to think along those lines to consider a physically real idealized geometrical object.
Here I'll recast your square as a planar slice through a real object in our (3d+1d) universe.
With reasonable assumptions about the local behaviour of spacetime, you can't construct a physically perfect square because of the small-length-scale behaviour of matter rather than that or the presence of infinities of infinitesimals. The assumption here is that locally around the square the spacetime is Minkowskian, which for a small and light square is practically guaranteed everywhere outside the event horizons of black holes and far from the hot dense phase of the universe. "Practically guaranteed" here means that in spite of plausible theoretical objections to the perfectness, there exists no mechanism to show that the object is not a perfect square (i.e., such objections are conjectural physics leaning hard on a purely mathematical argument).
"Digitalization" and discretization arguments run into observational problems right away.
The wavelength of light is not quantized, for example, and is not clearly bounded in the infrared. (In the ultraviolet you get pair production and gravitational collapse, however.) While one could make an argument that at the emission event of every photon there is not an infinity of available photon wavelengths, you would have to forbid infinitesimal spacetime intervals to avoid emitted photons stretching into arbitrary wavelengths under the metric expansion of the universe, and the only practical way of doing that is through discretization (with or without emergence).
There is a substantial weight of evidence that suggests that if spacetime (or whatever it emerges from) is discretized, the discretization length is not significantly above the Planck length; notably gamma rays, x-rays, light and radio from violent astrophysical events do not appear to win races against each other in an ordered fashion.
So there may be infinitesimal spacetime intervals, and so any quantity that depends on spacetime intervals has an infinite set of values to choose from.
Absent a description of gravity-matter interaction when matter's small-scale behaviours are relevant, we cannot really preclude the possibility of building a perfect square in an unreasonable (but nevertheless physical) local patch of dynamical spacetime, such that the microscopic behaviour of the latter offsets the odd quantum mechanical contributions to the square. At best we can try to place limits on how long such a system could survive (it could last a very long time in the cold sparse phase of the universe).
> How does analogue vs digital (assuming you mean that analogue) matter here? You'd also want to specify which "digital physics" you want to rely on.
In the kind of "digital physics" where you have a fixed grid it would be possible to create a truly perfect square, that's all I was referring to. (I'm well aware that such physics would be incompatible with Lorentz invariance and thus unlike our real universe).
This Yablo's paradox seem self referential to me. The statements are making claims about a series of statements of which they themselves are part of. I see the statements only making claims about subsequent statements... but still.
How about, rather that banning "self references", you have a more carefull phrasing requiring all structures to be fully and independently defined before you start asking questions (or making claims) about them? (No side effects from the question please).
Does this avoid all Goedelish paradoxes?
It depends what you mean by a Godelish paradox. Godel proved that there are statements which are true, but unprovable. To me, that's quite a paradox, and there's no escaping it.
Hmm, maybe I just answered my own question. You can't define the set of integers without using elements of the set of integers. Like Peano's successor function. And if you have that power, you can state paradoxes. Like the above mentioned Yablo's paradox. ?
You can also give up recursive enumerability. `True Arithmetic`, which takes as axioms all of the true statements in PA is certainly complete and consistent.
I like very much the program x virus example/citation.. but I would put it in the other way around:
"A program can find all virus, unless the operating system is a virus itself."
"Digital Physics" (the movie) is now free on Amazon Prime. It is also available for rent/purchase on iTunes and Vimeo, in case you are kind enough to support an independent filmmaker:) Come explore the world of self-reference, infinity, complexity, Gödel & Turing, and psychedelics with Khatchig!!
You almost certainly have had to debug a Gödelian paradox in your day-to-day programming. It's just that programmers call it "nontermination" or "infinite loops".
In 1952 the logician Martin Löb invented something called "provability logic" as a way to formulate Gödel's theorem more abstractly, so that we could see how the proof worked without having to work with explicit numerical encodings of formulas. (Think of this as the difference between working with strings versus abstract syntax trees.)
His version of the proof is now called Löb's theorem, and its structure is almost identical to what logicians call Curry's paradox, and which (via the Curry-Howard correspondence) programmers know as the Y combinator. The Y combinator is used to implement recursion in the lambda calculus, specifically including the ability to go into infinite loops.
Isn't Gödel's incompleteness a consequence of overly ambitious material implication properties? When you look at the truth table:
A | B | A -> B
0 | 0 | 1
0 | 1 | 1
1 | 0 | 0
1 | 1 | 1
I fail to see why all except for 1 -> 0 = 0 aren't undefined. I understand reasoning behind why this was done, but mixing unrelated predicates seems like a generally bad idea, even if it allows mechanical proofs.
Aren't there already "complete" systems like relevance logic? Now with computers we can perhaps make proofs we need "relevant" instead of being based on fundamentally incomplete though "simpler" logic?
Logic already has separate symbols for 'A implies B' and 'A proves B', where the first can be considered equivalent to '(not A) or B' for all intents and purposes. Since 'A proves B' seems like the very definition of relevance, the only part you could possibly object to is that 'A proves B' implies 'A implies B', but that's given since the alternative would lead to a contradiction where A proves B, but B is false while A is not.
Also, if I understand you correctly you're trying to 'fix' incompleteness by making A -> B undecidable, which seems like it would achieve the opposite.
The first incompleteness theorem shows that, in a sense, the culprit of a logic's incompleteness is not its "simplicity" but its "complexity": if the logic is rich enough to include Peano arithmetic, then it is incomplete.
Compared to mathematics in general, a complete logic system is far less powerful and cannot be used to prove nearly as many interesting things.
Well no, Gödel's incompleteness theorem doesn't really have anything to do with material implication. It tells us that there is some formula G such that neither G nor ¬G is provable. Proof systems for relevance logic restrict valid derivations compared to classical propositional logic (relevance logic requires you to use the antecedent), so they can prove even fewer things.
"is false" doesn't mean anything in Godel's system. That's too high level and imprecise. We're dealing with only symbol manipulation here. We only have provability (which really is "there exists a derivation for") - we don't have "truth".
[1] https://www.amazon.ca/Undecidable-Propositions-Principia-Mat...