Cartesian products and relations

Start with two choices in a stated order

A drink order chooses a drink and then a size. If the drinks are tea and water, and the sizes are small and large, the four possibilities are (tea, small), (tea, large), (water, small) and (water, large). The first entry tells you the drink; the second tells you the size. Swapping them changes their roles.

We will organise similar choices with short labels: A = {1, 2} and B = {a, b, c}. The symbols could label two time slots and three rooms. They need not be numbers on a measured axis. Each choice from A can be paired with each choice from B unless a later rule excludes a combination.

You need to read element membership and distinguish a set from one of its elements. A set lists each distinct element once: {1, 2, 1} = {1, 2}, and ∅ is the set with no elements. The notation x ∈ A means x is an element of A. The notation R ⊆ P means every element of R belongs to P. These conventions are used below rather than assumed from the chapter’s order.

On a first reading, work through the finite grid, the three-arrow relation and the two-stage path table. The preparation links can help with ordered coordinates and the language of domain and range. Return to the final identities after you can explain what “there exists a middle element” means; their short proofs use that idea rather than a new calculation technique. The later lessons on equivalence, order and mappings build on these definitions, but are not needed to begin here.

An ordered pair keeps both entries in their roles

For ordered pairs, (u, v) = (x, y) exactly when u = x and v = y. Thus (1, 2) ≠ (2, 1), even though the unordered sets {1, 2} and {2, 1} are equal. Braces describe a set; parentheses here describe a pair. Repeating an entry is allowed: (1, 1) is a pair, while {1, 1} is just the one-element set {1}.

The entries may themselves be letters, sets or other objects. Their roles still matter. The pair ({1, 2}, 3) has a set as its first entry and a number as its second; it is not the three-element set {1, 2, 3}. We use ordinary ordered pairs without needing a particular construction of pairs from sets.

A collection of ordered pairs is itself a set. Changing the order in which its pairs are listed does not change that collection, but reversing the entries inside a pair can change which element of the collection it is. Keep these two different kinds of order separate.

The Cartesian product contains every permitted combination

For sets A and B, their Cartesian product is A × B = {(a, b) : a ∈ A and b ∈ B}. The colon means “such that.” The first coordinate comes from the first factor A; the second comes from B. Membership in this product requires both conditions at the same time.

For A = {1, 2} and B = {a, b, c}, the product is {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}. The grid has one column for each first element and one row for each second element. Every cell is one possible pair. The complete table states the same six possibilities without requiring you to interpret a picture.

If A and B are finite with m and n distinct elements, each of the m first entries has n possible second entries. These m groups do not overlap, because different first entries make different pairs. Therefore |A × B| = mn, where |X| means the number of distinct elements of a finite set X. This finite counting formula does not treat an infinite size as an ordinary real number.

There is no requirement that the two factors be disjoint. For A = {1, 2}, A × A includes (1, 1), (1, 2), (2, 1) and (2, 2). The two unequal entries and the two equal-entry pairs are all allowed. The product is sometimes written A²; that notation means a set of pairs here, not squaring each element.

Factor order and empty sets change the possible pairs

In B × A the entries have reversed roles. With our disjoint labels, (a, 1) belongs to B × A but not A × B, so these products differ although both have six elements. Exchanging coordinates gives a one-to-one correspondence between the products; a correspondence does not make their pairs identical. The products can be equal in special cases, such as A = B or an empty factor, so “always unequal” would also be wrong.

If either factor is empty, no pair can satisfy both membership conditions: A × ∅ = ∅ and ∅ × B = ∅. This holds for finite or infinite A and B. For finite sets, the count also gives m × 0 = 0.

Do not confuse ∅ with {∅}. The set {∅} has one element, namely the empty set. If A = {1, 2}, then A × {∅} = {(1, ∅), (2, ∅)}, with two pairs; A × ∅ has none. A blank target column means there are no target elements, not that one target element is an empty set.

For products of three factors, write what the entries mean. An ordered triple (a, b, c) has three roles. A nested pair ((a, b), c) and a nested pair (a, (b, c)) can encode the same three choices through natural correspondences, but they are different pair structures. We keep two-factor products throughout this lesson.

