Problems on sets

This les­son brings together the ideas of the chap­ter so far in a set of prob­lems of the kind found in com­pet­i­tive exam­i­na­tions: sets of mul­ti­ples, sets defined by a for­mula, count­ing sub­sets, and sim­pli­fy­ing set expres­sions. In most of them the quick­est route is to write out the first few ele­ments of each set and look for the pat­tern.

Sets of mul­ti­ples#

For a nat­ural num­ber $a$, write $aN = \{ax : x \in N\}$, the set of all pos­i­tive mul­ti­ples of $a$. So $aN = \{a, 2a, 3a, 4a, \ldots\}$.

Exam­ple 1#

Find $3N \cap 7N$.

$$3N = \{3, 6, 9, 12, 15, 18, 21, \ldots\}, \qquad 7N = \{7, 14, 21, 28, 35, 42, \ldots\}$$

The com­mon ele­ments are the num­bers that are mul­ti­ples of both 3 and 7, that is, mul­ti­ples of 21:

$$3N \cap 7N = \{21, 42, 63, \ldots\} = 21N$$

Exam­ple 2#

If $bN \cap cN = dN$, where $b, c \in N$ are rel­a­tively prime, express $d$ in terms of $b$ and $c$.

Two num­bers are rel­a­tively prime (or coprime) if their H.C.F. is 1, for exam­ple $(2, 3)$, $(3, 5)$, $(7, 10)$, $(5, 7)$ and $(7, 9)$. They need not be prime them­selves: 7 and 10 are coprime though 10 is not prime. (Do not con­fuse this with twin primes: two primes whose dif­fer­ence is 2, such as $(3, 5)$ and $(5, 7)$.)

Try $b = 2$ and $c = 3$: $2N = \{2, 4, 6, 8, 10, 12, \ldots\}$ and $3N = \{3, 6, 9, 12, \ldots\}$, so $2N \cap 3N = \{6, 12, 18, \ldots\} = 6N$. Here $d = 6 = 2 \times 3$.

In gen­eral, $bN \cap cN$ is the set of com­mon mul­ti­ples of $b$ and $c$, which is the set of mul­ti­ples of their L.C.M. For coprime num­bers the L.C.M. is the prod­uct, so $d = bc$.

If $b$ and $c$ are not coprime, $d$ is their L.C.M. For exam­ple $4N \cap 6N = 12N$, not $24N$.

Sets defined by a for­mula#

Exam­ple 3#

If $A = \{8^n - 7n - 1 : n \in N\}$ and $B = \{49(n - 1) : n \in N\}$, which is true: $A \subset B$, $B \subset A$, or $A = B$?

Write out the first few ele­ments.

For $A$: $n = 1$ gives $8 - 7 - 1 = 0$; $n = 2$ gives $64 - 14 - 1 = 49$; $n = 3$ gives $512 - 21 - 1 = 490$. So $A = \{0, 49, 490, \ldots\}$.

For $B$: the ele­ments are $0, 49, 98, 147, \ldots$, all the mul­ti­ples of 49 start­ing from 0.

Every ele­ment of $A$ seen so far is a mul­ti­ple of 49, and this is true for every $n$. (It can be proved by induc­tion: assume $8^k - 7k - 1 = 49q$; then $8^{k+1} - 7(k + 1) - 1 = 8(8^k - 7k - 1) + 49k = 49(8q + k)$.) So $A \subseteq B$. But $98 \in B$ and $98 \notin A$, because the ele­ments of $A$ jump from 49 to 490. Hence $A \subset B$, a proper sub­set.

Exam­ple 4#

If $A$ is the set of divi­sors of 15, $B$ is the set of prime num­bers smaller than 10, and $C$ is the set of even num­bers smaller than 9, find $(A \cup C) \cap B$.

$$A = \{1, 3, 5, 15\}, \quad B = \{2, 3, 5, 7\}, \quad C = \{2, 4, 6, 8\}$$

$A \cup C = \{1, 2, 3, 4, 5, 6, 8, 15\}$, and its inter­sec­tion with $B$ is $\{2, 3, 5\}$.

Count­ing sub­sets#

Exam­ple 5#

Two finite sets have $m$ and $n$ ele­ments. The total num­ber of sub­sets of the first set is 56 more than the total num­ber of sub­sets of the sec­ond. Find $m$ and $n$.

The first set has $2^m$ sub­sets and the sec­ond $2^n$, so

$$2^m - 2^n = 56$$

Look at the pow­ers of 2: $1, 2, 4, 8, 16, 32, 64, 128, \ldots$ The only two whose dif­fer­ence is 56 are 64 and 8. So $2^m = 64$ and $2^n = 8$, giv­ing $m = 6$ and $n = 3$.

Check: $64 = 56 + 8$.

Exam­ple 6#

A set $A$ has 4 ele­ments, one of which is the num­ber 1. How many sub­sets of $A$ con­tain the ele­ment 1?

A sub­set that con­tains 1 is fixed by decid­ing, for each of the other 3 ele­ments, whether it is in or out. That gives $2^3 = 8$ sub­sets. They are exactly half of all the $2^4 = 16$ sub­sets of $A$; the other 8 do not con­tain 1.

Sim­pli­fy­ing set expres­sions#

Exam­ple 7#

Sim­plify $A \cap (A \cup B)'$.

$(A \cup B)'$ is every­thing out­side both cir­cles. Noth­ing out­side both cir­cles can be inside $A$. So $A \cap (A \cup B)' = \phi$.

By the laws: $A \cap (A \cup B)' = A \cap (A' \cap B') = (A \cap A') \cap B' = \phi \cap B' = \phi$.

Exam­ple 8#

Sim­plify $(A - B) \cup (A \cap B)$.

$A - B$ is the "$A$ only" region and $A \cap B$ is the over­lap. Together they make up the whole of cir­cle $A$. So the expres­sion equals $A$.

Prac­tice#

1. Find $4N \cap 6N$.
2. Find $5N \cap 7N$ and $2N \cap 4N$.
3. Which of these pairs are coprime: $(8, 15)$, $(12, 18)$, $(9, 28)$?
4. If $A = \{4^n - 3n - 1 : n \in N\}$ and $B = \{9(n - 1) : n \in N\}$, write the first three ele­ments of each and decide whether $A \subset B$.
5. If $A$ is the set of fac­tors of 20, $B$ the set of prime num­bers less than 12, and $C$ the set of odd num­bers less than 10, find $(A \cap B) \cup C$.
6. The num­ber of sub­sets of a set with $m$ ele­ments is 112 more than the num­ber of sub­sets of a set with $n$ ele­ments. Find $m$ and $n$.
7. A set has 5 ele­ments. How many of its sub­sets have exactly 2 ele­ments? (List or count them.)
8. Sim­plify $(A \cup B) \cap (A \cup B)'$.
9. Sim­plify $B \cup (A - B)$.
10. Sim­plify $(A \cap B') \cup (A' \cap B) \cup (A \cap B)$.

Answers#