Sets
[callout headingicon=”noicon” textalign=”textleft” type=”basic”]
I don’t want to belong to any club that will accept people like me as a member.
Groucho Marx
[/callout]
In our quest to reason about quantities and relationships, we’d like to handle quantities that are a bit more general than integers (real numbers, for example). We’d also like to handle relationships. To do this we will develop a language that is essentially equivalent to logic, but is a bit more intuitive to use. That language is the language of sets.
Overview of Sets
- What is a Set? (this page) Sets are like open sentences.
- Set Operations and Subsets. Sets can be made more interesting by combining them. This can be tricky.
- The Element’s Eye View. How to prove statements about sets?
- Set-builder Notation. Sets are often specified by open sentences. This can be trickier than it seems.
- Families of Sets and ‘Generalized’ Set Operations. Why stop at two sets?
- Practice with Sets.
What is a set?
The intuitive definition of a set is just a collection of things. This is, of course, not much of a definition. Many mathematicians in the late nineteenth century actually thought the precise definition of set did not much matter. But the philosopher and mathematician Bertrand Russell, writing in 1901, discovered that we have to be more careful. He considered the following:
Definition. We call a collection ordinary if it does not contain itself. Otherwise we call the collection extraordinary.
Most collections are ordinary, for example the collection of all Bernese mountain dogs is not itself a Bernese mountain dog. The set of all natural numbers is not itself a natural number. But some collections are extraordinary, for example:
- The collection of abstract ideas is an abstract idea.
- The collection of mathematical objects is a mathematical object.
- The collection of all collections is a collection.
Russell therefore asked the question: Is the collection of ordinary collections ordinary? To make this easier, let’s write $E$ for the collection of extraordinary collections, $O$ for the collection of ordinary collections, and write $\in E$ and $\in O$ for “is extraordinary” and “is ordinary”, respectively. Thus a collection $C$ satisfies $C\in O$ exactly when $C\notin C$ and $C\in E$ exactly when $C\in C$.
There are two possibilities. If the collection of ordinary collections is ordinary ($O\in O$), then we know that $O$ must be ordinary, so $O$ cannot contain itself, i.e. $O\notin O$. If the collection of ordinary collections is extraordinary, ($O\in E$), then we know that $O$ must contain itself, so $O\in O$. But a collection cannot be both ordinary and extraordinary.
So such a collection leads to a paradox–precisely as the sentence this sentence is false did. Russell’s paradox shows that we need to be very careful about the words “is in”.
Definition. A set $S$ is an object for which the question “Is $x$ in $S$?” has an unambiguous answer. We write $x\in S$ (read “$x$ is an element of $S$”) if the answer is yes and $x\notin S$ if the answer is no.
Another way to phrase this is: $S$ is a set exactly when $x\in S$ is an open sentence.