Numb3rs
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):
- One can draw a straight line between any two points.
- One can extend any line segment indefinitely in either direction.
- One can draw a circle with any center and any radius.
- All right angles are equal.
- 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 is a natural number.
- Every natural number n has a successor number called n+1.
- There is no natural number which has 1 as a successor.
- The equality relation is reflexive, meaning if x is a natural
number than x=x
- The equality relation is symmetric, meaning if x and y are
natural numbers so that x=y, then y=x.
- The equality relation is transitive, meaning if x, y, and z are
natural numbers so that x=y and y=z, then x=z.
- 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.
- If x and y are natural numbers with the same successor, then x=y.
- 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.