- Foundation
- About 16 min
- 5 practice questions
Cartesian products and relations
Form ordered pairs and Cartesian products, count them with n(A × B) = pq, describe a relation by its domain, codomain and range, and test reflexive, symmetric and transitive.
If something looks wrong, please tell us.
A set on its own has no order: {1, 2} and {2, 1} are the same. Yet many ideas need order, such as a point (2, 3) on a graph or the pairing of each student with a roll number. This lesson introduces ordered pairs, builds the Cartesian product of two sets and then defines a relation, which is simply a chosen set of ordered pairs. Relations lead directly to functions in the next part of the course.
Ordered pairs
An ordered pair (a, b) has a first entry a and a second entry b, and the order matters: (2, 3) and (3, 2) are different. Two ordered pairs are equal only when their first entries are equal and their second entries are equal: (a, b) = (c, d) means a = c and b = d.
The Cartesian product
The Cartesian product A × B is the set of all ordered pairs whose first entry comes from A and second entry from B: A × B = {(a, b) : a ∈ A, b ∈ B}. If n(A) = p and n(B) = q, each of the p first entries pairs with each of the q second entries, so n(A × B) = pq. In general A × B ≠ B × A, because the pairs are reversed. If either set is empty, the product is empty.
Worked example 1: a product and its size
Let A = {1, 2} and B = {x, y, z}. Then A × B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}, which has 2 × 3 = 6 pairs. B × A = {(x, 1), (x, 2), (y, 1), (y, 2), (z, 1), (z, 2)} also has 6 pairs, but they are different pairs, so A × B ≠ B × A.
Worked example 2: equal ordered pairs
Find x and y if (x + 1, y − 2) = (3, 1). Equate first entries: x + 1 = 3, so x = 2. Equate second entries: y − 2 = 1, so y = 3. Always write two separate equations, one for each position.
Relations
A relation R from A to B is any subset of A × B. If (a, b) ∈ R we say a is related to b. The domain of R is the set of first entries that actually appear, the range is the set of second entries that actually appear, and the codomain is the whole of B. The range is always a subset of the codomain. Since a relation is any subset of A × B and A × B has pq elements, the number of relations from A to B is 2^(pq). This count includes the empty relation and the whole of A × B.
Worked example 3: domain and range
Let A = {1, 2, 3, 4}, B = {1, 2, 3, 4, 5, 6} and R = {(a, b) : a ∈ A, b ∈ B, b = a + 2}. Go through A: 1 gives 3, 2 gives 4, 3 gives 5 and 4 gives 6. So R = {(1, 3), (2, 4), (3, 5), (4, 6)}. Domain = {1, 2, 3, 4}, range = {3, 4, 5, 6} and codomain = B. The elements 1 and 2 of B are in the codomain but not in the range.
Relations on one set
A relation from A to A is called a relation on A. Three properties are tested: R is reflexive if (a, a) ∈ R for every a in A; symmetric if whenever (a, b) ∈ R, also (b, a) ∈ R; and transitive if whenever (a, b) ∈ R and (b, c) ∈ R, also (a, c) ∈ R. A relation with all three properties is an equivalence relation. For example, on A = {1, 2, 3}, the relation {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} contains every (a, a), contains (2, 1) with (1, 2), and every chain closes: (1, 2) with (2, 1) needs (1, 1), and (2, 1) with (1, 2) needs (2, 2), both present. So it is an equivalence relation.
n(A × B) = n(A) × n(B). With n(A) = p and n(B) = q there are 2^(pq) relations from A to B. Range ⊆ codomain.
Key takeaways
Order matters in a pair, so A × B and B × A differ. A relation is a subset of A × B; its domain and range are read off the pairs that actually occur. Reflexive needs every (a, a), symmetric needs every reverse pair, and transitive needs every chain to close. All three together make an equivalence relation.
Check your understanding
-
1. If n(A) = 3 and n(B) = 4, how many elements does A × B have?
- 7
- 64
- 12
- 81
Show answer
Answer: C. Each of the 3 elements of A pairs with each of the 4 elements of B: 3 × 4 = 12.
-
2. If n(A) = 2 and n(B) = 3, how many relations are there from A to B?
- 64
- 6
- 8
- 32
Show answer
Answer: A. n(A × B) = 6, and every subset of A × B is a relation, so there are 2^6 = 64.
-
3. If (2a − 1, b + 3) = (5, 7), what are a and b?
- a = 2, b = 4
- a = 3, b = 10
- a = 3, b = 4
- a = 4, b = 3
Show answer
Answer: C. 2a − 1 = 5 gives a = 3; b + 3 = 7 gives b = 4.
-
4. What is the range of the relation R = {(1, 2), (2, 3), (3, 4)}?
- {1, 2, 3}
- {1, 2, 3, 4}
- {1, 4}
- {2, 3, 4}
Show answer
Answer: D. The range is the set of second entries: 2, 3 and 4.
-
5. On A = {1, 2, 3}, the relation R = {(1, 1), (2, 2), (3, 3), (1, 2)} is
- reflexive, symmetric and transitive
- symmetric but not reflexive
- reflexive and transitive but not symmetric
- neither reflexive nor transitive
Show answer
Answer: C. Every (a, a) is present, so R is reflexive. (1, 2) is present but (2, 1) is not, so it is not symmetric. The only chains are (1, 1) then (1, 2) and (1, 2) then (2, 2), both giving (1, 2), which is present, so it is transitive.
Sign in to keep track of the lessons you finish.