# Discrete Mathematics/Set theory/Exercises

From Wikibooks, open books for an open world

## Contents

## Set Theory Exercise 1[edit]

1

- Is each of the following a well-defined set? Give brief reasons for each of your answers.
- (a) The collection of all alphanumeric characters.
- (b) The collection of all tall people.
- (c) The collection of all real numbers
*x*for which:- 2
*x*– 9 = 16.

- 2
- (d) The collection of all integers
*x*for which:- 2
*x*– 9 = 16.

- 2
- (e) The collection of all good tennis players.

2

**U**= {natural numbers};*A*= {2, 4, 6, 8, 10};*B*= {1, 3, 6, 7, 8}- State whether each of the following is true or false:
- (a) 2 ∈
*A* - (b) 11 ∈
*B* - (c) 4 ∉
*B* - (d)
*A*∈**U** - (e)
*A*= {even numbers}

3

**U**=**R**;*A*= {4, √2, 2/3, -2.5, -5, 33, √9, π}- Using the {…} set notation, write the sets of:
- (a) natural numbers in
*A* - (b) integers in
*A* - (c) rational numbers in
*A* - (d) irrational numbers in
*A*

4

- True or false?
- (a) ø = {0}
- (b)
*x*∈ {*x*} - (c) ø = { ø }
- (d) ø ∈ { ø }

5

- The following sets have been defined using the | notation. Re-write them by listing some of the elements.
- (a) {
*p*|*p*is a capital city,*p*is in Europe} - (b) {
*x*|*x*= 2*n*- 5,*x*and*n*are natural numbers} - (c) {
*y*| 2*y*^{2}= 50,*y*is an integer} - (d) {
*z*| 3*z*=*n*^{2},*z*and*n*are natural numbers}

## Set Theory Exercise 2[edit]

1

In A? |
In B? |
In C? |
Region |
---|---|---|---|

Y | Y | Y | |

Y | Y | N | |

Y | N | Y | |

Y | N | N | |

N | Y | Y | |

N | Y | N | |

N | N | Y | |

N | N | N |

- Copy the truth table to the right, and write at the end of each row the number of the corresponding region in
*Fig. 4 Venn Diagrams*.

2

- If
**U**= {letters of the alphabet},*A*= {a, a, a, b, b, a, c},*B*= {c, b, a, c} and*C*= {a, b, c}, what can be said about*A*,*B*and*C*?

3

**U**= {natural numbers};*A*= {2, 4, 6, 8, 10};*B*= {1, 3, 6, 7, 8}

- State whether each of the following is true or false:

- (a)
*A*⊂**U**

- (b)
*B*⊆*A*

- (c) ø ⊂
**U**

4

**U**= {a, b, c, d, e, f, g, h};*P*= {c, f};*Q*= {a, c, d, e, f, h};*R*= {c, d, h}

- (a) Draw a Venn diagram, showing these sets with all the elements entered into the appropriate regions. If necessary, redraw the diagram to eliminate any empty regions.

- (b) Which of sets
*P*,*Q*and*R*are proper subsets of others? Write your answer(s) using the ⊂ symbol.

- (c)
*P*and*R*are disjoint sets. True or False?

5

- Sketch Venn diagrams that show the universal set,
**U**, the sets*A*and*B*, and a single element*x*in each of the following cases:

- (a)
*x*∈*A*;*A*⊂*B*

- (b)
*x*∈*A*;*A*and*B*are disjoint

- (c)
*x*∈*A*;*x*∉*B*;*B*⊂*A*

- (d)
*x*∈*A*;*x*∈*B*;*A*is not a subset of*B*;*B*is not a subset of*A*

## Set Theory Exercise 3[edit]

1

**U**= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}*A*= {2, 4, 6, 8, 10}*B*= {1, 3, 6, 7, 8}*C*= {3, 7}

- (a) Illustrate the sets
**U**,*A*,*B*and*C*in a Venn diagram, marking all the elements in the appropriate places. (Note: if any region in your diagram does not contain any elements, re-draw the set loops to correct this.)

- (b)
*Using your Venn diagram*, list the elements in each of the following sets:

