GCSE Link: None
A subset of a given larger set is one which is fully contained in the larger set.
That means that the set A is a subset of the set B if and only if every
element of A is also in B. "A is a subset of B" is
written with the notation A ⊆ B (note the similarity to the ≤ sign).
For example, {2, 3} ⊆
{1, 2, 3,
4, 5}.
The opposite of a subset is a superset: A is a superset of B if and only if
every element of B is also in A, i.e. if B is a subset
of A. The notation is A ⊇ B (similar to ≥). For
example, {1, 2, 3,
4, 5} ⊇ {2,
3}.
Note that any set is a subset and superset of itself. To exclude the set itself, we can use
proper subset/superset, where the larger set must contain all items of the smaller set and
more. The notation is A ⊂ B for a proper subset and A ⊃ B
for a proper superset (see the similarity with ≤ vs < and ≥ vs >?).
There are also a number of operations we can perform on two sets.
The set union of two sets contains every value that appears in either set.
The notation for this is A ∪ B (like a "U" for "Union"). For example,
{1, 2, 3} ∪
{3, 4, 5} is
{1, 2, 3,
4, 5} (note that we don't include the
3 twice because sets can't contain duplicates).
The set intersection of two sets contains any value that appears in both sets.
The notation for this is A ∩ B (the union symbol upside down). For example,
{1, 2, 3} ∩
{3, 4, 5} is
{3}.
The set difference of two sets contains any value that appears in the first set but not the second.
The notation for this is A - B (or alternatively A \ B). For example,
{1, 2, 3} -
{3, 4, 5} is
{1, 2}.
The Cartesian product of two sets is a set of all pairs where the first element comes from the first set and the second element comes from the second set.
It is written A × B. For example, {1,
2, 3} × {3,
4, 5} is {(1,3),
(1,4), (1,5),
(2,3), (2,4),
(2,5), (3,3),
(3,4), (3,5)}
Example 1 shows an example implementation of the Cartesian product in pseudo-code.
Example 1
SUBROUTINE CartesianProduct(a, b)
result ← {}
FOREACH x IN a
FOREACH y IN b
result.Add((x, y))
ENDFOR
ENDFOR
RETURN result
ENDSUBROUTINE
Evaluate the expression ({3, 1,
4} ∪ {3, 4,
5}) × ({1, 5,
9} \ {2, 6,
5}).
This simplifies to {1, 3,
4, 5} × {1,
9}, which is {(1,1),
(1,9), (3,1),
(3,9), (4,1),
(4,9), (5,1),
(5,9)}