Section 4 – Unions and Intersections

We are now ready to discuss a couple of familiar set theoretic operations: unions and intersections. Given two sets and , it would be “nice” to have a set that contains all the elements that belong to at least one of or . In fact, it would be nicer to generalize this to a collection of sets instead of just two, though we must be careful about using words like “two”, “three” and so on, since we haven’t really defined what numbers are so far. We don’t want to run the risk of inadvertently introducing circularity in our arguments! Anyway, this brings us to the following axiom.

Axiom of unions: For every collection of sets, there exists a set that contains all the elements that belong to at least one set of the given collection.

In other words, for every collection , there exists a set such that if for some in , then . Now, the set may contain “extra” elements that may not belong to any in . This can be easily fixed by invoking the axiom of specification to form the set . This set is called the union of the collection of set. Its uniqueness is guaranteed by the axiom of extension.

Generally, if is a collection of sets, then the union is denoted by , or .

A quick look at a couple of simple facts.

1) , and

2) .

We finally arrive at the definition of the union of two sets, and . .

Below is a list of a few facts about unions of pairs:

• ,
• (commutativity),
• (associativity),
• (idempotence),
• if and only if .

Now, we define the intersection of two sets, and as follows.

.

Once again, a few facts about intersections of pairs (analogous to the ones involving unions):

• ,
• ,
• ,
• ,
• if and only if .

Also, if , then the sets and are called disjoint sets.

Two useful distributive laws involving unions and intersections:

• ,
• .

We prove the first one of the above. The proof of the second one is left as an exercise to the reader. The proof relies on the idea that we show each side is a subset of the other. So, suppose belongs to the left hand side; then and , which implies and or , which implies or , which implies ; hence belongs to the right hand side. This proves that the left hand side is a subset of the right hand side. A similar argument shows that the right hand side is a subset of the left hand side. And, we are done.

The operation of the intersection of sets from a collection, , is similar to that of the union of sets from . However, the definition will require that we prohibit from being empty, and we will see why in the next section. So, for each collection, , there exists a set such that if and only if for every in . To construct such a set , we choose any set in – this is possible because – and write .

Note that the above construction is only used to prove that exists. The existence of doesn’t depend on any arbitrary set in the collection . We can, in fact, write

.

The set is called the intersection of the collection of sets. The axiom of extension, once again, guarantees its uniqueness. The usual notation for such a set is or .

EXERCISE: if and only if .

SOLUTION: We first prove the “if” part. So, suppose . Now, if , then either or . In the first case, and , which implies and . In the second case, we again have (since ), which implies and . In either case, we have . Hence, is a subset of .

Similarly, if , then and . Now, if , then , which implies . And, if , then once again . Thus, in either case, . Hence, is a subset of . We, thus, proved . This concludes the proof of the “if” part.

Now, we prove the “only if” part. So, suppose . If , then belongs to the left hand side of the equality, which implies belongs to the right hand side. This implies (and .) Hence, . And, we are done.

Section 1 – The Axiom of Extension

We encounter sets, or if we prefer, collections of objects, everyday in our lives. A herd of cattle, a group of women, or a bunch of yahoos are all instances of sets of living beings. “The mathematical concept of a set can be used as the foundation for all known mathematics.” The purpose here is to develop the basic properties of sets. As a slight digression, I wouldn’t consider myself a Platonist; hence, I don’t believe there are some abstract properties of sets “out there” and that the chief purpose of mathematics is to discover those abstract things, so to speak. Even though the idea of a set is ubiquitous and it seems like the very concept of a set is “external” to us, I still think that we must build, or rather postulate, the existence of the fundamental properties of sets. (I think I am more of a quasi-empiricist.)

Now, we won’t define what a set is, just as we don’t define what points or lines are in the familiar axiomatic approach to elementary geometry. So, we somewhat rely on our intuition to develop a definition of sets. Of course, our intuition may go wrong once in a while, but one of the very purposes of our exposition is to reason very clearly about our intuitive ideas, so that we can correct them any time if we discover they are wrong.

