The Strengthened Liar and Paradoxes of Incompleteness
HTML-код
- Опубликовано: 31 май 2024
- The Liar's Statement is one the most infamous problems in logic, but less well-understood is this paradox's connection to the concept of formal incompleteness. Indeed a close examination of this relationship produces an unexpected connection, leading us to ask - are some of the most famous theorems that have come out of mathematics, logic, and computability over the last century nothing more than a trivial application of reasoning known as the Strengthened Liar?
Content:
00:00 - Intro
00:57 - The Liar's Paradox and Incompleteness
05:53 - The Meaning of Incompleteness
09:45 - The Strengthened Liar 
Наука
![Eminem - Houdini [Official Music Video]](http://i.ytimg.com/vi/22tVWwmTie8/mqdefault.jpg)
Dialect moved from physics to logic and I'm glad to be riding along. Please know that the content you produce is highly appreciated!
As the universe operates anything but intuitively logical, it is a crucial skill to be able to identify a provable reality vs a mere mathematical solution.
This is what makes the multiverse idea and string theory's hidden dimensions just fantasy. However, block time is proven i.e. having no freewill is proven via the constant speed of light. Yet how many people believe they have no freewill..
The halting problem is a nicer way of making this issue much more tangible in my opinion. If you have a computer program and it really does halt then you could imagine simulating it all the way out to the halting state in finite time. It seems like there must be a fact of the matter about whether it would eventually halt or not. But Turing showed this question is computationally undecidable in general through a pretty simple proof, and this also implies both Tarski's undefinability theorem and the incompleteness theorems.
Exactly. The halting problem can be expressed using pure math symbols, and is undecidable, proof by diagonalization.
Not only that. From the Halting problem follows Rice's Theorem, which informally can be read as "for a sufficiently complex program, you can't predict what it will do just looking at the source code." And "sufficiently complex" is really, really simple. So right there you can prove things like "your compiler will always risk outputting code you'll never actually run" and "your tests will always risk not hitting the conditions that demonstrate you have a mistake in the code." It's an incredibly powerful statement for computer science.
@@darrennew8211 for a sufficiently complex program with a sufficiently infinite memory of sufficiently all-finite access time
@@tricky778 No, it doesn't need even an unbounded amount of memory or time, let alone an infinite amount. You can figure out if a bounded machine halts, but you can't do it merely by looking at the code of the program without actually simulating it. So, basically, run it for long enough that it's either looping or halted, and then you know. But you still wind up having to run the machine to determine the answer.
@@darrennew8211 no, you don't have to simulate the machine if it has bounded memory, although you might argue there are some program snippets that can be written for some iterations of which the analysis is equivalent to simulation. I don't think that qualifies to be called simulating the machine because the latter phrase implies writing an emulator and analysing the state to synthesise a prover rather than finding that you can transform a subprover into a emulator.
The video is generally good, but I find some statements to be quite questionable.
7:06 - "By showing that an absurd self-referential statement could be constructed in almost solely mathematical terms, one could argue that Gödel was cleverly demonstrating that mathematics was merely a language like any other and therefore subject to all of its usual foibles".
That is inaccurate (and it's a relatively common misconception around Gödel incompleteness theorems). First of all, Gödel theorems are about formal systems, not about "math" in general. Like all theorems, they have hypothesis, and if those are not satisfied, the results do not follow. Gödel theorems apply only to _some_ formal systems, but not to others, and not to _all_ formal systems. It was proved that, for example, Boolean Algebra (aka, propositional logic) is both complete and consistent formal system. In fact, Boolean Algebra is "perfect" (perfect, in this context, means: complete + consistent + decidable). Euclidean geometry is also a notable exception to Gödel incompleteness theorems.
Secondly, it is well-known that mathematics, when viewed as a language (which is quite restrictive view, but let's go along with it), is a _formal_ language, which natural languages (such as English) simply are not. The differences are many, so concluding that "[...] mathematics was merely a language like any other" is just wrong.
7:51 - "The validity of every incompleteness theorem boils down to whether or not you believe the sentence "This statement is unprovable." is truly a valid paradox".
This is excessive, to put it mildly. The word "believe", here, is really inappropriate: by using that word, it makes it sound like mathematics is a matter of belief (basically a religion). Would you say: "The validity of 2+2=4 boils down to whether or not you believe in addition"? I hope no. Theorems are, well, theorems: their validity is an objective matter (proof verification, etc.), not a matter of belief.
In summary, while I found the video quite enjoyable, I also found it does not manage to go past some misconceptions about Gödel incompleteness theorems. Advanced theorems of mathematical logic are hard to correctly "translate" in laymen terms: analogies, metaphors, and informal descriptions can be used. But we need to be very careful about them, because, if we take them too far, we risk losing key details (as the saying goes, "the devil is in the details").
We addressed the fact that some system of formal logic can be considered complete towards the end of the video, but we think your objection here doesn't really take into account what is meant by the word "formal". Formal just means your language conforms to more specific and agreed-upon rules than non-formal languages, but the implication and meaning of something doesn't change simply because the language is "formal". Indeed, Gödel is often argued to be showing that if you want your math to be expressive and powerful enough to handle certain systems, you have to adopt particular tools of language that lead to incompleteness. This of course, would only be profound if you didn't believe math was a language to begin, and rather treated it as something almost religiously existing of its own accord, which was the case of the Hilbert Program.
Mathematics intrinsically is belief. No "proof" is ever objective; it relies on assuming certain axioms. Nothing proves those axioms. Furthermore, you have to assume inference rules, which nothing can prove either. "2 + 2 = 4" is not a universal objective truth, and there are plenty of systems in physics where basic addition isn't useful and 2 + 2 doesn't equal four. (Honestly, in our opinion, a large part of the reverence for mathematics just stems from misplaced religious feeling.) So yes, if you don't believe the Liar's Paradox is significant, it would be extremely inconsistent to then go on and say that you do believe Gödel's Theorem is significant. Now, one can make the case that the Liar's Paradox is significant, but that's a different matter...
@@dialectphilosophy Firstly, thanks for the reply, and I would like to point out that, despite my criticism, I did find the video enjoyable and the quality (animation, special effects, etc.) high. I want to make clear that the criticism is precisely aimed at particular statements, but does not detract from the video as a whole.
Breaking down the arguments.
1. Formal language vs non-formal languages - Here I have many things to say, but it would take too long to properly explain why I think formal languages and non-formal languages are fundamentally different.
2. "Mathematics intrinsically is belief". That's an interesting point of view, and I'm sure you are not the only one upholding it. But do you have any evidence to back it up?
3. ""2 + 2 = 4" is not a universal objective truth". That's a remarkable claim. Can you prove it? Going a step back: are there any objective truths? Or even more basic: are there any truths at all?
4. "there are plenty of systems in physics where basic addition isn't useful and 2 + 2 doesn't equal four" - I have some doubts regarding the second part of the claim: can you show a physical system where 2+2 does not equal 4? In fact, are physical systems even relevant to show whether 2+2=4? From Wikipedia (page "Mathematics"): _Although mathematics is extensively used for modeling phenomena, the fundamental truths of mathematics are independent from any scientific experimentation_ .
5. "No "proof" is ever objective; it relies on assuming certain axioms. Nothing proves those axioms." - Boolean Algebra has literally zero axioms. And yet, it does have theorems. As a side-note, I think we fundamentally disagree on the meaning of "objective". For example, to me, relying on assuming certain axioms doesn't detract from the objectivity of a proof (regardless of what we think of said axioms).
6. "Furthermore, you have to assume inference rules, which nothing can prove either". But do we need to "prove" inference rules? At a basic level, this sounds like the fallacy of arguing against the principle of non-contradiction. We would still dismiss a contradictory argument even if we didn't have a proof of the principle of non-contradiction. What about nonsensical arguments? Would we not reject them, despite (natural language) "implication" having no proof either?
At a deeper level, there are formal systems (again, Boolean Algebra) where inference rules aren't truly "rules" at all - they are just definitions (of some particular functions, namely, Boolean operators). If we agree that definitions aren't assumptions, then we can still do inference without assumptions.
I understand your final (and probably most important) argument about the link between the Liar Paradox and Gödel theorems. I find that an argument can be reasonably made. Yet, if we start from "mathematics intrinsically is belief", I think the Liar Paradox (and Gödel incompleteness) is the least of your problems.
For me, Godel's incompleteness theorem is made less scary/problematic when you realise that language itself can only construct a *countably* infinite set of ideas, even though we assume an *uncountably* infinite set of numbers regularly without issues. It's not so much trying to create a paradox as it is saying that there will always be indeterminate things which are not worth discussing (unless if you find it fun) because we can't know anything with the tools we have. It's like trying to discuss what lies "within" a black hole. It's a meaningless question, albeit fun to think about, because we have no idea what actually happens to matter that dense. I see Godel's incompleteness in new light after reading Kant's Critique of Reason.
Interested to see how you will animate Godel numbering, it's a fascinating proof and I feel like you will actually do a good job of demonstrating it.
Thank you! We're a big fan of Kant here, and know exactly what you mean. Also, it's interesting you bring up the uncountability aspect to the argument, since it was the uncountability of real numbers which was demonstrated by Cantor's original diagonalization argument, and it was that argument in turn which inspired Richard's Paradox, which in turn inspired Gödel's Theorem. All these things definitely seem connected in one way or another, but it's teasing out what exactly these connections are which are the difficult part.
@@dialectphilosophy @dialectphilosophy you said accelaration is not the solution of twin paradox then what's the real solution of twin paradox?you stopped making video on it and never told the real solution of twin paradox?
I taught a seminar on the first incompleteness theorem presenting Godel's proof, and we eventually reached this conclusion. A proof must terminate, so proofs are countable, but a proposition with a universal quantifier ( for all n, P(n) ), like Godel's statement, is itself a countably infinite conjunction of propositions ( P(1) and P(2) and P(3) and ... ). If one presumes to enumerate the provable conjunctions of propositions, one can construct by diagonalization a conjunction of propositions that cannot be on the list and so cannot be provable even though each proposition is part of a provable conjunction of propositions.
At that point, I lost interest in the subject. Is mental masturbation any more useful than the literal kind?
@@pwinsider007 I'm also waiting to understand relativity.
@@restonthewindThere are grounds for asserting the equivalency of (a) a universally quantified claim and (b) a conjunction of claims, as you described, when quantifying over a finite domain of discourse.
From this, it does not follow that there are grounds for doing so when that domain is countably infinite -- much less uncountably infinite.
You just don't want me to get anything done for the next 15 minutes, huh?
What do you mean
@@CHUSLAAM.jindabaad2496 I often put videos on for background noise, but whenever I find a good one, I end up glued to the screen 😆
@@sudokode still what do you mean 😁😂
@@CHUSLAAM.jindabaad2496 lol meaning instead of doing the task at hand, I'm watching this 15 minute video. Dialect is one of those once in a while channels that I have alerts on for 👌
@@sudokode oh got it bro 🤡😁
BTW thnx for your replies ❤️😁
i think the trivial take of the paradox is that thinking that it only contradicts with itself but the deeper problem is that it contradicts with the assumption that every statement can only be either true or false
I really appreciate how your videos tackle questions that are often glossed over even many in university-level courses.
I have been thinking about this problem for some time now and one major conclusion that I have come to is that these problems are snowclones of the stone paradox. The stone paradox is a popular variant of an omnipotence paradox. "can god create a stone so heavy that he could not lift it." Either he could not create the stone or he could not lift it. Can I create a Turing machine which cannot be predicted whether it halts or not. Can I create a set that is not contained in any other set. Can I create a statement that cannot be determined if it is true or false. Can I create a mathematical theorem that cannot be proved. There are two principles that are in conflict with one another. One principle is the ability to create any object. (statement, turing machine, set etc.) The other principle is being able to FULLY understand ALL of the properties of these objects. These two principles are in conflict with one another. Either some objects of a particular type cannot be created or some objects cannot be fully understood.
I thought from a long time now that incompleteness theorem was some sort of meaningless artifacts... I'm glad to find a video going in that sense... Thank you 😊
I appreciate how you presented the Nelson-Grelling paradox before moving on to start to tackle these better-known paradoxes. Together, the presentations suggest that the real issue is understanding the nontrivial implications of bivalency. -Tom
Great! I was really looking forward to a new video on logic, and here it is. Amazing stuff!
Undecidabilty truly exists. The physical meaning of undecidable statements is that their computation never ends. We cannot just look into them and decide if they are true or false, we have to play out (compute) their logic.
The strenghtened liar paradoxe is based on the fact that you accept the law of excluded middle which is not the case in every logic but is indeed used in the classic logic. In the end logic is just a set of rules, these rules even as trivial as they seem can be rejected.
That seems like a perfectly valid interpretation
@@dialectphilosophy @dialectphilosophy you said accelaration is not the solution of twin paradox then what's the real solution of twin paradox?you stopped making video on it and never told the real solution of twin paradox?
@@dialectphilosophy @dialectphilosophy you said accelaration is not the solution of twin paradox then what's the real solution of twin paradox?you stopped making video on it and never told the real solution of twin paradox?
Wonderful! I just can't wait for your next upload.
I want to ask about your footnote at 11:37, which I will copy here in full:
"The traditional presentation of the Strengthened Liar takes the two mutual assertions listed above to be proof of a further paradox, arguing that a given Liar statement L cannot have the truth values "true" and "indeterminate" at the same time without contradiction. However, the statements "L is true" and "L is indeterminate" have somewhat different contexts; the former asserts the fact that L does not belong [to] the true category, while the latter asserts the fact that L does belong to the indeterminate category. These truth values not being mutually exclusive, there is no contradiction, and the strengthened liar is not actually in any way "strengthened". This reasoning, as will be seen, becomes crucial to the thinking that underpins the metamathematical considerations of the incompleteness theorems of Gödel, Turing, and Tarski."
Your second sentence seems wrong to me. Let me unpack my problem with it. You identify two statements, which I will call "P" and "Q".
P: "L is true".
Q: "L is indeterminate".
You then go on to say that P says that L is NOT true. (Specifically, you say that P "asserts the fact that L does not belong [to] the true category"). Actually, P is saying the opposite. P is saying that L IS true.
So P definitely does contradict Q.
While yes, you could unpack L as "L is not true" and then re-write P as
P: "'L is not true' is true."
You could do this ad infinitum. You seem to have made an arbitrary choice to only unpack L's self-reference one time, for the sake of your argument. You danced around the contradiction between P and Q.
Agreed. Interestingly, Dialect's conclusion was opposite in video about Grelling-Nelson paradox
This video has helped me get a new understanding. I think of the 'liar paradox' as a natural constructor of inconsistency in a given theory. So for me the three theorems states that their corresponding systems are very solid in the sense we cannot construct a valid proof of a statement that implies a paradox (of the same nature that the liar). The incompleteness therefore seems to be a guardian forbiding access to constructions that can give birth to the inconsistency of the theory.
I am ( and as I look back on my life have always been) a DEVOUT skeptic.
Your videos talk about many of the issues I always have (and still do BTW) struggled with.
Thank you for your efforts. When I have consumed all of your inputs, I will have to process all of them, as a whole, before I can even think (at more than the surface level) about their implications.
Thank you for your service.
I'm blown away by the quality of the content by Dialect.
Been waiting for this !! Thx
Coincidentally, I just started on Davidson's _Truth and Predication._ Are you considering covering Tarski's semantic conception of truth, since it does take the self-reference out of the picture? I'm usually with most philosophers in barring The Liar from being a truth-bearer, and just treating it as indexical.
You need to up your game, buddy. The purpose of lying is to deceive. Any competent liar would have the ability to lie with only truth statement.
In more mature environment, where competent liars breeds competent truth detectors, liars morph into … something else.
@@patrickchuan4550 @Patrick Chuan To clarify: I'm using "The Liar" as shorthand for The Liar's Paradox, following the convention of the video - nothing to do with deception. Truth-bearers are things which can have a truth-value (TRUE or FALSE), and an indexical statement is one whose truth-value relies on when, where and/or who uttered it.
@Eta Agreed. Liar is a syntactic paradox that manifests strictly across lines of a proof. No one who uses a language would use it for anything. I get why Dialect is targeting this, if only because of all the hype around Incompleteness. But really it's just a result that a very niche community used as a kind of self-corrective of foundationalist excess. WGAF?
That said, i think T-sentences would be interpreted by Dialect as the "strengthened" Liar. I"m totally with following Davidson in terms of philosophy of language, which makes this all a tempest in a teapot. Particularly the last paragraph of "Nice Derangement of Epitaphs."😂
Yo this production quality is crazy this cannel needs way more subs
It may very well turn out that unprovability and incompleteness theorems are merely that of semantics. Trivial perhaps in the sense of comprehension, yet the terminology it introduces pivotal to our understanding of other emerging phenomena. The narrative construct of reality appears to be strongly at play here.
Your work is a subject of deep personal gratitude, it is hard to express the relief it brings when one sees someone else capable of expressing the formerly formless tempests of thought into tractable and tangible form like you have done with this work. 🙏
Thank you for your kind words! We are still in the process of studying Gödel's Theorem, with the hope of bringing a series of videos that will completely walk-through and demystify the proof. But it is certainly insightful to suggest, as you do, that incompleteness may very well be just about semantics at the end of the day, but that semantics is no less important given its pivotal role in how we form theories of our reality.
@@dialectphilosophythat is the most concise and succinct description of my understanding of reality and jotted down effortlessly. You are the @delvetv of my physics! Being on the spectrum makes formulating my thoughts into words challenging, the absence of the visual imagery of general relativity as a flowing river had me stuck.
Was it a few things fell into place. It would appear that Claude Shannon is to Einstein what Newton is to Galileo. Each respectively squaring the circle of the other. Notiers theorem cones to the rescue again. Newtonian physics are two-dimensional, and Galileo provided the link on how energy flows from 1D to 2D giving us potential and kinetic energy that is conserved. There exists a similar conservation in space-time with the flow of energy being expressed in the conservation thermal and informational entropy. Shannon providing the link in this case allowing for the interpretation of the 3 expected discontinuities demonstrated in the Heisenberg uncertainty principle, the wave function, and the measuring problem.
Right on. Thanks for sharing.
As Godel said, the crucial thing about his theorem is that it's 'not a logical paradox but a mathematical theorem within an absolutely uncontroversial part of mathematics (finitary number theory or combinatorics).' The Godel-sentence corresponds to a completely concrete statement to the effect that there is no number whose decimal representation meets a certain list of concrete criteria. You might want to read a rigorous general-audience book on Godel's theorem like Torkel Franzén's 'Gödel's Theorem: An Incomplete Guide To Its Use And Abuse.'
I find the presentation intriguing. But I wonder what is being presented here. Are these Dialect's own thoughts? Or is this a condensed presentation of peer-reviewed work from multiple experts in the field? After all, while I do have some familiarity with the discussed concepts, I am by no means on a level where can I confidently asses the correctness of what is presented here. For that reason, I will put significant value into the opinions of experts on this subject matter and I'd appreciate it if Dialect could share any references to such work.
These are our own thoughts, presented after a great deal of study of the topics. However, this work should be considered "investigative" not "conclusive" as we are still looking into the theorems and their meaning. The problem you will find with the "opinion of experts" is that they offer little consensus about what the theorems actually mean. The theorem itself is so esoteric almost no one understands it, and those who claim they do argue with one another about differences in meaning. To us, the wide divergence in professional interpretations is a big red flag that something is at issue with the theorem.
As to resources, in this video we consulted the works of Gödel and Tarksi directly. The English translation of Gödel's Incompleteness Theorem we sourced from www.jamesrmeyer.com, and Tarksi's "On the Semantic Conception of Truth" can be found in multiple places via a quick googling.
@@dialectphilosophywho are you behind Dialect? The endings of each of your videos seems very mysterious, hopefully your not some type of esoteric philosophical cult or string theorist grifters 😂. The way you tease a higher understanding to these deep questions of the universe is intriguing. When is the other shoe going to drop?
@@opiesmith9270 Don't worry, we are a happy, loving cult, with plenty of room for more philosophic esotericism...
These videos are genius, please put them all on DVD and I wil $$$BUY$$$ it
I have a question about including the halting problem in this list.
I have seen explanations of it that does not seem to refer to the liars paradox.
Is this a misunderstanding because I lack the needed theoretical framework?
There are a few ways to derive the halting problem, but they are essentially equivalent as at some point or another they all invoke a means of self-reference. Indeed in its most immediate and evident form, the halting problem can be framed as a liar's paradox.
@@dialectphilosophy I can see what you are getting at, but does this not mean that all proofs by contradiction can be boiled down to the liars paradox? After all, they assume something is true but then a later part contradicts it. The liars paradox can be thought of as simplest form of proof by contradiction.
the halting problem can be proven with some construction similar to the liar. thats true.
by proving it you have shown that at least one non computable problem exists.
Thanks. I lack the mathematical / logical understanding to make much of this sort of thing one way or another. I do enjoy watching / reading about it, though. However, I can say that it teaches me something important. It teaches me about the limits of any definable system, which has application to life in general. In designing systems, one simply cannot make them perfect; there will always be possible events that lie entirely outside the system's parameters. I think the best we can do is to design simple, flexible systems, and get good people to use them; people who are aware of the system's limitations, as well as their own. Unfortunately, humans - and the systems they've put in place - hate this sort of thing. Bureaucracy, hierarchy, pecking order, rule of law... People don't like others who step 'out of bounds', or overstep their authority. Humans have very strict, pyramidal ideas about such things, which go back to tribal, feudal, military, city-state notions that are now thoroughly outmoded. But explain that to a prospective employer, & you won't get the job! ;) tavi.
An intuitionist's answer would be if you want to answer whether something is true you need to construct it. Since the Gödel statement explicitly says it is not provable (there is not theorem-number for this statement due to the diagonalization), it cannot be true from an intuitionist standpoint.
Really would enjoy a proper video on philosophy, especially Kant and Hegel. Would really shed some light on these kinds of problems
not sure if they could say anything interesting about this, especially if we remind ourselves about Hegels "logic"
Hello Dialect, can you answer me this question? As everyone knows travelling at the speed of light C means not travelling along the Time axis of a 4D space-time diagram. When a body travels at less than C such as a particle with Mass then it moves more along the Time Axis and less along the Space axis. This can be represented with a line that is of fixed length C that moves through the 4D diagram at an angle related to speed. Going along with this math principle then a body in an inertial frame is moving at C. This is difficult for many to accept and understand however as you know this is mathmatically correct. The thing is if we are moving a C in Time then does it not follow that rotating the 4D spacetime we can be observed from another prespective of an observer in Time that we and all that are in that inertial frame, are now seen as massless particles with differing energies. In other words if we are moving at C along the Time axis.. do we become like a photon?
and consequently all Massless particles must therefore aquire mass?
I have always had the idea that the large scale universe moves away in a progressively increasing noninertial frame and is length contracted back into the small scale Universe.. kind of like a 4D mobius strip, and as such there is a parallel mirror Universe the same as ours hidden in the Time dimension. Indeed is has been said that Time behaves more space like and Space more Time like in Blackholes.
So again what do think it mean to you that we move at C in Time?
You don't understand, for example in the halting problem, saying that the halting problem contradiction program is a "trivial program that does not have any significance about the vast set of all computer programs", is not accurate. I am going to loosely use the term "subgraph minor" in a very generalized sense, in that, in the context I will be using it, it will mean that a certain program A is embedded inside another program B, and part of its computation involves A. I am not using the phrase "subgraph minor" in its usual sense, I abstractly generalized it and hopefully you can derive its generalized meaning. Call the hypothetical program that is supposed to decide of another program halts, halts(). Call the halting problem program H, which says "H = if halts(me) is true, dont halt, otherwise, halt". I can embed H as a subgraph minor in any other computer program, in fact, I can show that it can **emerge** as a subgraph minor of any other computer program unpredictably. You don't know if H emerges somewhere in the computation of the program, you don't know. A computer can't tell. It can be anywhere.
Because H can be explicitly, or emerge, as a subgraph minor of an infinite variety of computer programs, then H affects an infinite family of computer programs, and thus prevents computation on an infinite variety of tasks. Far, far, far, from trivial. This H can be embedded into infinite computer programs and you won't be able to tell it is there -- especially because it can appear through emergence. Call the set S the set of all computer programs that are either H, or have H as a subgraph minor (either emergenty or explicitly). The real kicker is that you can show that H, if existed, would allow computers to output more things not previously producible from the set of programs in the complement of S. Meaning that computers cannot output certain sequences of 1s and 0s.
These sequences of 1s and 0s that a computer cannot output are *dense/equidistributed* in the set of all possible strings of 1s and 0s, meaning, these sequences are everywhere unpredictably. There are holes EVERYWHERE in the set of all things that a computer can compute. A computer can't know where they are and because it is dense/equidistributed in the set, it will affect computers uniformly over the vast distribution of all things that are may or may not be computable.
Don't believe me? One way to see that a theorem is in correspondence with reality is if the direct relevant consequences of that theorem are also implied by other previously known theorems. The relevant direct consequence of the halting problem in question is, "computers cannot output certain sequences of 1s and 0s"
But first, let's backtrack:
The whole task of the halting problem was to disprove the idea of a kind of Generalized Strong Turing Completeness. Turing Completeness means that any machine in question is isomorphic to a Turing Machine. But what does a Turing Machine do? We hope it means it can output anything, and so we can define Strong Turing Completeness: A machine possesses Strong Turing Completeness if it can output any infinite sequence of 1s and 0s. We know that a Turing Machine can output infinite sequences of 1s and 0s, take the digits of pi or e for example. But the question is if it can output all infinite sequences of 1s and 0s? The answer to this question is false, via uncountability. The set of all programs of finite length is computationally enumerable and is a countable infinity. You cannot provide a bijection between the set of all computer programs and all sequences of ones and zeros. Thus we have a failure of Strong Turing Completeness for any machine.
Here we have shown that the consequences of the halting problem theorem, namely that computers cannot output certain sequences of 1s and 0s, is also directly implied by yet another theorem about uncountability. What's more, the statement "computers cannot output certain sequences of 1s and 0s" is logically equivalent to the theorem of the halting problem, they both imply each other. Proof left as exercise to the reader (think Busy Beaver function). Thus, uncountability also proves the halting problem theorem. Even though they are different results.
I can go further and continue proving the statement "computers cannot output certain sequences of 1s and 0s" with other ways too, even besides uncountability and the halting problem, there's the Compression Theorem, which also implies it, and the Compression Theorem is a *combinatorial result* which doesn't rely on "philosophical handwavy ideas", combinatorics is the least hand-wavy thing in mathematics itself. Or even the uncomputability of Kolmogorov Complexity proves it too. The list goes on...
----------------------------------------------
As for the Incompleteness Theorem, one way to know it is true is if we have *seen its affects already upon us*, and we have: We already have empirical evidence that it is correct, take Goodstein's Theorem, Goodstein's Theorem is a true result in mathematics that is unprovable in Peano arithmetic. The Incompleteness Theorem already predicted them, and that is one. Here is another Paris-Harrington principle, or the Kruskal's tree theorem. These are all theorems that were unprovable in some axiomatic systems, but we managed to find other stronger axiomatic systems to prove them eventually. This was all predicted by Godel's Incompleteness Theorem.
Another commenter said:
>One explicitly constructable unprovable statement that might be essentially unique or might be just one amongst an infinitely vast and unconstrained set of statements and that's all the info we have.
I actually have the exact answer to your question. I have thought about this for YEARS.
Take
P -> G is unprovable
G -> P is true.
Two separate statements, not a relationship between a thing and itself, those are two separate statements.
You might say, "but but this 'trivial' statement has no bearing on and no consequence on any other statements other than itself, thus its is an isoated incidence"
But this is wrong. This relationship of P and G, can be embedded into other logical-relationships as a subgraph minor, and can emerge OUT of other logical-relationships as a subgraph minor in an emergent and non-explicit sense. I am using the term "subgraph minor" in a very generalized sense as a metaphor. It is only an educational metaphor to explain the nature of the concept I am describing. If you look up what a graph minor is, you will be able to understand my argument: This unprovability relationship can literally be embedded into certain other statements and you can't even tell by looking it it. Thus it will affect an infinite variety of relationships, nontrivially. And it will be unpredictable when this is unprovability relationship is a subgraph minor of some logical relationships because of emergence. Ie, something as simple as "every even number is the sum of 2 primes" can have this relationship embedded inside it deep within its emergent consequences, you can't tell.
It is far, far, from an isolated incidence. Statements and relationships such as these form a dense and equidistributed set amongst the distribution of all possible statements. A computer won't know where they are, a computer can't know where they are, and a computer will never know where they are.
So take that for "trivial".
:P
Also, to computer scientists and mathematicians, if you want to use the statements which I have said in this RUclips comment in any papers/research, please cite me and ask before hand :)
- Morphism.
The problem with comparing the liar's paradox to Gödel's construction to the liar's paradox is that Gödel's construction encodes the formal logic of the system it's written in into the statement. The liar's paradox assumes all of the rules you take for granted regarding English, truth, and more. Imagine if the liar's statement was as long as an English textbook... It wouldn't be such a popular riddle.
It's possible with a Gödel statement to reformulate the original rules to include the truth, or even the falsehood of the statement as a given (i.e. as an axiom). The result is a *new* system that requires a new statement to be formulated with the new rules in order to have a "paradox", but then this new statement is different. From the point of view of the liar's paradox, changing the rules of language/truth would alter the meaning of "this statement", since the statement changes when the rules around it change.
This is what happens with things like the axiom of choice (in ZF theory). The axiom of choice cannot be proven or disproven, but we can assume its truth or falsehood and to develop two new systems of logic from those assumptions. What Gödel's proof shows is that no matter how carefully you create your system of logic, there are always statements that are like this.
To me, I see to problem with these statements being trivial. That is their purpose, to trivially show an inconsistency with the axioms of a given system. Their purpose is explicitly not to prove can be undefined, but to disprove that something can't be undefined.
Perhaps one day we will come up with a structured system that does not have this problem, but to me these statements serve their purpose correctly. After all, you only need one example of something existing to prove it exists.
These models are black swans, if you will. Obvious, even trivial contradictions to the idea that all behavior in the system they are created within could be defined or evaluated.
Is there a way to contact the creator of this channel, directly? I have a subject I would love for him to do.
Whenever dialect uploads should be a national holiday. Such good content
Titel sounds great already!
What
Excellent video. I'm hoping we can get a similar analysis of Entanglement and Bell's Theorm.
One day...
@@dialectphilosophy Please make it soon!
@@dialectphilosophy Yes, please do Bell’s theorem/entanglement. I've watched scores of videos on it already, but if you manage to present it the way you've presented physics subjects so far, I may - just may - actually have a shot at understanding (and accepting) it lol.
@@tabbyheraclitus7835 Well thank you for your confidence! We hope to start approaching QM topics by the end of this summer, so maybe we'll get to it sooner rather than later
Anyway!, I like your post' on RUclips. It's vitamines for the brain. So a big thank for your work. It is done very professionel and i feel it is done with passion and love ❤️
I would assert that math is not the God that we thought it was. Faith is back in the drivers seat folks.
I'm encouraged buy this channel. Finally some folks are applying rigor to the rigor assumed to be in math and science and coming up with sensible explanations.
Try the example of Russell's Paradox.
Set A = {the set of all sets that do not contain themselves}
Suppose we define two other sets.
Set A1 = Every set that is in Set A but not Set A itself.
Set A2 = Every set that is in Set A and also Set A itself.
Both of these are perfectly good sets that you can do whatever you want with, with no paradox or problem. (I guess, I haven't proven that.)
So the problem is that any definition you can make for a set is supposed to be workable.
And the general case of Russell's Paradox is:
Set B contains element x and also does not contain element x.
Why is that supposed to work? Are we supposed to have a language which does not allow us to create self-contradictory statements?
I definitely remember from my time as a philosophy student that Brouwer and his school of intuitionism considered Gödel theorems utterly trivial and I tended to agree 'intuitively' (hehe) but could you address that in a future video, ty in advance!
Sometimes, in mathematics and formal logic, intuition acts as a shortcut, and gets there first. The "hard part" (and "hard" may be an understatement here) is making it rigorous.
This is all just IMHO: Those self-referencing statements can be read in more than one way. It is possible to read (this statement is false) as ((this statement ist false) is false), but it's not necessary to create that recursion. Instead, (this statement) can be an external reference, so that the sentence is out of context. Ok, even if we deliberately go down the route of recursion, the solution is quite simple: It does not exist since the recursion never ends. One cannot read the terms in a recursion as valid states of a system, like intermediate results from a calculation are not the solution of it. It's a bit like finding out the color of a chamelion by putting it on top of another chamelion.
Thanks for interesting content like this. Love it :)
I don’t normally pick when people misuse “begs the question” but this video’s pretty pedantic so I think it bears noting that the phrase was misused 😄
"eck cetera"
Love you dialect
@@Wagon_Lord We pronounce it the street way 👀
Awesome!
The Liar's Paradox can be easily fixed: The *Liar's* "Paradox"
Logic deals with arguments.
"This statement is false." ....isn't a valid argument. It's a statement.
If we were to look at it and ask if it is a valid argument or not, we would find it's not valid. It's a conclusion without any premise claiming to support the conclusion, at best.
So, it would be given a truth-value of "unknown", instead of true or false.
Meaning: the video is spot on saying that the two statements are ostensibly the same. This points to something much deeper....
The difference, however, is that the strengthed liar is a valid conclusion when used with a premise or set of premises that support a claim. The "paradox" is giving a truth value to the argument being presented (the theorems mentioned).
It's a metaphysical means of finding physical evidence for truths.
In other words: Support I come up with a theorem that sounds ridiculous and, scientifically speaking, is absurd. If I claim that my theorem is purely conjecture, it will likely be ignored. However, (while unlikely with me being the author) the same theorem may contain some new way of viewing things that could lead to a deeper revelation about reality by others.
.....Then again: the truth of everything I've posted isn't provable. 🤷♂️
I only hope that you someday talk more about alternative logic formal systems/formal languages, such as paraconsistent logics, linear logic, fuzzy logic and even temporal logic.
These offer alternatives to the classical notion of "truth" one finds with Gödel, Tarski, Russel, Turing-Church and other classical logical positivists.
We considered discussing alternative constructions of logic in this video, but are still sorting out our feelings about them. Right now we are leaning toward the idea that "logic" is similar to math or science in the way of being a description or model of our reality, meaning that, as you suggest, it might be wise to choose to adopt a different, "alternative logic" model to better suit a theory of nature.
I do think self-reference paradoxes are telling us something profound, and that is that any set of abstract axioms will always contain a contradiction. That is why we cant simply deduce everything from pure thought, we will always have to run experiments and observe the real world to confirm whatever we think.
This video is a banger !
A linguistic statement, such as a mathematical formula, asserts (explicitly or implicitly) a specific relationship between two different [categories of] things (a subject and object). A linguistic statement that asserts a "relationship" between itself "and" itself is simply "useless" -- i.e. has no "utility", other than, perhaps, to demonstrate the "incompleteness" of its rules of grammar/syntax as not specifically and explicitly disallowing such statements as "invalid" (or at least "undefined", e.g. 1/0). It's a bit like writing a computer program that does nothing more than print out (or overwrite itself with) its own code -- what's the point / "purpose" / functional utility of that -- other than to expend CPU cycles -- or demonstrate the "trivial" case (e.g. "1 = 1" or "This is a linguistic statement.")?
SHAMELESS PLUG: Check out (read carefully -- it's a work in progress -- and thoughtfully) my "Anthropos Cartographer" meta-philosophy (a.k.a. 'Experiential Meta-Mechanics'; a.k.a. 'The Quantum Philosophy'; a.k.a. 'Networkology' ) in the comments at "What is a Worldview" (ruclips.net/video/AVAmY1HvExI/видео.html) Thanks
>A linguistic statement that asserts a "relationship" between itself "and" itself is simply "useless"
Watch this:
P -> G is unprovable
G -> P is true.
Two separate statements, not a relationship between a thing and itself, those are two separate statements.
You might say, "but but this 'trivial' statement has no bearing on and no consequence on any other statements other than itself, thus its is an isoated incidence"
But this is wrong. This relationship of P and G, can be embedded into other logical-relationships as a subgraph minor, and can emerge OUT of other logical-relationships as a subgraph minor in an emergent and non-explicit sense. Thus it will affect an infinite variety of relationships, nontrivially. And it will be unpredictable when this is a subgraph minor of some logical relationships because of emergence. Ie, something as simple as "every even number is the sum of 2 primes" can have this relationship embedded inside it deep within its emergent consequences, you can't tell.
Don't all of these systems have a circular nature that have no complete meaning? The real problem here is to try and understand what exactly axioms are and how they provide a structured system while at the same time not being fully and exactly clear on what it is that these axiomatic statements precisely are in the first place. It looks like we accept them on the basis of seeming self-evidence, but it is the 'seeming' that provides the initial solidity of these systems until we look more closely and see its circular nature. What I mean to say here is that meaning isn't exact and I have a hard time thinking that you could find a system that isn't contingent on some type of meaning based structure.
In my opinion, this shows how meaning itself is not, and can never be, exact. Strangely enough, we don't seem to require perfect definitions to use these systems which I find interesting. There seems to be objective consistency despite never being able to have perfect exactness in any system. I think this is potentially the more fundamental mystery; the ability for us to make connections and perceive meaning in a consistent and inter-subjective way where we didn't perceive any before.
That was spectacular. I have been working on these things for two decades and the author and I seem to be at about the exact same point of this. The author seemed about 100-fold more articulate than myself. He seems to have an identical view to mine on Gödel 1931 Incompleteness and Tarski Undefinability. I have additional technical details that support our identical views.
Feel free to share your work with us via our contact email! We've suspended our ambition to do a walk-through of Gödel's theorem for the time being, as we've made our way through it several times and still cannot quite fully penetrate the obscure symbolism of it.
@@dialectphilosophy I contacted you by email and also posted the key essence of the technical details that support our shared view immediately above. My system seems to be anchored in proof theory rather than model theory. Montague Semantics allows this to be extended to natural language reasoning.
Thank you man for this great, nice and incredible explanation, visualization...
D I A L E C T
Please humor my offtopic question regarding time dilation and length contraction... the thought experiments we use to support these are about observing moving clocks and objects.. but isn't the act of observation itself reception of light from those clocks and objects, and would hinder the correct result?
Also, these concepts arise out of the equivalence principle and the unchanging speed of light, as I understand. The first, I am completely ok with. But the second irks me to no end, although unfairly. I just cannot fathom how everything will contort and delay/hasten to make sure light stays at the same speed, but put that light in water and voila it has changed? I know it is not a logical criticism, but it makes me feel like there is something we are missing there.. I hope you take a moment to satisfy this fool's curiosity ... great videos thank you!
You're definitely on the right track of thinking. In the next three-four weeks there will be a video from us about that very subject.
What about sentences though like "this statement is neither true nor false"? Or even "this statement has no meaning"? Or "this statement is indeterminate"?
This has been said before, probably in the comment thread, however "This statement is a lie" and "This statement is unprovable" are somewhat different in that one is in the vernacular and the other is a mathematical statement. The formalism of mathematics is not exactly the same as regular speech. "This statement is unprovable" is likely true, in fact, since if it can be proven, it is an invalid assertion.
Binary logic is a useful but very "limited" construct. Analog also has its (human) limitations but does appear to more closely mimic the universe.
Everything in the universe exist somewhere in the balance between either -∞ and +∞ or 0 and +∞ to infinite degrees of precision.
Maybe the best we can do is create an approximation with fuzzy logic and remind ourselves that there is no "ultimate" true or false.
I agree that the perception of Godels incompleteness theorems suffer from popular mysticism, and very much require more contextualization. I especially appreciate how you compare the incompleteness theorems to the liar paradox, because it is, as you say, at the heart of the issue. I think you could have gone much further and explicitly though, and hope you will in subsequent videos, that the incompleteness and undefineability theorems aren't really at all about the arithmetic systems they are purported to be, but the logical systems in which their arithmetic systems are embedded in. And in all cases what's really going on is that they are able to construct a liar paradox within their system, and use that to prove by contradiction that the attempt to do something in full generality, such as define all the true or provable statements within this system, is impossible. A bit of a slight of hand, surely, because you'd ordinarily conceive of truth or provability as excluding those kinds of statements, and their method of constructing things like 'all true statements' only run into the problem because they start from the set of all possible formula(even malformed ones).
I don't agree with your interpretation of the strengthened liar paradox, though. There is a further paradox, and the reason that the strengthened liar paradox is in fact strengthened is that it actually frustrates the attempt to weasel out of the paradox with a third logical category of 'indeterminate': If it is indeterminate, then it is true, which is a paradox. The contexts you're trying to assert which differentiate those statements are the statement being viewed as a whole from the outside versus the self-reference from the inside. The fact that those references seem to take different values illustrates perfectly that the source of paradoxes, or rather the discontent with the existence of paradoxes, is trying to view logical statements as static when the real meaning of them is in their evaluation: a dynamic, computational process.
What the strengthened liar paradox demonstrates is that may not be a panacea to extend your logical system with a third truth-value of indeterminate, that it doesn't completely resolve paradoxes. And that should be right, because what indeterminacy really means is that the process of evaluating a statement does not terminate(the word terminate is even in the word indeterminate, terminating evaluation on the value of indeterminate is an abuse of language if not a paradox in itself); it's a statement about the process of evaluating a statement, not the value of the statement. And determining, in full generality, which statements' evaluations will definitely terminate or not is, supposedly, impossible: that is the halting problem.
I was comfortable with the halting problem, but you're making me second guess my assumptions(thanks!). What the proof seems to be actually saying is that any program made to determine whether a program halts can be made to return the erroneous(post factually) value on a program which invokes it. That seems like a dramatically different conclusion than the standard interpretation, and depending on what you mean by 'universal' halting, may be perfectly good enough to allow for what you'd call a solution of the problem. It also seems to be more a property of the invoking function, that it can flip whether it halts or not, than the halting algorithm itself(It reminds me of the idea that if you could predict the future, or were given a prediction of the future, you could change it with your free will). On the other hand, you could view it as the halting algorithm which is given the decision of whether to halt or loop the programs which would invoke it to try to thwart it(it could even log, separately, that "I told this function it would die/live forever to trick it into living/killing itself"). And given a real description of the halting algorithm, you would know whether it would return true/false/loop forever in this instance. A situation which is a far cry from 'a halting problem is unsolvable'.
Theoretical computer science is a bit divorced from practical application in this regard: as computer programmers, we determine whether our algorithms halt all the time. I have never seen an algorithm that I can't decide will halt or not; the algorithms which invoke halting algorithms seem to be a special class, and the problem should be re-framed as how halting algorithms fail rather than their flat impossibility, because both solving the halting problem practically and the special cases where it fails are interesting.
All that being said, I think it's ultimately naive to characterize all these theorems as essentially meaningless self-justifying exercises, to categorize them as gibberish is arguing with bad faith and missing anything actually interesting about them. The reason that the liar's paradox is significant, despite being a patently stupid statement, is that it is the simplest example of a statement whose evaluation results in a indeterminate loop, which is a class of logical behavior well worth understanding. What sets of statements/systems demonstrate similar behavior in a more complex way? Is it always a bug, or can it be a feature? And as to the question of whether or not those systems have any meaning in reality, I would point out that reality, apparently, never seems to terminate... and also references itself ubiquitously. There are isomorphisms(and automorphisms) between indeterminate logical systems(paired with an interpreter) and physical(time evolving) systems. Does that mean anything? Maybe. Seems like it does. It's true at least, and I'd like to see the details more fleshed out.
("from whence'" is redundant: 'whence' itself means 'from where'(and 'whither' means 'to where'. 'Whence derives Incompleteness...' is succinct and beautifully archaic. Keep it up I love your videos)
Thank you for watching and for your very excellent analysis! We're certainly open to the idea that the liar's paradox is significant in some way that is more subtle than what it first appears to be, and if one wishes to argue this, then arguing for the significance of incompleteness theorems certainly gets a whole lot easier. Possibly our issue is more along the lines of the fact that, if more people understood what level of similarity these incompleteness proofs bear to the liars paradox, they'd be less inclined to assign them such wide-ranging mystical interpretations in the first place.
And we have by no means made up our minds on this topic, as these mostly are first impressions coming from outside the subject. That said, your analysis of the halting problem and computability strikes us as being dead-on. We have made our way through Gödel's proof a few times already, and want to begin a video series on it, but we still are having a great deal of trouble understanding it and interpreting it. As such, it may be some time before we can come forward with any real significant insights, but nonetheless stay tuned!
Could this have something to with quantum indeterminacy?
You can find numerous academic papers arguing that quantum indeterminacy is related to formalistic incompleteness (we showed one in the video). It's certainly an intriguing idea, but we'd recommend caution and critical thinking before jumping to any conclusions.
The answer is a resounding and unequivocal "no". These things are completely unrelated.
I guess the real question for me with this has always been how constrained of an existence proof it is. Does this imply that there might exist arbitrary true statements that are unprovable (let's say, for example, could the riemann hypothesis be true and unprovable) or does it rely on a really narrow set of conditions to construct the existence of the unprovable yet true statement, that we wouldn't expect to apply to anything outside of those conditions?
I suppose the whole point of an existence proof is that it doesn't have to comment on how many examples might exist, just that there will always be at least one. But sometimes we also know from the proof that any possible example of the thing which is being proved to exist must satisfy some constraints (which, continuing the previous example, could potentially enable us to prove that the riemann hypothesis is definitely provable one way or another, without knowing whether it's true or false or knowing the proof). I haven't really heard anyone comment on whether gödels theorem gives us any insight like this or not, or whether all that's known is there's just one explicitly constructable unprovable statement that might be essentially unique or might be just one amongst an infinitely vast and unconstrained set of statements and that's all the info we have.
>One explicitly constructable unprovable statement that might be essentially unique or might be just one amongst an infinitely vast and unconstrained set of statements and that's all the info we have.
I actually have the exact answer to your question. I have thought about this for YEARS.
Take
P -> G is unprovable
G -> P is true.
Two separate statements, not a relationship between a thing and itself, those are two separate statements.
You might say, "but but this 'trivial' statement has no bearing on and no consequence on any other statements other than itself, thus its is an isoated incidence"
But this is wrong. This relationship of P and G, can be embedded into other logical-relationships as a subgraph minor, and can emerge OUT of other logical-relationships as a subgraph minor in an emergent and non-explicit sense. I am using the term "subgraph minor" in a very generalized sense as a metaphor. It is only an educational metaphor to explain the nature of the concept I am describing. If you look up what a graph minor is, you will be able to understand my argument: This unprovability relationship can literally be embedded into certain other statements and you can't even tell by looking it it. Thus it will affect an infinite variety of relationships, nontrivially. And it will be unpredictable when this is unprovability relationship is a subgraph minor of some logical relationships because of emergence. Ie, something as simple as "every even number is the sum of 2 primes" can have this relationship embedded inside it deep within its emergent consequences, you can't tell.
It is far, far, from an isolated incidence.
Yesterday I was wondering if every conclusion had a question that could be asked that the answer to which would be that conclusion. I had come to a conclusion where this didn't seem to be so but in thinking about a question for every conclusion I forgot what it was.
You probably meant question and answer, not question and conclusion.
More over Rice's theorem generalizes Turing's theorem to a whole broad range of properties and is pretty important when you are dealing with any type of meta program, whole architectures have been rewritten as a result of Rice theorems. It is pretty important in cybersec...
Hop this helps 👍
It seems to me that math is a language, albeit a quantitative language rather than a qualitative one. Insofar as there are real and relevant differences between quantitative and qualitative ways of describing the world we can treat them as different; however, insofar as both are languages in the broad sense, both must be subject to the limitations of language, i.e: being vulnerable to semantic meaningless when constructed self-referentially. Thank you for this video helping me tease out this distinction.
I like how Dialect approaches these topics.
As requested some of my own thoughts:
- language can approximate reality, and in many cases well enough to be very workable, but it is not reality itself ... Try to define, or even describe, an elephant ...if an elephant gives birth to its offspring that misses one or more of the characteristics, is it still an elephant? And given evolution again not a trivial answer IMHO
- second, recursive or undefined, statements, functions, out sets might be undefined or non convergent, but might have a result that is workable in certain cases (e.g. -1/12)
This for me suggests that there is no real golden truth, but given a certain context, assuming a golden truth makes life a bit more manageable and doable.
On ne pourra jamais construire une sphère parfaite avec des briques de 'Lego'
Godel also explain that the undecidable statement "This statement has no proof" is a true statement. The issue is that it cannot be proven within the system if was stated in, and in fact all such statements become decidable in a type higher than them is stated by Godel an (infamous) footnote 48a at the end of his article. No "strengthened liar" is needed, so the theorems of Godel need not drop the assumption of the law of the excluded middle.
A more interesting idea that appears in Godel's article is "w-consistentcy", that there are consistent systems where you can make a proof for the validity of a statement of a single number, but the universally quantified "This statement is true for all natural numbers" is false (Think about the current situation with Golbach's Conjecture to get an idea of how this could possibly be- although we do NOT know that golbach is an example of w-inconstencey). In such a system, Godel's theorems may not hold even though they the systems are consistent.
Yes, we read that same footnote. The "higher system" which "proves" that the undecidable statement is true is exactly the strengthened liar argument, and Gödel states quite clearly in his introduction. Without applying the reasoning of the strengthened liar, nothing proves "this statement has no proof" is a true statement, and so you'd still be stuck at the paradox of the liar. The theorem does require dropping the law of the excluded middle, as Gödel clearly acknowledged.
I generalize these concepts in the statement that all systems are limited. You could perhaps imagine an infinite system, but to verify everything within that system would require infinite resources, therefore would be practically impossible. It might be possible in theory, granted infinite resources, but that amounts to it being potentially true but unprovable. We can generally always _imagine_ things which we can't actually do.
I just think to myself: How would one go about defining something that is imbedded in the language that is being used to define it? That is not possible. To me, this is what the larger scale truth that Gödel is describing, hints at. In my opinion, using language to define language is always going to be circular. Trying to define 3 dimension with 3D math will always end with incompleteness.
That's an insightful remark, and likely at the base of Tarski's ambition to construct a "hierarchy of languages". Indeed, you've struck on what we think the deeper meaning of these incompleteness theorems truly is, which is that every language is going to be stuck ultimately with undefined or circularly-defined terms, and is going to have to source meaning for those terms from elsewhere.
@@dialectphilosophy Thank you for the reply. I have really been appreciating your perspectives on topics that seem to need fresh points of view.
This truth, (whatever that is...🤔😉) does not inherently mean that, with properly constructed conventions and rigorous definition use case, they are useless to construct...in my opinion, obviously. Chemistry, and classical physics being prime examples on our macro scale. I think quantum mechanics has a harder time because it is going down the rabbit hole as opposed to climbing a ladder, like astronomy. That is where things get trickier. Not only do you have to already have a rigorous language model to interpret observations with, you also have to invent new conventions before describing what observations are telling us. That is, in itself a type of conundrum... I spent some time pondering the usefulness of phenomenology, only to conclude that meta cognition still requires the material institution of language to be shared, effectively neutralizing it's broader usefulness, except for learning how to learn how to teach... (What a mouthful nested ideas become). My final conclusion comes to this: even if solipsism, or Boltzmann brains, are really the truth, language still needs to be shared. Even if a person creates a technology with ideas that are not themselves shared, that technology will only counter our need for inventing language and therefore work backwards against the institution of language necessary for maintaining an advanced society... 😌 Phew... I'm tired now.
@@dialectphilosophy Other minds: and the allegory of the cave also means that because the onus for learning ultimately falls on the individual, it is up to the elder wise people to broadcast teach at all times... Which is how I imagine a competent University should operate... Then again, it's all arbitrary, and on a relative scale.
@@dialectphilosophy I feel that a good antidote to all this over-hype (of the paradoxes), in my reading experience anyway, is the critique of the notion of a language which comes at the end of Donald Davidson's article "A Nice Derangement of Epitaphs." I can't justify this intuition in a YT note, but perhaps you'll run across that one at some point and find it relevant. I'm really only mentioning it here because there seems to be some slippage in the discussion between the "language" that humans use/create and the formal "languages" that these theorems are in and about. It seems important not to conflate those two.
> Formalism treats math like a religion because everything derives from some small set of axioms
what?
> The incompleteness theorems prove (for Godel) that math is just another kind of language game
Yeah right, for Godel the Platonist. If anything, the whole program of Hilbert was nominalist in nature. Hilbert was the one who believed math wasn't grasping any real truths.
Why not at least mention the obvious possibility that the point was just to debunk any kind of formalist or logicist program. Ie. to debunk the idea that math can be done in an entirely formal way of axioms and their deductions.
> statements which have no empirical content are intuitively taken to be (essentially) meaningless
Now you're saying that everyone's born a logical positivist?
> This is only because those statements which are true but not provable are in fact only statements about the meaninglessness of other statements
Preposterous. The whole example all of this is working with is self-referential, it's explicitly not about other statements.
Anyway, I also don't think the footnote makes much sense. Yes, the statement being not-true is consistent with it being indeterminate, obviously. But the point is that this agreement of the content of the claim (that it is not-true) with its indeterminacy, itself makes it true, which is the opposite category. Just how the agreement of the claim of the basic statement (that it is false) is in agreement with its falsity, thereby making it true.
My personal opinion is that the details of Godel encoding matter more than they're given credit for. If these claims are legitimately constructed out of axioms capable of basic arithmetic, then that's that. What doubt is there? And, if there's no other problems or objections, then that's that. There are true unprovable statements in certain formal systems and that's that.
At most you can peddle this empiricist rubbish about "where is muh sensible content" but that's it. What reason even is there to believe this? In this essentially Humean idea that absolutely everything and anything we think about is reducible to sense impressions, and if it isn't, well, we just don't think of it! Can't people see how ridiculous this is?
To be frank I don't really see how truth is essentially replaceable with provability. They're clearly pretty different. But even when it comes to the liar's paradox I don't see the issue with just saying that it is a true contradiction (the statement is both true and false). The insistence on the opposite just stems from a highly dogmatic commitment to the law of non-contradiction. One which, ironically, isn't a claim of any empirical content either.
Does the "indeterminate" option not still contradict the "true" option? Like, indeterminate means we cannot say whether it's true or false. If we /determine/ its truth, then we cannot assign the truth value "indeterminate". So the statement "this statement is not true " would still /truly/ and /determinately/ say that it is not true, if it is indeterminate. Thus, it would self-contradict.
Or did I miss something?
Check out the footnote in that section. Some people do argue that "indeterminate" and "true" truth values contradict each other (which is why the paradox is called "strengthened") but Gödel's and others thinking is that these truth-values are not mutually exclusive.
@@dialectphilosophy That's interesting, thank you. I still find it difficult to wrap my head around one statement being both true and indeterminate at once, but I might try to look it up in Gödel's own argument (if it's not too formalised for me :D).
@@dialectphilosophy If the statement says it is indeterminate, and it is proven to be indeterminate, doesn't that make it true?
But if the statement says it is indeterminate, but it's proven true, doesn't that make it false?
But if it's proven true and false, doesn't that make it self-contradictory?
But if it says it's indeterminate and you can't prove it's indeterminate, then maybe it's indeterminate. If you can't prove it's true, and you can't prove it's false, and you can't prove it's indeterminate, and you can't prove it contradicts itself, then you can't prove there's any problem with it.
I might be missing something here, but if Hilbert's program was to derive all of mathematics from the axioms, couldn't we just add all the unprovable statements to the axioms and carry on?
The short answer is "No", and this is one of the key points of Gödel's first incompleteness theorem. The slightly longer answer is that, if you start with a formal system which satisfies the hypothesis of Gödel's first incompleteness theorem, even after adding unprovable propositions as axioms, the resulting formal system will still have (new) unprovable propositions; thus, it is "intrinsically" incomplete. The more you add axioms, the more unprovable propositions will come up.
However, what is typically missed is another key aspect. Gödel's incompleteness theorems do not apply to _all_ formal systems: like all theorems, they have _hypothesis_ and, if those hypothesis aren't satisfied, then the theorems results do not apply. Thus, there are actually formal systems which are both complete and consistent, such as: Boolean Algebra, Euclidean Geometry, Presburger Arithmetic. In fact, the whole point of Gödel was to rigorously show that not all axiomatizations of arithmetic are equivalent: some of them (like Peano) are more "powerful" ("expressive" is probably a better term), but they "pay the price" for such "power" by being either incomplete or inconsistent, while others (like Presburger) are "weaker" (less expressive), but they are both complete and consistent.
@@QuantumMechanicYT There's a subtle point here that I hadn't gotten before.
Say you have an axiom system with 15 axioms, and there's a collection Y of unprovable propositions with those axioms.
You add a 16th axiom. Are there now additional unprovable propositions that were provable before? Or is it that there were an infinite number of them before, and there are still an in finite number, but some that were unprovable before can now be proved?
Perhaps with a new axiom Goedel's theorem gives you a way to find additional unprovable propositions that were unprovable before but that the theorem did not provide a method to find before?
@@jethomas5 I am afraid that I do not know the answer to your question, which I find very interesting. My best guess is that the collection Y is infinite right from the start, but adding one (or more) axiom(s) still adds new elements (possibly infinitely more) to Y.
@@QuantumMechanicYT Thank you! I believe that Goedel's method provides a way to find an infinite number of them.
I expect that if a proposition is unprovable with 18 axioms, it will still be unprovable if you remove one of them and have only 17 axioms. Because if you could prove it with 17 axioms, adding another will not make the proof stop working. So each new axiom removes some items from Y leaving only an infinite number remaining. I read into your statement above a claim that it isn't true, and wondered whether my intuition was known to be wrong.
Godel developed a 3-valued logic for this purpose. Nowadays we know RM3. What the theorem REALLY says is Incomplete OR Inconsistent. It turns out you can have Completeness! No worries. You need to learn to live with inconsistency but you already do. You use three-valued logic every time you go through a stoplight. Turns out that intermediate, inconsistent, both true and false (different from neither true nor false!), third truth value is quite useful, not only for unraveling the Liar, but also Paradoxes of Relevance. (They are often called "informal" fallacies, because "classical" logic can't see them. You need three-valued logic to solve them.)
If you have any inconsistency in a logical language, you can trivially deduce any conclusion you want to arrive at. You may as well throw the whole system out the window.
@@Elrog3 No the entire system doesn't need to be thrown out the window if shown to be inconsistent. There are systems that are wholly inconsistent with each other and yet are useful for certain applications like modular arithmetic would be wholly inconsistent with normal arithmetic without either making a distinction in your operations or developing another system that can underly the mechanics of both.
@@christopheriman4921 Two separate logical languages being inconsistent with each other isn't the same as a logical language being inconsistent with itself, which is what I was talking about.
@@Elrog3 I know but if you look at any inconsistency in a mathematical field as another potential useful mathematical construct I can see how math in general could be wholly contradictory with itself and still be useful.
@@Elrog3 Sorry for the lateness of my reply. Your definition of logical language is the problem. You are assuming binary logic. I said RM3, it's not binary. There is no triviality.
3:28 could it be just axioms who are true but improvable ?
How do you decide they are true if you can't prove them?
every time i see an ai image a shiver just comes over me, this is not the future i dreamed of long ago
Yes I agree. Fuck AI.
All this not as mysterious as Dialect appears to make it. If decisions (about truth) are restricted to formal reasoning and representational semantics, antinomies and contradictions occur either as undecidable (over infinite time) or temporally contradictory (alternating truth values in time). If judgments are rendered in real time, they must be passed for reasons relating to human, social requirements. And still, they can be revised or even contravened in time. So anyone hearing, "this statement is a lie" can just stop there and conclude "the speaker is lying." Or go one more step and decide, "yes, that's true." No step of thinking it through produces a contradiction, which we nominally understand as a statement asserting a thing and its opposite at the same time.
The whole idea of undecidability, "paradox," halting, or incompleteness relates to a kind of perfection that doesn't transcend the boundaries of mathematical logic as an atemporal infinitude. As far as incompleteness goes, language changes, so no problem there.
That there are 'paradoxes' in this realm only show that the way we use natural language cannot be reduced to formal logic.
What is maybe more toward Dialect's project is that the mathematical idealization of reality (and perhaps Foundationalism in general) is being critiqued.
Moreeee!
Btw If we can say that a sentence is indeterminate, what keeps us from saying that the strengthened liar is meta indeterminate, as Metaindeterminate being "undecidable"?
This is some seriously high quality content. Thank you.
What does the color black sound like?
First we must resolve the question of whether "this statement is false" is a proposition, we suppose so because it is a proposition if the "this" it refers to is a proposition, which it is if it is which it is if it is which it is if it is, etc...
This proposition that the least defined fixed point of logical negation is a proposition may, if we have a theory of types in which a mapping from propositions to propositions is a subtype of a suitable generalisation, be a choice but the fact the least defined fixed point of logical negation is bottom might contradict one of the two options when we assume that it is such a mapping and perhaps we must conclude the complement, that it is not a proposition, but that logical negation is another type of functional which is a proposition when it's argument is a proposition but it is something else otherwise.
Type theory by the time of Gödel's theorems wasn't so well developed and so the assumption that logic negation is always a mapping from propositions to propositions seems to have been relied upon without justification. In fact, there seems to be some doubt about whether, even if there is only one nullary constructor available can you say (fix id) is anything other than bottom which might be necessary to even type the sentence - sadly I don't know enough of the field to answer that but I hope to learn enough soon to be able to.
That was all way over our head!
@@dialectphilosophy I can only hope I'm not just a gpt4 installation
@@dialectphilosophy short story, if negation N is of type Bool -> Bool then fixed point of N is N(N(N(...))). That's the proposition were talking about, since N negates propositions we assume the ... Is a boolean and then so is the whole. But without a final boolean at the end of the infinite nesting we might be in a situation with the type of N being something like "if the argument is of type Bool then so is the result type, but if the argument is of type Void then so is the result type" . If so, then N(N(...)) may be Void and not Bool and our statement is a meaningless loop instead of being an undecidable proposition. However, some propositions are free for us to choose their truth value and we have consistency either way, and a proposal for the type of the expression might be such a thing.
I’m very fond of your relativity videos, but I’m not sure i agree with you on this subject. We do know of undecidable problems which are easy to understand in natural language. For instance, the tiling problem: the statement “you can tile the plane with a repeating pattern made up from this given configuration” is in most cases unprovable. It seems to me to be a clear case that shows that the undecidability and unprovability theorems are not about trivialities at all. If you Google “tiling problem and undecidability” you can find a lot of information about it which I’m sure will interest you very much. Anyway, thank you for your dedicated work!
Hey thanks for watching! To address your objection, it's important to note that questioning the validity of the incompleteness theorem (which, the more we study it, the more lacking of such validity we feel it shows) does not mean incompleteness or undecidability is not an actual thing -- it would simply mean that dressing up the liar's paradox in mathematical clothing isn't a proof of such incompleteness.
In general however, "undecidability" proofs do make us suspicious, since a mathematical proof can contain no more information than the assumptions put into it. Additionally such proofs are often extraordinarily abstruse, highly-technical and only claimed to be understood by a few individuals. Thus, for instance, the fact that experts can't agree on what the meaning of Gödel's incompleteness theorem actually is, is a giant red flag for us.
"True but not provable" is misleading. The statements are undecidable rather than true, and one may construct a consistent system as easily by declaring them "false" as by declaring them "true" even if the "true" interpretation seems more intuitive.
For example, "a number x satisfies x*x=--1" is undecidable in conventional or real arithmetic, and we may intuitively declare it false, but we may also declare it true and develop complex arithmetic, and complex arithmetic has practical advantages like the fact that all polynomials of order n have n complex zeros. In this case, the undecidable proposition is not like "this statement is false", but if complex arithmetic is consistent, then the "existence" of the imaginary number i must be undecidable in real arithmetic because complex arithmetic only extends real arithmetic by adding the existence of i axiomatically.
Hofstadter's "Godel, Escher, Bach" doesn't purport to explain consciousness or anything similarly metaphysical in terms of incompleteness that I recall, and it denies that Godel's undecidable proposition is "true" in any meaningful sense by positing a system of "supernatural numbers" in which the statement is false. Hofstadter is being playful rather than mystical by calling the numbers "supernatural". Complex arithmetic similarly extends the "real numbers" with "imaginary numbers" to construct "complex numbers". All numbers are artificial abstractions, so all are in some sense imaginary.
In terms of consciousness and the like, the book is more concerned with self-reference than with incompleteness per se. Hofstadter does not make the Penrose argument that I recall.
I have disagreements with what was presented here. You seem to have introduced a new category that is "neither true nor false" and then treated it as if it were "true but not false".
Take L to be a liar statement such as: "This statement is not true"
(so I don't have to nest quotation marks)
"L is true because it is indeterminate" is false. And the statement that it was equivocated with ("There are statements within the system which are true but not provable") does not follow.
(Given here so you don't have to scroll up and find it in the vid)
L is false
L is not true
L is True
At 11:19, the middle statement does follow from the top statement, but the middle statement is more broad. What you essentially did with that middle statement is taking a statement 'A', and deducing the statement 'A or B'. That is valid; its called disjunct introduction. The bottom statement does not follow from the middle statement. Indeterminacy does not mean 'true'. A contradiction is still produced here though because the bottom statement does follow directly from the top statement without the middle statement being there. A statement being false means that the negation of the statement is true. In the context of allowing for indeterminacy, being 'false' is more specific than being 'not true.
L is true
L is not true
L is false or indeterminant
At 11:27, the middle statement does follow from the top statement, but to be more explicit, I'd add in the intermediate step of saying "L is false" and then doing disjunct introduction. But there's a problem here. The middle statement also contradicts the top statement. "L is true" contradicts "L is not true". That makes the top statement false because that assumption lead to a contradiction. You can't just do a proof, reach a contradiction halfway through and keep going, and then compare whether some later line contradicts the first assumption to say that there's no contradiction. For a proof to be valid, the entire list of prior assumptions, statements, and possible derivates of them all have to mesh well and not contradict.
To make this clear, call P some proposition. "P is indeterminate" contradicts "P is true". "P is indeterminate" contradicts "P is false". Indeterminacy is a category of its own. Being 'not true' means "false or indeterminate". Being 'not false' means "true or indeterminate". Just as being 'false' is more specific than being 'not true' and it implies that the negation of a statement is true, being 'true' is more specific than 'not false' and it implies the negation of the statement is false.
To answer the prompt, I think these types of statements are meaningless, but they are fun to analyze nonetheless.
This is incredibly well formulated.
I feel that this is just another way to try to understand or define the boarders between things, can they ever be accurately measured? :)
When you get big picture there is nothing strange with all these paradoxes.
11:38 I think there is a typo and should read "L is not true"
The footnote refers to the fact that L (which is the statement 'this statement is not true') is being declared true. So "L is true" translates to "This statement is not true" is true" which is the conclusion of the strengthened liar.
Valeu!
Thank you so much for your support and generosity. We're grateful for individuals like yourself, and the contributions that help keep this channel going!
Why do we take it so much for granted that there is no external and inclusive idea to our own propositions that constitutes a universe where our undeterminate propositions are actually fully determinate? Is our mind all inclusive, so that such loopholes are comprehensible? Do our propositions reflect a total reallity?
Question to the author: Is the channel a pragmatist channel? I think it is as it shows its hallmarks like fallibilism etc.
The incompleteness theorems aren't empirical. In other words, there's a sense in which they're not about reality. But the same can be said for an axiomatic formulation of arithmetic, even though arithmetic is clearly applicable to counting physical objects.
Many years ago, I took a couple semesters of metamathematics and then decided not to pursue it any further because I didn't think there was anything there that still really needed to be solved. Of course you could find conjectures sort-of in the same ballpark, that no one knew whether they could be proved or not. But it seemed to me as though the important questions had been settled. Alas, I don't remember it well at all.
I think of it like “not guilty”
It doesn’t mean that it’s innocent
Good.
You can make your design more aesthetically appealing (in comparison to your competitors) by using better typography with “curly” quotes, apostrophes and long dashes.
x · y looks prettier than x x y.
I find it hard to believe that these problems say anything about Nature itself, rather they say something about the systems making these statements that emerge out of the frameworks they build. These frameworks themselves are built upon an initial set of foundational axioms, that to a certain extent are themselves dependent on the perceptions of the systems building the frameworks. The perception mechanisms are inherently hanging on the evolutionary constraints of the respective system, and on what happened to be evolutionarily advantageous to perceive. Given this, there ought to be an infinite amount of frameworks, each having a certain degree of internal consistency, but that are heavily dependent on the evolutionary constraints of the systems building them. A large subset of these frameworks would presumably be eliminated from the get go, as the systems that would otherwise build them, wouldn't have enough fitness ("in the natural world"), given their evolutionary constraints, and would inherently be outcompeted. "On the unreasonable effectiveness of mathematics" would be inherent to any system that has good enough evolutionary constraints, so as to survive and thrive, and have a development of an ever more intricate representation of the world (be it initially, by developing counting capabilities, evaluate discreteness, etc). Nonetheless, the subset of frameworks built by this system would still be only a "slice" in the total set of possible frameworks. Furthermore, we probably shouldn't expect absolute internal consistency relative to the frameworks we build.
That's a very insightful way of looking at it! "Math is unreasonably effective" at describing reality for the same reason humans are "unreasonable adapted" to surviving -- we've evolved successfully by developing a useful model and framework for our reality. Meaning, if our math weren't unreasonably effective we would be around at all to ask why😂
A follow up video is necessary.
Gödel's proof is profound because it reveals "the impredicativity of self-referentiality". The implications in understanding epistemological failures of all sorts of modern insanities (most of which have to do with politics, or with legitimate subjects that have been politicized, and thus become immune to reason) are absolutely non-trivial. For context, ready Robert Rosen's _Essays On Life Itself._
My impression of what you are trying to accomplish with this channel is to make subjects that seem counterintuitive more understandable, bypassing the esoteric syntax of formalism and reconnecting the underlying concepts to *_relatable_* semantic content. What Gödel did was to show that pure syntax is ultimately of no practical use. You can't do much with it. He showed that the entire enterprise proposed by Russell was trivial.
The philosophical and epistemological implications would be trivial only if the human species understood them so well that we consistently avoided the logical and practical pitfalls they warn against. But we don't. I see it everywhere, every day. Very seldom does such a work of pure logic have such profound implications for what should constitute rational behavior, if only those implications were understood rather than ignored.
Stated alternatively, people's inability to eschew the absurdity of trivialities like the liar's paradox is the source of most of the insanity that poses any real existential threats to human survival.
the liar is something else than goedels sentence in my opinion. the liar says something about his own truthness value and when you try to assign true or false you encounter an endless loop.
for goedels sentence there is no paradox. he constructed a true sentence in a non-contradictory formal axiom system which says: this statement is unprovable.
a true, unprovable statement means your system is incomplete.
ps: how do we know it is true? if "this statement is unprovable." was wrong, we hence had a false, provable statement. that would mean our system is contradictory. but the assumption was a non contradictory system.
You cannot see the field, if you are in the field.
Thx
Made myself a t-shirt that says "don't believe what you read on a t-shirt"..