A binary relation selects pairs from a declared product

A binary relation from A to B is a subset R ⊆ A × B. Writing a R b means (a, b) ∈ R. It is a statement about that ordered pair, not a multiplication of a and b. A relation on A means a relation from A to itself, so R ⊆ A × A.

Choose R = {(1, a), (1, b), (2, b)} inside our six-pair product. Its arrow diagram draws exactly 1 → a, 1 → b and 2 → b. Its grid selects exactly those three cells. Its pair table lists exactly those three pairs. The unused target c remains in the declared set B even though no arrow reaches it.

A relation may have no pairs, some pairs, or every pair of the product. The empty relation ∅ is a subset of every product. If the product itself is empty, ∅ is its only subset and therefore its only relation. In a nonempty finite product, every subset is a possible relation; any additional meaning such as “is scheduled in” must be specified separately.

The declared sets are part of the setting. The same pair list can be viewed inside different larger products, and its possible function or composition claims then need those declared sets. A proposed pair outside A × B is not an additional pair of a relation from A to B; it violates the stated type.

The actual domain and range collect the elements used

For R ⊆ A × B, define dom(R) = {a ∈ A : there exists b ∈ B with (a, b) ∈ R}, and ran(R) = {b ∈ B : there exists a ∈ A with (a, b) ∈ R}. The domain collects first entries that actually occur; the range collects second entries that actually occur. Consequently dom(R) ⊆ A and ran(R) ⊆ B, but either inclusion may be strict.

For the three-pair R, dom(R) = {1, 2} and ran(R) = {a, b}. The domain happens to equal A; the range does not equal B because c is unused. Removing the pair (2, b) leaves 2 in the declared source A but outside the new actual domain.

For an empty relation, both the actual domain and the actual range are empty, even if A and B are nonempty. An element without an arrow is not assigned a mysterious value: it simply contributes no pair. Throughout this lesson “declared source” means A and “actual domain” means dom(R), so those terms are not silently interchanged.

Being a function requires exactly one output per declared input

A function from A to B is a relation R ⊆ A × B for which every a ∈ A has exactly one b ∈ B with (a, b) ∈ R. “Exactly one” includes existence and uniqueness. Having at most one output is not enough when a declared input has none. Having at least one is not enough when an input has two different outputs.

Our three-pair R is not a function from A to B because 1 is paired with both a and b. The relation F = {(1, a), (2, b)} is a function from A to B, even though c remains unused. A function need not reach every element of its target. The relation P = {(1, a)} is a function from {1} to B, but not from the larger declared source {1, 2} to B.

The empty relation is a function from ∅ to any B: there is no source element that violates the requirement. From a nonempty A to ∅, no function exists, because any a ∈ A would need an output in a set with no elements. This explains the empty cases through the definition rather than through a drawing alone.

The converse reverses the ordered relationship

The converse of R ⊆ A × B is R⁻¹ = {(b, a) ∈ B × A : (a, b) ∈ R}. This superscript denotes the inverse relation, also called the converse; it is not a reciprocal number. Every arrow reverses, and the declared source and target exchange roles. Our R gives R⁻¹ = {(a, 1), (b, 1), (b, 2)}.

Reversing twice returns each original pair, so (R⁻¹)⁻¹ = R. First entries of the converse are precisely second entries of the original, giving dom(R⁻¹) = ran(R) and ran(R⁻¹) = dom(R). These identities hold for empty relations too.

A converse relation always exists, but it need not be an inverse function from B to A. For the function F = {(1, a), (2, b)} above, c has no output in F⁻¹, so its converse is not a function from all of B. If two inputs of a function share one output, its converse gives that output two possible returns. A function has a converse that is a function from the full target back to the full source exactly when every target element is reached once. Later mapping lessons name this a bijection; the pair condition already explains it here.

Compose by finding a complete two-arrow path

Let R ⊆ A × B and S ⊆ B × C. We use the convention S ∘ R for “R first, then S.” Define S ∘ R = {(a, c) ∈ A × C : there exists b ∈ B with (a, b) ∈ R and (b, c) ∈ S}. The same middle element b must satisfy both links. The result is a relation from A to C, not from A to B.

