Godel's 1st Incompleteness Theorem - Proof by Diagonalization

Рет қаралды 60,895

4 жыл бұрын

Godel’s Incompleteness Theorem states that for any consistent formal system, within which a certain amount of arithmetic can be carried out, there are statements which can neither be proved nor disproved. Thereby setting bounds to what mathematics could prove.
English translation of the original paper:
www.jamesrmeyer.com/ffgit/god...
In this video we’ll examine the context for the theorem, get a gist of what it’s all about and then we’ll step through a semi-formal proof of it, for those who’d like to dig a little deeper.
At the start of 20th century mathematicians, such as David Hilbert, Bertrand Russell, Alfred North Whitehead, had a sense that given just the right set of axioms of a formal system, any mathematical theory could be proven to be true or false by systematically applying these axioms in a chain of logical operations. This is where Kurt Gödel, in his 1931 paper, shook the foundations of mathematics, proving that for any consistent formal system, within which a certain amount of arithmetic can be carried out, such as Paleo Arithmetic, there are statements which can neither be proved nor disproved.
The axiomatic system must be consistent, which means that no statement and it’s negation can both be derived by just following a different sequence of axioms and theorems.
And finally, the mention of “certain amount of arithmetic” refers to being able to at least enumerate the theorems of the language. So a very simple system that has no computing power, may in fact be consistent and entirely complete. But then it also won’t have the power needed to express even simple computations.
Let’s now examine how Godel proved his theorem. In essence, he constructed a legitimate, well formulated mathematical statement that implied that it itself is not provable.
To construct such a statement, we start with this linguistic paradox:
“This statement is not true”
Simply reading it out presents a problem, since if we were to assume that the statement is true, it’s meaning would suggest the opposite. On the other hand, if the statement is not true, then its implied meaning turns out to be true, hence the paradox.
So what would it take to construct a similar statement, but express it formally, in mathematical notation?
There are two immediate problems to handle. First of all, the word “true”, somewhat surprisingly, is not defined axiomatically. Numbers and formulas don’t have a property of “true”. We think of axioms as being defined to be true and any theorems that are derived from them would therefore also be true. But the concept of truth would then still be outside of the system itself.
Tarski's undefinability theorem:
en.wikipedia.org/wiki/Tarski%...
The other problematic word is “this”. It refers to the statement itself, without the statement having been defined yet. It’s like saying “This video is exactly 16 minutes and 9 seconds long” without first having made the video.
To get around this problem, Godel established a way to convert statements, such as theorems and even proofs of those theorems, into natural numbers as a type of encoding. Then, having listed encodings of specific kinds of formulas, he showed that there is a natural number in that list that corresponds to a formula that states its own unprovability.
Godel Encoding establishes a one to one correspondence between a unique sequence of characters and some unique number. This allowed Godel to convert any mathematical statement, as well as a proof of that statement into two unique numbers.
A Simple Proof of Gödel's Incompleteness Theorems
mat.iitm.ac.in/home/asingh/pu...
Examples of unprovable statements
en.wikipedia.org/wiki/Paris%E...
Further reading on Godel's Incompleteness Theorems:
plato.stanford.edu/entries/go...
Written and narrated by Andre Violentyev

Пікірлер: 148

@UMaaM8 Ай бұрын

6:01 "Its like saying this video is exactly 16 minutes and 9 seconds long without first having made the video" - lovely 😀

@skeptic3045 3 жыл бұрын

Deep! I have tried to understand Gödels Incompleteness theorem for hours..Finally your diagonalization argument made it clear...Subscribed...

@stablesort 3 жыл бұрын

Thanks and welcome aboard!

@balthazarbeutelwolf9097 3 ай бұрын

the diagonalisation is not really the core of the proof, it merely shows the incompleteness once you have established a form of self-reference. The tricky part is to make the self-reference work. Practically, the problem is that no formula can contain its own goedel number. However, it can contain a number equivalent to it, or rather: the means by which that number is being constructed. In computational terms, you have a similar problem trying to write a program that prints its own code (without reading a file). Doable, but tricky.

@markustreml 7 ай бұрын

Great work! It connects the simplicity of Gödel's own introduction with just enough syntactic formality to overcome the semantic notion of truth and sum up the essentials very nicely!

@nilp0inter2 3 жыл бұрын

As a programmer, your explanation in programming terms was very enlightening. Thank you! Please do another video on the second Godel's theorem.

@stablesort 3 жыл бұрын

Thanks, will do! When I was making this video I was considering cramming Godel's 2nd incompleteness theorem in as well, but ultimately decided to save it for later. What's the rush, right?

@nilp0inter2 3 жыл бұрын

@@stablesort Good decision. Better to make it short and sweet 😊

@adriangalvez798 2 ай бұрын

I am reading Godel Escher Bach as well and hearing your analogy to coding la guage helped me a lot! Thanks :)

@asmithgames5926 4 күн бұрын

Eagerly awaiting your Second Incompleteness Theorem video!!

@Ko_kB 9 ай бұрын

Excellent work. I hope it gets more views, it certainly deserves more

@user-ky5dy5hl4d 11 ай бұрын

Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true. Bertrand Russell

@traviswalker9327 2 жыл бұрын

Hey, I loved the clarity of this video. I hope you do another on Godel's Second Incompleteness Theorem!

@amatya.rakshasa 2 жыл бұрын

