Cartesian products and relations: record which pairs are allowed

An ordered pair has a first coordinate and a second coordinate. Two pairs are equal precisely when their corresponding coordinates agree. Therefore exchanging the coordinates usually changes the pair, even though exchanging entries inside an ordinary two-element set does not change that set. If one coordinate names a teacher and the other a course, reversing them also changes the type of question being asked. Types help catch errors before a calculation starts.

The Cartesian product contains every allowed first coordinate paired with every allowed second coordinate. For finite factors its size is the product of their sizes because each first coordinate admits the full list of second coordinates. If either factor is empty, no pair can be formed and the product is empty. A product of three factors similarly records three positions, although one must specify whether nested pairs or triples are being used formally.

A binary relation from A to B is any subset of their Cartesian product. Writing aRb abbreviates saying that the ordered pair belongs to the selected subset. A comparison relation on integers may select pairs whose first entry is smaller; a permission relation may select user-resource pairs that allow access. Neither relation is required to give exactly one second entry for each first entry. Some entries may have no partner or many partners.

A function is the special case where every element of the declared domain has exactly one output in the codomain. Merely drawing arrows does not establish that condition; inspect both existence and uniqueness. A table with two rows sharing an input but different outputs represents a relation, not a function on that input domain. A table omitting an input is also not a total function on that domain, although it could define a function on a smaller domain.

To compose a relation from A to B with one from B to C, look for a middle object in B that connects both stages. The composite relates an initial a to a final c whenever at least one such middle object exists. Multiple witnesses still produce just one pair in the composite set. This differs from counting paths: two distinct intermediate routes can establish the same yes-or-no relationship.

The inverse relation reverses every pair and swaps the domain and codomain roles. It always exists as a relation, even when it is not a function. For example, reversing the graph of squaring over real inputs gives two outputs for most positive inputs and none for negative inputs. The distinction explains why solving an equation backwards may require a restriction of domain rather than an informal instruction to undo the formula.