## Kurt Gödel’s Story

It is my impression that, even among mathematicians, mathematical logicians are a bit weird. Kurt Gödel was no exception.

Gödel is famous for proving foundational questions about mathematics. He asked questions like, “Can I prove that math is consistent?” and, “If I have a true statement, can I prove that it’s true?” and, “Can I prove that it’s impossible to prove the statement ‘This statement is unprovable’ is provable?”

Yeah, not exactly the most obvious questions to ask, but important ones, I promise.

Gödel was born in 1906 in what is now Brno, Czech Republic, but was then in Austria-Hungary. His family called him Herr Warum (“Mr. Why”), which is impressive given how fond children everywhere are of that question.

By the time he went to the University of Vienna at 18, he had already mastered university-level math. During this time, he came across Russell’s work on the foundations of mathematics, and met Hilbert, who, around that time, was thinking deeply about axioms and logical systems, and whether it could be shown they had no contradictions, and whether all true statements could be proven.

By 23, Gödel finished his PhD in mathematical logic. Two years later, he published his seminal work on his incompleteness theorems. These papers have the answers to the questions I introduced, but I want to finish talking about Gödel. We’ll discuss the details next time.

Two years after that, in 1933, Gödel became a lecturer at the University of Vienna. He also traveled to the US, where he met Einstein, who became his good friend.

During this time, Hitler came to power in Germany. A few years later, the professor who had originally interested Gödel in logic was assassinated by one of his former students, essentially because he was friends with Jews.1 This caused a “nervous crisis” in Gödel. He became paranoid, fearing that he would be poisoned. These symptoms continued later in his life.

In 1938, Nazi Germany annexed Austria. Gödel’s job title was eliminated, so he had to apply to a new job. However, since he had been friends with Jews, they turned him down.

Things got worse the next year. Germany found him fit for conscription, and World War II began. Within the year, Gödel left for Princeton, at the Institute of Advanced Study, where Einstein was.

And, being Gödel, he decided that an Atlantic crossing was too much. So he took the obviously less strenuous route of a train ride across Russia to Japan, a boat ride across the Pacific, then another train ride to Princeton, New Jersey.2

He was very productive during his time in Princeton, proving some other results about the foundations of mathematics.

In 1947, Einstein took Gödel to his US citizenship exam. Gödel, being a constant logician, told Einstein he had discovered an inconsistency in the US constitution that could allow the US to become a dictatorship. Einstein was concerned… not about the possibility of a dictatorship, but that Gödel’s eccentric behavior might endanger his citizenship application.

Einstein was right to fear.

During Gödel’s hearing, the judge asked what kind of government they had in Austria. Gödel replied that it was a republic, but that the constitution was such that it was changed into a dictatorship. The judge expressed his regret, then said that this could not happen in this country.

Gödel replied, “Oh, yes, I can prove it.”

Fortunately, the judge was an acquaintance of Einstein’s, and said, “Oh God, let’s not go into this.”2

Anyway, Gödel kept on working. Among other things, for Einstein’s 70th birthday, Gödel created a spacetime which… breaks general relativity. Well, at least, it has all sorts of things go wrong. For instance, there are “closed timelike loops” through every point of spacetime, meaning that anyone and everyone can time travel. He also expanded Leibniz’s “proof” of God’s existence.

Later in his life, his paranoia recurred. He had an overwhelming fear of being poisoned, and would only eat food that his wife prepared for him. When she was hospitalized for 6 months, he refused to eat, eventually starving to death. At the time of his death, he weighed only 30 kilos.

In the next post, we’ll get to talk about Gödel’s completeness and incompleteness theorems, and come face to face with the inherent limitations of mathematics!

(For those of you who enjoyed this, you might also enjoy my articles on Georg Cantor and Karl Schwarzschild!)

1.  Though Schlick was not a Jew, his murder became a cause of celebration, which fed the growing anti-Jewish sentiments in Vienna. When Germany annexed Austria, the murderer was released, having only served 2 years of a 10 year sentence.
2.  To be fair, his exit visa explicitly stipulated the trans-Siberian route. The Atlantic crossing was dangerous during the war. More details can be found here
3.  The constitutional problem that Gödel found was never recorded, but a good guess is that he was referring to Article V, which allows the constitution to be amended. Though it is very hard to pull off, you could, in theory, change the constitution to allow amendments relatively easily, say by a majority of both houses of congress. This is essentially what the constitution of the Weimar republic (pre-WWII Germany) said. Once the constitution is easy to change, it is a (relatively) simple matter to make the president a dictator. Germany’s Reichstag (congress) made Hitler a dictator in this way.