Keep R = {(1, a), (1, b), (2, b)} and take C = {x, y}, S = {(a, x), (b, x), (b, y)}. There are five paths: 1 → a → x, 1 → b → x, 1 → b → y, 2 → b → x and 2 → b → y. Their endpoint pairs give S ∘ R = {(1, x), (1, y), (2, x), (2, y)}.

Two paths reach (1, x), using middle witnesses a and b. The composite is a set of endpoint pairs, so that pair appears only once. One witness is enough for membership; every complete path can be retained separately to explain why the pair exists. Counting paths is a different question from counting pairs in the composite.

A first arrow without a following arrow creates no composite pair. If instead S = {(c, x)}, R never reaches c, so S ∘ R = ∅ although both relations are nonempty. If R or S is empty, the composite is empty. With an empty shared B, composition is defined but has no possible witness and is empty as well.

Some books write the composition in a different order. Always read its definition. Here the right-hand R acts first, matching the familiar convention for function composition, and the declared middle set B agrees on both sides. If one relation ends in B while the next starts in a different declared set D, first state an appropriate common setting or restriction before composing. The finite model rejects a mismatch instead of silently treating it as an empty result.

The definition extends beyond finite arrow diagrams

A relation does not require a finite pair list. For example, Q = {(u, v) ∈ ℝ × ℝ : v = u²} is a relation from the real numbers to the real numbers. Its actual domain is ℝ and its range is [0, ∞): every real square is nonnegative, and every nonnegative v has the input √v. A finite sample of its graph would not establish that complete domain or range.

The converse Q⁻¹ consists of (v, u) with v = u². Its actual domain is [0, ∞), its range is ℝ, and a positive first entry v has two outputs √v and −√v. At v = 0 the only output is zero; a negative first entry has none. Thus it is not a function from ℝ to ℝ, and it is not a function even from its actual nonnegative domain to ℝ.

Restrict Q’s original source and its declared target to [0, ∞), obtaining the square function from [0, ∞) to [0, ∞). Its converse then pairs each v ≥ 0 with the single nonnegative √v and is a function between those same nonnegative sets. Restricting only the original source while leaving its target ℝ would leave negative declared inputs in the converse without an output. These explicit source and target restrictions make the inverse function claim correct; they do not erase a negative root from the unrestricted relation.

A middle witness proves identities beyond the pictures

The identity relation on A is I_A = {(a, a) : a ∈ A}. It follows that R ∘ I_A = R and I_B ∘ R = R for R ⊆ A × B. In the first composition, an identity arrow fixes the source element before R; in the second, it fixes the target after R. The definitions retain all original pairs and introduce no others, including when a set is empty.

For R ⊆ A × B and S ⊆ B × C, (S ∘ R)⁻¹ = R⁻¹ ∘ S⁻¹. A pair (c, a) is in the left side exactly when some b satisfies a R b and b S c. Reversing those same links gives c S⁻¹ b and b R⁻¹ a, precisely membership in the right side. The order reverses along with the arrows.

Composition is associative when the types fit: for T ⊆ C × D, T ∘ (S ∘ R) = (T ∘ S) ∘ R. Both sides contain exactly the pairs (a, d) for which there exist b ∈ B and c ∈ C with a R b, b S c and c T d. Parentheses change which two links are combined first, but do not change the complete three-link path. This statement does not permit reversing the order of R, S and T.

These are element-by-element arguments for arbitrary sets. The finite diagrams provide useful checks and examples; they are not substitutes for the middle-witness reasoning when a relation is infinite. If the two nested existential choices are unfamiliar, return to this section after writing out the five finite paths and explaining why duplicate endpoint pairs appear only once.

Worked examples

Try it yourself

1. Are (2, 5) and (5, 2) equal? Are {2, 5} and {5, 2} equal? Explain both answers.

   Show the answer and reasoning

   The pairs are unequal, but the sets are equal.

   An ordered pair must have equal first entries and equal second entries. The first entries 2 and 5 differ. A set is determined by its elements without an order, and both sets contain exactly 2 and 5.

