Godel's 1st Incompleteness Theorem - Proof by Diagonalization

[@skeptic3045]

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

[@stablesort]

Thanks and welcome aboard!

[@balthazarbeutelwolf9097]

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]

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]

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

[@stablesort]

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]

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

[@mahanmoshiry7304]

I really do appreciate that you described the theorem rigorously and didn’t “dumb it down” , while maintaining attraction.

[@williamrhopkins]

Excellent. This is by far and away the best exposition of Godel's work I have come across. I appreciate the programming language approach at the end. I believe this was how Alan Turing came at the subject.

[@adriangalvez798]

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

[@williamrhopkins]

If I recall from reading it years ago, Hofstadter uses the following approach. Suppose I have a formal, system G and within that system I can write a statement "I am not a theorem of G" then either the system is inconsistent or incomplete. He skips the details of how to write the statement but captures the essence of the argument beautifully.

[@Ko_kB]

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

[@farouqzaabab9668]

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]

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]

​@@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 kzbin.info/www/bejne/rJ2thIeXq66Mac0

[@stablesort]

Thanks, I'll definitely try that next time.

[@allensong8354]

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

[@metaskepsistu_berlin9598]

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

[@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.

[@amitozazad1584]

We need more of such stuff on youtube! Awesome!

[@stablesort]

Glad you liked it!

[@freddyfozzyfilms2688]

I really like the computational intuition you bring to mathematics

[@stablesort]

I appreciate your compliment, thank you!

[@2tehnik]

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

[@stablesort]

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]

​@@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]

@@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 =)

[@nullspace_repo]

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!

[@asmithgames5926]

Eagerly awaiting your Second Incompleteness Theorem video!!

[@pkr619]

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]

Thanks for the words of encouragement; will do!

[@aleksandarrudic3694]

This video should have a Godel number of views

[@DarrenMcStravick]

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

[@cormacmallett2449]

It would appear so...

[@UMaaM8]

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

[@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.

[@blairhakamies4132]

Well done. Congratulations 👏

[@traviswalker9327]

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

[@amatya.rakshasa]

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!!

[@SanjilDhakal-1729]

Why we are defining such function which can not give all possiable Gödel numbers ..I'm talking about negation function you defined 10:20 ..F j(n) => ~P(F n(n))..this function checks provability of statement of diagonal Gödel number only ...Or I'm still not getting please explain .?????🤯🤯

[@秦强-q7o]

this vegetable bonsai is impressing

[@lincolnuland5443]

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

[@veganwolf3268]

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.

[@shubhamg9495]

This video is a gem.

[@NaturalDutchSpirit]

Nice job on the 16min 9sec video trick

[@glennpaquette2228]

Something is strange here. At 9:53, he says that Pr(s) is the set of Godel number of all provable statements. Then he says P(A) = Pr(s). But P(A) is not a set. It is a provability predicate. What's going on?

[@alejorabirog1679]

Thank you :)

[@aenimosity7]

Thanks for the great video!!

[@SilvioZanin]

My question is: When you call A = for example, F1(n) = n+1, g(A) is the Gödel number of this, and there's a proof of F1(n) that's for example, Fn(n) = B, and g(B) = p, that's the proof of statement A. When you call P(A), this is the proof of statement A, that's p (g(B) or is ANOTHER proposition that's "A is provable"? Because both can be associated with a Gödel number and, if there's a number for both of them, there's a formula Fj(n)...

[@nilp0inter2]

Thank you very much!

[@stablesort]

I am glad you liked it!

[@dosomething3]

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

[@stablesort]

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=)

[@Darkev77]

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...

[@robinschaufler444]

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

[@asmithgames5926]

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.

[@lake5044]

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]

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.

[@homomorphichomosexual]

as far as I understand, this is why you need to be able to encode a certain amount of complexity in the system - basically enough to define the function H(i) that picks out F_i. if you can define this function so it's defined by a finite string and halts for all inputs, you can then define its negation. python example: def get_method(x: int) -> callable[int, int]: # Enumeration to pick out f_x for the relevant language here ... def Q(x: int) -> int: # Shows that the enumeration doesn't work for all valid Python functions, # since this is a valid (halting) Python function from int to int. To show this for another # system S, we'd have to be able to encode this function in the system. f_x = get_method(x) return f_x(x) + 1 so this relies on being able to encode the function that gets you the table into the language!

[@5r3t5n0m]

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?

[@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]

Consciousness is all there is.

[@Khashayarissi-ob4yj]

With luck and more power to you.۔ hoping for more videos.

[@rafaellopezmartinez6200]

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]

Great suggestion!

[@plucas2003]

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

[@larsprins3200]

At 13:07 : we just care about "valid" functions, requiring that their character string is of finite length. Defining Q(n) as F_n(n), its character string would need to include the character string for the formula of each F_i(n) of which there are infinitely many. Doesn't this mean that Q(n) is of *_infinite length_* and hence not a "valid" function? Q(n) would thus not be a contradiction to the original assumption that it is possible to list all "valid" functions, i.e., list all possible formulas with one free variable?

[@andersonmeneses3599]

