Discrete Mathematics/Set theory/Exercises

Set Theory Exercise 1

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:

2x – 9 = 16.

(d) The collection of all integers x for which:

2x – 9 = 16.

(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 = 2n - 5, x and n are natural numbers}

(c) {y | 2y² = 50, y is an integer}

(d) {z | 3z = n², z and n are natural numbers}

Answers

Back to Set Theory

Set Theory Exercise 2

1

In A?	In B?	In C?
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

Answers

Back to Set Theory

Set Theory Exercise 3

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!)

Answers

Back to Set Theory

Set Theory Exercise 4

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

Answers

Back to Set Theory

Set Theory Exercise 5

1

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

Write down the elements of:

(a) X × Y

(b) Y × X

(c) X² (= 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?

Answers

Back to Set Theory