Chapter Five

Set Theory

Section 5.1

Basic Definitions of Set Theory

The following solutions make use of information found on pages 231-239 of the textbook.

Exercise 5.1.1:  Definitions

Fill in the blanks to complete the following sentences.

  1. The notation  a Î S  means that a is an element of S.
  2. The order of the elements listed in a set is  irrelevant, so {x1,x2,x3} = {x2,x3,x1}.
  3. The empty set is the set containing no elements and is denoted by Æ.
  4. For an arbitrary set A, the cardinality of the set A is the number of elements in A and is denoted by n(A) or equivalently |A|.
  5. If A and B are sets, A is called a subset of B, written, A Í  B, if, and only if, every element of A is also an element of B.
  6. Let A and B be sets. A is a  proper subset of B if, and only if, every element of A is an element of B, but there is at least one element of B that is not in A. This is written A Ì B .
  7. Given sets A and B, A equals B, written  A=B if, and only if, every element of A is in B and every element of B is in A. Symbolically: A = B if, and only if,
    A     Í  B, and B Í  A.
  8. Let A and B be subsets of a universal set U.
    The  union of A and B, denoted A È B is the set of all elements x in U such that x is in A or x is in B. Symbolically
    A È B={xÎ U | xÎ A Ú xÎ B}.
    The intersection of A and B, denoted AÇB is the set of all elements x in U such that x is in A and x is in B. Symbolically
    A Ç B={xÎ U | xÎ A Ù  xÎ B}.
    The  difference of B minus A, denoted B-A, is the set of all elements x in U such that x is in B and x is not in A. Symbolically
    B-A={xÎ U | xÎ B Ù  x Ï A}.
    The  complement of A, denoted Ac, is the set of all elements x in U such that x is not in A.  Symbolically Ac={xÎ U |  x Ï A}.
  9. Let n be a positive integer and let x1, x2,..., xn be (not necessarily distinct) elements. The  ordered n-tuple,(x1,x2,..., xn), consists of x1,x2,..., xn together with the ordering: first x1, then x2 and so forth up to xn. An ordered 2-tuple (x1,x2), is called an ordered pair.
    Two ordered n-tuples (x1,x2,..., xn)=(y1,y2,..., yn) are  equal if, and only if, x1=y1, x2=y2, ...,  xn =yn.
  10. Given two sets A and B, the  Cartesian product of A and B, denoted A ´ B, is the set of all ordered pairs (a,b) where a is in A and b is in B.
    Symbolically A ´ B={(a,b) | aÎ A Ù  bÎ B}.
  11. Let A(x) represent the predicate ``x is an element of A'' and let B(x) represent the predicate ``x is an element of B''. Write the following definitions using the symbolic logic from Chapters 1 and 2.
    A Í  B:  (" x Î U)  A(x) Þ B(x)
    A not a subset of B: ($ x Î U)  such that A(x) Ù ~ B(x)
    A = B:  (" x Î U)  A(x) Û B(x)
    A È B:   A(x) Ú B(x)
    A Ç B:   A(x) Ù B(x)
    B - A:    B(x) Ù ~ A(x)

 

Exercise 5.1.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. a) How many elements does the set {3, 3, {3}} have?
b) Is {1,1,2} = {1,2}?
c) Is 1 Î {1}?
d) Is 1 Π {{1}}?  

Full solution

2. Describe the following sets in words.

a) {1,2, ..., 100} 

b) {x Î R | x > 0} 

c) {y Î Z+   | -3 £ y £ 3}

Hint
Full solution

3. Suppose A = {a,b,c,d}, B = {a,b,e} and C = {a,b,c,d,e}.
Give reasons for your answers to the following questions.

a) Is B Í A? 
b) Is A Í C? 
c) Is A a proper subset of C? 
d) Is B Í B?

Full solution

4. Draw a Venn diagram to represent the relationship between the
following sets: A = {1,2,3}, B = {1,4}, C = {2,3}. 

Hint
Full solution

5. True or false:
a) {4} Î {1, {3}, 4} 
b) {4} Í  {1, {3}, 4}
c) {3} Î {1, {3}, 4}
d) 1 Í {1, {3}, 4}

Full solution

6. Let   A = {x Î Z  | x = 4p-1   for some  p Î Z}   and    B = {y Î Z  | y = 4q-5   for some q Î Z}.
Prove that A = B.

