## ← 21-16 Godel's Incompleteness Theorem

• 1 Follower
• 70 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=la6BK5X2LI8" data-team="udacity"></div> ``` 1 Language

• English [en]

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. You may or may not have heard of Godel's Incomplete Theorem,
2. but since they are also mentioned in conjunction with the Halting Problem
3. and undecidability,
4. it worth saying a few words about them.
5. Godel's Incompleteness Theorem is named Austrian-born mathematician, Kurt Godel,
6. are concerned with mathematics,
7. but are actually closely related to undecidability
8. and as you might know, any mathematical system starts out
9. with a set of axioms.
10. What are axioms?
11. Axioms are statements which you assume to be true
12. without having any formal proof of them,
13. such as if A equals B
14. and B equals C, then A must also equal C
15. or you can always draw a line from one point to another point,
16. no matter where they are.
17. Those would be axioms.
18. Now axioms often sound very trivial, like this one here
19. or the fact that you can always draw a line between 2 points
20. but for many of them
21. there are actually scenarios where they are not true.
22. So axioms are the basis of
23. any mathematical theorem or proof.
24. Now what Kurt Godel showed, and it was a shocker at his time
25. and to many it is still today,
26. is the following:
27. So what Kurt Godel showed was that if you had a set of axioms
28. and they don't contradict each other
29. and they are listable,
30. which means you could have an algorithm that lists you all of these axioms,
31. so either they are finite or
32. they can even be infinite as long as you have an algorithm
33. that can produce them all; if this is the case,
34. then there are some statements
35. that are true but which you cannot prove
36. based on these axioms and this is what he meant by incompleteness
37. how he basically showed that
38. no matter what foundation you base
39. a mathematical system on,
40. as long as that is a consistent foundation,
41. then you can not prove everything
42. without adding additional axioms at least.
43. He also showed, and this is the second Incompleteness Theorem,
44. which is basically an extension of the first one
45. that a system of axioms
46. cannot not demonstrate its own consistency
47. and what that means is that
48. very informally,
49. a mathematical system can not be used to show that
50. it itself is consistent.
51. These 2 statements
52. are in a way very similar to the Halting Problem and Undecidability.
53. The axioms; you can think of those as programming statements.
54. So any program or algorithm
55. is composed of a number of simple instructions
56. that are then arranged,
57. and of course there is an infinite number of possible computer programs
58. that you can write, but they are made up of a fine set of building blocks
59. and the second Incompleteness Theorem
60. is of course very similar to undecidability
61. in the sense that it shows that
62. you cannot use a system to prove everything about that system,
63. very loosely speaking,
64. and the undecidability of the Halting Problem
65. and all of the other undecidable problems, of course
66. says that we cannot use algorithms
67. to calculate everything about algorithms.
68. I know that from a practical perspective
69. there's lots of criticism of this,
70. but truth be told, I just find that super fascinating.