Season 5
Episode 10: Frienemies

One major recurring phrase in this episode is 'set theory.'

What is set theory?

Set theory is, in some sense, the foundation of all mathematics.  All the many disparate areas of mathematics depend on set theory to supply the logical foundation for their theorems.  To make an analogy to the United States legal system, set theory would be the Constitution, establishining the fundamental rules on how the government will operate.  Were one to change the Constitution slightly, the government could wind up entirely different.  If the Constitution had powerfully conflicting rules, the government would probably not operate at all.

When one creates any logical system (whether it be a philosophy of government or a scientific theory), one must make basic assumptions.  In physics, these assumptions are called laws --- for example, Newton's law that every action has an equal and opposite reaction.  In mathematics, the basic assumptions are called axioms.  Axioms are generally very basic, unambiguous statements.

The more axioms one chooses, the more likely they might conflict in some (probably very subtle) way.  So when one picks axioms, one wants to pick as few as possible.  The same can be said for complicated axioms.  So, mathematicians have chosen as few and as simple axioms as possible.

Example 1.  Euclid's geometry.

The most recognizable axiomatic system comes from the ancient Greek mathematician Euclid.  Euclid was concerned with the geometry of the plane.  Specifically, he wanted to come up with basic rules for what kind of shapes could be constructed in the plane with a straight-edge (a ruler without length markings) and compass (which makes circles).  Here are the axioms (which Euclid called postulates):

  1. One can draw a straight line between any two points.
  2. One can extend any line segment indefinitely in either direction.
  3. One can draw a circle with any center and any radius.
  4. All right angles are equal.
  5. Given a line and a point not on that line, there is exactly one line through the given point which is parallel to the given line (meaning this new line does not intersect the given line).
From this (as well as a few other common assumptions such as if a=b and b=c then a=c), Euclid was able to produce a number of the basic results of geometry, such as the sum of the angles in a triangle being 180 degrees (which Euclid referred to as two right angles). 

One thing which becomes rather apparent is how different the fifth postulate is from the first four.  It is decidedly more complicated.  For many centuries, mathematicians believed that the fifth postulate's more complicated status meant that one should be able to prove the fifth postulate using just the other four.  However, it turns out this was not the case.  In the 1800s in fact, several mathematicians were involved in proving that not only was the fifth postulate not provable from the other four but that variations of the postulate could be assumed and produce "different geometries." 

If one assumes that there are no parallel lines, the geometry these postulates produce not only makes sense but corresponds to a situation we are very well-accustomed to: the sphere.  Imagine you are living on the surface of the Earth.  Though our planet seems flat over short distances, if you walk in a straight line, you will eventually end up back where you started --- though hopefully you have a boat!  But no matter how two people walk, their paths will eventually intersect, and so no lines are parallel.

If one assumes there are more than one parallel lines, the geometry produced is not so familiar.  This geometry is called hyperbolic geometry.  It turns out that there must be infinitely many parallel lines through a point which do not intersect a given line.  It is difficult to describe exactly.  One way to visualize it involves Poincaré's half-plane model.  Here, one takes the upper half-plane which consists of all the points (strictly) above the x-axis.  The strange part of this model is that one needs to choose a different distance function on the plane.  The basic idea is that the distance gets stretched out when points get close to the x-axis.  That is, points (1,2) and (2,2) are closer together than (10,2) and (11,2) even though the distances are equal on our usual plane.  Straight lines then correspond to semi-circles whose diameters lie along the x-axis.  Try and convince yourself that given such a semicircle and a point not on the semicircle that there are infinitely many semicircles which hit that point but not the given semicircle.  It may be helpful to consider several cases: one where the point is to the left or right of the given semicircle, one where the point is above the semicircle, and one where the point lies inside the semicircle.  Once you show that a single such semicircle exists, just show that there is enough wiggle room that one can increase the radius and move the center just a little bit.

Example 2.  The Peano axioms.

