What is Gödel’s Incompleteness Theorem and Why Did it Matter to Hilbert?

I wrote this article in Japanese and translated it into English using ChatGPT. I also used ChatGPT to create the English article title. I did my best to correct any translation mistakes, but please let me know if you find any errors. By the way, I did not use ChatGPT when writing the Japanese article. The entire article was written from scratch by me, Saikawa Goto.

Introduction

Movies and books covered in this article

Three takeaways from this article

Self-introduction article

The quotes in the article were translated using ChatGPT from Japanese books, and are not direct quotes from the foreign language original books, even if they exist.

In “Math Girls”, What Steps Lead to “Gödel’s Incompleteness Theorems”?

Setting of “Math Girls” Series

This book is the third installment of the “Math Girls” series. You can read them in any order, but it is a work that explains math in a novel-like format. Some people may feel that it is better to read them in order to fully understand the relationships between the characters and their growth.

Now, let’s introduce the characters.

The protagonist is “narrator” (The protagonist does not have a name), a second-year high school student who has a passion for math. He not only studies math at school but also conducts various research on his own based on his interests.

Miruka-san is a classmate of “narrator” and a mathematical genius with exceptional ability in math. She leads”narrator” and other members in various math discussions to unexpected heights. She also has impressive piano skills. While she is always calm and cool, it was discovered that she has a fear of heights.

Tetra-chan, a year below them, is great at English but struggles with math. She decides to learn from a senior (“narrator”) who is rumored to be good at math. Since then, they have become math discussion partners. Tetra-chan may not grasp concepts quickly, but she never gives up until she understands. Her perseverance and comprehension once she catches up are remarkable, and she sometimes asks “narrator” thought-provoking questions.

Yuri is “narrator’s” cousin. She’s a middle schooler who talks in a cat-like manner, often hanging out at “narrator’s” house. She loves learning math from her big brother (“narrator”). Although she doesn’t have much knowledge of math itself because she’s still in middle school, she’s extremely strong when it comes to logical discussions.

In addition to being a novel series, let’s mention another feature of this series.

Except for the first book, all of the books in this series have subtitles. In this book, the subtitle is “Gödel’s incompleteness theorems.” And this subtitle becomes the “final destination” of each series.

For a while from the beginning, the story unfolds in a way that makes you wonder, “How does this relate to the final destination?” But as you read on, you will understand “I see, so this book has such order in order to reach the final destination.”

In any series, as the “final destination” approaches, the explanations become quite advanced and difficult, and it would be hard to understand without considerable math skills (I also often struggle to understand what is written about “final destination”). However, the content up to the “final destination” is quite accessible even for math beginners, and if you follow the explanation, I believe you can reach a high level that you cannot reach on your own.

In this article, I will not explain much about the “final destination,” which is “Gödel’s incompleteness theorems.” This is because I do not understand it well enough to explain it to others. So in this article, I will focus on “how to approach Gödel’s incompleteness theorems step by step.”

What are “Peano Axioms”?

The series also includes a math teacher named Mr. Muraki, although he is not the main character. He is the person who gives the main characters problems to help them understand mathematics more deeply.

In this book, after some small talk at the beginning, the first big topic is “Peano axioms” introduced by Mr. Muraki. What exactly are the “Peano axioms”? Let’s start by writing down its definition.

This ostentatiously written “Peano axioms” is necessary to “define the natural number”.

The important thing is to “pretend to not know” what natural numbers are. We already know what “natural numbers” are, so it doesn’t seem to make sense to “define” them. However, it can also be said that “not defining them because we already know” is not a mathematical attitude.

So, for the time being, we will “pretend not to know” about “natural number” that is something that we feel only exists as a matter of course, and then the story of how to properly define “natural number” will unfold.

It’s interesting to think that we need such seemingly complicated rules just to define “1, 2, 3, 4…”!

About “0.999999…=1”

