Notes I: Sets and Functions

Reference 1: Topology and Modern Analysis, G F Simmons, Tata McGraw Hill Publication.

There are certain logical difficulties which arise in the foundations of set theory (see Problem 1). We avoid these difficulties by assuming that each discussion in which a number of sets are involved takes place in the context of a single fixed set. This set is called the universal set. It is denoted by U in this section and the next, and every set mentioned is assumed to contain elements of U. In later chapters, there will always be on the one hand, a given space within which we work, and this will serve without further comment as our universal set. It is often convenient to have available in U a set containing no elements whatsoever; we call this the empty set and denote it by the symbol \phi. A set is said to be finite if it is empty or consists of n elements for some positive integer n; otherwise, it is said to be infinite.

The relation \subseteq is called set inclusion. The following are the properties of set inclusion (it is an equivalence relation):

i) A \subseteq A for every A;

ii) A \subseteq B and B \subseteq A imply A=B.

iii) A \subseteq B and B \subseteq C imply A \subseteq C.

It is quite important to observe that (i) and (ii) above can be combined into a single statement that A=B \longrightarrow A \subseteq B and B \subseteq A. This remark contains a useful principle of proof, namely, that the only way to show that two sets are equal apart from merely inspecting them, is to show that each is a subset of the other.

Problems:

  1. Perhaps, the most famous of the logical difficulties referred to in the theory of sets is Russell’s paradox. To explain what this is, we begin by observing that a set can easily have elements which are themselves sets., e.g., \{ 1, \{ 2,3\}, 4\}. This means the possibility that a set might well contain itself as one of its elements. We call such a set an abnormal set, and any set which does not have itself as an element we call a normal set. Most sets are notmal,, and if we suspect that abnormal sets are in some way undesirable, we might try to to confine our attention to the set N of all normal sets. Someone is now sure to ask, is N itself normal or abnormal? It is evidently one or the other, as it cannot be both. Show that if N is normal, it must be abnormal. Proof 1: Set N is the set of all normal sets. Clearly, it contains itself, so it is abnormal. Part II: Show that if N is abnormal, then it is normal. Part 2 proof: As N is abnormal, it contains itself as an element. Set N is the set of all normal sets, so it does not contain itself. So, it is normal. We see in this way that each of our two alternatives is self-contradictory, and it seems to be the assumption that such a set N exists which has brought us to this impasse. For further discussion of these matters, refer to Fraenkel’s Abstract Set Theory. Russell’s own account of the discovery can also be found.
  2. The symbol we have used for set inclusion is similar to that used for the familiar order relation on the real line: if x and y are real numbers, x \leq y means that y-x is non negative. The order relation on the real line has all the properties mentioned in the text: (a) x \leq x for every x (b) x \leq y and y \leq x means x=y, and (c) x \leq y and y \leq z means x \leq z. It also has an additional property: (d) For any x and y, either x \leq y or y \leq x. Property d says that any two real numbers are comparable with respect to the relation in question, and it leads us to call the order relation on the real line as a total (or linear) order relation. Show by an example that this property is not possessed by set inclusion. It is for this reason that set inclusion is called a partial order relation. Answer: Disjoint sets.
  3. (a) Let U be the single element set \{ 1\}. There are two subsets, the empty set \phi and \{1\} itself. If A and B are arbitrary subsets of U, there are four possible relations of the form A \subseteq B. Count the number of true relations amongst these. Answer: \phi \subset U, a true relation; U \subset \phi, which is not a true relation; U \subseteq U, which is a true relation; \phi \subseteq \phi, which is debatable. (3b) Let U be the set \{ 1,2\}. There are four subsets, namely, \phi, U, \{ 1 \} and \{ 2\}. If A and B are arbitrary subsets of U, there are 16 possible relations of the form A \subseteq B. Count the number of true ones: Answer: \phi \subseteq U, \phi \subseteq \{ 1\}, \phi \subseteq \{ 2 \}, \{ 1 \} \subseteq U, \{ 2\} \subseteq U, \{ 1 \} \subseteq \{ 1 \}, \{ 2 \} \subseteq \{ 2 \}. So, there are 7 such true relations out of 16. (3c) Now, let U be the set \{ 1,2,3\}. There are 8 subsets, namely, \phi, U, \{ 1\}, \{ 2\}, \{ 3 \}, \{1,2\} , \{ 1,3\}, \{ 2,3\}. There are 64 possible relations of the form A \subseteq B. Count the number of true ones. Answer: \phi \subseteq U, \phi \subseteq \{ 1 \}, \phi \subseteq \{ 2 \}, \phi \subseteq \{ 3 \}, \{ 1 \} \subseteq U, \{ 2 \} \subseteq U, \{ 3 \} \subseteq U, \{ 1, 2\} \subseteq U, \{ 1, 3\} \subseteq U, \{ 2,3\} \subseteq U, \{ 1\} \subseteq \{ 1, 2 \}, \{ 1 \} \subseteq \{ 1,3\}, \{ 2 \} \subseteq \{ 1,2 \}, \{ 2\} \subseteq \{ 2,3\}, \{ 3\} \subseteq \{ 1,3\}, \{ 3\} \subseteq \{ 2,3\}. And, also, except \phi and U, each is a subset of itself. Thus, there are such 30 true relations. (3d) Let U be the set \{ 1,2,3,\ldots, n\} for an arbitrary positive integer n. How many subsets are there ? Answer: 2^{n} subsets. How many possible relations of the form A \subseteq B? Answer: 2^{n} \times 2^{n}, that is, 2^{2n} possible pairings. Can you make an informed guess as to how many of these are true? Answer (trial 1): The empty set \phi is paired with each of the remaining 2^{n}-1 so these give 2^{n}-1 pairings; each set which is not U and \phi can be paired with U as a superset, so these give 2^{n}-2 pairings; except \phi and U, each subset is a subset of itself, so these are total 2^{n}-2 possibilities; each two element subset can be paired with 3-element subsets containing the original two elements and one more, and there are 2^{n}-2 such cases; each two element subset can be paired with 4-element subsets out of which two elements are original and two are chosen out of the remaining 2^{n}-2, that is, there are {2^{n}-2} \choose {2} pairings; …continuing in this way, we get the following final answer: 2(n-3)+\frac{(n-4)(n-1)}{2} + 2^{n}\times (n-3) + (2^{n-2}-1)(2^{2^{n}-n+2})