Here is one axiomatic formulation of the natural numbers (the numbers 1, 2, 3,...), which is written on the board when Charlie's frienemy is lecturing his class:
  1. 1 is a natural number.
  2. Every natural number n has a successor number called n+1.
  3. There is no natural number which has 1 as a successor.
  4. The equality relation is reflexive, meaning if x is a natural number than x=x
  5. The equality relation is symmetric, meaning if x and y are natural numbers so that x=y, then y=x.
  6. The equality relation is transitive, meaning if x, y, and z are natural numbers so that x=y and y=z, then x=z.
  7. The natural numbers are closed under equality, meaning that if x is a natural number and y is a number so that x=y, then y is also a natural number.
  8. If x and y are natural numbers with the same successor, then x=y.
  9. Suppose that A is a set with the property that (i) 1 is in A and (ii) if n is in A then n+1 is in A.  Then A contains every natural number.
Set Theory.

One can guess at this point that set theory is a set of axioms which somehow involves sets.  The power of set theory is that even the early, naive notion of set theory could be used to build all the common number systems, i.e. the integers, rational numbers, real numbers, etc., among other things.  So with the goal of utilizing as simple and as small a number of axioms as possible, set theory serves as the logical underpinning of mathematics.

The original set theory is called naive because it missed a subtle but extremely important point.  Naive set theory simply said that sets were just collections of things, whatever you would like.  There were no restrictions on what properties a set could have.  The mathematician and philosopher Bertrand Russel, who incidentally won a Nobel Prize in literature, came up with what is known as the Russel Paradox.  The paradox clearly illustrates a logical issue with any set theory which does not put restrictions on what a set is.

Russel Paradox.

We begin by noting that, although it may seem a strange thing to say, there is nothing to stop a set from containing itself.  This is the major flaw of putting literally no restriction on what a set can be.  So there may or may not actually exist a set which has itself sitting inside... itself.  Now, let R be the set of all sets which DO NOT contain themselves.  This is a completely reasonable seeming set and, indeed, it seems logical to believe that this set R actually includes all reasonable sets.  But now we ask the following equally reasonable question: does R contain itself?  Well, suppose not.  This would then mean that R would sit inside R, which is silly because R does not contain R.  So then R must contain R.  But this also violates the definition of R.  So we're stuck in a paradox.

It turns out that this paradox represents an extremely deep property of any logical axiomatic system.  In the 1950s, Kurt Gödel used this self-referencing property as the inspiration for his celebrated Incompleteness Theorem.  That particular theorem essentially states that any reasonably complicated axiomatic system (one which can be used to establish the common rules of arithmetic) which is consistent must be incomplete.  Consistent means that it has no self-contradictions.  An incomplete axiomatic system has statements which are true but which cannot be proven using the axioms.  The major idea of
Gödel's proof is that the statement "This statement cannot be proved" cannot be proved, thus guaranteeing that it is both true and not provable.

Zermelo-Fraenkel Set Theory.

The most common formulation of set theory is known as Zermelo-Fraenkel Set Theory.  The axioms are quite simple, mostly including the basic operations of sets (unions, power sets, the existence of the empty set, and so on).  And one of the axioms is specifically designed to prevent variations of the Russel Paradox from being possible.  The exact statement can be found on Wikipedia along with excellent explanations of each axiom: Zermelo Fraenkel Set Theory.

An additional axiom, known as the Axiom of Choice, is often added to Zermelo-Fraenkel Set Theory (denoted ZFC).  This axiom is rather unique in that it was simply assumed to be true for many years.  The statement is that, given any collection of sets, you can construct a new set by picking exactly one of the elements of each set in the collection.  For finite sets, this is clearly possible to do, but for an infinite collection of sets this statement is actually not provable from Zermelo-Fraenkel Set Theory.  The Axiom of Choice is independent of the axioms of Zermelo-Fraenkel Set Theory, meaning one can assume either the Axiom of Choice to be true or false.  Most mathematicians assume the Axiom of Choice but often prefer to use it as little as possible.