Set Theory · Gödel's First Incompleteness Theorem (Optional)

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Around 300 BC or so, the Greek mathematician Euclid outlined a famous set of axioms in the field of geometry. In other words, he came up with a very simple set of statements that he would assume to be true in order to prove more interesting things. The goal of any decent set of axioms is to be as boring as possible–Every axiom should be obviously and intuitively true, and there shouldn't be very many of them–and Euclid’s axioms are the prototypical example. You might recognize them from high school geometry, but more likely your teacher cheated and let you use fancier axioms. Here they are (in our own clumsy wording):

  1. There is exactly one line connecting any two distinct points.
  2. Any line segment can be extended to arbitrary length.
  3. For every two distinct points, there is exactly one circle centered at the first and touching the second.
  4. All right angles are equal.
  5. Given a line \(L\) and a point \(P\notin L\), there is exactly one line that passes through \(P\) and is parallel to \(L\). (Euclid used a different, equivalent axiom.)

These are all incredibly obvious facts. Some of them might seem so obvious that they're not worth mentioning. Of course there's only one line between a pair of distinct points, for example. And, there are only five of them. However, you can prove a lot of stuff from these axioms, e.g., the Pythagorean Theorem.

However, generations of mathematicians, including Euclid, were not happy with the fifth axiom, known as the parallel postulate. In their eyes, the fifth axiom seemed more like something that needed to be proven than an axiom; it certainly sounds like a less trivial statement than the first four. But, the parallel postulate was a key step in many geometric proofs. So, in order to get rid of this ugly axiom without losing a ton of geometry, they spent a couple thousand years trying to prove that the parallel postulate logically followed directly from the other four axioms.

It wasn't until the mid-19th century that mathematicians discovered that there are “geometries” in which the parallel postulate is false. In order to see this, you need to relax the definitions of “point” and “line” a bit, so the language gets a little bit messy.

Consider a sphere, and call a pair of classical points “an elliptical point” if they are exactly opposite each other on the sphere. Note that a single elliptical point is made up of two classical points. If a circle on the sphere is made up of elliptical points, call it “an elliptical line.” Elliptical lines are also called great circles because they are the largest circles that you can draw on a sphere–The Earth's equator is a nice example. You can think of them as any circle that divides the sphere into two equal halves.

A quick check shows that elliptical points and elliptical lines satisfy the first four axioms. However, they don't satisfy the fifth because all elliptical lines cross. (If you're following, you should be able to picture this easily.) So, obviously the fifth axiom can't follow from the first four because we have a counter-example! (Our counterexample is called an elliptical non-Euclidean geometry.)

This example is illustrative. While mathematicians often think of axioms as assumptions, they're perhaps better thought of as pieces of a definition. Neither Euclid nor we phrased them like this, but axioms one through four essentially define some properties of things that mathematicians have agreed to call points, lines, and angles. However, those definitions are more general than the English definitions of those words; in particular, elliptical points and elliptical lines are perfectly good points and lines under the first four axioms. The fifth axiom serves to narrow the definitions so that they represent something much closer to the English notions of points, lines, and angles.