## Where do axioms come from?

In the last post, we talked about what math is. To me, math is a quest of understanding what must be.

The basis for this quest are the axioms and definitions of mathematics. Definitions describe what we are talking about, while axioms describe what we assume those objects can do.

Where do those axioms and definitions come from?

Since math is taught so authoritatively, it can seem that the definitions and axioms of mathematics are part of what must be. That may be true to some extent, but that is not how math is done.

As we try to increase our mathematical understanding, our needs change. We realize that certain ideas or definitions we used before weren’t quite precise or rigorous enough to deal with the questions we want to ask now. Sometimes, we find out that our previous understanding was simply lacking.

In this post, I’d like to give some of the motivating reasons for the axioms and definitions we commonly use in mathematics. The reasons are general and overlap, and are probably not exhaustive.

The first of these reasons is trying to codify intuitive ideas.

For an example we can go back to calculus.

The idea of a “continuous function” is fairly simple; a function is continuous if, when you graph it, you don’t have to lift up your pencil.

For many purposes, that intuition is sufficient. But, if you needed to, how could you make this definition precise?

Though calculus was invented in the mid 1600’s, it wasn’t until 1817 that Bernard Bolzano gave the modern definition of continuity. His “epsilon-delta” definition also demonstrates another common occurrence for new, precise mathematical definitions. Even though the intuition for them is fairly clear, the technical details can be very confusing.

The more intuitive way to say his definition is “A function $f(x)$ is continuous at a point $x_0$, if inputs near the original input $x_0$ give outputs near the original output $f(x_0)$.” This makes more precise what we mean when we say a continuous function has no jumps.

But the precise way of stating this is “A function $f(x)$ is continuous at a point $x_0$ if, for any $\epsilon >0$, there exists a $\delta>0$ so that, if $|x-x_0|<\delta$ implies that $|f(x)-f(x_0)|<\epsilon$.”1

One of the first jobs of any math major beginning his or her “proofs” classes is to really internalize this definition. It, and its variations, come up all over the place.

Axioms and definitions are sometimes invented trying to answer the question, “what makes this proof work?”

It almost feels like cheating–you know the outcome you want, so just assume the things that makes it work!

If you’ve taken calculus, probably the most important theorem you learned was the Fundamental Theorem of Calculus. One way to state this theorem is “If $F(x)$ has a (continuous) derivative, then $F(b)-F(a) = \displaystyle\int_a^b F'(x)\,dx$.” In other words, the integral of the derivative is the original function.

But the assumption that $F(x)$ has a continuous derivative is stronger than really necessary. For instance, the theorem still works for $F(x) = |x|$, even though $|x|$ does not have a derivative (i.e., a well defined slope) at $x=0$.

So what property does a function need to make the fundamental theorem work? Somewhere in the proof, at some point you need to use that $F(x)$ has a continuous derivative. But if you look closely, you find you don’t quite need that condition. Instead, you need something a bit weaker. That precise condition is just given a name, absolutely continuous. (You can see the definition here on Wikipedia.)

Absolute continuity is not a basic, obvious definition or idea. It’s not very elegant in anyone’s view. It’s simply the condition that makes the proof work.

“What makes it work” might not be very elegant, but it is how math is done.

If we don’t know how to prove the theorem we want to, we’ll often ask, “What extra condition could we assume that would make it possible to prove this theorem?” And then we assume that condition holds, and often give it a name like “tame” or “well-behaved.” The conditions aren’t special or elegant–but they work.2

Another way that definitions are invented is when mathematicians want to generalize an idea to a more general situation. Another way to say this is that mathematicians are trying to somehow identify the intrinsic something of an idea.

This is a major theme of modern mathematics. “What does it mean to be a shape?” “What does it mean to multiply things?” These two questions lead to the complete reformulations of branches of mathematics.