Then the discussion moves on to “infinity.” The topic of infinity is quite complicated in the world of mathematics, and there are many strange stories about it. The discussion will unfold about the mysteries of infinity.

I found the topic of “infinity” very interesting, especially the idea that “0.999999… = 1”. I had known for a long time that “0.999999…” and “1” are the same number, but I read something interesting about its interpretation.

First, let me write what I originally knew about this. This is an explanation of why “0.99999999… = 1”.

I already had such computational understanding, but I didn’t really understand what “0.999999… = 1” meant until I read this book.

Regarding that point, let me quote Yuri’s statement.

This “0.999…” notation is the culprit. It’s confusing!
…You know, when we write a sequence, we write it with the (…) at the end. So, I thought that eventually “0.999…” would come up as we continue 0.9, 0.99, 0.999, and so on. But that’s not the case, is that. “0.999…” doesn’t come up after 0.9, 0.99, and 0.999. It’s confusing because of that notation. I wish they would have written something like a ❤ instead.
・0.9, 0.99, 0.999, … get closer and closer to ❤.
・And ❤ is equal to 1.
If they had said it like this, there wouldn’t have been any confusion.

The important point here is that “0.999…” does not come after “0.9, 0.99, 0.999”.

I also thought that “0.999…” would eventually come up, but it turns out that it doesn’t. Yuri uses the symbol “❤”, but in mathematics, in short they think about the following:

As we go on with 0.9, 0.99, 0.999, the sequence of these numbers approaches a certain number “❤”.

Then, based on that, they make the following decision:

That “certain number ❤” does not come up after going on with 0.9, 0.99, 0.999. So, we decided to represent that non-existent “certain number ❤” as 0.999….

So, it follows that the next statement is also natural.

“A certain number ❤” that this sequence of numbers gets closer by going 0.9, 0.99, 0.999, and so on, is 1.

Therefore, the conclusion is as follows:

0.999999… is equal to 1.

I think you can understand this even though 0.999999… looks like “a number a little less than 1” at first glance, it is actually the same as “1”.

It has to Do With Cantor’s Diagonal Argument and Limit

Continuing on from the concept of “infinity,” I come to the topic of “Cantor’s diagonal argument.”

Out of all mathematical proofs, I personally find “Cantor’s diagonal argument” the most fascinating. Even for those in the humanities, it’s a proof that can be easily understood if you follow the logic.

However, it’s also surprising to think, “How did Cantor come up with this method in the first place?” and “Why did he even think to prove something like this?”

Unfortunately, it’s difficult to explain without using diagrams, so I won’t go into detail about “Cantor’s diagonal argument” itself in this article. However, I will touch on what Cantor proved with this argument (If you are interested, please see the following site).

This relates to the problem of whether there are more natural numbers or real numbers. The term “more” isn’t entirely accurate and should be expressed as “higher density,” but we’ll use “more” here.

Before discussing “natural numbers and real numbers,” let’s first think about “natural numbers and positive even numbers.” In other words, let’s consider which is more abundant, “natural numbers or positive even numbers?”

Natural numbers are “1, 2, 3, 4…” and positive even numbers are “2, 4, 6, 8…” So, you might imagine that there are more natural numbers than positive even numbers. Indeed, if we compare “natural numbers up to 100” with “positive even numbers up to 100,” it is clear that “natural numbers up to 100” are more abundant.

However, the point of this discussion is that both are considering infinity. When we consider “infinity of natural numbers” and “infinity of positive even numbers”, we would not be able to explain how to explain which is larger.

That’s why Cantor came up with the criterion of “one-to-one correspondence”. He thought that “things that have one-to-one correspondence exist in the same amount (have the same cardinality)”.

Let’s look at a concrete example.

Shown above, for any natural number you choose, there is always a corresponding positive even number that can be matched with it. This relationship between natural numbers and positive even numbers stays the same no matter how large the natural number is. This means that you can specify a positive even number corresponding to any natural number.

In this way, it was concluded that “things that have a one-to-one correspondence exist in the same amount.”

