Cartesian Product and Tuples

Let X and Y denote sets, then the set of all ordered pairs (x,y) with $x \in X$, $y \in Y$ is called the cartesian product of X and Y and is written $X \times Y$. The cartesian product $X \times X$ is often denoted by X² . This definition can be extended : if X₁, X₂, ...,X_n are sets, then the set of all n-tuples $(x_1,x_2, \dots,x_n)$where $x_1 \in X_1$, $x_2 \in X_2$, ..., $x_n \in X_n$ is the cartesian product of X₁,X₂, ..., X_n and is written $X_1 \times X_2 \times \dots \times X_n$.

As an example, consider the cartesian product of the set of natural numbers and the set of Boolean values. The cartesian product is then the set of all ordered pairs of the form (n,b) where $n \in \Nat$ and $b \in \Bool$ and is written $\Nat \times \Bool$. Typical members of $\Nat \times \Bool$ include (3,true) ; (5,true) ; (9,false) ; (3,false).

The concept of a cartesian product may be more clearly understood by considering the following situation. Suppose a young child is given a list of natural numbers, e.g. $3,5,9,8,2,\dots$ and has to state whether or not they are odd. Suppose further that the child is required to submit the answers at a computer terminal by typing in successive natural number, boolean value pairs, for example ``3 true'' ; ``5 true'' ; ``8 false'' ; ``2 true''; ...and that after each pair is entered, the system responds with an appropriate message : ``Your answer is correct'' or ``Your answer is wrong!''. A Boolean-valued Pascal function is_correct_pair and its use in a program which will accomplish this task is shown in Fig. 2.1.

  

Figure 2.1: Pascal program for the cartesian product

The built-in Boolean function odd(n) returns true if n is odd and false if n is even. The formal parameter list n : natural; b : boolean in the function declaration states that the function will accept, as valid input, any ordered pair whose first element is a natural number and whose second element is a boolean value. The set of all such ordered pairs, which we express mathematically as $\Nat$ $\times$ $\Bool$ is therefore simply the collection of all valid input tuples for the function and delineates precisely the set of all syntactically legal input value pairs to the function is_correct_pair.