II. The Algebra of Sets:

In this section, we consider several useful ways in which sets can be combined with one another, and we develop the chief properties of these operations of combination.

As we emphasized above, all the sets we mention in this section are assumed to be subsets of our universal set U. U is the frame of reference, or the universe, for our present discussion. In our later work, the frame of reference in a particular context will naturally depend on what ideas we happen to be considering. If we find ourselves studying sets of real numbers, then U is the set R of real numbers. If we wish to study sets of complex numbers, then we take U to be the set C of all complex numbers. We sometimes want to narrow the frame of reference and to consider (for instance) only subsets of the closed unit interval [0,1], or of the closed unit disc \{z : |z|\leq 1 \} and in these cases we choose U accordingly. Generally speaking, the universal set U is at out disposal, and we are free to select it to fit the needs of the moment. For the present, however, U is to be regarded as a fixed but arbitrary set. This generally allows us to apply the ideas we develop below to any situation which arises in out later work.

It is extremely helpful to the imagination to have a geometric picture available in terms of which we can visualize sets and operations on sets. A convenient way to accomplish this is to represent U by a rectangular area in a plane, and the elements which make up U by the points of this area. Sets can then be pictured by areas within this rectangle, and diagrams can be drawn which illustrate operations on sets and relations between them. For instance, if A and B are sets, then Figure 1 represents the circumstance that A is a subset of B (we think of each set as consisting of all points within the corresponding closed curve). Diagrammatic thought of this kind is admittedly loose and imprecise; nevertheless, the reader will find it invaluable. No mathematics, however, abstract it may appear, is ever carried on without the help of mental images of some kind, and these are often nebulous, personal and difficult to describe.

The first operation we discuss in the algebra of sets is that of forming unions. The union of two sets A and B, written A \bigcup B, is defined to be the set of all elements which are in either A or B (including those which are in both). A \bigcup B is formed by lumping together the elements of A and those of B and regarding them as constituting a single set. In Figure 2, A \bigcup B is indicated by the shaded area. The above can also be expressed symbolically:

A \bigcup B = \{ x : x \in A or x \in B\}.

The operation of forming union is commutative and associative:

A \bigcup B = B \bigcup A and A \bigcup (B \bigcup C) = (A \bigcup B) \bigcup C.

It has the following additional properties: A \bigcup A = A, A \bigcup \phi=A, and A \bigcup U = U.

We also note that A \subseteq B \Leftrightarrow A \bigcup B = B so set inclusion can be expressed in terms of this operation.

