When we began studying set theory in Chapter 3, we made several assumptions regarding which things are sets. For example, we assumed that collections of numbers, like N, R, or (0, ∞) are sets. We supposed that operating with given sets to form new collections, as with union or intersection, resulted in sets. We also assumed that formulas could be used to describe certain sets. All of this seemed perfectly reasonable, but since all of these assumptions were made without a carefully thought-out system, we would be wise to pause and investigate if we have introduced any problems.

Consider the following question. Given a formula p(x), is there a set of the form {x : p(x)}? Consistent with the attitude of our previous work, we might quickly answer in the affirmative. Mathematicians, including Cantor, also initially thought that this was the case. However, it was shown independently by Bertrand Russell and Ernst Zermelo that not every formula can be used to define a set. For example, let p(x) := xx and A = {x : p(x)} and consider whether A is an element of itself. If AA, then due to the definition of p(x), AA, and if AA, then AA. Because of this built-in contradiction, it is impossible for A to be a set. This is known as Russell's paradox, and it was a serious challenge to set theory. One solution would have been to dismiss set theory altogether. The problem was that this new subject combined with advances in logic appeared to ...

Get A First Course in Mathematical Logic and Set Theory now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.