Discrete Math Quiz: Cartesian Products And Power Sets

18 questions · exam conditions

0:00

Cartesian Products And Power SetsQuestion 1 of 18

Let $A = \{1, 2\}$ and $B = \{x, y, z\}$ . If $S$ is a subset of $A \times B$ such that for each element $a \in A$ , there exists exactly one element $b \in B$ with $(a, b) \in S$ , how many such subsets $S$ are possible?

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Cartesian Products And Power Sets

Practice Cartesian Products And Power Sets in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Cartesian Products And Power Sets, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

6
8
9 (correct answer)
12

Explanation: For each element in A, we must choose exactly one element from B to pair with it. For element 1, we have 3 choices from B. For element 2, we have 3 choices from B. Since these choices are independent, the total number of such subsets S is 3 × 3 = 9. Each subset S represents a function from A to B.

Question 2

Let $A = \{x, y\}$ . If $|\mathcal{P}(A \times A)| = 2^k$ for some positive integer $k$ , what is the value of $k$ ?

2
4 (correct answer)
8
16

Explanation: The Cartesian product A × A has |A|² = 2² = 4 elements: {(x,x), (x,y), (y,x), (y,y)}. The power set of any set with n elements has 2^n elements. Therefore, |𝒫(A × A)| = 2^4, so k = 4.

Question 3

Let $S = \{a, b, c\}$ . Consider the set $R = \{(X, Y) \in \mathcal{P}(S) \times \mathcal{P}(S) : X \cap Y = \emptyset \text{ and } X \cup Y = S\}$ . What is $|R|$ ?

6 (correct answer)
8
12
16

Explanation: We need pairs (X,Y) where X and Y are disjoint subsets of S whose union is S. This means X and Y form a partition of S into exactly 2 non-empty parts. For each element in S, it must belong to exactly one of X or Y. However, both X and Y must be non-empty. The number of ways to partition a 3-element set into 2 non-empty parts is given by Stirling number S(3,2) = 3. But we need ordered pairs, so each partition gives 2 ordered pairs (X,Y) and (Y,X). Therefore |R| = 2 × 3 = 6.

Question 4

Let $A = \{1, 2\}$ and $B = \{a, b, c\}$ . Consider the collection $\mathcal{C} = \{R \subseteq A \times B : \text{for each } x \in A, \text{ there exists at most one } y \in B \text{ such that } (x,y) \in R\}$ . What is $|\mathcal{C}|$ ?

12
16 (correct answer)
18
24

Explanation: For each element in A, we can either pair it with no element from B, or with exactly one element from B. For element 1: 4 choices (no pairing, or pair with a, b, or c). For element 2: 4 choices (no pairing, or pair with a, b, or c). These choices are independent, giving 4 × 4 = 16 total partial functions from A to B.

Question 5

Let $A = \{1, 2\}$ and $B = \{x, y, z\}$ . If $S$ is a subset of $A \times B$ such that for every element $a \in A$ , there exists exactly one element $b \in B$ with $(a, b) \in S$ , how many different sets $S$ are possible?

6
8
9 (correct answer)
12

Explanation: Since S must contain exactly one ordered pair for each element of A, and |A| = 2, S must contain exactly 2 ordered pairs. For element 1 ∈ A, we can choose any of the 3 elements in B, giving 3 choices. For element 2 ∈ A, we can independently choose any of the 3 elements in B, giving 3 more choices. By the multiplication principle, there are 3 × 3 = 9 possible sets S. Choice A (6) incorrectly assumes we cannot repeat elements from B. Choice B (8) might result from miscounting or confusing this with a different combinatorial problem. Choice D (12) incorrectly counts ordered arrangements rather than sets.

Question 6

Let $A = \{1, 2\}$ and $B = \{x, y\}$ . Consider the set $T = \mathcal{P}(A \times B)$ . How many elements of $T$ contain exactly two ordered pairs that share the same first coordinate?

4
6 (correct answer)
8
10