oh cool. First time on your channel. Subscribed. Gonna go through your videos hoping that you did a deeper dive that you promised. Thank you!!

@amitozazad1584 3 жыл бұрын

We need more of such stuff on youtube! Awesome!

@stablesort 3 жыл бұрын

Glad you liked it!

@metaskepsistu_berlin9598 2 жыл бұрын

Best video on Godel's theorem. Please make a video on different ways we define truth in mathematics! I cant find anything about it.

@farouqzaabab9668 3 жыл бұрын

Your channel is an absolute treasure trove. Please keep on posting great videos like this. This platform needs great value videos like yours. Also, I would be very happy to help in de-noising the audio for some of the videos which have some background static. Thanks!

@stablesort 3 жыл бұрын

Thanks for the compliment and thanks for offering to de-noise the audio =) I think the noise was coming from my laptop fan. I'll try to isolate it better next time. By the way, how do you de-noise background static?

@farouqzaabab9668 3 жыл бұрын

@@stablesort You are so kind. De-noising is easy: first, you take a sample of the noise (you start recording the ambient noise in the room for maybe 10-15 seconds in your audio software). Then, you, select that as your noise sample, and use the de-noising option in your software (I use audacity, and this video explains better what am trying to say kzfaq.info/get/bejne/rNJ6hreS26-9Y58.html

@stablesort 3 жыл бұрын

Thanks, I'll definitely try that next time.

@pkr619 4 жыл бұрын

I have been watching your videos one after another, they are well put together, easy to understand and are of high quality ... keep posting. thanks!

@stablesort 4 жыл бұрын

Thanks for the words of encouragement; will do!

@AkiraNakamoto Жыл бұрын

Great video for people with bachelor or master of science degrees. Compared to this video, the other videos talking about the same subject mostly focus on anecdotal issues.

@freddyfozzyfilms2688 3 жыл бұрын

I really like the computational intuition you bring to mathematics

@stablesort 3 жыл бұрын

I appreciate your compliment, thank you!

@allensong8354 7 ай бұрын

thanks very much. I have searched for clear explanation for a long time

@2tehnik 3 жыл бұрын

Fascinating stuff. Thanks for explaining it in such a clear manner.

@stablesort 3 жыл бұрын

Thanks for the compliment! Indeed, it's fascinating stuff. I have been intrigued by it ever since taking a "theory of computation" class in college and it seems like every time I look into it, there is a ton more to uncover.

@2tehnik 3 жыл бұрын

@@stablesort I took a look back at the video to better understand the proof. And I'm not sure I totally understand what the function P(A) is supposed to do. does it return a binary value telling us if the statement A is true? Or does it do something else?

@stablesort 3 жыл бұрын

@@2tehnik There are a few hoops to jump to understand what it it. In short, the function P(A) determines if the statement A (that's the input to the function) is provable. Take a step back and imagine a function Q(X, Y) that determines if X is a square root of Y. You don't actually have to know how it does it, but it's fair to say that it's possible to construct such a function since square root is just an arithmetic calculation. Next we are going to do something very similar. Let's now imagine another function that returns true/false, Proof(p,s), that determines if “p is the Godel number of a proof of a statement whose Godel number is s” s = g(A) = g("some mathematical statement") p = g(B) = g("supposed proof of the statement above") Then we define Pr as the set of Godel numbers of all provable statements Pr(s) = ∃p Proof(p,s) Since we can freely convert a statement into its Godel encoding, and then convert the Godel encoding back into the original statement, we can further abbreviate into P(A) = Pr(s) = Pr(g(A)) P(A) means “A is provable” and we can call P a “provability predicate” . So yes, it's a function that returns true/false depending on whether statement "A" is provable. This is not that easy to immediately grasp. I know it took me a few passes to fully appreciate it =)

@aenimosity7 2 жыл бұрын

Thanks for the great video!!

@aleksandarrudic3694 3 жыл бұрын

This video should have a Godel number of views

@blairhakamies4132 9 ай бұрын

Well done. Congratulations 👏

@lincolnuland5443 2 ай бұрын

You are an excellent teacher. Amazing video. Thank you.

@nullspace_repo 11 ай бұрын

I'm doing research on Gödel's incompleteness theorems and found a couple of peer reviewed articles that have a lot of depth, but none cohesively explained it in laymen's terms as intuitively as this video!

@danieleppelsheimer9273 Ай бұрын

Great explanation!!! Thank you

@user-lc1dk1oc1l 2 жыл бұрын

this vegetable bonsai is impressing

@adityamishra7711 2 жыл бұрын

Well done !!, its intuitive

@BuleriaChk 2 ай бұрын

In oreder for the multiplication operator to exist, both its elements must exist. Russell's Paradox: 1^2 1 # = 2 = 1+1 (first order) Then #^2 = (1 + 1)^2 = [1^2 + 1^2] + [2(1)(1)] = 4(1^2) (second order - via Binomial Expansion) where the first term is existence and the second is interaction (multiiplication, entanglement, entropy) Note that existence and interaction are not 4D (1,1,1,1) which diagonal is 4 elements without multiplication. Every number is prime relative to its own base. n = n(n/n) = n(1_n) Goldbach's Theorem: every even number is the sum of two primes: n + n = 2n n is odd. Godel's characterization of wff's in his meta-language only uses odd numbers (products of primes). Therefore, the sums of odd numbers (even numbers) cannot be represented by hhis wff's. So it is just Goedel's meta-language that is incomplete, not positive real numbers. Together with Fermat's Last Theorem (applied to multinomials of arbitray powers), the arithmetic system is complete and consistent for positive real numbers. There are no negative numbers: -c = a - b, b > a b - c = a, a + 0 = a, a - a = 0.. If there are no negative numbers, there are no square roots of negative numbers. Proof of Fermat's Theorem for Village Idiots (n>2) c = a + b c^n = a^n + b^n +f(a,b,n) (Binomial Expansion) c^n = a^n + b^n iff f(a,b,n) = 0 f(a,b,n)0 c^n a^n + b^n QED Also valid for n > 1 c^2 = [a^2 + b^2] + [2ab]] 2ab < >0 c^2 a^2 + b^2 QED (Pythagoras was wrong; use your imagination) Check out my pdfs in physicsdiscussionforum "dot" org.

