Gödel and the limits of logic (2006)(plus.maths.org) |
Gödel and the limits of logic (2006)(plus.maths.org) |
[1] https://www.amazon.ca/Undecidable-Propositions-Principia-Mat...
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.
[1]: https://www.amazon.com/Computability-Logic-George-S-Boolos/d...
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.
[0] http://www.mit.edu/~yablo/pwsr.pdf
[1] http://ferenc.andrasek.hu/papersybprx/jcbeal_is_yablo_non_ci...
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
...
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?
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.
I blogged about this last year:
http://semantic-domain.blogspot.co.uk/2016/05/lobs-theorem-i...
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?
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.
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.
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).
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).
You can escape incompleteness with less powerfull axiomatic systems. But then you can't define the set of integers. (correct me if I'm wrong).
Discretization is not really the problem: you instead have to fix the definite position and momentum of the microscopic components of the square such that all the parts of it stay in place relative to one another and to the total arrangement of the shape they collectively form.
Switching to a taxicab geometry doesn't change the tendency of matter to move around; it only defines the points in which matter might be found in principle, and where it can never be found, ever.
In effect, the dynamism of spacetime is a red herring (we have difficulties building ideal spheres in flat space, theoretically speaking), and spacetime geometry (in the sense of minimal lengths vs infinite differentiability) is at best a marginal contribution to the problem.
While Lorentz invariance is essentially what blocks the quantization of energy, you can still have a discretized spacetime that preserves Lorentz invariance. One broad approach to that involves a Lorentz contraction on the spacings between the allowed points, so that observers may disagree on the lengths of objects marked off in Cartesian coordinates on the fundamental lattice spacings. In particular, even in the absence of gravitation, one observer will conclude a small object has a definite lattice length while a generic accelerated observer (and at least some boosted observers) will conclude that the same small object's length is in superposition.
Additionally, one may quantize lengths and times as in a Snyder spacetime, and still recover Lorentz invariance (or at the very least do away with preferred frames; things are tricky where boosts are high and ultimately it is likely impossible to recover the Lorentz subgroup in its entirety) in a quite natural fit with a deformation of Special Relativity.
Unfortunately we still have GR with its strong successes and several viable models which have minimum length scales. So at least at the energy limits we have access to now, we can't really make a concrete choice about which better describes our universe. In part that's because almost all these minimal-length theories are carefully designed to reproduce General Relativity in some limit because of its strong successes.
[0] https://en.wikipedia.org/wiki/Presburger_arithmetic [1] https://en.wikipedia.org/wiki/Robinson_arithmetic
(An amusing practical solution to the halting problem is to run two interpreters in parallel, with one running twice as fast as the other. If their states match after starting, the program is in a loop. This trick was sometimes used in the batch computing era to catch beginner student programs that were in a loop before they wasted much CPU time. Programs with long cycles wouldn't be caught, but that was usually not the problem with beginner programs.)
So what really bothers us about the halting theorem is that -- in general -- you cannot tell what a program will do with some input any faster than actually running it, and this, bounded halting, is not something we can work around.
Neither incompleteness nor undecidability imply the other[0].
[0] https://en.wikipedia.org/wiki/Decidability_(logic)#Relations...
In fact, when Gödel saw Turing's work and was convinced that Turing indeed captured the general notion of a formal system, he said that the incompleteness theorem was finally satisfactorily proven for all formal systems.