Sets and Subsets

or. equivalently.

The first way of writing 5 corresponds to definition by property (the ":" should be read as "given that"); the second to definition by enumeration. The key aspects of this notation are as follows:

• A capital letter denoting the set, here S.

• A lowercase letter denoting a typical element of the set, here x.

• Braces, (...), that enclose the elements of the set and emphasize that we treat them as a single entity.

In general, a lowercase letter such as x denotes items that may or may not be elements of some particular set. For example, here x can represent any number whatsoever. Then, if x takes on a value that is in the set. we write x e S

and if it takes on a value that is not in (he set, we write xiS

Also, in general, the definition of a set by property may be written

where P is a property that x may or may not have, so P(.v) is equivalent to the statement "jt possesses the property P."

Consider now three further sets of numbers:

A = [x e Z+ :x < 11) = (1,2, 3,-1,5, 6, 7.8.9. 10. II) (2.4)

Note that in the case of A and B we have extended the notation slightly by writing the set to which .v must belong (a property of -4 and B) to the left of the colon.

Example 2.1 Define the set Z+ in equation (2.3) by enumeration Solution

The difficulty here is that the set of positive integers is very large. The way around this is to have a notation to stand for "and so on" once a pattern has been established so that there is little ambiguity about what follows. One suggestion in this example might be

Z. = |l.2,3,4, ...j where "..." stands for "and so on.' Notice, however dial this notation only suggests ihc nature of Z since any infinitely long sequence of integers could follow 4. ■

We observe also that all the elements of A are also elements of Z+ and that all the elements of B are also elements of A. This observation leads to the following important definition:

Definition 2.1

If all the elements of a set X are also elements of a set ) . then X is a subset of Y and we write x ç y where c is the set-inclusion relation.

In our examples we have B C A and A C Z+. Note also that these two facts lead to ficZf. Since A contains B and Z+ contains A, then Z+ must contain B.

Is Zt a subset of A'l Clearly not. because there exist numbers x > 12 that are in Z, but not in A. This observation leads to

Definition 2.2

If all ihe elements in a set X are in a set Y, but not all the elements of Y are in X then X is a proper subset of Y, and we write

Definition 2.3

So. for our examples, we certainly have A c Z+. It must then also be true that BC/!t, since B c A. Now consider the relationship between A and B. Is B a proper subset of A? Clearly. B c A because ihe odd integers 1.3 II are in

The equality between two sets is defined by

Two sets X and Y ¿ire equal if they contain exactly the same elements, and we write

Note that the equality of two sets means that they are identical, as is the case with S and B defined earlier. Formally, we demonstrate that two sets are equal by showing that they are both subsets of each other. That is,

implies and is implied by

So far we have considered examples that are sets of numbers. It is important to emphasize, though, that we can talk of a huge variety of things that we can collect into sets. Some economic examples are as follows:

• The set of firms producing a particular good, usually referred to as the industry for that good.

• The set of buyers and sellers of a good, usually referred to as the market for that good.

• The set of quantities of goods and services that a consumer is physically capable of consuming, usually called the consumption set for the consumer.

• The set of bundles of goods and services that a consumer can afford to buy. usually called the budget set of the consumer.

• The set of output quantities a firm is technologically capable of producing and the input quantities required to produce these, usually called the production set for the firm.

• The set of output quantities technologically capable of being produced in an economy given the available resources, usually called the production possibility set for an economy.

Set Operations

We are now going to define operations on sets that can be thought of as roughly analogous to the basic operations of addition, subtraction, multiplication, and division that we carry out on numbers. To avoid some logical problems that can arise if we continue to assume thai we are dealing with any kinds of sets whatsoever, we take ii that we have some given set of items of some specific kind, called the universal set, U, and we define the set-theoretic operations in terms of subsets of U. A Venn diagram, shown in figure 2.1. is a useful device for illustrating the relationships between sets and subsets. The reclangle represents the universal set. U, so that any point in L' is an item t. The sets we are interested in are shown by collections of points such as A and B or .V and Note that this is a purely schematic representation, and U should be thought of as a set of items in general. not necessarily as points in a plane. When we think about (he relationship between the sets, we notice a difference between the cases shown in (a) and lb) of figure 2.1. In lb), X and J" overlap, whereas in (a) .4 and B do not.

Figure 2.1 Venn diagrams

Definition 2.4

The intersection, IV, of two sets X and )'' is the set of elements that are in both X and Y We write

Thus the intersection is the set of common elements. The expression X 0 Y is read "the intersection of X and Y." What about the intersection of the sets <4 and B in figure 2.1 (a)'? Clearly, it does not exist, since there are no common elements shared by A and B. This leads to the idea of a set that has no elements.

Definition 2.5

The empty set or the null set is the set with no elements. The empty set is always written 0.

Since there are no common elements shared by A and B. we can write

and these two sets are said to be disjoint. Since all the sets under discussion arc in U, we have 0 c U. We can also think about the total of elements in a number of sets.

Definition 2.6

The union of two sets A and B is the set of elements in one or other of the sets. We write

Example 2.2

The expression A u ft is read "the union of A and B" !n figure 2.1 (a), C simply consists of the points in A and the points in B thought of now as a single set. If we let R — X U V. then, in figure 2.1 (b). R is the set shaped something like "oo." Note that we must have

and if we now define 0 to be a proper subset of any nonempty subset of U. we can also write

,4 n B C C, where C = A U B So we see that intersections of sets are always contained in their unions.

Take as our universal set the set of positive integers. 2_, and let X = {x 6 : jc < 20 and a/2 e Z+) Y = [.x e Z+ : 10 < x < 24 and x/2 e ¿T+1 What are X P Y and X U Y7 Solution

The simplest way to answer this question is by enumeration. We have X = |2,4. 6. 8. 10. 12, 14, 16, 18, 20) Y = (10. 12. 14. 16. 18,20.22.24)