Our next operation is that of forming intersections. The intersection of two sets A and B, written A \bigcap B is the set of all elements which are in both A and B. In symbols, A \bigcap B = \{ x: x \in A and x \in B\}.

A \bigcap B is the common part of the sets A and B. In Figure 3, A \bigcap B is represented by the shaded area. If A \bigcap B is non-empty, we express this by saying that A intersects B. If, on the other hand, it happens that A and B have no common part, or equivalently, that A \bigcap B = \phi, then we say that A does not intersect B, or that A and B are disjoint and a class of sets in which all pairs of distinct sets are disjoint is called a disjoint class of sets. The operation of forming intersection is also commutative and associative:

A \bigcap B = B \bigcap A and A \bigcap (B \bigcap C) = (A \bigcap B) \bigcap C.

It has the further properties that

A \bigcap A = A, A \bigcap \phi = \phi, and A \bigcap U=A, and since

A \subseteq B \Leftrightarrow A \bigcap B = A,

We see that set inclusion can also be expressed in terms of forming intersections.

We have now defined two of the fundamental operations on sets and we have seen how each is related to set inclusion. The next obvious step is to see how they are related to one another. The facts here are given by the distributive laws:

A \bigcap (B \bigcup C) = (A \bigcap B) \bigcup (A bigcap C) and

A \bigcup (B \bigcap C) = (A \bigcup B) \bigcap (A \bigcup C)