Until Bernhard Riemann, a shape was always visualized in the plane or in space (or perhaps a higher dimensional $\mathbb{R}^n$.) But what makes a shape a shape? Riemann asked this question, and decided that the property that makes a shape a shape is that, at any point of the shape, you can travel in a certain number of directions. (In 3 dimensions, this would be up/down, left/right, and forward/backward.)

The usual visualization of shapes in space was a crutch that distracted us from the intrinsic properties of that shape. These “many-fold quantities,” as Riemann called them, or manifolds, as we call them now, have become the basis for geometry. (We’ve talked extensively about manifolds in this blog, starting here.)

Multiplying numbers has been done for as long as math has been done. More recently, multiplication of matrices has become useful. But what makes multiplication multiplication?

Answering that question leads to the idea of a group, the basis of the field of abstract algebra. A group is a bunch of things that you can multiply. You don’t really care what these things are (matrices, functions, numbers, shapes, symmetries, etc.), as long as you know how to “multiply” them. The general rules for what multiplication must do are the axioms of a group.3

These kinds of generalization often seems weird and/or useless when you’re first introduced to it. Even worse, it always feels like you’re adding a layer of complexity to something that is already complicated enough.

But stripping away the extra details and focusing on the core ideas turns out to be very valuable. First, sometimes it makes it easier to prove results you care about. Second, by unifying very disparate ideas (such as matrix multiplication and rotations and normal multiplication), if you can prove a theorem about groups in general, than it applies to all of these very different situations.

Finally, sometimes we have to come up with new axioms because our old ones were just plain wrong.

Because math is an investigation into what must be, we really don’t like when there are contradictions. In fact, we feel like there shouldn’t ever be contradictions. After all, we proved everything, right?

Usually they’re just an indication that you made a mistake somewhere in your reasoning. (I’m intimately familiar with that one…)

And often, mathematical theorems or examples can seem paradoxical, but really the only problem is with your intuition.

But occasionally, real problems are found.

One of the most prominent examples of this is Russell’s paradox.

Intuitively, a set is any collection of objects you can define. For instance, the integers between 1 and 5 are a set, $\{1, 2, 3, 4, 5\}$. All the natural numbers is a set. You can have more complicated sets, like the set of all sets of numbers.

Georg Cantor, among others, had enumerated what things you could do with sets.4 But a naive interpretation of sets, which works well enough for most purposes, leads to contradictions.

Russell’s paradox is this: Consider the set $R$, which is the set of all sets which are not in themselves.

Yeah, that’s weird. Maybe an easier one to get your head around is “the set of all sets.” Since it’s a set of all sets, and it is a set, the set of all sets has to contain itself.

The set $R$, the set of all sets which are not in themselves, is even weirder. But (naively) $R$ is a set because we can define it.

Is $R$ in itself?

If $R$ is in $R$, then $R$ is a set which contains itself. But that means (since $R$ is the set of all sets which are not in themselves) that $R$ can’t be in $R$.

Okay, so maybe $R$ is not in $R$. If it isn’t, though, the definition of $R$ (again, the set of all sets which are not in themselves) means that $R$ must be in $R$!

In other words, $R$ can’t be in $R$, but that means it must be in $R$, but that means it can’t be in $R$, but that means it must be in $R$, but that means…

This is a lot like the infamous statement, “This statement is false.”5

In order to clear up Russell’s paradox, along with a family of other paradoxes that come along with a more naive approach to set theory, new axioms were needed.

Over the next few decades, the now-standard Zermelo-Fraenkel axioms of set theory were developed. These axioms are designed to allow you to do most things you think you should be able to do with sets, like combine them and compare them and such, but they avoid paradoxes that can creep in if you try to allow everything.

To conclude, axioms and definitions are invented for many reasons, ranging from an attempt to make precise an intuitive idea to an attempt to remove paradoxes.

But math works, as long as we pick reasonable axioms, and we can use it to learn everything that must be.

Right?

Actually, it’s not quite so simple. There are fundamental limits on what we can use mathematics to understand. The only other option is that math is self-contradictory.

That is the content of Gödel’s incompleteness theorems. And that’s what we’ll talk about next time.