2. Let A = {1, 1, 2} and B = {p, q}. List A × B. Does (p, 1) belong?

   Show the answer and reasoning

   A × B = {(1, p), (1, q), (2, p), (2, q)} has four pairs. The pair (p, 1) does not belong.

   Repeated 1 is one set element, so |A| = 2 and |B| = 2. Product membership requires the first entry in A and the second in B. Here p ∉ A and 1 ∉ B.

3. For A = {r}, compare A × ∅ and A × {∅}.

   Show the answer and reasoning

   A × ∅ = ∅, while A × {∅} = {(r, ∅)}.

   The first target has no element to supply a second entry. The second target has one element, the empty set itself, so it supplies one valid second entry. The products therefore have zero and one elements respectively.

4. Let A = {1, 2, 3}, B = {u, v} and R = {(1, u), (2, u)}. Find dom(R), ran(R), and whether R is a function from A to B.

   Show the answer and reasoning

   dom(R) = {1, 2}, ran(R) = {u}, and R is not a function from A to B.

   Input 3 has no output, so the required existence for every declared input fails. It is a function from {1, 2} to B: sharing the output u is permitted, since each used input has exactly one output.

5. For R in the previous exercise, list R⁻¹ and decide whether it is a function from B to A.

   Show the answer and reasoning

   R⁻¹ = {(u, 1), (u, 2)}, and it is not a function from B to A.

   Swapping coordinates makes u have two outputs and v have no output. The converse relation is valid, but neither uniqueness at u nor existence at v satisfies the function requirement.

6. Let A = {1, 2}, B = {p, q}, C = {z}, R = {(1, p), (2, q)} and S = {(q, z)}. Find S ∘ R and justify every included pair.

   Show the answer and reasoning

   S ∘ R = {(2, z)}, established by the middle witness q.

   The complete path is 2 → q → z. The arrow 1 → p has no continuation in S, so it gives no composite pair. Being in the source does not guarantee an output in a general relation.

7. Let R = {(1, p), (1, q)} and S = {(p, z), (q, z)} in the matching products. How many complete paths and how many composite pairs are there?

   Show the answer and reasoning

   There are two paths but one composite pair, (1, z).

   The witnesses p and q give different two-arrow paths with identical endpoints. Membership in a set records (1, z) once. The existential condition asks for at least one witness, not exactly one.

8. Suppose R is declared from A to B and S from D to C, with B ≠ D. May the finite model silently use its S ∘ R rule with an empty answer?

   Show the answer and reasoning

   No. Its stated composition requires the same declared middle set; first specify a suitable common setting or restriction.

   A mismatch is a failure of this operation’s declared type, rather than evidence that there are no paths in a valid A-to-B-to-C setting. A general theory can define compatible common-universe compositions, but that is not a silently changed convention here.

9. For Q = {(u, v) ∈ ℝ² : v = u²}, list the outputs of first entries 4, 0 and −1 in Q⁻¹. What restriction makes the converse a square-root function?

   Show the answer and reasoning

   First entry 4 has outputs 2 and −2; 0 has only output 0; −1 has none. Restrict both the original source and its declared target to [0, ∞).

   The converse condition is v = u² with the entries swapped, so each second entry must be a real square root of the first. Restricting the original source to nonnegative u retains one root for each nonnegative first entry. Restricting the original target to [0, ∞) also excludes negative declared inputs from the converse. Together the restrictions give the square-root function from [0, ∞) to [0, ∞), including zero.

What to carry forward

• An ordered pair keeps two roles; a Cartesian product includes every combination allowed by its factors.
• A relation is a selected subset of a declared product. Its actual domain and range contain only the entries used by selected pairs.
• A function from A to B requires exactly one output for every a ∈ A; a general relation can have none or several.
• A converse swaps coordinates and types. It is always a relation but is not automatically an inverse function.
• S ∘ R means R first, then S in this lesson. A shared middle witness establishes a pair; multiple witnesses do not duplicate that pair.
• Empty factors, missing arrows and the declared middle set are part of the definitions, not details to fill in from a picture.