@shubhamg9495 Жыл бұрын

This video is a gem.

@markharris1223 Жыл бұрын

The single statement which did not leave me mystified was about mathematicians' tendency to overcomplicate. My relationship with maths at school was fraught. The single rule followed by all my maths teachers was: "Don't explain why". I loved, and was successful at ancient Greek, Latin and German at school, so I was not a dolt, but no maths teacher ever deigned to tell me why I was attempting to find the value of x. I went on to be a teacher of German. When a pupil seemed mystified by some aspect of German grammar, I used to say: "Any idiot can learn German. Look at me!". I watched this video because I find Gödel an interesting character. His diary describing his homesickness for Vienna ("Ich have manchmal Heimweh nach Wien") reveals a delightful character struggling to deal with his many issues. His diary steers clear of maths but gives fascinating detail, i.a., of his marriage to a nightclub dancer. I was reminded of Dirac's preoccupation in later life with Tina Turner.

@nilp0inter2 3 жыл бұрын

Thank you very much!

@stablesort 3 жыл бұрын

I am glad you liked it!

@veganwolf3268 2 жыл бұрын

I see a flaw in the diagonalization proof. When you add 1 to a function you are applying the successor function to the function, so even if your new function is not part of your list, it can be derived using the axioms of the system, namely the successor function or Peano's 5th axiom. Your premise is your list contains all possible functions that can be derived. Apparently this premise is false because you demonstrated that a new function can be derived. However, Gödel's theorem states that it can't be proved or derived, so the real contradiction is you claiming you can't prove or derive your new function when you just did that very thing.

@NaturalDutchSpirit Жыл бұрын

Nice job on the 16min 9sec video trick

@andersonmeneses3599 Жыл бұрын

Thanks!

@plucas2003 21 күн бұрын

isso é sensacional, fico muito triste que não pude ver isso na minha turma de lógica matemática!

@alejorabirog1679 8 ай бұрын

Thank you :)

@constantinefrangakis4379 2 жыл бұрын

Hello, I have a question. Suppose in the Logic setup of 10.33 sec, we consider the formula K(n), that for each n, is NOT Fn(n). But by the same argument as in Computer setup at 12 min, K(n) cannot be any of the F1(n), F2(n),... But lexicographically, if we can code the diagonal Fn(n) for n=1,..., we can also code Not Fn(n) for n=1,... Can you help me resolve the contradiction ?

@DarrenMcStravick Жыл бұрын

... is that a bok choy in a whiskey glass...?

@cormacmallett2449 2 ай бұрын

It would appear so...

@dulat1 4 ай бұрын

Hey thanks for the great video! maybe someone sees this and can answer. I don’t really understand why does Godel go through all the hustle of coming up with this encoding. Conceptually it is exactly the same idea as: - This statement cannot be proved. So my question is whether this is correct. Is the whole number encoding thing just to make it more formal or is it in principle different from that self-reference trick in the linguistic sentence?

@user-wp5gu2sy3f Ай бұрын

Resolution by infinit induction over ik-1 + jk resolution on Aleph reels

@5r3t5n0m 4 ай бұрын

It feels like there is something off when you pick a non-provable formula and put it in a set of probable formula. Feels like apples and oranges for a lack of better comparison. You're willing to assume something doesn't belong without proving it doesn't belong. Fxn Q cannot be on the list because it's a function of a function. Wouldn't that mean that it automatically becomes a two parameters function?

@robinschaufler444 8 ай бұрын

Elegant explanation. As a retired software developer, I really got your programming example. But what's the deal with the bok choi?

@Darkev77 2 жыл бұрын

At 10:18, if we assume that formula's necessary existence, couldn't we just apply that (negation) formula to literally every "F_n" (known and unknown) that exists within our system and hence suddenly all enumeration formulas for 1 variable are either unprovable or contradictory? Something is flawed here...

@pallharaldsson9015 Ай бұрын