Well, after that, Cantor tried to apply the same argument to “natural numbers” and “real numbers”. That is, he asked if there is a one-to-one correspondence between natural numbers and real numbers.

And what was used to prove this is called “Cantor’s diagonal argument,” and Cantor proved that “there is no one-to-one correspondence between natural numbers and real numbers”.

“Real number” refers to all kinds of numbers, including decimals and irrational numbers. Of course, natural numbers are also included in real numbers. If you think about it normally, it’s obvious that there are more real numbers than natural numbers. However, as we saw earlier when we considered “natural numbers and positive even numbers,” unexpected results can arise. In mathematics, there are often situations where we can make mistakes by relying on our intuition instead of engaging in rigorous discussions.

Cantor addressed this issue with a hyper-technical approach and proved that “there is no one-to-one correspondence,” in other words, “there are more real numbers than natural numbers.”

And this shows the fact that there is a size even in infinity. In other word, although natural numbers exist in infinity, “the infinity of real numbers” is larger than “the infinity of natural numbers”. So even with the same infinity, it means that “one infinity is larger than the other.”

I really think it’s amazing to even consider such a thing.

Furthermore, this leads to the discussion of limits. It’s probably a calculation that every science person does.

When I was a student, I didn’t really understand the concept of limits. I could memorize the calculation method and didn’t have much trouble with tests, but I had no idea what it meant to “think about limits”.

In this book, we go over the definition of “limits” again and try to understand it properly. I still have a hard time understanding the definition, but I think I vaguely understand “what limit is.”

About “Formal System”

Next, the topic of “Formal System” comes up, which is directly related to the “final destination” of “Gödel’s incompleteness theorems”.

This is a difficult concept to explain, but let me try my best.

First, let’s talk about the history of the “Formal System.”

It’s related to a project by a mathematician named Hilbert who wanted to “organize mathematics systematically.” Hilbert believed that “just as three primary colors, cyan, magenta, and yellow, can create all colors, all mathematical theorems can be proven from a limited set of axioms (assumption determined to be “correct” without proof) and rules of inference.” He began working towards this ambitious goal.

However, another mathematician named Gödel shattered Hilbert’s program and told him, “What you’re trying to do is impossible.” Gödel’s theory that crushed Hilbert’s ambition is known as “Gödel’s incompleteness theorems,” which is the “final destination,” as I say, of this topic.

Thus, due to “Formal System”, “Gödel’s incompleteness theorems” was born.

Now, let me explain what I understand about “Formal System”.

First of all, “mathematics” is a field that has been discovered by mathematicians around the world in different eras and combined together. This means that it is not like “assembling something according to a blueprint.”

For example, when building a house, you would typically start by creating a blueprint, gathering the necessary materials, consulting with workers, and setting a schedule. However, mathematics is different. If I compare it to building a house, the process was completely disjointed such as “someone making the bathroom”, “another person laying the floor in the living room”, and “the roof being completed before enough supporting columns are in place.”

Of course, if you were to build a house such way, problems like “a mysterious space is created” or “there is a column that doesn’t support anything” would arise and hinder the construction of the home. Similarly, in mathematics, situations such as “wait, something strange seems to be happening here” and “there seems to be a contradiction here” have started to occur.

So Hilbert thought, “Let’s build ‘mathematics’ in the correct order, like building a house.”

And thus, Hilbert’s program to “prove mathematical theorems using a limited set of axioms and rules of inference” began.

This can be thought of as an image of “MIYADAIKU (traditional Japanese construction method) “. Just like building a house using only “limited materials such as lumber and roofing tiles” and “techniques for combining wood without using nails “, Hilbert’s program aimed to prove all known theorems using only “limited axioms” and a “rule of inference for combining axioms that include already proven theorems”. The mathematical system thus organized is called a “Formal System”.

However, Hilbert’s ambition was shattered by Gödel.

A Rough Explanation of “Gödel’s Incompleteness Theorems”