Then

Xuy = (2,4,6.8. 10. 12, 14, 16. 18.20,22,24) = [X e Z+ : -v < 24 and x/2 e Z+)

Note (hat when we take the union, we do not count the common elements twice. ■

Example 2.3

By referring to figure 2.1 (b) with Z+ as the universal set, we can quickly establish that xnz+ = x. x u z. = z^ ynz+ = y, vuz+ = z+

This suggests an immediate generalization. If. for two sets S and V we have S c V, then S n V = 5 and 5 U V = V. This result is illustrated in figure 2.2. ■

It is useful to define as a set the elements that are not in some given set X.

Definition 2.7

The complement of a set X is the set of elements of the universal set U that are not elements of A", and it is written X. Thus

In figures 2.1 and 2.2 the complement of any set is simply the area outside the area denoting the set. Note that we must have

Example 2.4 Given Z+, X. and Y as defined in example 2.2. what are their complements? What are the complements of X Pi Y and X U V, written X n V' and X U V"? What are XnZj and XuZ+ ?

Solution

Since Z+ is the universal set in this example, we have Z+ = 0. Taking our earlier descriptions of X and Y. we have

= |.t e Z^ : X < 20 and x/2 ç Z4., or.i > 20)

= [x 6 Z. :x < 10. or.v > 24. or 10 < ;c < 24andx/2 i Z+\

= fx eZ.: a- < 10, or v > 20. or 10 < jc < 20 and x/2 \$ 2+1

= (.v e Z+ : -v < 24 and .v/2 £ Z+. or.v > 24}

Since X O Z+ = X, we have A' n Z+ = X. Since X U Z. = Z+. we have XlTzZ = Z+ = 0. ■

These examples show that if we have a set X C U or X = {.v € U : P{jc)} so that elements x in X have the property P. then the complement of X is the set of Jt-valueS that do not possess property P or X = {.v e U : not P{x)\.

We can think of the complement of a set A' c U as the difference between the sets X and U. This can be generalized to indicate the difference between any two sets.

The relative difference of X and >', denoted A' — Y. is the set of elements of X that are not also in V

As the Venn diagram in figure 2.1 (b) shows, we can think of X - Y as the part of X remaining when we take out the intersection of X and Yt SO we may write

Solution

If X = Y, then X - Y = X-X = XC\X = 0. If X = }',then Y - X = Y — Y = Y n f = 0, since no element of a set can be an element of its complement, and

Example 2.5 If X = 1', show that X - Y = Y - X = 0.

vice versa.

Solution

First note that if X DY = \fl. then X D F = X. It then follows immediately that x - y = x n >' = x m

Definition 2.9

We have considered only individual subsets of the universal set U. We now consider two important collections of subsets.

A partition of the universal set u is a collection of disjoint subsets of u, the union of which is U.

then these n subsets form a partition of U. This result is illustrated in figure 2.3. The key point is that each element off lies in one and only one of the subsets. Let 5 denote this collection of subsets, and let the union of the n subsets be denoted

Figure 2.3 A partition of U

S= Xi<ZU : U X, = U and X{ n X} = 0, i,j= I n, i ^ j is a partition of U.

Example 2.7 Show that {AT. X), for X C U, is a partition of 11. Solution

By the definition of a complement, we know that XUX = U. But also, X O X = 0. Thus (X. X) is a partition of t/, ■

Example 2.8 Do the sets X and Y of example 2.2 form a partition of 7, ? Solution

Example 2.9 Consider the collection of subsets of Z+ defined as follows:

X. = [x e Z+ : 10(i -!)<*< lOr, i e Z+} Does the collection of these X, form a partition of ZJl Solution

The first three subsets are

X, = [x e Z+ : 0 < .V < 10) X2 = f.r 6 Zf : 10 < jt < 20} X, = u € z+ : 20 < jr < 30}

Our intuition tells us strongly that this collection does form a partition of Z4. A proof goes as follows: First, we have to prove that the subsets are disjoint, so we take X, and Xj with j > i (and j > / + 1). If * 6 X;, then* < 10/ < 10(j - 1), and sox £ Xj. If x <S Xh then x > )0(y — 1) > 10/ and so x \$ X,. Thus the subsets are disjoint. To prove that any element of Z+ is in one of these sets, take any x e Z+ and note that either x is a multiple of 10 or it is not. If it is, then let i = x /10. Then we have.v e X,. If it is not. then x/lO can he written a + (fe/10), where a e Z+ and (6/10) < I. Then set / = a + 1. and it is straightforward to show that x e X, . ■

Definition 2.10

The power set of a set X is the set of nil subsets of X. and is written P( X). That is.V(X\ = lA •. A C X).

Example 2.10

Note first that 0 is a subset of every set X C (/, and by convention, we take A' itself to be a subset of A'. We also have (11, (2|. {3}. and the sets of pairs to give

■p(A') = ((I), (2), (3), (1,2). (1.3), [2, 3}. X. 0) ■

Note that 'P(X) in this example has exactly 23 = 8 elements. For any set X with a finite number n of elements, it can be shown that its power set has exactly 2" elements. In other words, a set with n elements has 2" subsets.

Example 2.11 Find the power sets of the following sets:

Solution

(i) The only possible subset of 0 is itself and so = |0). Note that using the formula for finding the number of subsets of a set, we have n = 0 and 2° = I.

(ii) A set with only one element is usually called a singleton, and it has two subsets, so 'P(X) = |(a),0) = {X.V)).

(iii) We cannot construct the power set of Z+ by enumeration, but we can define it by

the set of all possible sets of positive integers.

0 0