Now, a very reasonable thing to “expect” from a set is it should have elements or members. So, for example, Einstein was a member of the set of all the people who lived in the past. In mathematics, a line has points as its members, and a plane has lines as its members. The last example is a particularly important one for it underscores the idea that sets can be members of other sets!

So, a way to formalize the above notion is by developing the concept of belonging. This is a primitive (undefined) concept in axiomatic set theory. If is a member of ( is contained in , or is an element of ), we write . ( is a derivation of the Greek letter epsilon, , introduced by Peano in 1888.) If is not an element of , we write . Note that we generally reserve lowercase letters (, etc) for members or elements of a set, and we use uppercase letters to denote sets.

A possible relation between sets, more elementary than belonging, is equality. If two sets and are equal, we write If two sets and are not equal, we write

Now, the most basic property of belonging is its relation to equality, which brings us to the following formulation of our first axiom of set theory.

Axiom of extension: Two sets are equal if and only if they have the same elements.

Let us examine the relation between equality and belonging a little more deeply. Suppose we consider human beings instead of sets, and change our definition of belonging a little. If and are human beings, we write whenever is an ancestor of . Then our new (or analogous) axiom of extension would say if two human beings and are equal then they have the same ancestors (this is the “only if” part, and it is certainly true), and also that if and have the same ancestors, then they are equal (this is the “if” part, and it certainly is false.) and could be two sisters, in which case they have the same ancestors but they are certainly not the same person.

Conclusion: The axiom of extension is not just a logically necessary property of equality but a non-trivial statement about belonging.

Also, note that the two sets and have the same elements, and hence, by the axiom of extension, , even though it seems like has just two elements while has five! It is due to this that we drop duplicates while writing down the elements of a set. So, in the above example, it is customary to simply write .

Now, we come to the definition of a subset. Suppose and are sets. If every member of is a member of , then we say is a subset of , or includes , and write or . This definition, clearly, implies that every set is a subset of itself, i.e. , which demonstrates the reflexive property of set inclusion. (Of course, equality also satisfies the reflexive property, i.e. .) We say is a proper subset of whenever but . Now, if and , then , which demonstrates the transitive property of set inclusion. (Once again, equality also satisfies this property, i.e. if and , then .) However, we note that set inclusion doesn’t satisfy the symmetric property. This means, if, then it doesn’t necessarily imply . (On the other hand, equality satisfies the symmetric property, i.e. if , then .)

But, set inclusion does satisfy one very important property: the antisymmetric one. If we have and , then and have the same elements, and therefore, by the axiom of extension, . In fact, we can reformulate the axiom of extension as follows:

Axiom of extension(another version): Two sets and are equal if and only if and .

In mathematics, the above is almost always used whenever we are required to prove that two sets and are equal. All we do is show that and , and invoke the (above version of) axiom of extension to conclude that .

Before we conclude, we note that conceptually belonging () and set inclusion () are two different things. always holds, but is “false”; at least, it isn’t true of any reasonable set that anyone has ever constructed! This means, unlike set inclusion, belonging does not satisfy the reflexive property. Again, unlike set inclusion, belonging does not satisfy the transitive property. For example, a person could be considered a member of a country and a country could be considered a member of the United Nations Organizations (UNO); however, a person is not a member of the UNO.

Naive Set Theory (Paul Halmos)

 

I have just started reading Paul R. Halmos’ classic text Naive Set Theory, and I intend to blog on each section of the book. The purpose is mainly to internalize all the material presented in the book and at the same time provide the gist of each section, so that I can always come back and read whenever I feel like doing so. The actual text, divided into 25 sections (or chapters, if you will), comprises 102 pages. Halmos’ original intention was “to tell the beginning student of advanced mathematics the basic set theoretic facts of life, and to do so with the minimum of philosophical discourse and logical formalism… The style is usually informal to the point of being conversational.“

The reader is warned that “the expert specialist will find nothing new here.” Halmos recommends Hausdorff’s Set Theory and Axiomatic Set Theory by Suppes for a more extensive treatment of the subject. Nevertheless, the treatment by Halmos is not trivial at all. I personally feel his exposition is impeccable!

Almost all the ideas presented in the following posts belong to the author of the book, and I make absolutely no claims to originality in the exposition.