Explanation: First, A × B = {(1,x), (1,y), (2,x), (2,y)}. We need subsets containing exactly two ordered pairs that share the same first coordinate. This means exactly one first coordinate value appears exactly twice. Case 1: Subsets containing both (1,x) and (1,y), but no pairs with first coordinate 2: {(1,x), (1,y)}. Case 2: Subsets containing both (2,x) and (2,y), but no pairs with first coordinate 1: {(2,x), (2,y)}. Case 3: Subsets containing both (1,x) and (1,y), plus exactly one pair with first coordinate 2: {(1,x), (1,y), (2,x)} and {(1,x), (1,y), (2,y)}. Case 4: Subsets containing both (2,x) and (2,y), plus exactly one pair with first coordinate 1: {(2,x), (2,y), (1,x)} and {(2,x), (2,y), (1,y)}. Total: 1 + 1 + 2 + 2 = 6 subsets.

Question 7

Let $A = \{1, 2\}$ and $B = \{3, 4\}$ . Consider the set $S = (A \times B) \cup (B \times A)$ . How many elements are in the power set of $S$ ?

64
128
256 (correct answer)
512

Explanation: First, A × B = {(1,3), (1,4), (2,3), (2,4)} and B × A = {(3,1), (3,2), (4,1), (4,2)}. These sets are disjoint since the first coordinates come from different sets. Therefore S = (A × B) ∪ (B × A) has |A × B| + |B × A| = 4 + 4 = 8 elements. The power set of S has 2^8 = 256 elements.

Question 8

Let $A = \{1, 2, 3\}$ . Consider the set $T = \{(x, y) \in A \times A : x + y \text{ is even}\}$ . What is $|\mathcal{P}(T)|$ , where $\mathcal{P}(T)$ denotes the power set of $T$ ?

16
32 (correct answer)
64
128

Explanation: First, we find T by identifying pairs (x,y) where x + y is even. This happens when both x and y are odd or both are even. From A = {1,2,3}: odd pairs give (1,1), (1,3), (3,1), (3,3); even pairs give (2,2). So T = {(1,1), (1,3), (2,2), (3,1), (3,3)}, which has 5 elements. Therefore |𝒫(T)| = 2^5 = 32.

Question 9

Consider sets $M = \{p, q\}$ and $N = \{r, s, t\}$ . Let $K = (M \times N) \times M$ . Which of the following statements about the power set $\mathcal{P}(K)$ is true?

$|\mathcal{P}(K)| = 2^{18}$ because of separate power set calculations
$|\mathcal{P}(K)| = 2^{10}$ because of the nested Cartesian product structure
$|\mathcal{P}(K)| = 2^{8}$ because $|M \times N| = 6$ and $|M| = 2$
$|\mathcal{P}(K)| = 2^{12}$ because $K$ has 12 elements (correct answer)

Explanation: When you encounter questions about power sets and Cartesian products, you need to carefully work through the cardinality calculations step by step, being especially mindful of how nested operations affect the final count. To find

|\mathcal{P}(K)|

, you first need to determine

|K|

. Since

K = (M \times N) \times M

, start with the innermost operation:

|M \times N| = |M| \cdot |N| = 2 \cdot 3 = 6

. The set

M \times N

contains 6 ordered pairs:

\{(p,r), (p,s), (p,t), (q,r), (q,s), (q,t)\}

. Next,

K = (M \times N) \times M

means you're taking the Cartesian product of this 6-element set with the 2-element set

M

. Therefore,

|K| = |M \times N| \cdot |M| = 6 \cdot 2 = 12

. The power set of any set with

n

elements has

2^n

elements, so

|\mathcal{P}(K)| = 2^{12}

. Option A incorrectly suggests

2^{18}

, likely from miscounting or confusing the structure of nested operations. Option B gives

2^{10}

, which might stem from incorrectly calculating

|K|

as 10 instead of 12. Option C arrives at

2^8

, apparently by adding

|M \times N| + |M| = 6 + 2 = 8

rather than multiplying for the Cartesian product. Remember: for Cartesian products, always multiply cardinalities, and for power sets, the formula

|\mathcal{P}(S)| = 2^{|S|}

is your key tool. Work systematically from the inside out when dealing with nested operations.

Question 10

Given sets $U = \{p, q\}$ and $V = \{r, s\}$ , let $W = \mathcal{P}(U) \times V$ , where $\mathcal{P}(U)$ is the power set of $U$ . Which element is NOT in $W$ ?

