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

The *difference* between sets and , also known as the *relative complement* of in , is the set defined by

.

If we assume the existence of a universe, , such that all the sets are subsets of , then we can considerably simplify our notation. So, for instance, can simply be written as , which denotes the complement of in . Similarly, , , and so on. A quick look at a few more facts:

- ,
- ,
- if and only if .

The last one is proved as follows. We prove the “if” part first. Suppose . If , then clearly . But, since , we have , which implies . Hence, . This closes the proof of the “if” part. Now, we prove the “only if” part. So, suppose . Now, if , then clearly . But, since , we have , which implies . Hence, . This closes the proof of the “only if” part, and, we are done.

The following are the well-known *DeMorgan’s laws* (about complements):

, and .

Let’s quickly prove the first one. Suppose belongs to the left hand side. Then, , which implies and , which implies and , which implies . This proves that the left hand side is a subset of the right hand side. We can similarly prove the right hand side is a subset of the left hand side, and this closes our proof.

Though it isn’t very apparent, but if we look carefully at the couple of problems whose proofs we did above, we note something called the *principle of duality* for sets. One encounters such dual principles in mathematics quite often. In this case, this dual principle is stated a follows.

Principle of duality (for sets): If in an inclusion or equation involving unions, intersections and complements of subsets of (the universe) we replace each set by its complement, interchange unions and intersections, and reverse all set-inclusions, the result is another theorem.

Using the above principle, it is easy to “derive” one of the DeMorgan’s laws from another and vice versa. In addition, DeMorgan’s laws can be extended to larger collections of sets instead of just pairs.

Here are a few exercises on complementation.

- ,
- if and only if ,
- ,
- ,
- ,
- .

We will prove the last one, leaving the remaining as exercises to the reader. Suppose belongs to the left hand side. Then, and . Now, note that if , then , which implies , which implies . If, on the other hand, , then , which implies , which implies . Hence, in either case, the left hand side is a subset of , and we are done.

We now define the *symmetric difference* (or *Boolean sum*) of two sets and as follows:

.

This is basically the set of all elements in or but not in . In other words, . Again, a few facts (involving symmetric differences) that aren’t hard to prove:

- ,
- ,
- (commutativity),
- (associativity),
- ,
- .

This brings us now to the *axiom of powers*, which basically states if is a set then there exists a set that contains all the possible subsets of as its elements.

Axiom of powers:If is a set, then there exists a set (collection) , such that if , then .

The set , described above, may be too “comprehens ive”, *i.e.*, it may contain sets other than the subsets of . Once again, we “fix” this by applying the axiom of specification to form the new set . The set is called the *power set* of , and the axiom of extension, again, guarantees its uniqueness. We denote by to show the dependence of on . A few illustrative examples: , , , and so on.

Note that if is a finite set, containing elements, then the power set contains elements. The “usual” way to prove this is by either using a simple combinatorial argument or by using some algebra. The combinatorial argument is as follows. An element in either belongs to a subset of or it doesn’t: there are thus two choices; since there are elements in , the number of all possible subsets of is therefore . A more algebraic way of proving the same result is as follows. The number of subsets with elements is . So, the number of subsets of is . But, from the binomial theorem, we have . Putting , we get as our required answer.

A few elementary facts:

- .
- If , then .
- .

EXERCISES:

1.Prove that .

2.Prove that .

After postulating a couple of important axioms in the previous two sections, we now arrive at a couple of important results.

1. There exists an empty set. (In fact, there exists exactly one!)

2. The empty set is a subset of every set.

Indeed, to prove the first result, suppose is some set. Then, the set is clearly an empty set, *i.e.* it doesn’t contain any elements. To “picture” this, imagine an empty box with nothing inside it. In fact, we can apply the axiom of specification to with any universally false sentence to *create* an empty set. The empty set is denoted by . The axiom of extension, on the other hand, guarantees there can be only *one* empty set.

Now, how do we argue that , for any arbitrary set ? Well, the reasoning is an indirect one, and for most beginners, it doesn’t seem like a complete one. There is something in the argument that doesn’t feel quite “right!” However, there is nothing “incomplete” about the argument, and here it is anyway.

Suppose, for the sake of contradiction, the emptyset, , is *not* a subset of Then, there exists an element in that doesn’t belong to But, the empty set is empty, and hence, no such element exists! This means our initial hypothesis is false. Hence, we conclude (maybe, still somewhat reluctantly) .

Now, the set theory we have developed thus far isn’t a very rich one; after all, we have only showed there is only one set and that it is empty! Can we do better? Can we come up with an axiom that can help us *construct* new sets? Well, it turns out, there is one.

