SME
Discrete Mathematics · Problem type
Power set and Cartesian product sizes
Use this for “A has 3 elements and B has 4. How many subsets does A have, and how many ordered pairs are in A × B?”
Diagram
Row 3: 1, 3, 3, 1; they add to 2³ = 8.
This is an example. Type your own values to start a new problem.
|P(A)|
=
2
|A × B|
=
|A|
×
|B|
Formulas
|P(A)| = 2^|A|
8
=
2
3
|A × B| = |A| × |B|
12 = 3 × 4
Assumptions
•
Each element of A is in a subset or not, two choices each, so A has 2ⁿ subsets, counting ∅ and A itself.
•
A × B pairs every element of A with every element of B, so it has n × m ordered pairs.
•
Row n of Pascal’s triangle counts the subsets of each size; its entries add to 2ⁿ.
Step-by-step
WE KNOW
|A| = 3, |B| = 4
FIND
subsets of A (|P(A)|), ordered pairs (|A × B|)
Step 1 · Find subsets of A (|P(A)|)
Use |P(A)| = 2^|A|
Each of the n elements is either in the subset or out: 2 choices, n times.
|P(A)|
=
2
3
|P(A)| = 8
Step 2 · Find ordered pairs (|A × B|)
Use |A × B| = |A| × |B|
Each of the n first entries pairs with each of the m second entries.
|A × B| = 3 × 4
|A × B| = 12
Check
Put the numbers back in. Both sides should match.
8
=
2
3
✓
12 = 3 × 4 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.