7:35 The Gödel's encodings clever but it does NOT result in finite numbers, even with a finitely long statement (in general). Is that a problem? I don't know. I.e. the empty statement is always 0, but even a single-letter statement seems problematic. While e.g. the single-letter "f" is 2^3 = 8 *given* the table of letters there ("f" = 3 is ok, it doesn't have to correspond to ASCII). Unlike ASCII and Unicode which are finite encodings, for any possible statement the set of letters needs to be infinite, and then "f" could be an arbitrarily high number depending on where you put it into the encoding table, and having it in the first few elements of the table is an arbitrary ordering of letters. I'm not saying it needs to be "last", infinitely high number, but it could be. There ARE infinitely many numbers, integers, AND rationals, so it's unclear to me if it's a problem, i.e. you can encode each pair of numbers for a statement and a proof into a rational (only not divide by 0, doesn't seem like a real limitation, though I'm not sure).

@danstoian7721 3 жыл бұрын

Thanks a lot! Very interesting. I know about Godel from a Logic professor I had as a student. The second proof is similar to the proof that the infinity of rational numbers is greater than the infinity of integers. But I guess it's because of the diagonailization stuff I don't understand

@stablesort 3 жыл бұрын

Right, Right. The "Cantor's denationalization" argument essentially constructs more and more rational numbers that could fit in between two integers. The assumption is that it's possible to enumerate all rational numbers, which turns out to be false. Thus, there are more rational number than "counting" numbers, or natural numbers. In our case, we try to enumerate/list all possible functions. At the first glance, it seems like a reasonable idea - just list them shortest to longest, trying out all possible combinations of characters. But then we show that there is a function that is not in the list!

@danielgautreau161 7 ай бұрын

You CAN enumerate the rationals. The set of REAL numbers is uncountable.@@stablesort

@fabianperson Жыл бұрын

Very well.

@jeffbguarino Жыл бұрын

Things that bother me is when they scale things up. Like having very large numbers represent statement and using an algorithm to convert back and forth. When the numbers become really huge , this whole thing breaks down, due to practicality. But practicality of the universe and quantum laws. You can only make a number so large , you need matter or light, energy to represent the huge numbers. When you reach a certain mass , your computer will collapse into a black hole. Cantor's diagonal slash will fail. Just keep making your piece of paper bigger and bigger and it will collapse into a black hole. If you try making your numbers smaller and smaller , eventually you will get quantum tunneling and the numbers will be all over the place and the method will fail completely. That is what all the mathematicians do, assume Planks constant is zero and they ignore Einstein's GTR. The do it all the time. They also ignore time and only use space. The space on the paper or blackboard. They assume that every statement happens instantaneously . Like A=B+C. So is this statement just there ? or does it happen as you read it from left to right. It takes time to read it. So not only space is involved but time also. So a 100 page proof just exists in space. It is there all at once with no time component. But in reality there is the space time continuum. A proof should be able to have more than one answer just like the electron going through a double slit , never lands on the same spot twice. I have a feeling that physics in the last 30 years is making no progress , as in joining Quantum and General Relativity because they are all using math. The math that was created using classical physics. Math has no quantum aspect to it at all. You don't get elements of a set tunneling out into another set. But this is how the world works.

@ROForeverMan 8 ай бұрын

Consciousness is all there is.

@mohamedmusharaf406 4 жыл бұрын

Sir! Is it possible for you to do a video on Aho-Corasick String searching algorithm?

@stablesort 4 жыл бұрын

That's a great suggestion, thank you. I am adding this topic to my list. Cheers!

@lake5044 3 жыл бұрын

Question: How do we know that the function Q is a "valid" function in the first place? Just because we can write it as "Q(n) = Fn(n)+1 (for each n in N)" does not prove that it can be generated by concatenating all the allowed characters of the compilable language. There is no way to refer to "Fn" given that they are infinite. And therefore, the function Q requires infinite characters to be well defined; the naive way would be hardcoding the output for every integer. Which means that this function does not prove that there is a function that can be obtained by compilable strings that would not be in the enumeration F.

@stablesort 3 жыл бұрын

Good question. How does one know if any function is a valid function? Well, a function must conform to a grammar. All grammars can be defined by a finite state machine + memory stack (standard axioms of logic) that consumes “tokens”, such as variable names, numbers, brackets, etc. You feed a string that represents a function into this state machine and then check if the last state is a “terminal” one. As in, all opening brackets matched with closing ones, etc. If not, then it’s not a valid function. Going back to “Q(n) = Fn(n)+1”, indeed there are infinite number of functions but that’s OK. When referring to some specific Fn, such as F12345, it automatically means that we picked that specific function out of the set of all valid functions, even though the size of that set is infinite. It’s like saying the size of the set of all positive integers is infinite, but we can still refer to any specific positive integer. If you are not convinced, here is another example. We have a set of all natural numbers, let’s call it N. Obviously it’s infinite in size. But still, given any number you can decide if that number is in this set or not. This decision making, as I understand it, is granted by the rules of inference and the definition of what a “set” is. I hope this helps.

@rafaellopezmartinez6200 3 жыл бұрын

Great explanation! Maybe it would be good to point out that this construction is also used (as you said by Cantor) to proof that Real numbers are infinitely more than naturals, which are also infinite! The last example about the list of compiling functions was genius! Thanks a lot.

@stablesort 3 жыл бұрын

Great suggestion!

@user-uu1bx4xv1s 4 жыл бұрын

wowwwww！every day i come to your channel check whether you update new episode！

@stablesort 4 жыл бұрын

Thank you for your words of encouragement =)

@dosomething3 3 жыл бұрын

I was sure you were a bot 🤖. But I see that you are real.

@bohanxu6125 3 жыл бұрын