*A*∩*B*,*A*∪*C*,*A*′,*B*′,*B*∩*A*′,*B*∩*C*′,*A*–*B*,*A*Δ*B*

- (c) Complete the statement using a single symbol:
*C*-*B*= ... .

2

- True or false?

- (a) | ø | = 1

- (b) | { x, x } | = 2

- (c) |
**U**∩ ø | = 0

3

- What can you say about two sets
*P*and*Q*if:

- (a)
*P*∩*Q*′ = ø - (b)
*P*∪*Q*=*P*?

4

- Make six copies of the Venn diagram shown alongside, and then shade the areas represented by:

- (a)
*A*′ ∪*B*

- (b)
*A*∩*B*′

- (c) (
*A*∩*B*) ′

- (d)
*A*′ ∪*B*′

- (e) (
*A*∪*B*) ′

- (f)
*A*′ ∩*B*′

5

- Identify the sets represented by each of the shaded areas below, using the set notation symbols ∩, ∪ and ′ only:

(a) | (b) |

(c) | (d) |

6

- (a) One of the shaded regions in question 5 represents the set
*A*–*B*. Identify which one it is, and hence write a definition of*A*–*B*using only symbols from the list ∩, ∪ and ′.

- (b) Again using one of your answers to question 5, write a definition of
*A*Δ*B*using only symbols from the list ∩, ∪ and ′. (There are two possibilities here – see if you can find them both!)

## Set Theory Exercise 4[edit]

1

- (a) If
*A*= {1, 2, 3, 4}, write down**P**(*A*) by listing its elements. What is the value of |**P**(*A*) |?

- (b) If |
*A*| = 5, what is the value of |**P**(*A*) |?

- (c) If |
*A*| = 10, what is the value of |**P**(*A*) |?

2

- Prove the following identities, stating carefully which of the set laws you are using at each stage of the proof.

- (a)
*B*∪ (ø ∩*A*) =*B*

- (b) (A ′ ∩
**U**) ′ =*A*

- (c) (C ∪
*A*) ∩ (*B*∪*A*) =*A*∪ (*B*∩ C)

- (d) (
*A*∩*B*) ∪ (*A*∩*B*' ) =*A*

- (e) (
*A*∩*B*) ∪ (*A*∪*B*' ) ′ =*B*

- (f)
*A*∩ (*A*∪*B*) =*A*

## Set Theory Exercise 5[edit]

1

*X*= {a, c} and*Y*= {a, b, e, f}.

- Write down the elements of:

- (a)
*X*×*Y*

- (b)
*Y*×*X*

- (c)
*X*^{2}(=*X*×*X*)

- (d) What could you say about two sets
*A*and*B*if*A*×*B*=*B*×*A*?

2

- A chess board’s 8 rows are labelled 1 to 8, and its 8 columns
*a*to*h*. Each square of the board is described by the ordered pair (column letter, row number).

- (a) A knight is positioned at (
*d*, 3). Write down its possible positions after a single move of the knight.

- (b) If
*R*= {1, 2, ..., 8},*C*= {*a*,*b*, ...,*h*}, and*P*= {coordinates of all squares on the chess board}, use set notation to express*P*in terms of*R*and*C*.

- (c) A rook is positioned at (
*g*, 2). If*T*= {2} and*G*= {g}, express its possible positions after one move of the rook in terms of*R*,*C*,*T*and*G*.

3

- In a certain programming language, all variable names have to be 3 characters long. The first character must be a letter from 'a' to 'z'; the others can be letters or digits from 0 to 9.

- If
*L*= {a, b, c, ... , z},*D*= {0, 1, 2, ..., 9}, and*V*= {permissible variable names}, use a Cartesian product to complete:

*V*= {*pqr*| (*p*,*q*,*r*) ∈ ... }

4

- It is believed that, for any sets
*A*,*B*and*C*,*A*× (*B*∩*C*) = (*A*×*B*) ∩ (*A*×*C*).

- (Note that, if this is true, it says that × is
*distributive*over ∩.)

- Copy and complete the two Cartesian diagrams shown below – one for the expression on each side of the equation – to investigate this.

- Do you think that the proposition is true?