These properties depend only on simple logic applied to the meaning of symbols involved. For instance, the first of the two distributive laws says that and element is in A and B or C precisely when it is in A and B or A and C. We can convince ourselves of the validity of these laws by drawing pictures (Venn Diagrams). The second distributive law is illustrated in Figure 4 where A \bigcup (B \bigcap C is formed on the left by shading and (A \bigcup B) \bigcap (A \bigcup C) on the right by cross shading. A moment’s consideration by the reader ought to convince him that one gets the same sets in both cases.

The last of our major operations on sets is the formation of complements. The complement of a set A, denoted by A^{'} is the set of all elements not in A. Since the only elements we are considering are those which make up U, it goes without saying — but it ought to be said that A^{['} consists of all elements of U which are not in A. Symbolically: A^{'} = \{ x: x \notin A, x \in U\}

Figure 5 in which A^{'} is shaded indicates this operation. The operation of forming complements has the following obvious properties:

(A^{'})^{'} = A

\phi^{'} = U

U^{'}=\phi

A \bigcup A^{'} = U

A \bigcap A^{'} = \phi.

Further, it is related to set inclusion by A \subseteq B \Longleftrightarrow B^{'} \subseteq A^{'}, and to the formation of unions and intersections by

(A \bigcup B)^{'} = A^{'} \bigcap B^{'}

(A \bigcap B)^{'} = A^{'} \bigcup B^{'}.

In words, the above laws, called De Morgan’s Laws, can be beautifully related as: The complement of union of two sets is the intersection of the complements; the complement of the intersection of two sets is the union of the complements.

Or, in yet other words, the first De Morgan law says: an element is not in either of the two sets precisely when it is outside of both; and the second De Morgan law can be expressed as: an element is not in both sets precisely when it is outside of one or the other.

The operations of forming unions and intersections are primarily binary operations, that is, each is a process which applies to a pair of sets and yields a third. We have emphasized this by our use of parentheses to indicate the order in which the operations are to be performed, as in (A_{1} \bigcup A_{2})\bigcup A_{3}, where the parentheses direct us first to unite A_{1} and A_{2}, and then to unite the result of this with A_{3}. Associativity makes it possible to dispense with parentheses in an expression like this and to write A_{1} \bigcup A_{2} \bigcup A_{3} where we understand that these sets are to be united in any order and the order in which we do it is irrelevant (that is, all possible different orders yield the same result). Similar remarks apply to A_{1} \bigcap A_{2} \bigcap A_{3}. Furthermore, if \{ A_{1}, A_{2}, \ldots, A_{n}\} is any finite class of sets, then we can form

A_{1} \bigcup A_{2} \bigcup \ldots \bigcup A_{n}

A_{1} \bigcap A_{2} \bigcap \ldots \bigcap A_{n}

in much the same way without any ambiguity of meaning whatever. In order to shorten the notation, we let I = \{1, 2, 3, \ldots, n \} be the set of subscripts which index the sets under consideration. I is called the index set. We then compress the symbols for the union and intersection just mentioned to \bigcup_{i \in I}A_{i} and \bigcap_{i \in I}A_{i}. For the sake of both brevity and clarity, these sets are often written \bigcup_{i=1}^{n}A_{i} and \bigcap_{i=1}^{n}A_{i}.

These extensions of our ideas and notation don[‘t reach nearly far enough. It is often necessary to form unions and intersections of large (really large!) classes of sets. Let \{A_{i} \} be an entirely arbitrary class of sets indexed by a set I of subscripts. Then,

\bigcup_{i \in I}A_{i} = \{x : x \in A \hspace{0.1in} for \hspace{0.1in} at \hspace{0.1in} least \hspace{0.1in} one \hspace{0.1in} i \in I \}.

And,

\bigcap_{i \in I}A_{i} = \{ x: x \in A_{i} \hspace{0.1in} for \hspace{0.1in} each \hspace{0.1in} i \in I\}

define their unions and intersections.

As above, we usually abbreviate these notations in \bigcup_{i}A_{i} and \bigcap_{i}A_{i} and if the class \{ A_{i}\} consists of a sequence of sets, that is, if \{ A_{i}\} = \{A_{1}, A_{2}, \ldots, A_{n} \}, then their unions and intersections are often written in the form \bigcup_{i=1}^{\infty}A_{i} and \bigcap_{i}A_{i}. Observe that we did not require the class A_{i} to be non-empty. If it does happen that the class is empty, then the above definitions give (remembering that all sets under consideration are subsets of U) \bigcup_{i}A_{i} and \bigcap_{i}A_{i}=U. The second of these facts amounts to the following statement: if we require of an element that it belongs to each set of the class, but there be no set present in the class, then every element satisfies this requirement. (We call this as the school of “vacuous logic” in theory of sets.) Note that if we had not made the explicit assumption that all sets under consideration are to be considered as subsets of U, we would not be able to fix a meaning to the intersection of an empty class of sets. A moments reflection makes it clear that the De Morgan equations are valid for arbitrary unions and intersections: (we can write a little proof also; it is easy):

(\bigcup_{i}A_{i})^{'} = \bigcap_{i}A_{i}^{'}

Complement of arbitrary union is intersection of complements.

(\bigcap_{i}A_{i})^{'} = \bigcup_{i}A_{i}^{'}

Complement of arbitrary intersection is union of complements.

**********************

It is instructive to verify the above general De Morgan laws for the case in which the class \{ A_{i}\} is empty. We present the answers below:

Consider the first general DeMorgan law: (\bigcup_{i}A_{i})^{'} = \bigcap_{i}A_{i}^{'}. Now, as \{ A_{i} \} = \phi, so \bigcup_{i}A_{i}=\phi and hence, the LHS is (\bigcup_{i}A_{i})^{'}= (\phi)^{'}=U whereas RHS Is \bigcap_{i}A_{i}^{'}= \bigcap_{i}U=U same as LHS. QED.

Now, consider the second generalized De Morgan Law:

(\bigcap_{i}A_{i})^{'} = \bigcup_{i}A_{i}^{'}, which we want to verify when the class of sets \{ A_{i}\} is empty. Consider \bigcap_{i}A_{i}=\phi and so (\bigcap_{i}A_{i})^{'} = (\phi)^{'}=U, which is our LHS. Now let us see RHS: \bigcup_{i}A_{i}^{'} = \bigcup_{i}(\phi)^{'}=\bigcup_{i}U=U which is same as LHS. QED.

**********************

We conclude our treatment of the general theory of sets with a brief discussion of certain special classes of sets which are of considerable importance in topology, logic, and measure theory. We usually denote classes of sets by capital letters in boldface.

First some general remarks which will be useful both now and later, especially in connection with topological spaces. We shall often have occasion to speak of finite unions and finite intersections, by which we mean unions and intersections of finite classes of sets, and by a finite class of sets we always mean one which is empty or consists of n sets for some positive integer n. If we say that a class of sets A is closed under the formation of finite unions, we mean that A contains the union of each of its finite subclasses; and since the empty subclass qualifies as a finite subclass of A , we see that its union, the empty set, is necessarily an element of A. In the same way, a class of sets which is closed under the formation of finite intersections necessarily contains the universal set.

Now, for the special classes of sets mentioned above. For the remainder of this section, we specifically assume that the universal set is non-empty. A Boolean algebra of sets is a non-empty class A of subsets of U which has the following properties:

(i) A \hspace{0.1in}and \hspace{0.1in} B \in {\bf {A}} \Longrightarrow A \bigcup B \in \bf{A}

(ii) A \hspace{0.1in} and \hspace{0.1in} B \in {\bf{A}} \Longrightarrow A \bigcap B \in \bf{A}

(iii) A \in {\bf{A}} \Longrightarrow A^{'} \in \bf{A}.

Since A is assumed to be non-empty, it must contain at least one set A. Then, property iii above shows that A^{'} \in {\bf{A}} also, so that A \bigcap A^{'} = \phi \in {\bf{A}} also. Moreover, A^{'} \bigcup A = U \in {\bf{A}} also. Since the class consisting of only the empty set and the Universal set is also clearly a boolean algebra of sets, these two distinct sets are the only ones which every Boolean algebra of sets must contain. It is equally clear that the class of all subsets of U is also a Boolean algebra of sets. There are many other less trivial kinds, and their applications are manifold in fields of study as diverse as electronics and statistics.

Let A be a Boolean algebra of sets. It is obvious that if \{ A_{1}, A_{2}, \ldots, A_{n}\} is a non-empty finite sub-class of A then

A_{1}\bigcup A_{2} \bigcup \ldots \bigcup A_{n} and A_{1}\bigcap A_{2} \bigcap \ldots \bigcap A_{n} are both sets in A; and since A contains both the empty set and the universal set, it is easy to see that A is a class of sets which is closed under the formation of finite unions, finite intersections and complements. We now go in the other direction, and let A be a class of sets which is closed under the formation of finite unions, finite intersections, and complements. By these assumptions, A automatically contains the empty set and the universal set, so it is non-empty and is easily seen to be a Boolean algebra of sets. We conclude from these remarks that Boolean algebras of sets can be described alternatively as classes of sets which are closed under the formation of finite unions, finite intersections, and complements. It should be emphasized once again that when discussing Boolean algebras of sets, we always assume that the universal set is non-empty.

One final comment. We speak of Boolean algebras of sets because there are other kinds of Boolean algebras than those which consist of sets, and we wish to preserve this distinction. We explore this topic further in our Appendix on Boolean algebras.

Problems:

  1. If \{ A_{i}\} and \{ B_{j}\} are two classes of sets such that \{ A_{i}\} \subseteq \{ B_{j}\}, prove that \bigcup_{i}A_{i} \subseteq \bigcup_{j}B_{j} and \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}.

Answer 1: Recall that a class of sets means a set of sets. By this definition, the following obviously holds: \bigcup_{i}A_{i} \subseteq \bigcup_{j}B_{j}. But, the second claim (I have yet to prove it for myself): \bigcap_{j}B_{j} \subseteq \bigcap_{i}A_{i}.

2. The difference between two sets A and B, denoted by A-B, is the set of all elements in A and not in B, thus A-B=A \bigcap B^{'}. Show that the following holds true:

A-B = A - (A \bigcap B) = (A \bigcup B) -B

(A-B)-C=A-(B \bigcup C)

A - (B-C) = (A-B) \bigcup (A \bigcap C)

(A \bigcup B) - C = (A-C) \bigcup (B-C)

A-(B \bigcup C) = (A-B) \bigcap (A-C)

3. The symmetric difference of two sets A and B, denoted by A \triangle B, is defined by A \triangle B = (A-B) \bigcup (B-A); it is thus the union of their differences in opposite orders. Prove the following:

A \triangle (B \triangle C) = (A \triangle B) \triangle C….that is, symmetric difference is associative

A \triangle \phi = A

A \triangle A = \phi

A \triangle B = B \triangle A…that is, symmetric difference is commutative

Distributive law like relation: prove: A \bigcap (B \triangle C) = (A \bigcap B) \triangle (A \bigcap C)

4. A ring of sets is a non-empty class A of sets such that if A and B are in A, then A \triangle B and A \bigcap B are also in A. Show that A must also contain the empty set, A \bigcup B, and A-B. Prove that if a non empty class of sets contains the union and difference of any pair of its sets, then it is a ring of sets. Prove that a Boolean algebra of sets is a ring of sets.

5. Show that the class of all finite subsets (including the empty set) of an infinite set is a ring of sets but is not a Boolean algebra of sets.

6. Show that the class of all finite unions of closed open intervals on the real line is a ring of sets but is not a Boolean algebra of sets.

7. Assuming that the universal set U is non-empty, show that Boolean algebras of sets can be described rings of sets which contain U.

Let me host the solutions after a while.

Regards,

Nalin Pithwa

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.