I understand enumerateable formulas are not general functions.. the later is of course uncountable. Question 1: I still don't see how to resolve the contradiction between {the set of enumerateable formulas is countable}, and {the cantor diagonal self-referencing formulas is enumerateable}. If {the cantor diagonal self-referencing formulas is enumerateable} is true... we can use it (and cantor diagonalization) to prove that {the set of enumerateable formulas is countable} is not true Question 2: Is the listing at 12:44 (order by length, exhaust all characters, and throw out the ones that is grammatically incorrect and the ones that doesn't express a formula) a proof that {the set of enumerateable formulas is countable}? .... or it's not a proof because "the throwing out" part might not halt... so it's not a valid construction of a list of enumerateable formulas?

@asmithgames5926 4 күн бұрын

I believe all proofs of Godel's FIrst Incompleteness Theorem are invalid, but the theorem itself is true. Self-contradictory statements shouldn't be allowed (and aren't even a normal feature of theorems we write in math). Think about all the hand-waving these arguments have. And in Godel numbering, attempting to encode "This statement is not provable" wouldn't be so easy. There is no "this statement" symbol, so to encode this concept in the Nth statement, we'd have Statement(N): "Statement(N) is not provable". Encoding this would create a large number much greater than N, which would result in this NOT being the Nth valid statement. So the Godel numbering itself would prevent against self-referentiality, unless the arithmetic specifically had a symbol for encoding the concept "this statement". So for any system, you could add a "this statement" symbol to its Godel numbering, but by doing so you'd be making your system 'weird', in that most mathematical systems don't bother with self-referentiality. Basically, I'm conjecturing that Godel's First Incompleteness Theorem is "incomplete" (unproven) for non-self-referential systems. (Meaning, it is possibly true, but hasn't been proven.) Put another way, Godel's First Incompleteness Theorem is the Tyler Durden of mathematics. This is still the best video I've seen on the topic so far.

@dosomething3 3 жыл бұрын

I wasn’t listening. But heard every word. I’ll give it another shot.

@stablesort 3 жыл бұрын

There are a lot of subtleties involved. I have been coming back to Godel's Incompleteness Theorem for years and I find something new every time. So don't be discouraged=)

@naveenkumaruthamanthil3579 2 жыл бұрын

Thanks for the great video! Frankly, not v clear about the concept, especially the diagonalisation argument that was made towards the end. Defention of Q(n)=Fn(n)+1 is fine. Then comes the question, does Q(n) exist in the list? You say it couldn't becaise its the diagonal element + 1. Hope my understanding is correct upto here? My confusion or rather question is why can't Q(10) be, say Q(10) = F11(11) = F(10) + 1? What's preventing us from making a table which satifies the above? Am I missing anything? Thanks in advance ☺️

@henrikf8777 2 жыл бұрын

The question is if the function Q is in the table. If: Q(n) = F_n(n) + 1 = F_n+1(n+1) Then it's still different from any F_n() since F_n(x) is not equal to F_n(n) + 1 even if that equals F_n+1(n+1)

@chingkui 3 ай бұрын

The diagonalization argument for the first incompleteness proof at around 11 minutes cannot be right. Here, the index j is actually a function of n, that is, if -P(Fn(x)) is the formula Fj(x), then for a different m, -P(Fm(x)) is in general a different formula Fk(x) where k≠j. For a concrete example, if Fn(x) is the formula that state that there is a graph with exactly x vertices that satisfies a certain definable properties and Fm(x) states that a particular diophantine equation has more than x solutions, then -P(Fm(x)) and -P(Fn(x)) cannot be the same Fj(x).

@chingkui 3 ай бұрын

The mistake is that when you choose the index n, you also fix j. You can't independently change n without affecting j. When you quantify the equivalence between Fj and -P(Fn) over n and wrote ∀n (Fj(n)↔-P(Fn(n))), you are causing confusion by mixing the variable n and the constant index n of Fn. But they are not the same thing, one is a variable, the other is a constant, they just happened to share the same name. When you wrote Fj(j)↔-P(Fj(j)), you are turning the notation confusion into a real mistake because the quantifier only applies to the variable n, not to the constant index n of Fn. If you spell out everything without any hidden dependency and notation ambiguity, then you should have written ∀x (Fjn(x)↔-P(Fn(x))) (note that I am using jn to highlight j's dependency on n). And then all you can claim is Fjn(jn)↔-P(Fn(jn)) which is not the desired incompleteness statement.

@Epoch11 2 ай бұрын

Why couldn't Q be (n-1), I don't understand this proof I understand it in regards to cantor's proof of infinity but not here.

@fisheromen18 Жыл бұрын

It seems to me the diagonalizaiton argument demonstrates nothing more than the existence of functions that cannot be expressed by a finite sequence of symbols. In other words, the set of all functions that can be expressed in our mathematics is countably infinite, the but set of all funcitons is uncountably infinite. But I do not see how this parallels the incompleteness theorem stating there are statements that cannot be proven or disproven. can anyone help my understanding here?

@ThichMauXanh 2 жыл бұрын

I'm completely lost. Please help! Let's suppose F_n(n) = n^2 + 1. So what does it mean to say notP(F_n(n))? "Not Provable(n^2+1)"? What does this even mean?? And how is this even some F_j(n) given the fact that F_j(n) is just some formula like 2n+1.... Your explanation up to this point was slow and all good, but it is just frustrating at this point and you did not explain or give any example at all...

@radscorpion8 Жыл бұрын

