Cartesian product and power set
Pairs and n-tuples, the Cartesian product A × B and Aⁿ, the power set P(E), partitions of a set, with their cardinalities and the encoding of a subset as a bit vector.
- 24 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Pair and n-tuple: what is it?
Show the answer
An ordered list of 2 (or n) elements, where order and repeats matter: (1, 2) differs from (2, 1), and (1, 1) exists.
A set ignores order and duplicates: {1, 2} = {2, 1} = {1, 2, 2}. Round brackets mark an object where position matters.
What is the power set of E = {a, b}?
{∅, {a}, {b}, {a, b}}{{a}, {b}}{∅, a, b, {a, b}}{∅, {a}, {b}}
Show the answer
{∅, {a}, {b}, {a, b}}It needs ∅ and E itself, and sets rather than elements: {a} is a subset, a is an element of E. There are 2² = 4.
The Cartesian product A × B contains … pairs.
Show the answer
The Cartesian product A × B contains |A| × |B| pairs.
Each element of A pairs with each element of B. For Aⁿ, there are |A|ⁿ n-tuples.
Cartesian product: what is it?
Show the answer
The set of all pairs (a, b) with a in A and b in B, written A × B; its cardinality is |A| × |B|.
With A = {1, 2} and B = {x, y, z}, there are 2 × 3 = 6 pairs. A × B and B × A have the same cardinality but are not equal.