Cartesian Products and Relations
Cartesian Product For the sets A,B, the Cartesian product, or cross product, of A and B, denoted as A X B, is equal to the set {(a,b) | a ∈ A, b ∈ B}.
The elements of A X B are ordered pairs.
For (a,b), (c,d) ∈ A X B, (a,b) = (c,d) if and only if a = c and b = d.
If A,B are finite sets, then by the rule of product, the number of possible elements in A X B is |A X B| = |A||B|.
Although, in general, A X B ≠ B X A, it is true that |A X B| = |B X A|.
It can be such that A and B have different universes, such that A ⊆ 𝓤₁ and B ⊆ 𝓤₂, where 𝓤₁ ≠ 𝓤₂. Even if A and B have equal universes, where A,B ⊆ 𝓤, it does not mean A X B ⊆ 𝓤.
In general, for more than two sets, let n ∈ ℤ⁺, n ≥ 3. For the sets A₁, A₂, ..., An, the n-fold product of A₁, A₂, ..., An, denoted as A₁ X A₂ X ... X An is equal to the set {(a₁,a₂,...,an) | aᵢ ∈ A, 1 ≤ i ≤ n}.
The elements of A₁ X A₂ X ... X An are called ordered n-tuples. If n = 3, it is usually called a triple.
Just like with two sets, if (a₁,a₂,...,an), (b₁,b₂,...,bn) ∈ A₁ X A₂ X ... X An, then (a₁,a₂,...,an) = (b₁,b₂,...,bn) if and only if aᵢ = bᵢ for all 1 ≤ i ≤ n.
Example Let A = {2,3,4} and B = {4,5}. Then the following is true: A X B = {(2,4), (2,5), (3,4), (3,5), (4,4), (4,5)} B X A = {(4,2), (4,3), (4,4), (5,2), (5,3), (5,4)} B² = B X B = {(4,4), (4,5), (5,4), (5,5)} B³ = B X B X B = {(a,b,c) | a,b,c ∈ B}
Example The Cartesian product ℝ X ℝ = {(x,y) | x,y ∈ ℝ} is recognized as the real plane of coordinate geometry and two-dimensional calculus. The subset ℝ⁺ X ℝ⁺ consists of the first quadrant of this plane. ℝ³ = ℝ X ℝ X ℝ represents the Euclidean three-space.
Example Just as the previous example, let A = {2,3,4} and B = {4,5}. Now let C = {x,y}. The following tree diagram demonstrates A X B:
The following tree diagram demonstrates B X A:
The following tree diagram demonstrates A X B X C:
The above tree diagram confirms that |A X B X C| = |A||B||C| = 12.
Tree diagrams are examples of a general structure called a tree. Trees and graphs are structures used in computer science and optimization theory.
Relations For sets A,B, any subset of A X B is called a relation, or binary relation, from A to B, denoted as ℛ. Any subset of A X A is called a relation, or binary relation, on A.
Example Let A = {2,3,4} and B = {4,5}. The following are some relations from A to B: ∅ ∈ A X B {(2,4)} ∈ A X B {(2,4), (2,5)} ∈ A X B {(2,4), (3,4), (4,4)} ∈ A X B {(2,4), (3,4), (4,5)} ∈ A X B A X B ∈ A X B Since |A X B| = 6, then there are 2⁶ possible relations from A to B.
For finite sets A,B, there are a total of 2|AXB| = 2|A||B| relations from A to B, because relations from A to B are all possible subsets of A X B. Therefore, the cardinality of the power set of A X B is the number of relations from A to B.
Additionally, since |A X B| = |B X A|, then the number of relations from B to A is 2|BXA| = 2|B||A| = 2|A||B| = 2|AXB|. This is because relations from B to A consist of the ordered pairs in A X B but in reversed order for each element.
Example Let B = {1,2} and A = ℘(B) = {∅,{1},{2},{1,2}}. Then the following is an example of a relation on A: ℛ = A X A = A² = {(∅, ∅), (∅,{1}), (∅,{2}), (∅,{1,2}), ({1},{1}), ({1},{1,2}), ({2},{2}), ({2},{1,2}), ({1,2},{1,2})} Then ℛ is the subset relation, where (C,D) ∈ ℛ if and only if C,D ⊆ B and C ⊆ D.
Example Let A = ℤ⁺ and the relation ℛ is defined on set A as {(x,y) | x ≤ y}. This relation is a "less than or equal to" relation for the set of positive integers. It can be represented graphically as the set of points with positive integer components located on or above the line y = x in the Euclidean plane, such as the following:
The entire relation cannot be listed, but it can be noted that (7,7) ∈ ℛ and (7,11) ∃ ℛ, but (8,2) ∉ ℛ. This can also be written as 7 ℛ 7 and 7 ℛ 11, or 8 ℛ 2 (with a diagonal stroke on the ℛ).
Example Let ℛ be the subset of ℤ⁺ ⋃ {0} X ℤ⁺ ⋃ {0} where ℛ = {(m,n) | n = 7m}. Then the following are some ordered pairs in ℛ: (0,0), (1,7), (11,77), (15,105) This relation ℛ on ℤ⁺ ⋃ {0} can be defined recursively as the following: (1) (0,0) ∈ ℛ (2) If (s,t) ∈ ℛ, then (s + 1, t + 7) ∈ ℛ. Using the recursive definition to show that the ordered pair (3,21) from ℤ⁺ ⋃ {0} X ℤ⁺ ⋃ {0} is in ℛ. (0,0) ∈ ℛ => (0 + 1, 0 + 7) = (1,7) ∈ ℛ. (1,7) ∈ ℛ => (1 + 1, 7 + 7) = (2,14) ∈ ℛ. (2,14) ∈ ℛ => (2 + 1, 14 + 7) = (3,21) ∈ ℛ.
Observations 1. For any set A, A X ∅ = ∅ X A = ∅. If A X ∅ ≠ ∅, then let (a,b) ∈ A X ∅. Then a ∈ A and b ∈ ∅, which is impossible.
2. The following theorem demonstrates the relationship between the Cartesian product and the binary operations of union and intersection:
For any sets A,B,C ⊆ 𝓤: i) A X (B ⋂ C) = (A X B) ⋂ (A X C) ii) A X (B ⋃ C) = (A X B) ⋃ (A X C) iii) (A ⋂ B) X C = (A X C) ⋂ (B X C) iv) (A ⋃ B) X C = (A X C) ⋃ (B X C)
Example To prove that A X (B ⋂ C) = (A X B) ⋂ (A X C): Using the concept of set equality, for all a,b ∈ 𝓤, (a,b) ∈ A X (B ⋂ C) <=> a ∈ A and b ∈ B ⋂ C <=> a ∈ A and b ∈ B,C <=> a ∈ A, b ∈ B and a ∈ A and b ∈ C <=> (a,b) ∈ A X B and (a,b) ∈ A X C <=> (a,b) ∈ (A X B) ⋂ (A X C)
PDF reference: 273/915
A X B = {(1,2), (1,5), (2,2), (2,5), (3,2), (3,5), (4,2), (4,5)}
B X A = {(2,1), (5,1), (2,2), (5,2), (2,3), (5,3), (2,4), (5,4)}
A ⋃ (B X C) = {1,2,3,4} ⋃ {(2,3), (5,3), (2,4), (5,4), (2,7), (5,7)} = {1,2,3,4,(2,3), (5,3), (2,4), (5,4), (2,7), (5,7)}
(A ⋃ B) X C = ({1,2,3,4} ⋃ {2,5}) X {3,4,7} = {1,2,3,4,5} X {3,4,7} = {(1,3), (1,4), (1,7), (2,3), (2,4), (2,7), (3,3), (3,4), (3,7), (4,3), (4,4), (4,7), (5,3), (5,4), (5,7)}
(A X C) ⋃ (B X C) = {(1,3), (1,4), (1,7), (2,3), (2,4), (2,7), (3,3), (3,4), (3,7), (4,3), (4,4), (4,7)} ⋃ {(2,3), (5,3), (2,4), (5,4), (2,7), (5,7)} = {(1,3), (1,4), (1,7), (2,3), (2,4), (2,7), (3,3), (3,4), (3,7), (4,3), (4,4), (4,7), (5,3), (5,4), (5,7)}
a) |A X B| = (the number of choices of elements in A)(the number of choices of elements in B) = |A||B| = 9
b) number of relations from A to B = number of subsets of the power set of A X B = 2|AXB| = 2|A||B| = 2⁹
c) number of relations on A = number of subsets of the power set of A X A = 2|AXA| = 2|A||A| = 2⁹
d) number of relations from A to B that contain (1,2) and (1,5) = total number of relations – the number of subsets of the power set of {(1,2), (1,5)} = 2⁹ – 2² = 2⁷
e) number of relations from A to B that contain exactly 5 ordered pairs = the number of subsets of the total number of power sets of A X B that have 5 ordered pairs = C(9,5)
f) number of relations on A that contain at least 7 ordered pairs = the number of subsets of the total number of power sets of A X A that have 7 ordered pairs + the number of subsets of the total number of power sets of A X A that have 8 ordered pairs + the number of subsets of the total number of power sets of A X A that have 9 (because |A²| = 9) ordered pairs = C(9,7) + C(9,8) + C(9,9)
|P(A X B)| = 2|AXB| = 2|A||B| = 2²⁰
Class Example
Show that (A X B) X C ≠ A X (B X C) ≠ A X B X C.
Let A = {a,b,c}, B = {1,2,3,4}, and C = {red,blue}.
An example of (A X B) X C: (a,3) X C = ((a,3),red)
An example of A X (B X C): A X (4,blue) (c,(4,blue))
An example of A X B X C: (a,1,red)
Therefore, (A X B) X C ≠ A X (B X C), because there is an ordered pair in the first element of (A X B) X C and not for A X (B X C).
Additionally, neither equal A X B X C, because this is a 3-tuple (3 elements) while the others were an ordered pair (2 elements).
Quiz Question
Let A = {1,2,3}, B = {2,4,5}. a) Find two different elements of (A X B) X A. b) How many relations are there from A to B that contain exactly 5 ordered pairs?
a)
Examples:
((2,2),2) and ((2,2),1)
b)
|A X B| = |A||B| = 9
|{ℛ ⊆ A X B | |ℛ| = 5}| = C(9,5) = 126