$(\{p, q\}, r)$
$(\{p\}, s)$
$(\emptyset, r)$
$(\{p, q, r\}, s)$ (correct answer)

Explanation: The power set 𝒫(U) = {∅, {p}, {q}, {p,q}}. The Cartesian product W = 𝒫(U) × V contains ordered pairs where the first component is a subset of U and the second component is an element of V. Since {p,q,r} is not a subset of U = {p,q} (it contains r which is not in U), the pair ({p,q,r}, s) cannot be in W.

Question 11

Given finite sets $P$ and $Q$ where $|P| = 3$ and $|Q| = 2$ , let $T = \{S \in \mathcal{P}(P \times Q) : |S| \leq 2\}$ . What is $|T|$ ?

22 (correct answer)
28
36
42

Explanation: The set P × Q has |P| × |Q| = 3 × 2 = 6 elements. We want subsets S of P × Q with |S| ≤ 2, so |S| ∈ {0, 1, 2}. The number of such subsets is C(6,0) + C(6,1) + C(6,2) = 1 + 6 + 15 = 22.

Question 12

Consider sets $X = \{1, 2, 3\}$ and $Y = \{a, b\}$ . Let $Z = X \times \mathcal{P}(Y)$ , where $\mathcal{P}(Y)$ is the power set of $Y$ . Which of the following correctly describes $|Z|$ ?

$|Z| = 6$ because $X$ has 3 elements and $Y$ has 2 elements
$|Z| = 8$ because $\mathcal{P}(Y)$ has 4 elements and we need 2 coordinates
$|Z| = 12$ because $X$ has 3 elements and $\mathcal{P}(Y)$ has 4 elements (correct answer)
$|Z| = 32$ because we take the power set after forming the Cartesian product

Explanation: The power set 𝒫(Y) = {∅, {a}, {b}, {a,b}} has 2^2 = 4 elements. The Cartesian product Z = X × 𝒫(Y) pairs each element of X with each element of 𝒫(Y), giving |Z| = |X| × |𝒫(Y)| = 3 × 4 = 12 elements.

Question 13

Consider sets $X = \{a, b\}$ and $Y = \{1, 2, 3\}$ . Let $P$ be the power set of $X \times Y$ . Which of the following statements about $|P|$ is correct?

$|P| = 3^{2}$ because Y has 3 elements and X has 2 elements
$|P| = 6^{2}$ because we can choose any subset of Y for each element of X
$|P| = 2^{5}$ because there are 5 non-empty subsets of $X \times Y$
$|P| = 2^{6}$ because $X \times Y$ has 6 elements (correct answer)

Explanation: When you encounter questions about power sets, remember that the power set of any set

S

contains

2^{|S|}

elements, where

|S|

is the cardinality of

S

. The key is first determining how many elements are in the original set. To find

|P|

, you need to determine

|X \times Y|

first. The Cartesian product

X \times Y

consists of all ordered pairs

(x,y)

where

x \in X

and

y \in Y

. Since

X = \{a, b\}

and

Y = \{1, 2, 3\}

, we have:

X \times Y = \{(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)\}

This gives us

|X \times Y| = |X| \times |Y| = 2 \times 3 = 6

elements. Therefore, the power set

P

has

|P| = 2^6 = 64

elements. Choice A incorrectly applies

3^2

, perhaps confusing the formula for Cartesian products with power sets. Choice B uses

6^2

, which has no basis in set theory—this might stem from mistakenly thinking about functions from

X

Y

. Choice C claims

2^5

based on counting only non-empty subsets, but power sets always include the empty set, and the exponent should match the cardinality of the original set, not the number of its non-empty subsets. Remember this pattern: for any power set question, count the elements in the original set first, then apply

2^n

. The power set formula is fundamental and appears frequently in discrete math problems.

Question 14

Let $A = \{1, 2\}$ and $B = \{3, 4, 5\}$ . Define $H = \{(a, S) : a \in A, S \in \mathcal{P}(B), a + |S| \text{ is odd}\}$ . What is $|H|$ ?

8 (correct answer)
10
12
16