I'm a little unsure about one part, you said suppose there is a formula with the format of NOT Provable(F_n(n)) - or !P(F_n(n)) for programmers. Now on the previous slide you have P(A) = Pr(s), which was the set of godel numbers for all provable statements. So first of all !P(A) should return a set of godel numbers for all unprovable statements, rather than a formula that outputs a single natural number. But anyway, that minor discrepancy aside, lets say that !P(A_i) chooses for a single godel number for some group of unprovable statements, and you equate that to !P(F_n(n)). The problem is it seems that we are assuming !P(F_n(n)) is a natural number, or that it exists, which hasn't been demonstrated. For all we know the set of godel numbers for all unprovable statements is empty. So it seems like, in a more complex manner, we are essentially just assuming what we are trying to prove. I really love the explanation though! I will definitely read his paper to see what he learned, as i know you said this was just a sketch :)

@georgecazacu6118 Жыл бұрын

At time 9:52 Pr(s) is not clearly defined. Is it the set of all p numbers or the set {0,1}, i.e. TRUE/FALSE? Either way, it creates confusion down the way when you introduce the ~ (non) operator in the diagonalization process.

@joesjoberg7417 3 ай бұрын

I was confused for a minute as well. The words on the screen are misleading. Pr(s) = exist(P) proof(P, s) is NOT the set of godel numbers of all provable statements. Instead, Pr(s) is the statement that 's' is/isn't provable. In other words, Pr(s)=0 or Pr(s)=1. And ~Pr(s) = 1 - Pr(s)

@nitinissacjoy5270 Жыл бұрын

You got me at 6:00

@SilvioZanin 2 жыл бұрын

Why diagonalization implies that Fj(j) cannot be proved?

@reedarnold7905 Жыл бұрын

So are the non-provable statement's numbers... prime? I've been musing over the last year or so that the real number line is entirely self-referential. The number-line creates itself. R = U(2R, 3R, 5R, 7R, 11R...pR, etc) for all primes. This means that, for instance, the distribution of prime numbers is mirrored in the distribution of the multiples of 2, and 3, and 4, etc. etc... Anyway. For true mathematicians this is probably a pretty banal thought. But something about the 'self-creation' of the numbers terrifies me and seems somehow pertinent here.

@blueckaym Жыл бұрын

"5 proves 7" doesn't have mathematical sense at all. Not because of the specific numbers 5 and 7, but because they "sense" they have comes from their original text (that produced the given numbers when encoded). Ie the "proves" in the sentence comes from outside math too. So how you're supposed to operate within Math?

@wdobni 8 ай бұрын

i'm sure it makes some kind of sense on a mathematical plane.....to me it sounds more like a paradox than a theorem...it might be analogous to Xeno's Theorem which proves you can't get from A to B, wherein to get to B you must first go half way, and then half of the remaining way and then half of that which still remains and there is no end of dividing distances in half and therefore you can never reach B in mathematics it is not very difficult to make absurd statements and postulates seem profound....the square root of negative one is a simple example that pervades mathematics and is itself a paradox that is offensive to the mind but used everywhere all the time. the point is that somebody will eventually invent a mathematics that proves Godel's incompleteness theorems are wrong.....probably by using an infinite ramanujan series and e and i and a new definition of 'diagonal'

@SkillUpMobileGaming 3 жыл бұрын

At 9:35, why is there a "for some" symbol instead of a "for all" symbol?

@fullfungo Жыл бұрын

It reads: *there is* a proof (p) for the given statement (s). If you used for all, it would be: *all* proofs (p) prove the given statement (s); and this is clearly false.

@beutyindetail Жыл бұрын

how do youtubers can say the exact length of their videos. it happened many times already. like, how did you know that it would be 16:09 long?

@ramkrishnadas4230 2 жыл бұрын

Let us see, if I can get it this time. May be this will prove that I can get it.

@TheSpuerto 2 жыл бұрын

Loved the bok choy

@stablesort 2 жыл бұрын

@andie_pants 2 жыл бұрын

We can neither confirm nor deny the existence of...

@s.a.vanvleck45 3 жыл бұрын

There may be a problem with your proof ... your enumeration of all formulas with one free variable makes sense, because the number of such formulas is countable. However, your "diagonal" formula F() is not a formula of a free variable, since it is a different formula for each n, i.e. F(1) and F(2) are not the same formula with a different value for its free variable, but are different formulas. As such, it does not have to be one of the enumerated formulas. What am I missing? (You could say that F() is a *function* of a single variable. However, the number of *functions* , not *formulas*, of a single variable is not countable, so then the enumeration is not possible. I guess you have to limit yourself to some concept of functions that are somehow definable, or constructible, by formulas? That wasn't clear from the lecture.)

@stablesort 3 жыл бұрын

Great question. Yes, you do have to limit the discussion to "valid" formulas (and "valid" functions for that matter). And by that I think it's fair to say formulas that are grammatically/syntactically correct. For example, "F(x) = 2x + 1" is valid, while "F(x) = 2x+" is not valid. Going back to your original question, even when talking strictly about formulas, since they are enumerable, there is a set of them and each has an associated number. For example, formula #123. It's also possible to have one formula reference some other formula in that set. For example: F234(x) = F123(x) + 1 Remember that we are talking about natural numbers only. Which means all of the formulas could be defined as lookup tables, just like in Excel. Given input n, the function looks up the corresponding value in the table. As such, the values in the table could be defined totally arbitrarily. By the same argument, you could define a function that returns values exactly as reading from the diagonal of our enumerated formulas. What do you think, is that too much of a stretch? =) Full disclosure - 16 minute video is not enough to touch every detail of Godel's proof. I did my best condensing it to the key points, but still, there is plenty of room for exploration.