Axiom of pairing:If and are two sets, then there exists a set such that and .

The above axiom guarantees that if there are two sets, and , then there exists another one, , that contains both of these. However, may contain elements other than and . So, can we guarantee there is a set that contains exactly and and nothing else? Indeed, we can. We just apply the axiom of specification to with the sentence “ or .” Thus, the set is the required one.

The above construction of a particular set illustrates one important fact: all the remaining principles of set construction are pseudo-special cases of the axiom of specification. Indeed, if it were given that there exists a set containing some particular elements, then the existence of a set containing *exactly* those elements (and nothing else) would follow as a special case of the axiom of specification.

Now, observe if is a set, then the axiom of pairing implies the existence of the set , which is the same as the set and is called a *singleton* of . Also, note that and are different sets; the first has no elements at all, whereas the second has exactly one element, *viz.* the empty set. In fact, there is a minimalist (inductive) way of constructing the set of natural numbers, , (due to von Neumann) using the* axiom of infinity* as follows.

But, more on this later.

The axiom of extension (discussed in Section 1) is unique in the sense that it postulates the existence of a relation between belonging and equality. All the other axioms of set theory, on the other hand, are designed to *create* new sets out of old ones!

The axiom of specification, loosely speaking, states that given some arbitrary (but well-defined) set (our universe), if we can make some “intelligent” assertion about the elements of , then we specify or characterize a subset of . An intelligent assertion about the elements of could, for example, specify a property that is shared by some elements of and not shared by the other elements. In the end, we will take up an example about an assertion that is tied to the famous *Russell’s paradox*.

For now, let us discuss a simple example. Suppose is the set of all (living) women. If we use to denote an arbitrary element of , then the *sentence* “ is married” is true for some of the elements of and false for others. Thus, we could *generate* a subset of using such a sentence. So, the subset of all the women who are married is denoted by . To take another example, if is the set of natural numbers, then . Now, note that the subset of is not the same as the number Loosely speaking, a box containing a hat is not the same thing as the hat itself.

Now, we only need to define what a *sentence* is before we can precisely formulate our axiom of specification. The following rules would be a formal way to (recursively) define a sentence:

“” is a sentence.”

“” is a sentence.

If is a sentence, then is a sentence.

If are sentences, then is a sentence.

If are sentences, then is a sentence.

If are sentences, then is a sentence.

If are sentences, then is a sentence.

If is a sentence, then is a sentence.

If is a sentence, then is a sentence.

Note that the two types of sentences, “” and ““, stated in the first two rules, are what we would call *atomic* sentences, while the rest of the other rules specify (valid) ways of generating (infinitely) many sentences from those two atomic sentences using the usual logical operators. Also, note that some of the rules above are rather redundant because it is possible to *convert* certain sentences having a set of logical operators to another sentence having a different set of logical operators. For example, “” can be written as ““, and so on. Anyway, we are digressing too far from our objective.

Having defined what a sentence is, we can now formulate the major principle of set theory, often referred to by its German name *Aussonderungsaxiom*.

Axiom of specification:To every set and to every condition , there corresponds a set whose elements are exactly those elements of for which holds.

A “condition” here just means a sentence. The letter is *free* in the sentence , meaning occurs in at least once without occurring in the phrases “for some ” or “for all “. Now, the axiom of extension guarantees us that the axiom of specification determines the set B uniquely, and we usually write .

This finally brings us to the example we mentioned in the beginning of this section. Let us define . Suppose is some arbitrary set. Let . Then for all ,

.

Can we have ? The answer is no, and here’s why. Suppose, for the sake of contradiction, . Then, we have either , or . If , then using , we have , a contradiction. And, if , then using again, the assumption yields , a contradiction. This proves that is false, and hence we conclude . Note that our set was an arbitrary one, and we just showed that there is something (*viz.* B) that does not belong to . We have, thus, essentially proved that

there is no universe.

Here, “universe” means “universe of discourse”, a set that contains all the objects that enter into that discussion.

It was mentioned earlier that the above example has something to do with *Russell’s paradox*. We shall see why. In the earlier pre-axiomatic approaches to set theory, the existence of a universe was taken for granted. Now, in the above example, we just showed that implies the non-existence of a universe. So, if we assume that a universe exists, then it implies that , but we have already shown that this leads to a contradiction! And this was exactly the content of *Russell’s paradox*. In Halmos’ own words:

The moral is that it is impossible , especially in mathematics, to get something for nothing. To specify a set, it is not enough to pronounce some magic words (which may form a sentence such as ““); it is necessary also to have at hand a set whose elements the magic words apply.

## Recent Comments