In this book, towards the end, there is a discussion about “Gödel’s incompleteness theorems,” which I found to be quite difficult. Although I read it and sort of understand it, I do not fully comprehend it enough to explain it to someone else.

So in this article, I’ll just briefly touch on “Gödel’s incompleteness theorems”.

Now, these theorems shattered Hilbert’s plans, but how exactly did Gödel do that? To explain that, I need to delve a bit more into the “Formal System” that Hilbert was trying to construct.

He was aiming to demonstrate the “Completeness” and “Consistency” of mathematics within this system. To be more specific:

Do you feel like “Completeness” is something that’s obvious? Many people think of mathematics as a field where “correct claims can be proven to be correct.” Additionally, since the Hilbert program was created with the motive of dealing with situations where contradictions arise, it is only natural to expect “Consistency”.

However, “Gödel’s incompleteness theorems” shattered Hilbert’s expectations by proving the following two points:

So, here’s what I mean. Hilbert thought the following:

Mathematics is expected to be both “complete” and “consistent”, and it can be proven.

However, Gödel proved the following:

If mathematics is “consistent”, then it is “incomplete”, and even if mathematics is “consistent”, the “consistency” cannot be proven within the system.

Note that Gödel did not refer whether the mathematics we are involved with is “complete” or “consistent”. By showing that “if mathematics is consistent, then it is not complete,” he shattered Hilbert’s belief that “mathematics is complete and consistent.” He also proved that “even if mathematics is consistent, the fact itself cannot be proven,” regarding consistency.

It is clear that it was a significant blow to Hilbert’s grand goal.

The book provides a detailed account of how Gödel performed such an acrobatic proof. To be honest, it was too difficult for me to understand with just one read. However, while general math books may discuss what “Gödel’s incompleteness theorems” are, they rarely touch on the details of the proof, making this work quite valuable in that sense.

What amazed me about Gödel’s idea while reading this book was the “Gödel number.”

Gödel lead “Gödel’s incompleteness theorems” by delving deeply into “well-formed formulas.” A “well-formed formula” is a symbolically represented proposition, such as “1+1=2.” Well-formed formulas can contain familiar symbols like “+” and “>”, as well as unfamiliar symbols like “!%” and “&&,” but they all involve some kind of “symbol.”

Gödel then assigned a unique “number” to each of these symbols in a special way, which he called the “Gödel number.”

Essentially, Gödel converted all “well-formed formulas,” including symbols, into “numbers” to make it easier to continue his discussions, which led to the discovery of “Gödel’s incompleteness theorems.”

The idea of converting symbols into numbers is amazing, and Gödel’s solution to achieving this is impressive. While I only understood parts of Gödel’s incompleteness theorems, I was amazed by the concept of the “Gödel number.”

Conclusion

The book’s final destination, Gödel’s incompleteness theorems, is certainly extremely difficult, but it is not just filled with difficult topics. I think it’s a work that makes you feel, “Mathematics can be viewed in this way too.” I wouldn’t recommend it to those who dislike mathematics, but for those who are interested in mathematics but feel intimidated and haven’t been able to get into it, I highly recommend this book.

I think the conversations between the characters in addition to the math parts are also appealing. Among them, I really like Miruka-san, and the scenes where she encourages the protagonist while he can’t stop thinking about math are both very mathematical and interesting.

Can you see all dimensions?
You only see the point moving around the circle.
You cannot see the spiral.

（●●●●KANRENKIJI）The Invisible Gorilla

By telling him that if he looks at it in three-dimensional space, he can see it as a “spiral,” but if he looks at it in two-dimensional space, it is just a “point going around the circumference,” she is suggesting that “you seem depressed, but that is just because you are not seeing what you should be seeing properly.” The exchange between the two characters, who share a common language of “math,” is an encouraging word that works precisely because of their shared interest. It’s great to see this kind of exchange, and I hope you have an enriching “mathematical experience.”