AN INTRODUCTION TO SET THEORY - Professor William A. R. Weiss, October 2, 2008
Infinity -> Set Theory -> Mathematics
Set Theory is the true study of Infinity, this alone assures the subject of a place prominent in human culture.
But even more, Set Theory is the milieu in which mathematics takes place today.
As such, it is expected to provide a firm foundation for the rest of matematics, and it does - up to a point.
We will prove theorems shedding on this issue.
Because the fundamentals of Set Theory are known to all mathematicians, basic problems in the subject seem elementary.
Here are three simple statements about sets and functions. They look like they could appear on a homework assignment in an undergraduate course.
- For any two sets X and Y , either there is a one-to-one function from X into Y or a one-to-one function from Y into X.
- If there is a one-to-one function from X into Y and also a one-to-one function from Y into X, then there is a one-to-one function from X onto Y .
- If X is a subset of the real numbers, then either there is a one-to-one function from the set of real numbers into X or there is a one-to-one function from X into the set of rational numbers.
They won’t appear on an assignment, however, because they are quite difficult to prove.
Statement (2) is true; it is called the Schroder-Bernstein Theorem. The proof, if you haven’t seen it before, is quite tricky but nevertheless uses only standard ideas from the nineteenth century.
Statement (1) is also true, but its proof needed a new concept from the twentieth century, a new axiom called the Axiom of Choice.
Statement (3) actually was on a homework assignment of sorts. It was the first problem in a tremendously influential list of twenty-three problems posed by David Hilbert to the 1900 meeting of the International Congress of Mathematicians.
Statement (3) is a reformulation of the famous Continuum Hypothesis. We don’t know if it is true or not, but there is hope that the twenty-first century will bring a solution. We do know, however, that another new axiom will be needed here. All these statements will be discussed later in the book.
Although Elementary Set Theory is well-known and straightforward, the modern subject, Axiomatic Set Theory, is both conceptually more difficult and more interesting. Complex issues arise in Set Theory more than any
other area of pure mathematics; in particular, Mathematical Logic is used in a fundamental way. Although the necessary logic is presented in this book, it would be beneficial for the reader to have taken a prior course in logic
under the auspices of mathematics, computer science or philosophy. In fact, it would be beneficial for everyone to have had a course in logic, but most people seem to make their way in the world without one.
In order to introduce one of the thorny issues, let’s consider the set of all those numbers which can be easily described, say in fewer then twenty English words. This leads to something called Richard’s Paradox. The set
{x : x is a number which can be described in fewer than twenty English words}
must be finite since there are only finitely many English words. Now, there are infinitely many counting numbers (i.e., the natural numbers) and so there must be some counting number (in fact infinitely many of them) which are not in our set. So there is a smallest counting number which is not in the set. This number can be uniquely described as “the smallest counting number which cannot be described in fewer than twenty English words”. Count them—14 words. So the number must be in the set. But it can’t be in the set.