I am interested to know some set theory. Here’s what I know from reading Naïve Set Theory by Paul Halmos, a recommended book by MIRI. It is well under a hundred pages. I think it's going to be useful for me, perhaps not immediately, but soon. So my goal is not just comprehending the material but also retaining it. To this end, I will attempt to write these posts mostly from memory and whenever I draw a blank I will refer to the book but resume writing much later to make sure I can recall.
No definition of a set
Instead of formally defining what a set is, let's just stick to the naïve and informal impression that we have of a set, which is that a set is a collection of elements. Whenever we attempt to write down a set, we use the curly braces and mention its elements inside it. Suppose a set has elements , and then we may express the set as
Consider the question: what does it mean for two sets to be equal? And for that, we will first see a couple of basic relations between sets.
One is belonging and the other is inclusion. They sound similar but there's a subtle difference. We say element belongs to , when is an element of . It is denoted as . We say includes or is a subset of when each element of is also an element of . It is denoted as or .
Now let us define the equality of two sets. Two sets and are equal if and only if is a subset of and is a subset of . This is the axiom of extension. It describes what it means for two sets to be equal and also suggests how one may prove two sets to be equal.
Constructing sets by constructing sentences
One way to build a set out of a given set is to make assertions about the elements of the given set and the new set contains exactly the elements for which the assertion is true. So, given a set and an assertion we construct a set which contains exactly those elements of A for which S(x) is true.
One can construct by using first-order logical symbols along with the belongs to and inclusion relations. must be a free variable in . This way of constructing a subset out of a given set is the axiom of specification.
There's no universe
Consider the assertion . Let's apply this assertion to an arbitrary set and call the resulting subset . Does ?
We will show that it's not the case that . The proof is by contradiction:
Assume . There are two possibilities.
- . If this is true then S(B) is false therefore by the axiom of specification. Contradiction.
- . If this is true then S(B) is true therefore by the axiom of specification. Contradiction.
Hence, our assumption must be false. Therefore .
What we have shown is that for any arbitrary set , we can construct a set such that it does not belong to . Perhaps the axiom of specification is too strong because this result indicates that there's no universal set containing everything. For now we will not consider such as described by as sets.
Construction via pairing
Let us assume some set exists. One consequence of the axiom of specification is the existence of an empty set, denoted by . The corresponding specification would be .
There's another way to construct sets by pairing two sets. For any two sets and , there exists another set such that and belong to . This is the axiom of pairing and as a direct consequence of applying axiom of specification we can show the existence of a set with only and as its elements. Such a set is called the unordered pair of and , where unordered simply implies we don't care about the order of the elements and .
We can apply axiom of pairing to a single set and what we obtain is which is simply . Such a set is called the singleton of . Assuming some set exists, we have shown the existence of the empty set and using the axiom of pairing we can construct new sets resulting in sets such as ad infinitum.