@s.a.vanvleck45 3 жыл бұрын

@@stablesort That would help, but I don't think that's enough ... Consider the set of all functions that map the natural numbers to {0, 1}. Then all such functions result in valid formulas, but there are as many such functions as there are subsets of natural numbers (i.e. each f defines a subset f^inv(1)), which is the continuum. So I think we have to look at a more restricted set of functions -- those definable by formulas? -- such as the diagonalizing function is still one of them?

@stablesort 3 жыл бұрын

@@s.a.vanvleck45 I am redacting my previous comment - it's totally confusing (I completely misunderstood your point). My apologies. I am going to think about this a little more before I make any more incorrect statements... To be continued.

@johnrickert5572 3 жыл бұрын

If we are using 0, + - x and / with a free variable t, then I believe the formulas will be rational functions. If that is correct, then e^t would not be on the list. (Or one could take the integer part of e^t if the range has to be N.)

@kazikmajster5650 Жыл бұрын

Dude, the English language IS axiomatic!

@gniewo6 Ай бұрын

Why?

@pendaranroberts4350 3 жыл бұрын

Given that Cantor's supposed proof that there are more real numbers than natural numbers is a proof of something that makes no conceptual sense, I wonder now whether Godel was also just conceptually confused.

@stablesort 3 жыл бұрын

Thanks for leaving a comment. Indeed, convincing yourself that there are more real numbers than there are natural ones is a hard pill to swallow. I guess when dealing with infinities, it's hard to anything conceptually concrete. It's all a matter of using some set of rules for constructing numbers and listing them. And going by those rules it turns out it's possible to reach certain conclusions - such as that there are more real numbers than natural and that the rules themselves are not entirely complete.

@jamestagge3429 Жыл бұрын

I am very dyslexic so i have a problem trying to understand things like Goedel's theorems which are always defined in such technical terms. I can do NO math. I better understand when things are conveyed in a more "mechanical" manner. All i would like to know is the simple outline of the process, i.e, he took a formula like (whatever) which stated (whatever) and translated that via Russell's calculus or other mathematical symbols, etc., to his numbering system or whatever....in other words how did he get to the statement "this statement cannot be proved". Literally, physically how did he get there because it is a self-referencing statement and they are meaningless. It is then claimed that if the statement “this statement cannot be proved” is true, then it must have a proof. Proof of what? Can one say that “there is a proof of that” when “that” is not identified? That rule in such a case is then as meaningless as the statement which is its object. There is no content in the latter to which the former refers. We are conveying gibberish. If one traces the formulation of “this statement cannot be proved” back to the material of its origin, what is conveyed in that (I ask because I have no earthly idea. All of the vidoes do a horrible job of explaining this process if layman’s terms). I would have thought that propositional calculus alone would have been a sufficient means of reformulating mathematical statements into those semantic, but it appears that more translation was required, thus the Goedel numbers. So I believe that if we extrapolate back from “this statement cannot be proved”, which is a self-referencing statement, which is by that alone, illegitimate and conveys no information about anything, to generate such a contradiction, a means permitting contradiction would be required. Consider, a self-referencing statement cannot be formulated unless the subject content is eliminated that the paradox might be manifest. This is sophistry and not science. If Quines paradox was his inspiration then there is something very wrong. How can such a purported feat of mathematics arise from the implementation of such a fraud as self-referencing statements? Refuting Quine’s paradox or any other is easy. I would enjoy demonstrating. Please could someone explain this Goedel process to me in the context of the aboves?

@ROForeverMan 8 ай бұрын

Is simple: mental masturbation.

@ebsolas 3 жыл бұрын

I see what you did there 6:09

@veritopian1823 2 жыл бұрын

Thanks for the vid. It seems to me there's a categorisation problem with Godel's argument though... The "diagonalisation" function is a different *kind* of function from the others - i.e. the function applied is dynamic not static. The example given implies that all the functions in the table are not able to reference each other. They're standalone functions, and have no access to the table / list of functions. But the diagonalisation function has an extra layer of abstraction. It IS able to "see" the table and reference it, whereas the functions in the table are not. It is a "meta" function - able to abstract not just the parameter, but the function itself. In programming - the table contents would correspond to hard-coded function names - e.g. sin($x) But the diagonalisation function is a dynamic function - e.g. $x($x) There would have to be a separate table of "functions which can reference the table", for it to be logical. It seems to me that all of Godels incompleteness arguments are similar, IMO he does not categorise things properly - i.e. he doesn't seem to draw a hard conceptual distinction between iterative and non-iterative processes... - the 'halting problem' is exactly that...

@adityamishra7711 Жыл бұрын

i think i can understand what you are trying to refer to.... but from a mathematical perspective, the diagonal function is isomorphic ( identical to ) to any function having a single free variable.... and thus it must be in the list...moreover there is no proof that other functions can't refer to toher in this list... so what you really need is a contadiction to rule out the consideration of diagonal function in this list... which we don't have... otherwise atleast mathematically its completely logical

@veritopian1823 Жыл бұрын

