Cartesian products and power sets - Discrete Math

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|$ ?
Answer: 6 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.
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$ ?
Answer: $(\{p, q, r\}, s)$ 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.
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}|$ ?
Answer: 16 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.
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$ ?
Answer: 256 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.
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|$ ?
Answer: 12 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.
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\}$ ?
Answer: 9 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.
Let $A = \{x, y\}$ . If $|\mathcal{P}(A \times A)| = 2^k$ for some positive integer $k$ , what is the value of $k$ ?
Answer: 4 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.
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?
Answer: $|P| = 2^{6}$ because $X \times Y$ has 6 elements 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$ to $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.
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?
Answer: 6 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.
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$ ?
Answer: 32 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.
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|$ ?
Answer: $|Z| = 12$ because $X$ has 3 elements and $\mathcal{P}(Y)$ has 4 elements 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.
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$ ?
Answer: 4 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.
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?
Answer: 9 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.
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?
Answer: $|\mathcal{P}(K)| = 2^{12}$ because $K$ has 12 elements 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.
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|$ ?
Answer: 22 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.
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?
Answer: 9 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.
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|$ ?
Answer: 8 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.
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|$ ?
Answer: 6 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.

Start this quiz