Sorry for the delay for this post. We’ve been writing posts weekly for six months. Unfortunately, that turns out to be an unsustainable pace with all the other things we have to get done. We’ll continue to post, but it will be less often than before. Feel free to subscribe to get an email when we post!

1. And this is not the most confusing definition. Another definition (often, but not always equivalent) is “The inverse image of an open set is open.” I don’t want to define those terms here, but this definition, though very useful, is even less intuitive than Bolzano’s.
2. My impression is that this is how “Hilbert spaces” got their name. Hilbert spaces are infinite dimensional vector spaces, with a way to measure lengths of vectors, and angles between them. That is all very natural. But Hilbert spaces have the additional property that they are “complete,” essentially meaning that there are no “vectors missing” from the space. This condition is very important in being able to prove anything about infinite dimensional vector spaces. Hilbert had a number of papers about these complete vector spaces, and others found them useful, and so started calling them Hilbert spaces.
3. There are four axioms of a group. 1. Multiplication of things in the group have to stay in the group. 2. Multiplication is associative, i.e., $(a\cdot b)\cdot c = a\cdot(b\cdot c)$. 3. There is a “1,” meaning anything you multiply by “1” stays the same. 4. Everything has an inverse, so that if you multiply them together, you get “1.” There are lots of examples of groups, such as the positive numbers, or invertible matrices. But there are less obvious examples, like the set of all rotations in space, $SO(3)$. These are a group since, if you do one rotation, then another, that is the same as doing one big rotation. (Doing one rotation, then another, i.e., composition, is the “multiplication.”) The “1” rotation is the rotation of zero degrees, i.e., doing nothing. And the inverse is undoing the rotation you just did.
4. I don’t say “wrote down axioms” because he never actually wrote down precise axioms for his set theory.
5. Perhaps even more accurately, the set $R$ is like “the smallest number that can’t be described in less than 13 words.” It seems to make sense, but, looking closer, there’s obviously some sort of problem with this number.

## What is math?

What is math?

Most people’s conception of math was drilled into them during grade school.

In my experience, grade school math goes something like this: The teacher says that we need to calculate a thing. He then shows how to calculate that thing, with seven slight variations. Your homework is to calculate six of each of the variations. The test will have five of those seven.

After a decade of this, most walk away thinking that math is calculation. And because of the rote way the material was introduced, many get the impression that math is set in stone. If you perform a particular set of arcane, incomprehensible steps, you will be led to the mythical “right answer.” No other steps are allowed, and heaven help you if you don’t happen to remember the right steps for a particular problem. In that case there is nothing to be done but despair.

And, of course, they believe that all math has been handed down to them from on high, as wisdom from the ancients. It is imperturbable, impenetrable, impeccable.

But that is not what math is.

So, what is math?

Calculation is a useful tool, but it is definitely not what math is.

Math is a quest for understanding. And like any good epic fantasy series, it seems to never quite be finished.1

And the understanding we mathematicians seek is an odd sort of understanding. The goal of science is to understand what is, to describe and understand the universe around them.

Mathematicians, on the other hand, seek to understand what must be.

After all, the questions a mathematician asks are not generally about things that could even exist. Have you ever seen a perfectly straight, infinitely thin line? Or an angle of precisely 90 degrees? But, if I have a perfectly flat triangle with a 90 degree angle, I know the side lengths have a certain relationship, $a^2 + b^2 = c^2$.

And sure, we can count 37 cows, but do the cows care that there are a prime number of them? But 37 is prime, and so the 37 cows cannot be evenly split between more than one person.

I sometimes like to describe this by saying that I, as a mathematician, try to figure out what even God cannot do. Even an all-powerful God cannot create a perfect flat triangle with a 90 degree angle, whose side lengths do not obey the Pythagorean relationship. Neither could He evenly divide 37 cows between more than one person.2

The basis for deciding what must be are the definitions and axioms of mathematics.

Definitions and axioms are different, but very closely related.

Definitions describe the things we talk about. For instance, a straight line (versus a curved one) might be defined as “a line which lies evenly with the points on itself,” as in Euclid.

Axioms describe what we can do with the things we’ve defined. These tend to be very basic, “obvious” things. For example, the axiom of symmetry says that “If $A=B$, then $B=A$.” In this example, you could see the axiom as something you can do (“You can switch the sides of an equation.”) or you could see the axiom as defining what two things being equal really means.