@@adityamishra7711 I just rewatched the vid... No, I was right... Function Q cannot exist in the list because it *depends on* the list. The list must exist before Q can be defined. This is not the case for any of the functions in the list. They are different categories / levels of function. Q is a meta-function. As I said before. Godel's reasoning was flawed. Thanks for your reply.

@user-vz3yh9gi1l 11 ай бұрын

@@veritopian1823 Godel never said that he doesn't use meta-analysis. On the contrary, his theorem is constructed using an embedded meta-language that can talk about itself. Another thing, of course, is that Godel's theorem is a piece of shit. Similar to Haling Problem, which totally ignores "hot" metaprogramming, which is supported by some realworld languages and realworld platforms. If we proceed from your example, then indeed, when the table itself becomes dynamic, the theorem will not work. Fortunately, there is nothing static in the World and in the world of mathematics, because mathematics works in human brains. Everything that works in them is dynamic by definition. Alas, our great "genius" was not aware of this. Surely he couldn't have known cognitive science before it was created? He is not so genius as to conduct a valid meta-analysis of fully dynamic structures and assume that, in fact, only such an analysis can be valid in general. It's too complicated for a real genius. It is much easier at the end of life to go crazy and starve to death, suspecting that someone want to poison you. Here it is, the thinking of a genius. The public loves it and encourages it with glory.

@theoneed2051 2 жыл бұрын

Is that a plant, or a vegetable to his right?

@Eddy-dk6ug 3 ай бұрын

I thought that was Logic

@markwrede8878 5 ай бұрын

Apparently Godel thought god would provide completeness. The theorem proves inconsistency.

@raresaturn 3 жыл бұрын

all this Function experiment does is prove infinity+1 is still infinity

@stablesort 3 жыл бұрын

Well said =)

@Lolwutdesu9000 2 жыл бұрын

At 5:35, surely the second theorem 2 should be another number, like 5? Is this a typo? Otherwise, we essentially have a form of circular reasoning.

@yoavshati 2 жыл бұрын

It's actually very common to use the same theorems multiple times in a proof You're not using 2 to prove 2, you're using 2 twice to prove something else

@meltedice-cream6499 2 жыл бұрын

Didn’t N started from 1 and not 0

@stablesort 2 жыл бұрын

Depends on which textbook you go by. I believe it used to be that natural numbers started from 1 but later on the standard became zero. Doesn't really matter IMHO :)

@v2ike6udik 6 ай бұрын

nice illuminati butterly.

@ROForeverMan 8 ай бұрын

Self-reference is not what you think. Self-reference is God: I am God.

@tchaivorakfauresohnsieg9532 6 ай бұрын

Are you Italian?

@nowisthetime12 3 жыл бұрын

Your use of "contracts" when I think you mean "contradicts" is confusing.

@stablesort 3 жыл бұрын

Thanks for the comment. Did I mispronounce it at some point in the video? Not sure where that happened.

@Tadesan Жыл бұрын

I have cabbage on my desk so your argument is invalid.

@ernsaglam Жыл бұрын

what the real fck did I just watch?

@marcomaiocchi5808 Жыл бұрын

when talking about such complicated topic, start with a simple example first

@rkara2 4 ай бұрын

Bok choi for dinner?

@anonymousperson4639 2 жыл бұрын

Here’s the real question-why is my math teacher giving me this as homework? *i am twelve for your information* I am just wondering-

@noreigaoconnorspecialk6771 8 ай бұрын

Takes too long to illustrate the "diagonals"

@swenmeinert3967 3 жыл бұрын

No, not clear.

@stablesort 3 жыл бұрын

Sorry, this is a hard topic. May be try this: www.jamesrmeyer.com/ffgit/godel-original-english.html

@swenmeinert3967 3 жыл бұрын

@@stablesort For me it goes to fast with those mathematical expressions.

@lake5044 3 жыл бұрын

@@swenmeinert3967 It's really hard to time the pace of math explanations. What I find useful is to pause at every new equation/expression until it makes sense, and then resume watching.

@fullfungo Жыл бұрын

@@swenmeinert3967 set it to 0.25x

@kallianpublico7517 7 ай бұрын

You have not explained what an axiomatic system is. Why do I state this? Because you state, matter of factly, that language is not an axiomatic system without giving an explanation. Also you fail to use the word tautology. When you mention Tarsky and his assertion that, basically, mathematical meaning can not be derived from linguistic meaning you get to the heart of the matter, but skip it. The narrative of math is not like the narrative of language, but you do not give the logical next deduction: which narrative is prior and which is posterior. Math is inferior to language because mathematical reasoning can never create language whereas linguistic reasoning can always create math. Mathematical meaning, though successful, can only hope to approach the scope of linguistic meaning. To highlight the abyss just try and present a mathematical definition: a formal system, of time.

@ivangaborige8623 Ай бұрын

Gödel's first incompleteness theorem is fundamentally logically flawed. Even the math could be complete. - A fact of scientific history. He is afraid, but rather very close to the whole, a profession in the field of mathematics, he laughed and laughed when Gödel already formalized the mathematical formalization. He just wanted to use numbers. It didn't even go through, it already failed. In mathematics. This, in turn, helped Neumann in computing. Because, paradoxically, Gödel's only usable theory was Gödel numbering / coding. Which also had practical benefits. Of course, only at first in computer technology. When every character and bit had to be saved. Well, what was useful was exactly what failed in mathematics. What is useless and wrong has been raised on the altar.