Thanks!

[@danieleppelsheimer9273]

Great explanation!!! Thank you

[@dulat1]

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?

[@errorite6653]

The encoding Gödel originally used is somewhat arbitrary; all that is needed for the proof to work is a computable bijective mapping between the set of sentences/proofs in the language of Peano arithmetic and the set of all natural numbers. Gödel's prime factorization approach is just one way of achieving that, but a direct enumeration of all grammatically valid combinations of characters would also work, since they could technically be listed off one-by-one, even if very slowly. Once this mapping has been proven to exist, the precise mathematical statement that Gödel proves is literally that, "There must exist a natural number g such that the statement with Gödel number g is true if and only if there exists no natural number p such that p is the Gödel number of a verifiable proof of the statement with Gödel number g." Sorry if that sounds convoluted lol

[@unexpectedTrajectory]

Your 2nd proof is quite interesting (my background is also CS though I love math). I think, though, that it's a bit off, or that your conclusion is. The problem I'd assumption/criteria #4 for the functions/programs. You can't know for all programs which do or don't halt (I'm pretty sure you know that.) So you absolutely CAN make a sequential list of programs that compile (setting aside my spidy sense that certain programs probably are valid but don't compile because they would require the compiler to solve the halting problem...). What you can't do is write a generic program that diagonalizes across those programs or arbitrarily simulates any of them and then ads 1 AND always gives an output, because you still haven't solved the halting problem. I think you basically recreated a proof of the halting problem, rather then proving that the programs aren't innumerable. The set of all valid programs is clearly a proper subset of the set of all strings (interpreted as programs), and the set of all strings is clearly of the same cardinality as the rational, which Cantor showed to be numerable (countable) by the other kind of diagonalization. Let me know if you think I misunderstood you. Thanks.

[@unexpectedTrajectory]

Ok, re-relistened to that section. Yes, I'm convinced the issue is #4. You can innumerate/list all valid programs, but you can't list all programs that halt. Q(n) IS on the list of all programs, it just doesn't halt. Actually imagine it running on itself. It's going to infinitely recurse (simulating f requires simulating f requires simulating f requires...)

[@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).

[@LeiZhu-v4t]

Other than the mistake with Pr(s) being a predicate instead of a set of Godel numbers, the first proof is incorrect in defining F_i(n) as functions that generate natural numbers. It needs to generate statements since the input A of P(A) is a statement not a natural number, otherwise P(F_n(n)) wouldn't make sense.

[@chingkui]

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]

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.

[@naveenkumaruthamanthil3579]

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]

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)

[@mohamedmusharaf406]

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

[@stablesort]

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

[@bohanxu6125]

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?

[@ThichMauXanh]

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...

[@卡机不]

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

[@stablesort]

Thank you for your words of encouragement =)

[@dosomething3]

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

[@BelegaerTheGreat]

Dude, the English language IS axiomatic!

[@gniewo6]

Why?

[@alexanderying1558]

10:01 Isn't the set of sequences here uncountable, i.e. there exists no such enumeration? If so, that would be a big issue in this proof idea...

[@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 :)

[@constantinefrangakis4379]

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 ?

[@danstoian7721]

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]

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]

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

[@s.a.vanvleck45]

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]

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]

@@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]

​@@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]

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.)

[@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?

[@adityamishra7711]

Well done !!, its intuitive

[@Epoch11]

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.

[@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.

[@wotr-wotr]

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)

[@pendaranroberts4350]

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]

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.

[@Neamhain97]

2:05-2:25 I don't like how vague these words are and how there seems to be no consensus on what these words actually mean.

[@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?

[@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?

[@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]

Is simple: mental masturbation.

[@unexpectedTrajectory]

3:25 I thought we also knew that no system could prove its own consistency?

[@unexpectedTrajectory]

Which you mentioned at the end...

[@wdobni]

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'

[@ramkrishnadas4230]

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

[@SkillUpMobileGaming]

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.

[@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.

[@ROForeverMan]

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

[@nitinissacjoy5270]

You got me at 6:00

[@theoneed2051]

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

[@fabianperson]

Very well.

[@mixpasta]

Loved the bok choy

[@stablesort]

:)

[@nowisthetime12]

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

[@stablesort]

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

[@BuleriaChk]

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.

[@ebsolas]

I see what you did there 6:09

[@markwrede8878]

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

[@Lolwutdesu9000]

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]

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]

Didn’t N started from 1 and not 0

[@stablesort]

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 :)

[@raresaturn]

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

[@stablesort]

Well said =)

[@tchaivorakfauresohnsieg9532]

Are you Italian?

[@veritopian1823]

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.

[@ТимофейТимощенко-н9ю]

@@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.

[@Eddy-dk6ug]

I thought that was Logic

[@v2ike6udik]

nice illuminati butterly.

[@ernsaglam]

what the real fck did I just watch?

[@marcomaiocchi5808]

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

[@kallianpublico7517]

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.

[@rkara2]

Bok choi for dinner?

[@noreigaoconnorspecialk6771]

Takes too long to illustrate the "diagonals"

[@Tadesan]

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