You are currently browsing the tag archive for the ‘Paul Halmo’ tag.

We are now ready to discuss a couple of familiar set theoretic operations: unions and intersections. Given two sets $A$ and $B$, it would be “nice” to have a set $U$ that contains all the elements that belong to at least one of $A$ or $B$. 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 $C$, there exists a set $U$ such that if $x \in X$ for some $X$ in $C$, then $x \in U$. Now, the set $U$ may contain “extra” elements that may not belong to any $X$ in $C$. This can be easily fixed by invoking the axiom of specification to form the set $\{ x \in U: x \in X \mbox{ for some } X \mbox{ in } C \}$. This set is called the union of the collection $C$ of set. Its uniqueness is guaranteed by the axiom of extension.

Generally, if $C$ is a collection of sets, then the union is denoted by $\bigcup \{ X: X \in C \}$, or $\bigcup_{X \in C} X$.

A quick look at a couple of simple facts.

1) $\bigcup \{ X: X \in \emptyset \} = \emptyset$, and

2) $\bigcup \{ X: X \in \{ A \} \} = A$.

We finally arrive at the definition of the union of two sets, $A$ and $B$. $A \cup B = \{ x: x \in A \mbox{ or } x \in B \}$.

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

• $A \cup \emptyset = A$,
• $A \cup B = B \cup A$ (commutativity),
• $A \cup ( B \cup C) = (A \cup B) \cup C$ (associativity),
• $A \cup A = A$ (idempotence),
• $A \subset B$ if and only if $A \cup B = B$.

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

$A \cap B = \{ x: x \in A \mbox{ and } x \in B\}$.

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

• $A \cap \emptyset = \emptyset$,
• $A \cap B = B \cap A$ ,
• $A \cap ( B \cap C) = (A \cap B) \cap C$,
• $A \cap A = A$,
• $A \subset B$ if and only if $A \cap B = A$.

Also, if $A \cap B = \emptyset$, then the sets $A$ and $B$ are called disjoint sets.

Two useful distributive laws involving unions and intersections:

• $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$,
• $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.

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 $x$ belongs to the left hand side; then $x \in A$ and $x \in B \cup C$, which implies $x \in A$ and $x \in B$ or $C$, which implies $x \in A \cap B$ or $x \in A \cap C$, which implies $x \in (A \cap B) \cup (A \cap C)$; hence $x$ 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, $C$, is similar to that of the union of sets from $C$. However, the definition will require that we prohibit $C$ from being empty, and we will see why in the next section. So, for each collection, $C$, there exists a set $V$ such that $x \in V$ if and only if $x \in X$ for every $X$ in $C$. To construct such a set $V$, we choose any set $A$ in $C$ – this is possible because $C \not= \emptyset$ – and write $\{ x \in A: x \in X \mbox{ for all } X \mbox{ in } C\}$.

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

$\{ x: x \in X \mbox{ for all } X \mbox{ in } C\}$.

The set $V$ is called the intersection of the collection $C$ of sets. The axiom of extension, once again, guarantees its uniqueness. The usual notation for such a set $V$ is $\bigcap \{ X: X \in C \}$ or $\bigcap_{X \in C} X$.

EXERCISE: $(A \cap B) \cup C = A \cap (B \cup C)$ if and only if $C \subset A$.

SOLUTION: We first prove the “if” part. So, suppose $C \subset A$. Now, if $x \in (A \cap B) \cup C$, then either $x \in A \cap B$ or $x \in C$. In the first case, $x \in A$ and $x \in B$, which implies $x \in A$ and $x \in B \cup C$. In the second case, we again have $x \in A$ (since $C \subset A$), which implies $x \in A$ and $x \in B \cup C$. In either case, we have $x \in A \cap (B \cup C)$. Hence, $(A \cap B) \cup C$ is a subset of $A \cap (B \cup C)$.

Similarly, if $x \in A \cap (B \cup C)$, then $x \in A$ and $x \in B \cup C$. Now, if $x \in B$, then $x \in A \cap B$, which implies $x \in (A \cap B) \cup C$. And, if $x \in C$, then once again $x \in (A \cap B) \cup C$. Thus, in either case, $x \in (A \cap B) \cup C$. Hence, $A \cap (B \cup C)$ is a subset of $(A \cap B) \cup C$. We, thus, proved $(A \cap B) \cup C = A \cap (B \cup C)$. This concludes the proof of the “if” part.

Now, we prove the “only if” part. So, suppose $(A \cap B) \cup C = A \cap (B \cup C)$. If $x \in C$, then $x$ belongs to the left hand side of the equality, which implies $x$ belongs to the right hand side. This implies $x \in A$ (and $x \in B \cup C$.) Hence, $C \subset A$. And, we are done.

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 $x$ is a member of $A$ ($x$ is contained in $A$, or $x$ is an element of $A$), we write $x \in A$. ($\in$ is a derivation of the Greek letter epsilon, $\epsilon$, introduced by Peano in 1888.) If $x$ is not an element of $A$, we write $x \not\in A$. Note that we generally reserve lowercase letters ($x, y$, 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 $A$ and $B$ are equal, we write $A = B.$ If two sets $A$ and $B$ are not equal, we write $A \not= B.$

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 $x$ and $A$ are human beings, we write $x \in A$ whenever $x$ is an ancestor of $A$. Then our new (or analogous) axiom of extension would say if two human beings $A$ and $B$ are equal then they have the same ancestors (this is the “only if” part, and it is certainly true), and also that if $A$ and $B$ have the same ancestors, then they are equal (this is the “if” part, and it certainly is false.) $A$ and $B$ 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 $A = \{ x, y \}$ and $B = \{ x, x, y, y, y \}$ have the same elements, and hence, by the axiom of extension, $A = B$, even though it seems like $A$ has just two elements while $B$ 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 $B = \{ x,y \}$.

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

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

Axiom of extension(another version): Two sets $A$ and $B$ are equal if and only if $A \subset B$ and $B \subset A$.

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

Before we conclude, we note that conceptually belonging ($\in$) and set inclusion ($\subset$) are two different things. $A \subset A$ always holds, but $A \in A$ 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.

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.

• 238,103 hits