Gödel's first incompleteness theorem explained using (almost) the most common 1000 English words
The Up Goer 5 Text Editor, based on the xkcd comic Up Goer 5, takes what you write and tells you whether any of the words you used is outside of the most used 1000 words in the English language. As a challenge to myself, I used the editor to write out an outline of (my understanding of) Gödel's first incompleteness theorem. I cheated a little bit, using ' ' quotes for some technical language. Enjoy.
Mr Gödel shows that writing and moving letters around can't tell us everything that is true about numbers (part one):
When I write words, each word is made of letters. So, a group of letters can have a meaning. The same is true when we talk about numbers instead of words, but with numbers, there is only one meaning, and we can use different "letters" to change the meaning. So, if I want to say "one is the same as two," I can write '1=2' (which is not true), and if I want to say "one is not the same as two," I can write '~1=2' (which is true). If we start by saying obviously true things, like '0=0' ("nothing is the same as nothing") or '0+x=x' ("a thing added to nothing makes the same thing"), we can use letters to say new things, like '(0=0)^(0+x=x)' ("nothing is the same as nothing, AND a thing added to nothing makes the same thing"). But can we find out everything that is true about numbers just by saying some obviously true things and moving letters around to find out other true things? Mr Gödel showed that the answer is no.
First, I will tell you some things you should know. Many years ago, some people who worked with numbers thought that everything it is possible to know about numbers could be shown by moving letters around. It was shown that, when working with words like "and", "or" and "not", moving letters around was enough to show everything that was true or not true. But what about with harder-to-understand things, like numbers?
Some people who worked with numbers tried to write about numbers by using sets. Mr Russell and Mr Whitehead were two such people. They wrote a book called "[Important things about numbers]" which was very long -- in fact, it took more than three hundred pieces of paper to show that one and one make two.
Mr Gödel had an idea, though. He showed that, when you say something like "one and one make two", the thing you say can be made into a number. All you have to do is give a number to each letter you use, and put each of those numbers to the upper right of a 'prime' number -- that is, a number that can't be written as a number times another number besides one. The number of the first letter goes to the upper right of the smallest 'prime' number, the number of the second letter goes to the upper right of the second 'prime' number, and so on. So, if three is to the upper right of two, then we have two times two times two. Then the numbers get put together and we write the first number times the second number times the third number, and so on.
Suppose we say "nothing is the same as nothing". This can be written as three letters: '0=0'.
Give '0' the number one, and give '=' the number two. Then Mr Gödel would make a new number: two, times three times three, times five. This is the only way the thing we said can be made into a number, and the number can be changed back into the thing we said.
We can say longer things as well, and still turn the things we say into numbers. We can talk about numbers, or about the things we say about number, or even about the things we say about the things we say about numbers, using the way Mr Gödel shows us. It is important to note that we can talk about things we know about (like one, two, three and so on) but we can also talk about things we don't know about (using letters like 'x' or 'P') as long as we give each letter a number that is not used by any other letter.
Mr Gödel made a number that said " "can't be shown by moving letters when written two times" can't be shown by moving letters when written two times." (This might remind you of the work of Mr Quine). In short, the number says "I can't be shown by moving letters around". The thing the number says must be either true or not true.
If it is true, then the number says something true that can't be shown by moving letters.
If it is not true, then it CAN be shown by moving letters, but this means that moving letters can cause us to believe things that aren't true. This goes against what we first thought, since we started by saying only things that are obviously true.
So, the thing Mr Gödel's number says must be true, even though it can't be shown by moving letters around.
Mr Gödel shows that writing and moving letters around can't tell us everything that is true about numbers (part one):
When I write words, each word is made of letters. So, a group of letters can have a meaning. The same is true when we talk about numbers instead of words, but with numbers, there is only one meaning, and we can use different "letters" to change the meaning. So, if I want to say "one is the same as two," I can write '1=2' (which is not true), and if I want to say "one is not the same as two," I can write '~1=2' (which is true). If we start by saying obviously true things, like '0=0' ("nothing is the same as nothing") or '0+x=x' ("a thing added to nothing makes the same thing"), we can use letters to say new things, like '(0=0)^(0+x=x)' ("nothing is the same as nothing, AND a thing added to nothing makes the same thing"). But can we find out everything that is true about numbers just by saying some obviously true things and moving letters around to find out other true things? Mr Gödel showed that the answer is no.
First, I will tell you some things you should know. Many years ago, some people who worked with numbers thought that everything it is possible to know about numbers could be shown by moving letters around. It was shown that, when working with words like "and", "or" and "not", moving letters around was enough to show everything that was true or not true. But what about with harder-to-understand things, like numbers?
Some people who worked with numbers tried to write about numbers by using sets. Mr Russell and Mr Whitehead were two such people. They wrote a book called "[Important things about numbers]" which was very long -- in fact, it took more than three hundred pieces of paper to show that one and one make two.
Mr Gödel had an idea, though. He showed that, when you say something like "one and one make two", the thing you say can be made into a number. All you have to do is give a number to each letter you use, and put each of those numbers to the upper right of a 'prime' number -- that is, a number that can't be written as a number times another number besides one. The number of the first letter goes to the upper right of the smallest 'prime' number, the number of the second letter goes to the upper right of the second 'prime' number, and so on. So, if three is to the upper right of two, then we have two times two times two. Then the numbers get put together and we write the first number times the second number times the third number, and so on.
Suppose we say "nothing is the same as nothing". This can be written as three letters: '0=0'.
Give '0' the number one, and give '=' the number two. Then Mr Gödel would make a new number: two, times three times three, times five. This is the only way the thing we said can be made into a number, and the number can be changed back into the thing we said.
We can say longer things as well, and still turn the things we say into numbers. We can talk about numbers, or about the things we say about number, or even about the things we say about the things we say about numbers, using the way Mr Gödel shows us. It is important to note that we can talk about things we know about (like one, two, three and so on) but we can also talk about things we don't know about (using letters like 'x' or 'P') as long as we give each letter a number that is not used by any other letter.
Mr Gödel made a number that said " "can't be shown by moving letters when written two times" can't be shown by moving letters when written two times." (This might remind you of the work of Mr Quine). In short, the number says "I can't be shown by moving letters around". The thing the number says must be either true or not true.
If it is true, then the number says something true that can't be shown by moving letters.
If it is not true, then it CAN be shown by moving letters, but this means that moving letters can cause us to believe things that aren't true. This goes against what we first thought, since we started by saying only things that are obviously true.
So, the thing Mr Gödel's number says must be true, even though it can't be shown by moving letters around.
Comments
Post a Comment