1:30 Yeah, imagine a system that proves only one statement, and that statement is false. This system is not sound, but neither does it lead to a contradiction, therefore it is consistent.
Liked the video: clever way to tap Turing's theorem for proving Godel's; but if soundness implies consistency, as you rightly say, then soundness is stronger, not weaker than consistency.
That's true. However, if soundness -> consistency, then inconsistency -> unsoundness, so then saying a system is "inconsistent" is stronger than saying it is "unsound". This makes sense because "unsound" means the theory says things that aren't true, whereas "inconsistent" is a specific type of untrue thing that a theory could say (a contradiction).
Man, this is so good I'm sad I didn't come up with this kind of explanation myself. Also surprisingly I miss all the related formal puzzles. I did not really understand, until now, how much fun the "simulating machines in minimal arithmetic" stuff is to me.
It is not math that is incomplete, but a formal system with axiom system sufficiently strong to encode natural numbers with both addition and multiplciation. (there is a formal system for natural numbers without multiplication which is complete and decidable) Mathematics is very different from formal systems. Formal systems are games with predetermined rules. If you are working withing fromal system, you are not discovering anything, you can only make more explicit what is already expressed by the axioms. Mathematics is creative and has to do with abstract ideas of space, count, structure etc. And these ideas are rewised and expanded all the time in mathematics. Axiomatic method is created only post hoc to make the communication of mathematics more explicit and convincing.
@@pedrogabrielbueno9151 Hi. I'm also non-expert. I'm educated as engineer. I'm afraid i don't know of any material specifically devoted to this problem. But how i would go about it: 1. Learn about history of mathematics - focus on how is the mathematics done throughout the history (at least from thales to 20th centurh) - Notice that how geometry was done in Euclid - Elements is now how it was discovered and done beore, euclid was a systemizer in my opinion - putting known knowledge on rigorous foundation. 2. Learn basic principles of mathematical proof (proof by construction, direct proof, mathematical induction, proof by contradiction). Try to notice that you basically need to know what you are proving before you even start a proof, that there is a lot taken for granted outside the proof itself (be it work of others, or your intuition). 3. Learn about logic and deductive theories. Priest - Logic: A Very Short Introduction explains what logic is and explains Goedel's Theorems. Tarski - Introduction to Logic and the methodology of deductive sciences explains how deductive theories are build and the fact that you don't even have to know about incompleteness theorem for it to be clear that deductive theories have limited capability (you have to choose the axioms somehow). 4. Philosophy: Lakatos - Proofs and Refutations, Polya - Mathematics and plausible reasoning Learning about how discovery of mathematics is process of going through a lot of examples of simple observable mathematical facts, and then from intuition making conjectures of how it could be generalized, and then trying to refute or prove those conjectures.
@@GeorgWilde I`m familiar with Lakatos and Tarski, thanks for the other recommendations though. It would be interesting to see any formal discussion of this idea anyways!
I don't understand why soundness is a weaker constraint than consistency. Given "If x belongs to/meets A, then x also belongs to/meets B", A is a subset of B, then A is a stronger (more exclusive) constraint, right? So, from "if something is sound, then it is also consistent" follows that soundness is stronger than consistency. What am I missing?
But isn't eliminating the possibility that the program halts a proof in itself that it must loop? We suppose "n" is true, we show it can't so it must be that "not n" is true...or isn't it?
Yes, sort of. I'm really glad you had this thought, as it's the crux of the proof of the second incompleteness theorem (and why I gave this a side mention). There's a couple of issues stopping us from formalizing this idea into a real proof here. The first is that I'm talking generally about a program that should exist, but because we're not talking about a specific program and input, it's hard to formally argue whether it halts or loops. The second is that as we try to write a proof that this program must actually halt, there's an important hidden assumption that we need to finish the proof (which leads to Gödel's second incompleteness theorem). I'll be going into more detail in the next video. One final note is that the lack of a proof of A is not itself a proof of not A. The reason is that our math system is incomplete (hopefully), so it's always possible that both A and not A cannot be proven.
Thanks for the quick answer. Really looking forward to your next video but...The fact that we can't prove neither a sentence nor its opposite doesn't mean neither is true right? Supposing the system is consistent at least. So, unless it doesn't have a truth value or it violates the law of excluded middle, once you prove one of the statement wrong, even if you can't prove the other one directly it must still be true. Don't all reductio ab absurdum arguments work like this?
Right, this is a point that definitely confused me for a while, and hopefully will be cleared up when we tackle it for real in the next video. The subtle difference between a true statement and having a proof of that statement resolves the contradiction. In trying to formalize a proof that the program loops, we'll have to rely on a hidden, unprovable assumption. There's also a philosophical question of what truth means for statements that cannot be proved one way or the other. Does the fact that there is no proof just mean we don't worry about truth for that statement? Is it still true and it's opposite false? We'll be moving away from soundness to consistency so that we avoid this question.
How are we so sure that M(x) actually loops when the oracle program can't prove so? We say if M(x) halts, there should definitely be a proof that it does. But we are talking about incompleteness here, how are we so sure? That part of the video really confused me.
You define "sound" in two different ways: 1) If we can prove something --> it is true 2) If something is true --> we can prove it (if pigs can fly we can prove it) Which one is the correct? Are those definitions interchangeable?
The first is soundness. When I'm using the pig example, I'm actually using the contrapositive (it should never be the case that pigs can't fly -> proof of pigs fly). The second is the definition of completeness.
What does it mean to say a theorem is true? Godel Incompleteness makes a distinction between truth and provability. A provable theorem simply means that starting with one or more of the axioms and the rules of inference a theorem can be arrived at by simple string manipulation. It's like a system of dominoes, and a "domino" theorem says that a particular domino will fall if we give a push to the first few dominos (the axioms). A true but unprovable theorem means that no amount of string manipulation can take you, step by step, from the axioms to the theorem, yet the theorem is nonetheless true. OK, but what does it mean to say the theorem is true? There isn't some set of truths which transcends all formal systems and whose members are the true theorems of all possible formal systems. So a true theorem only makes sense within the context of a formal system of axioms and string manipulation rules. It appears that the truth of a theorem means that the theorem is a consequence of the axioms and string manipulation rules, but that for unprovable true theorems there is no amount of string manipulation steps that will get you from the axioms to the theorem. In the domino system, the analogy would be that a particular domino falls over at some point after we give a push to the first few dominos but that there is no step by step process that you can calculate ahead of time (without actually starting the dominos toppling chain reaction) that would show you (prove to you) that the target domino will fall. This sounds absurd. However, the domino system would need to be nonlinear (contain self-reference/recursion) in order for this to happen. Any system of standing dominos that I've ever witnessed didn't contain recursion. So this analogy breaks down, but nonetheless, it illustrates what is meant by truth and provability. The statement that Incompleteness only happens if the system is sufficiently expressive simply means that the system must exhibit self-reference. My novel Shards Of Divinities examines these ideas in more detail. See nissim-levy.com/shards-of-divinities
Can anyone critique my notions in this? I would appreciate it very much................As a follow up to my recent posts on (Goedel’s incompleteness theorem) the architecture of materiality and that of the realm of abstraction, the two structurally linked, which prohibits for formulation of conceptual contradictions, I present the following for critique. After watching several video presentations of Geodel’s incompleteness theorems 1 and 2, as presented in each I have been able to find, it was made clear that he admired Quine’s liar’s paradox to a measure which inspired him to formulate a means of translating mathematical statements into a system reflective of the structure of formal semantics, essentially a language by which he could intentionally introduce self-referencing (for some unfathomable reason). Given that it is claimed that this introduces paradoxical conditions into the foundations of mathematics, his theorems can only be considered as suspect, a corruption of mathematic’s logical structure. The self-reference is born of a conceptual contradiction, that which I have previously shown to be impossible within the bounds of material reality and the system of logic reflective of it. To demonstrate again, below is a previous critique of Quine’s liars paradox. Quine’s liar’s paradox is in the form of the statement, “this statement is false”. Apparently, he was so impacted by this that he claimed it to be a crisis of thought. It is a crisis of nothing, but perhaps only of the diminishment of his reputation. “This statement is false” is a fraud for several reasons. The first is that the term “statement” as employed, which is the subject, a noun, is merely a place holder, an empty vessel, a term without meaning, perhaps a definition of a set of which there are no members. It refers to no previous utterance for were that the case, there would be no paradox. No information was conveyed which could be judged as true or false. It can be neither. The statement commands that its consideration be as such, if true, it is false, but if false, it is true, but again, if true, it is false, etc. The object of the statement, its falsity, cannot at once be both true and false which the consideration of the paradox demands, nor can it at once be the cause and the effect of the paradoxical function. This then breaks the law of logic, that of non-contradiction. Neither the structure of materiality, the means of the “process of existence”, nor that of the realm of abstraction which is its direct reflection, permits such corruption of language or thought. One cannot claim that he can formulate a position by the appeal to truths, that denies truth, i.e., the employment of terms and concepts in a statement which in its very expression, they are denied. It is like saying “I think I am not thinking” and expecting that it could ever be true. How is it that such piffle could be offered as a proof of that possible by such a man as Quine, purportedly of such genius? How could it then be embraced by another such as Goedel to be employed in the foundational structure of his discipline, corrupting the assumptions and discoveries of the previous centuries? Something is very wrong. If I am I would appreciate being shown how and where. All such paradoxes are easily shown to be sophistry, their resolutions obvious in most cases. What then are we left to conclude? To deliberately introduce the self-reference into mathematics to demonstrate by its inclusion that somehow reality will permit such conceptual contradictions is a grave indictment of Goedel. Consider; As mentioned above, that he might introduce the self-reference into mathematics, he generated a kind of formal semantics, as shown in most lectures and videos, which ultimately translated numbers and mathematical symbols into language, producing the statement, “this statement cannot be proved”, it being paradoxical in that in mathematics, all statements which are true have a proof and a false statement has none. Thus if true, that it is cannot be proved, then it has a proof, but if false, there can be no proof, but if true it cannot be proved, etc., thus the paradox. If then this language could be created by the method of Goedel numbers (no need to go into this here), it logically and by definition could be “reverse engineered” back to the mathematical formulae from which it was derived. Thus, if logic can be shown to have been defied in this means of the introduction of the self-reference into mathematics via this “language” then should not these original mathematical formulae retain the effect of the contradiction of this self-reference? It is claimed that this is not the case, for the structure of mathematics does not permit such which was the impetus for its development and employment in the first place. I would venture then that the entire exercise has absolutely no purpose, no meaning and no effect. It is stated in all the lectures I have seen that these (original) mathematical formulae had to be translated into a semantic structure that the self-reference could be introduced at all. If then it could not be expressed in mathematical terms alone and if it is found when translated into semantic structures to be false, does that not make clear the deception? If Quine’s liar’s paradox can so easily be shown to be sophistry, how is Goedel’s scheme not equally so? If the conceptual contradiction created by Goedel’s statement “this statement has no proof” is so exposed, no less a defiance of logic than Quine’s liar’s paradox then how can all that rests upon it not be considered suspect, i.e., completeness, consistency, decidability, etc.? I realize that I am no equal to Goedel, who himself was admired by Einstein, an intellect greater than that of anyone in the last couple of centuries. However, unless someone can refute my critique and show how Quine’s liar’s paradox and by extension, Goedel’s are actually valid, it’s only logical that the work which rests upon their acceptance be considered as invalid.
1:30 Yeah, imagine a system that proves only one statement, and that statement is false. This system is not sound, but neither does it lead to a contradiction, therefore it is consistent.
Liked the video: clever way to tap Turing's theorem for proving Godel's; but if soundness implies consistency, as you rightly say, then soundness is stronger, not weaker than consistency.
That's true. However, if soundness -> consistency, then inconsistency -> unsoundness, so then saying a system is "inconsistent" is stronger than saying it is "unsound". This makes sense because "unsound" means the theory says things that aren't true, whereas "inconsistent" is a specific type of untrue thing that a theory could say (a contradiction).
Since the context here is negated, what he meant was unsoundness is weaker than inconsistency.
He should have worded that more carefully though.
Man, this is so good I'm sad I didn't come up with this kind of explanation myself. Also surprisingly I miss all the related formal puzzles. I did not really understand, until now, how much fun the "simulating machines in minimal arithmetic" stuff is to me.
It is not math that is incomplete, but a formal system with axiom system sufficiently strong to encode natural numbers with both addition and multiplciation. (there is a formal system for natural numbers without multiplication which is complete and decidable) Mathematics is very different from formal systems. Formal systems are games with predetermined rules. If you are working withing fromal system, you are not discovering anything, you can only make more explicit what is already expressed by the axioms. Mathematics is creative and has to do with abstract ideas of space, count, structure etc. And these ideas are rewised and expanded all the time in mathematics. Axiomatic method is created only post hoc to make the communication of mathematics more explicit and convincing.
I tend to agree with you, even though I'm not an expert on either field. Do you have any reference to a discussion of this?
@@pedrogabrielbueno9151 Hi. I'm also non-expert. I'm educated as engineer.
I'm afraid i don't know of any material specifically devoted to this problem.
But how i would go about it:
1. Learn about history of mathematics - focus on how is the mathematics done throughout the history (at least from thales to 20th centurh) - Notice that how geometry was done in Euclid - Elements is now how it was discovered and done beore, euclid was a systemizer in my opinion - putting known knowledge on rigorous foundation.
2. Learn basic principles of mathematical proof (proof by construction, direct proof, mathematical induction, proof by contradiction). Try to notice that you basically need to know what you are proving before you even start a proof, that there is a lot taken for granted outside the proof itself (be it work of others, or your intuition).
3. Learn about logic and deductive theories. Priest - Logic: A Very Short Introduction explains what logic is and explains Goedel's Theorems. Tarski - Introduction to Logic and the methodology of deductive sciences explains how deductive theories are build and the fact that you don't even have to know about incompleteness theorem for it to be clear that deductive theories have limited capability (you have to choose the axioms somehow).
4. Philosophy: Lakatos - Proofs and Refutations, Polya - Mathematics and plausible reasoning
Learning about how discovery of mathematics is process of going through a lot of examples of simple observable mathematical facts, and then from intuition making conjectures of how it could be generalized, and then trying to refute or prove those conjectures.
@@GeorgWilde I`m familiar with Lakatos and Tarski, thanks for the other recommendations though. It would be interesting to see any formal discussion of this idea anyways!
I don't understand why soundness is a weaker constraint than consistency. Given "If x belongs to/meets A, then x also belongs to/meets B", A is a subset of B, then A is a stronger (more exclusive) constraint, right? So, from "if something is sound, then it is also consistent" follows that soundness is stronger than consistency. What am I missing?
So what if the proof of this incompleteness theorem is in itself incomplete or inconsistent ?
Please make more videos .. this is my favourite series on UA-cam.
Question: at 5:54 you said we can't prove that it loops, but how isn't that exactly what you did in the preceding 30 seconds?
But isn't eliminating the possibility that the program halts a proof in itself that it must loop? We suppose "n" is true, we show it can't so it must be that "not n" is true...or isn't it?
Yes, sort of. I'm really glad you had this thought, as it's the crux of the proof of the second incompleteness theorem (and why I gave this a side mention).
There's a couple of issues stopping us from formalizing this idea into a real proof here. The first is that I'm talking generally about a program that should exist, but because we're not talking about a specific program and input, it's hard to formally argue whether it halts or loops.
The second is that as we try to write a proof that this program must actually halt, there's an important hidden assumption that we need to finish the proof (which leads to Gödel's second incompleteness theorem). I'll be going into more detail in the next video.
One final note is that the lack of a proof of A is not itself a proof of not A. The reason is that our math system is incomplete (hopefully), so it's always possible that both A and not A cannot be proven.
Thanks for the quick answer. Really looking forward to your next video but...The fact that we can't prove neither a sentence nor its opposite doesn't mean neither is true right? Supposing the system is consistent at least. So, unless it doesn't have a truth value or it violates the law of excluded middle, once you prove one of the statement wrong, even if you can't prove the other one directly it must still be true. Don't all reductio ab absurdum arguments work like this?
Right, this is a point that definitely confused me for a while, and hopefully will be cleared up when we tackle it for real in the next video. The subtle difference between a true statement and having a proof of that statement resolves the contradiction. In trying to formalize a proof that the program loops, we'll have to rely on a hidden, unprovable assumption.
There's also a philosophical question of what truth means for statements that cannot be proved one way or the other. Does the fact that there is no proof just mean we don't worry about truth for that statement? Is it still true and it's opposite false? We'll be moving away from soundness to consistency so that we avoid this question.
The way you describe soundness and consistency makes it sound like if a math system is unsound it must also be inconsistent. Is that not true?
Other way around. If it's sound, it's consistent. Therefore, if it's inconsistent, it's unsound.
Which program do you use to create your animations? thx
Awesome! Always look forward to your videos :)
how to prove the stronger form of the theorem(inconsistent instead of unsound)
How are we so sure that M(x) actually loops when the oracle program can't prove so? We say if M(x) halts, there should definitely be a proof that it does. But we are talking about incompleteness here, how are we so sure? That part of the video really confused me.
The proof that it halts will be the steps of the program itself.
Great vid. Looking forward to the next!
how can the list of accountable math-proofs include the proof that list is complete ?
You define "sound" in two different ways:
1) If we can prove something --> it is true
2) If something is true --> we can prove it (if pigs can fly we can prove it)
Which one is the correct? Are those definitions interchangeable?
The first is soundness. When I'm using the pig example, I'm actually using the contrapositive (it should never be the case that pigs can't fly -> proof of pigs fly).
The second is the definition of completeness.
What does it mean to say a theorem is true? Godel Incompleteness makes a distinction between truth and provability. A provable theorem simply means that starting with one or more of the axioms and the rules of inference a theorem can be arrived at by simple string manipulation. It's like a system of dominoes, and a "domino" theorem says that a particular domino will fall if we give a push to the first few dominos (the axioms).
A true but unprovable theorem means that no amount of string manipulation can take you, step by step, from the axioms to the theorem, yet the theorem is nonetheless true. OK, but what does it mean to say the theorem is true? There isn't some set of truths which transcends all formal systems and whose members are the true theorems of all possible formal systems. So a true theorem only makes sense within the context of a formal system of axioms and string manipulation rules.
It appears that the truth of a theorem means that the theorem is a consequence of the axioms and string manipulation rules, but that for unprovable true theorems there is no amount of string manipulation steps that will get you from the axioms to the theorem. In the domino system, the analogy would be that a particular domino falls over at some point after we give a push to the first few dominos but that there is no step by step process that you can calculate ahead of time (without actually starting the dominos toppling chain reaction) that would show you (prove to you) that the target domino will fall.
This sounds absurd. However, the domino system would need to be nonlinear (contain self-reference/recursion) in order for this to happen. Any system of standing dominos that I've ever witnessed didn't contain recursion. So this analogy breaks down, but nonetheless, it illustrates what is meant by truth and provability. The statement that Incompleteness only happens if the system is sufficiently expressive simply means that the system must exhibit self-reference.
My novel Shards Of Divinities examines these ideas in more detail. See nissim-levy.com/shards-of-divinities
Great videos! I was wondering which program you use to make the videos? Very excited for the next videos!
Leander Goldbach I use Adobe Animate (formerly Flash). I should learn how to use Illustrator and After Effects, but I'm an old dog.
Cool. Thanks for the reply. I really like the look of your videos. Looks unique. Probably because you don't use contours?
Can anyone critique my notions in this? I would appreciate it very much................As a follow up to my recent posts on (Goedel’s incompleteness theorem) the architecture of materiality and that of the realm of abstraction, the two structurally linked, which prohibits for formulation of conceptual contradictions, I present the following for critique.
After watching several video presentations of Geodel’s incompleteness theorems 1 and 2, as presented in each I have been able to find, it was made clear that he admired Quine’s liar’s paradox to a measure which inspired him to formulate a means of translating mathematical statements into a system reflective of the structure of formal semantics, essentially a language by which he could intentionally introduce self-referencing (for some unfathomable reason). Given that it is claimed that this introduces paradoxical conditions into the foundations of mathematics, his theorems can only be considered as suspect, a corruption of mathematic’s logical structure. The self-reference is born of a conceptual contradiction, that which I have previously shown to be impossible within the bounds of material reality and the system of logic reflective of it. To demonstrate again, below is a previous critique of Quine’s liars paradox.
Quine’s liar’s paradox is in the form of the statement, “this statement is false”. Apparently, he was so impacted by this that he claimed it to be a crisis of thought. It is a crisis of nothing, but perhaps only of the diminishment of his reputation. “This statement is false” is a fraud for several reasons. The first is that the term “statement” as employed, which is the subject, a noun, is merely a place holder, an empty vessel, a term without meaning, perhaps a definition of a set of which there are no members. It refers to no previous utterance for were that the case, there would be no paradox. No information was conveyed which could be judged as true or false. It can be neither. The statement commands that its consideration be as such, if true, it is false, but if false, it is true, but again, if true, it is false, etc. The object of the statement, its falsity, cannot at once be both true and false which the consideration of the paradox demands, nor can it at once be the cause and the effect of the paradoxical function. This then breaks the law of logic, that of non-contradiction.
Neither the structure of materiality, the means of the “process of existence”, nor that of the realm of abstraction which is its direct reflection, permits such corruption of language or thought. One cannot claim that he can formulate a position by the appeal to truths, that denies truth, i.e., the employment of terms and concepts in a statement which in its very expression, they are denied. It is like saying “I think I am not thinking” and expecting that it could ever be true. How is it that such piffle could be offered as a proof of that possible by such a man as Quine, purportedly of such genius? How could it then be embraced by another such as Goedel to be employed in the foundational structure of his discipline, corrupting the assumptions and discoveries of the previous centuries? Something is very wrong. If I am I would appreciate being shown how and where.
All such paradoxes are easily shown to be sophistry, their resolutions obvious in most cases. What then are we left to conclude? To deliberately introduce the self-reference into mathematics to demonstrate by its inclusion that somehow reality will permit such conceptual contradictions is a grave indictment of Goedel. Consider;
As mentioned above, that he might introduce the self-reference into mathematics, he generated a kind of formal semantics, as shown in most lectures and videos, which ultimately translated numbers and mathematical symbols into language, producing the statement, “this statement cannot be proved”, it being paradoxical in that in mathematics, all statements which are true have a proof and a false statement has none. Thus if true, that it is cannot be proved, then it has a proof, but if false, there can be no proof, but if true it cannot be proved, etc., thus the paradox. If then this language could be created by the method of Goedel numbers (no need to go into this here), it logically and by definition could be “reverse engineered” back to the mathematical formulae from which it was derived. Thus, if logic can be shown to have been defied in this means of the introduction of the self-reference into mathematics via this “language” then should not these original mathematical formulae retain the effect of the contradiction of this self-reference? It is claimed that this is not the case, for the structure of mathematics does not permit such which was the impetus for its development and employment in the first place. I would venture then that the entire exercise has absolutely no purpose, no meaning and no effect. It is stated in all the lectures I have seen that these (original) mathematical formulae had to be translated into a semantic structure that the self-reference could be introduced at all. If then it could not be expressed in mathematical terms alone and if it is found when translated into semantic structures to be false, does that not make clear the deception? If Quine’s liar’s paradox can so easily be shown to be sophistry, how is Goedel’s scheme not equally so? If the conceptual contradiction created by Goedel’s statement “this statement has no proof” is so exposed, no less a defiance of logic than Quine’s liar’s paradox then how can all that rests upon it not be considered suspect, i.e., completeness, consistency, decidability, etc.?
I realize that I am no equal to Goedel, who himself was admired by Einstein, an intellect greater than that of anyone in the last couple of centuries. However, unless someone can refute my critique and show how Quine’s liar’s paradox and by extension, Goedel’s are actually valid, it’s only logical that the work which rests upon their acceptance be considered as invalid.
d^2(godel)/dt^2 = gödel
The way you defined consistency, even in a mathematical sense, is not a definition I’ve been able to find.
"Gurdle"
This video was extremely helpful. just subbed
This is beautiful
Awesome!!!! Please keep making videos, this channel is gonna be amazing! =D
Nice!
I’m still searching for somebody who is able to explain that to me. Sound.
confusing. Don 't know there was a before video
So this is a proof that proves proofs cannot be proven
lol
LOL, but actually, it's scary :?
wth i just watched?
explaining this is programming code is stupid! now try explain algebra using calculus to an elementary student!