Hint
Full solution

7. Let the universal set be {1,2, ..., 10} and let  A = {1,2,3,4}, B = {2,4,6,8,10} and C = {1,3,5,7,9}. State:
a) A Ç B:
b) B È C:
c) B - A: 
d) A - C:
e) Bc:
f)  Ac:
g)  Ac È B:

Full solution

8. A Cartesian product with which you are probably already familiar is the xy-plane. The points which make up the plane are the elements of the set  R´R.  

a) On the set of axes below, plot the points representing the ordered pairs (1,2) and (2,1). 

b) Let A = {-1, 0, 1} and B = {3,4,5}. Write out the set A´B, and plot the elements of the set on the set of axes above. How many elements are in the set A´B?

Full solution

 

Section 5.2

Properties of Sets

The following solutions make use of information found on pages 244 - 256 of the textbook.

Exercise 5.2.1:  Definitions

Fill in the blanks to complete the following sentences.

1. Subset Relations: Let A, B and C be arbitrary sets.

  1. The Inclusion of Intersection Rule states: a) A Ç B Í A and b) A Ç B Í B
  2. The Inclusion in Union Rule states: a) A Í A È B   and b) B Í A È B
  3. The Transitive Property of Subsets is: if A Í B and B Í C, then A Í C.

Exercise 5.2.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.

1. Rewrite the subset relation P Í P È Q using the logical connectives and quantifiers from Chapters 1 and 2. Then use a truth table to prove that this relation is true.

Hint
Full solution

2. Rewrite the set property  (A Ç B)c = Ac È Bc  using the logical connectives and quantifiers from Chapters 1 and 2. Then use a truth table to prove this property is true.

Hint
Full solution

3. Determine whether the following statements are true or false.

a) A Í A Ç B  

b) C Í (A Ç B) È C

c) A È B Í A Ç B

d) A Ç (B È Ac) = A Ç B

e) (A È B)-(A Ç B)=A-B

Hint
Full solution

Section 5.3

The Empty Set, Partitions, Power Sets, and Boolean Algebras

The following solutions make use of the information found on pages 258 - 266 of the textbook.

Exercise 5.3.1:  Definitions

Fill in the blanks to complete the following sentences.

  1. The empty set is the unique set containing no elements. It is denoted by the symbol Æ.
  2. The empty set is a subset of every set. Symbolically: Æ Í A for any set A.
    Every set is a subset of itself. Symbolically: A Í A for any set A.
  3. Two sets are called  disjoint if, and only if, they have no elements in common.
    Symbolically: A and B are disjoint Û A Ç B = Æ.
  4. Sets A1, A2, ..., An are  mutually disjoint if, and only if, no two sets Ai, Aj, where i and j are distinct, have any common elements.  That is, for all  i, j = 1, 2, ..., n,    Ai Ç Aj = Æ   whenever i ¹ j.
  5. A collection of nonempty sets  {A1, A2, ..., An} is a partition of a set A if, and only if, it satisfies the two properties
    1. A = A1 È A2 È ... È An;
    2. A1, A2 , ... , An are mutually disjoint.
  6. Given a set A, the  power set of A, denoted P(A) is the set of all subsets of A.

Exercise 5.3.2:  Examples

You should attempt all these exercises yourself, using the textbook as an aid. Once you have attempted each question, check your answers by following the appropriate links. If you are stuck on a question, choose the link that gives you a hint and then try the question again.  

1. Complete the following proof of the statement:  There is only one set containing no elements.

Full solution 

2. Determine whether the following statements are true or false.

a) Æ = {Æ}

b) A È Æ = A

c) A Ç Ac = Æ

d) A È Ac = Æ

e) A Ç Æ = Æ 

f) (A - B) Ç B = Æ

g) {a, b, c} and {d, e} are disjoint sets. 

h) {1, 2}, {5, 7, 9} and {3, 4, 5} are mutually disjoint sets.

Full solution 

3. Let  A1  =  {n Î Z | n < 0 }  and  A2  = {n Î Z | n > 0 }.  Is {A1, A2} a partition of Z? If so, explain why; if not, give a partition.

Hint
Full solution

4. If  B = {1, 2, 3}, list the elements of P(B).

Hint
Full solution



Back to workbook solution page