Clear Notion
Login

Concepts

Read through concept notes with worked explanations and diagrams, chapter by chapter.

Concept 03 / 10Sets, Relations and Functions

Cartesian Product and Relations: Domain, Range, Codomain and Counting

Ordered pairs and the Cartesian product A x B, why n(A x B) = mn and the product is not commutative, a relation as any subset of A x B, its domain, range and inverse, and counting relations as 2^(mn).

Figure 1
An ordered pair (a,b)(a, b) is a pair in which position matters: (a,b)=(c,d)(a, b) = (c, d) if and only if a=ca = c and b=db = d. So (1,2)≠(2,1)(1, 2) \neq (2, 1), whereas the sets {1,2}\{1, 2\} and {2,1}\{2, 1\} are equal. This one difference is the whole reason the Cartesian product exists. The Cartesian product of AA and BB is A×B={(a,b):a∈A,b∈B}A \times B = \{(a, b) : a \in A, b \in B\}, every ordered pair whose first entry comes from AA and second from BB. If n(A)=mn(A) = m and n(B)=nn(B) = n, each of the mm first entries pairs with each of the nn second entries, so n(A×B)=mnn(A \times B) = mn. The familiar coordinate plane is R×R=R2\mathbb{R} \times \mathbb{R} = \mathbb{R}^{2}, and R3\mathbb{R}^{3} is the set of ordered triples. Taking the product of AA with itself kk times gives n(Ak)=mkn(A^{k}) = m^{k}. Properties worth knowing. A×B≠B×AA \times B \neq B \times A in general; they are equal only if A=BA = B or one of the sets is empty. A×ϕ=ϕ×A=ϕA \times \phi = \phi \times A = \phi, because there is no second entry to choose. The product distributes over union, intersection and difference: A×(B∪C)=(A×B)∪(A×C)A \times (B \cup C) = (A \times B) \cup (A \times C), A×(B∩C)=(A×B)∩(A×C)A \times (B \cap C) = (A \times B) \cap (A \times C) and A×(B−C)=(A×B)−(A×C)A \times (B - C) = (A \times B) - (A \times C). A particularly neat identity is (A×B)∩(C×D)=(A∩C)×(B∩D)(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D): a pair lies in both products exactly when its first entry is in AA and CC and its second is in BB and DD. The same is not true for unions, which is a common trap: (A×B)∪(C×D)(A \times B) \cup (C \times D) is usually strictly smaller than (A∪C)×(B∪D)(A \cup C) \times (B \cup D). A relation RR from AA to BB is simply any subset of A×BA \times B. If (a,b)∈R(a, b) \in R we write aRba R b and say aa is related to bb. The definition is deliberately minimal: a relation is nothing more than the list of which pairs are related. A relation from AA to AA is called a relation on AA. The domain of RR is the set of first entries that actually appear, {a:(a,b)∈R}\{a : (a, b) \in R\}. The range is the set of second entries that actually appear. The codomain is the whole of BB. So range ⊆\subseteq codomain, and the distinction becomes central when we discuss onto functions. The arrow diagram shows A={1,2,3}A = \{1, 2, 3\}, B={a,b}B = \{a, b\} and R={(1,a),(1,b),(3,b)}R = \{(1, a), (1, b), (3, b)\}. The element 22 has no arrow, so it is not in the domain; 11 has two arrows, which is allowed for a relation (but not for a function). Counting relations. Since a relation is any subset of A×BA \times B, and A×BA \times B has mnmn elements, the number of relations from AA to BB is 2mn2^{mn}. This count includes the empty relation ϕ\phi (nothing related to anything) and the universal relation A×BA \times B (everything related to everything). On a single set with nn elements, n(A×A)=n2n(A \times A) = n^{2}, so there are 2n22^{n^{2}} relations. A relation required to contain kk specific pairs leaves mn−kmn - k pairs free, giving 2mn−k2^{mn - k} relations. The inverse relation reverses every pair: R−1={(b,a):(a,b)∈R}R^{-1} = \{(b, a) : (a, b) \in R\}. It is a relation from BB to AA, with domain of R−1R^{-1} equal to the range of RR and vice versa. Every relation has an inverse relation; this is different from functions, where an inverse function exists only under extra conditions. Key Takeaways: - (a,b)=(c,d)  ⟺  a=c(a, b) = (c, d) \iff a = c and b=db = d. - n(A×B)=n(A)⋅n(B)n(A \times B) = n(A) \cdot n(B); A×B=B×AA \times B = B \times A only if A=BA = B or one set is empty. - A×ϕ=ϕA \times \phi = \phi. - A×(B∩C)=(A×B)∩(A×C)A \times (B \cap C) = (A \times B) \cap (A \times C), and similarly for ∪\cup and −-. - (A×B)∩(C×D)=(A∩C)×(B∩D)(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D), but the analogous statement for ∪\cup is false. - A relation from AA to BB is any subset of A×BA \times B; there are 2mn2^{mn} of them, and 2n22^{n^{2}} on an nn-element set. - Range ⊆\subseteq codomain; the domain contains only elements that actually have a partner. - Pitfall: writing ϕ\phi instead of A×BA \times B for the universal relation, or forgetting that the empty relation counts. Brain-Teaser 1: A×BA \times B has 66 elements, three of which are (1,a)(1, a), (2,b)(2, b) and (3,a)(3, a). Find AA, BB and the remaining three elements. Solution: The first entries show {1,2,3}⊆A\{1, 2, 3\} \subseteq A and the second entries show {a,b}⊆B\{a, b\} \subseteq B, so n(A)≥3n(A) \ge 3 and n(B)≥2n(B) \ge 2. Since n(A)⋅n(B)=6n(A) \cdot n(B) = 6, the only possibility is n(A)=3n(A) = 3 and n(B)=2n(B) = 2. Therefore A={1,2,3}A = \{1, 2, 3\} and B={a,b}B = \{a, b\}, and the remaining elements are (1,b)(1, b), (2,a)(2, a) and (3,b)(3, b). The method is to use the known pairs to force lower bounds, then use the product formula to show the bounds are tight. Brain-Teaser 2: AA and BB have 9999 elements in common. How many elements does (A×B)∩(B×A)(A \times B) \cap (B \times A) have? Solution: Apply (A×B)∩(C×D)=(A∩C)×(B∩D)(A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) with C=BC = B and D=AD = A: (A×B)∩(B×A)=(A∩B)×(B∩A)=(A∩B)×(A∩B)(A \times B) \cap (B \times A) = (A \cap B) \times (B \cap A) = (A \cap B) \times (A \cap B). This has 99×99=980199 \times 99 = 9801 elements. In words, a pair (x,y)(x, y) lies in both products only when xx belongs to both sets and so does yy. The sizes of AA and BB separately do not matter. Brain-Teaser 3: Let n(A)=2n(A) = 2 and n(B)=3n(B) = 3. How many relations from AA to BB are there? How many are non-empty? How many contain a particular pair (a1,b1)(a_{1}, b_{1})? How many have domain equal to all of AA? Solution: A×BA \times B has 66 pairs, so there are 26=642^{6} = 64 relations, and 6363 of them are non-empty. Containing (a1,b1)(a_{1}, b_{1}) fixes one pair, leaving 25=322^{5} = 32. For the domain to be all of AA, each element of AA must have at least one partner. The partner set of a1a_{1} can be any non-empty subset of BB (23−1=72^{3} - 1 = 7 choices), and independently so can the partner set of a2a_{2}, giving 7×7=497 \times 7 = 49. Thinking of a relation as 'each element of AA picks a subset of BB' is often cleaner than thinking about the pairs one by one.

Practice this concept

Free · no account required · instant solutions

Cartesian Product and Relations: Domain, Range, Codomain and Counting — DPP

10 questionsSee the solution the moment you answer

Practice