On top of this foundation, mathematics is built with logic. Given the definitions and axioms, certain conclusions follow as inescapable consequences. These conclusions we call theorems or lemmas or propositions.3

Because mathematics is taught in such an authoritative way, it can appear that the definitions and axioms of mathematics are in someway intrinsic, that they have existence outside of the creation of man. It can feel like the axioms and definitions are part of the “what must be” that mathematicians are searching for.

To some extent that may be true, but I don’t think this is completely true, and it’s certainly not how math is done.

When you read a textbook, the most recent thinking of the definitions and axioms that are thought to be important are presented. But that hides to some extent the fact that it took hundreds, or even thousands, or years to decide that those axioms should be the ones to form the foundation of the rest of mathematics.

Math evolves. Math changes. The definitions and axioms we use today are not the same ones that were used by Newton.

Referencing Newton actually brings up a good example of how math changes.

Newton (and Leibniz) invented calculus around 1670. It immediately proved its use in solving any number of important questions in physics and mathematics.

But Newton’s calculus was not built on what we would today consider a rigorous foundation.

In order to explain their ideas, both Newton and Leibniz used some idea of “infinitesimals,” quantities that were infinitely small.

Infinitesimals can be very useful in an intuitive explanation of calculus. (I often use them informally when I teach calculus myself.) And so Newton and Leibniz’s proofs of their results were accepted, even though some were uncomfortable with the idea of an infinitely small quantity.

But as mathematicians delved deeper into the ideas of calculus, it became clear that the infinitesimal arguments weren’t quite complete. There were important theorems that could not be carefully proven because the foundations of calculus were not proven with sufficient rigor.4

Thus, one of the major mathematical projects of the 1800’s was to prove the “soundness” of calculus, and make sure the foundations were correct.

This involved inventing new definitions. For instance, one of the key ideas of calculus is the limit. Informally, the limit asks, “As the inputs get close to a number, what do the outputs get close to?”

The intuition for limits is not difficult; you plug in numbers closer and closer to the one you want, and see if the outputs get close to some other number. But the careful definition for limit that we use today, the $\epsilon-\delta$ (epsilon-delta) definition, was not introduced till the 1820’s by Augustin-Louis Cauchy.

Mathematics is not static, and the axioms and definitions we use are not necessarily natural, sitting there for us to find. As we seek deeper understanding, we often come to a point where we realize our earlier understanding was incomplete, or even incorrect, and we seek to fix the foundations. This has occurred over and over and over again to get to our “fixed” modern ideas of mathematics.5

To summarize, mathematics is a quest for understanding what must be. But the very concepts we try to understand are not set in stone. The objects of mathematics are defined by people, and as we understand them better, the definitions and axioms we base our understanding on change.

In the next post I want to talk more in depth about why these definitions change, and how and why mathematicians come up with new definitions.

This post was mostly about the philosophy of math, which is quite a bit different than my normal post. But as we’ll see in a few weeks, Gödel’s incompleteness theorem is so weird that it is impossible to talk about it without discussing the philosophy of math. Gödel’s theorem puts a fundamental limit on mathematicians’ quest for understanding.

1. I’m looking at you, George R. R. Martin…
2. Well, at least without taking the King Solomon approach and cutting the 37th cow in half!
3. Usually “theorems” are bigger, more important conclusions, while “lemmas” are littler conclusions that are needed along the way to show the theorems are true. Propositions can go either way. On the other hand, sometimes lemmas end up being more important than the theorems.
4. More recently, mathematicians have come up with rigorous methods to talk about infinitesimals, for instance the hyperreal numbers. However, infinitesimal methods are no longer considered standard.
5. Even the work on calculus done in the early 1800’s was not final. The “Riemann” integral, which was the formalization of the integral by Riemann, is what is taught in high schools and early college math. But at the graduate level, we use the “Lebesgue” (Luh-bayg) integral instead, which was introduced in the early 1900’s. Both are rigorous approaches to the integral, but the Lebesgue integral makes a few key lemmas and theorems much easier to prove. The basis of the Lebesgue integral is less intuitive at first, but easier and more powerful in the end.