Mathematical Proof and the Principles of Mathematics/Sets

Introduction

Set theory is part of the foundations of modern mathematics. Indeed most mathematical objects can be described in the language of set theory.

Because sets are foundational, we don't try to define them in terms of other mathematical concepts. Instead, we formalize them by giving rules, called axioms, from which we can deduce all the other properties of sets that we are interested in.

What is a set?

To start with, we need to correct a few false impressions about set you may have from school. There you might have learned that a set is defined to be a collection of things and given an example such as $P=\{\mathrm {Cat} ,\mathrm {Dog} ,\mathrm {Hamster} \}$ .

First, the definition of the word 'set' uses the word 'collection', which means pretty much the same thing. This may help to establish some kind of intuition for what a set is, but it's ultimately circular; you can't define something as itself. This is why we take the term 'set' to be an undefined concept; the intuitive idea of a collection is one interpretation of the word 'set', but there may be others.

Second, the universe of discourse for set theory consists of just sets; there are no animals, colors, countries, etc. It should be said that some variations on set theory, the early versions in particular, do allow for what are called urelements which are not sets.. (The word 'urelement' is pronounced ur-element and is from the German prefix ur-, meaning root, added to the word 'element'.) It may seem like having nothing but sets would lead to a rather sterile theory, but it was realized early in the 20th century that these urelements were not needed to study mathematics. All the mathematical objects you are familiar with, numbers, functions, points on the plain, can be modeled with sets. Note that it's pointless to make an assumption such as, "Suppose $x$ is a set." The object $x$ is automatically a set just by being an object in our universe of discourse, so there's no need to assume that it is.

Third, although defining a set using a list of elements is possible, this is really a special case of using a predicate to define a set, as is usually done. So while you can write $P=\{0,2,5\}$ , this is really shorthand for $P=\{x:x=0\operatorname {or} x=2\operatorname {or} x=5\}$ .

Although we can't formally define sets in terms of something more fundamental, we can use the informal idea of a set as a collection of objects as a guide to intuition. More specifically, a set is an unordered collection of elements without multiplicity.

By 'unordered' we simply mean that the elements have no particular order. Reordering the elements doesn't give us a new set. By 'without multiplicity' we mean that an element of a set is not thought of as occurring multiple times in a set. It is either in the set or not in there. If we try to put an element into a set that is already in there, nothing changes.

We denote that x is an element of the set A by $x\in A$ . We can also denote that x is not an element of A by $x\notin A$ .

Some examples

For the examples given below, it is convenient to be able to assume the existence of numbers, specifically the natural numbers 0, 1, 2, ..., in our universe without formally defining what a number is. In order to keep things rigorous, we'll only use numbers when giving illustrative examples. Our formal development of set theory won't depend on numbers until we define them. We will show later that numbers can be defined as sets, although it may seem counterintuitive at first that this is possible.

As an example of a set, we take $P=\{0,2,5\}$ used above. We read this, P is the set containing the elements 0, 2 and 5. The curly braces enclosing a list is a standard notation for the set whose elements are the entries in the list.

Since the elements of a set are unordered and without multiplicities, the sets $\{5,2,0\},\;\{0,0,2,2,2,5\}$ are the same as P.

Another example is $E=\{n:n\ {\text{is an even natural number}}\}$ . This is an example of defining a set by comprehension, meaning whether something is an element is determined by some property of the element. As noted above, this method of defining a set includes the list method as a special case.

The notation $x\in y$ is read, "x is an element of y," or, "x is in y," and means x is one of the elements of y. We will often draw a slash through a predicate symbol to negate the predicate, so in this case the notation $x\notin y$ means that x is not an element of y. In our examples, $5\in P,5\notin E,4\notin P,4\in E.$

Note that we've defined some of the notation for sets here, but this notation presupposes that the sets involved actually exist. This must be proved from the axioms covered in the rest of the chapter.

The principle that a set is defined by the elements in it is known as extensionality. It is described by the first axiom of ZF set theory.

Axiomatisation of set theory

There is more than one way to axiomatise set theory, but the most popular by far is ZF set theory, which is described by a set of about nine rules known as the Zermelo-Fraenkel axioms. The axioms (which we will discuss in detail in the course of the wikibook) are as follows:

Axiom of Extensionality
Axiom of Existence
Axiom of Pair
Axiom of Union
Axiom Schema of Comprehension
Axiom of Power Set
Axiom of Foundation
Axiom of Infinity
Axiom Schema of Replacement

There is also a tenth axiom, called the Axiom of Choice, which is commonly added, giving ZFC set theory. However, when a particular result requires the Axiom of Choice, mathematicians usually state this explicitly since the Axiom of Choice is not as uncontroversial as the others.

ZF set theory is widely believed to be consistent, but it meets the conditions of Gödel's incompleteness theorems; this means it's impossible to prove its consistency.

It is known that the theory is incomplete, in fact statements are known for which neither the statement or its negation can be proved in ZFC. The most famous of these is the Continuum Hypothesis, to be covered later.

As they are usually stated, the axioms for set theory are not independent. Partly this is for historical reasons; Zermelo's original version of the axioms was expanded over time and the additions made some of the original axioms redundant.