Explanation: The power set 𝒫(B) has 2³ = 8 elements with cardinalities: 1 empty set (|S| = 0), 3 singletons (|S| = 1), 3 two-element sets (|S| = 2), and 1 three-element set (|S| = 3). For a + |S| to be odd: if a = 1 (odd), we need |S| even, so |S| ∈ {0,2}: 1 + 3 = 4 choices. If a = 2 (even), we need |S| odd, so |S| ∈ {1,3}: 3 + 1 = 4 choices. Total: 4 + 4 = 8.

Question 15

Let $A = \{1, 2, 3\}$ and consider the power set $\mathcal{P}(A)$ . How many ordered pairs $(X, Y)$ exist such that $X, Y \in \mathcal{P}(A)$ and $X \cap Y = \{2\}$ ?

9 (correct answer)
12
15
16

Explanation: For X ∩ Y = {2}, both X and Y must contain 2, and any element in both X and Y must be 2. This means elements 1 and 3 can each be: (i) in X only, (ii) in Y only, or (iii) in neither X nor Y. For each of elements 1 and 3, there are 3 independent choices, giving 3 × 3 = 9 total ordered pairs. Choice B (12) might result from incorrectly counting cases where elements can be in both sets. Choice C (15) could come from a systematic overcounting error. Choice D (16) might result from considering all possible intersections without the constraint.

Question 16

Given sets $A = \{a, b\}$ and $B = \{1, 2, 3\}$ , let $R \subseteq A \times B$ and $S \subseteq B \times A$ . If $|R| = 3$ and $|S| = 4$ , what is $|R \times S|$ ?

7
12 (correct answer)
24
72

Explanation: R × S is the Cartesian product of sets R and S, where each element is an ordered pair ((x,y), (z,w)) with (x,y) ∈ R and (z,w) ∈ S. Since |R| = 3 and |S| = 4, we have |R × S| = |R| × |S| = 3 × 4 = 12. Choice A (7) incorrectly adds the cardinalities instead of multiplying. Choice C (24) might result from confusing this with |A × B| × 2 or similar miscalculation. Choice D (72) appears to use |A × B| × |B × A| = 6 × 6 × 2, which is irrelevant to the actual question.

Question 17

Let $A = \{1, 2\}$ . Consider the set $\mathcal{P}(\mathcal{P}(A))$ . How many elements $X \in \mathcal{P}(\mathcal{P}(A))$ satisfy $\emptyset \in X$ and $A \in X$ ?

2
4 (correct answer)
8
16

Explanation: First, P(A) = P({1,2}) = {∅, {1}, {2}, {1,2}}. So |P(A)| = 4. Then P(P(A)) consists of all subsets of P(A), so |P(P(A))| = 2⁴ = 16. We need elements X ∈ P(P(A)) such that ∅ ∈ X and A ∈ X. Since A = {1,2}, this means X must contain both ∅ and {1,2}. The remaining elements of P(A) are {1} and {2}. For each of these, X can either contain it or not contain it. This gives us 2² = 4 possibilities: X can be {∅, {1,2}}, {∅, {1}, {1,2}}, {∅, {2}, {1,2}}, or {∅, {1}, {2}, {1,2}}. Choice A (2) might incorrectly consider only the minimum case. Choice C (8) might result from a different constraint interpretation. Choice D (16) would be all elements of P(P(A)), ignoring the constraints.

Question 18

Let $A = \{a, b\}$ and $B = \{1, 2, 3\}$ . Define the relation $R = \{((x,y), z) : (x,y) \in A \times A \text{ and } z \in B \text{ and } x \neq y\}$ . What is $|R|$ ?

4
6 (correct answer)
9
12

Explanation: R consists of ordered pairs ((x,y), z) where (x,y) ∈ A × A with x ≠ y, and z ∈ B. First, we find all (x,y) ∈ A × A with x ≠ y. Since A × A = {(a,a), (a,b), (b,a), (b,b)}, the pairs with x ≠ y are (a,b) and (b,a). So there are 2 such pairs. For each of these 2 pairs (x,y), z can be any element of B = {1, 2, 3}, giving 3 choices for z. Therefore, |R| = 2 × 3 = 6. Choice A (4) might incorrectly exclude some valid combinations. Choice C (9) might mistakenly count all of A × A (which has 4 elements) but make an error. Choice D (12) might incorrectly include all pairs from A × A without the constraint x ≠ y.