Product Spaces
Sometimes a system of applied interest can be adequately modeled with a single space. When a system is too complicated for a single space, we may be able to model it with multiple spaces at the same time. Product spaces integrate multiple component spaces together by first combining both their underlying sets and then their associated structures.
1 Product Sets
Product sets combine elements from multiple sets into composite elements. To develop this concept as cleanly as possible, we’ll first investigate how to combine elements from finite sets before considering the general case. Finally, we’ll investigate the behavior of subsets of these product sets.
1.1 Finite Product Sets
Consider two finite sets, one with three elements, X_{1} = \{ \Box, \clubsuit, \diamondsuit \}, and one with two elements, X_{2} = \{ \heartsuit, \spadesuit \}.
One way to combine these two sets together is to collect their individual elements together into larger set, X_{1} \cup X_{2} = \{ \Box, \clubsuit, \diamondsuit, \heartsuit, \spadesuit \}. This concatenated set allows us to choose from any of the elements in X_{1} and X_{2}, but we can only choose only one element at a time.
In order to choose elements from both sets at the same time, we need to account for all of the possible pairs of elements from X_{1} and X_{2}. This requires replicating one of the sets for each element in the other set.
For example, we can replicate X_{2} three times, one for each element of X_{1}. This gives three sets of pairs, \begin{align*} \{ \Box \} \times X_{2} &= \{ (\Box, \heartsuit), (\Box, \spadesuit) \} \\ \{ \clubsuit \} \times X_{2} &= \{ (\clubsuit, \heartsuit), (\clubsuit, \spadesuit) \} \\ \{ \diamondsuit \} \times X_{2} &= \{ (\diamondsuit, \heartsuit), (\diamondsuit, \spadesuit) \}. \end{align*}
Collecting the elements of these sets together gives a new set whose elements account for all of the possible pairings between the elements of X_{1} and X_{2}, \begin{align*} \bigcup_{x_{1} \in X_{1}} \{ x_{1} \} \times X_{2} &= \{ \Box \} \times X_{2} \cup \{ \clubsuit \} \times X_{2} \cup \{ \diamondsuit \} \times X_{2} \\ \\ &= \{ (\Box, \heartsuit), (\Box, \spadesuit), (\clubsuit, \heartsuit), (\clubsuit, \spadesuit), (\diamondsuit, \heartsuit), (\diamondsuit, \spadesuit) \} \\ &\equiv X_{1} \times X_{2}. \end{align*} This new set X_{1} \times X_{2} is denoted a product set with component sets X_{1} and X_{2}.
This construction, however, is not unique. An equivalent way to construct the product set of all pairs of elements in X_{1} and X_{2} is to replicate X_{1} twice, one for each of the two elements in X_{2}. This gives two sets of pairs, \begin{align*} X_{1} \times \{ \heartsuit \} &= \{ (\Box, \heartsuit), (\clubsuit, \heartsuit), (\diamondsuit, \heartsuit) \} \\ X_{1} \times \{ \spadesuit \} &= \{ (\Box, \spadesuit), (\clubsuit, \spadesuit), (\diamondsuit, \spadesuit) \}. \end{align*}
Collecting these sets together gives the new set \begin{align*} \bigcup_{x_{2} \in X_{2}} X_{1} \times \{ x_{2} \} &= X_{1} \times \{ \heartsuit \} \cup X_{1} \times \{ \spadesuit \} \\ &= \{ (\Box, \heartsuit), (\clubsuit, \heartsuit), (\diamondsuit, \heartsuit), (\Box, \spadesuit), (\clubsuit, \spadesuit), (\diamondsuit, \spadesuit) \}, \end{align*} which is exactly the product set we constructed above! In other words, we have two equivalent constructions of the product set (Figure 1), \begin{align*} X_{1} \times X_{2} &= \bigcup_{x_{1} \in X_{1}} \{ x_{1} \} \times X_{2} \\ &= \bigcup_{x_{2} \in X_{2}} X_{1} \times \{ x_{2} \}. \end{align*}
Each element of the product set is uniquely specified by one element of X_{1} and one element of X_{2}. Consequently, every variable taking values in the product set x \in X_{1} \times X_{2} is comprised of an ordered pair of variables from each component space, x = (x_{1}, x_{2}), with x_{1} \in X_{1} and x_{2} \times X_{2}.
1.2 General Product Sets
This construction immediately generalizes beyond finite sets. Given two sets X_{1} and X_{2}, we can construct the product set by replicating X_{2} once for each element of X_{1} and then combining the replicated elements together (Figure 2 (a)) X_{1} \times X_{2} = \bigcup_{x_{1} \in X_{1}} \{ x_{1} \} \times X_{2}. Equivalently we can construct the product set by replicating X_{1} once for each element of X_{2} and then combining the replicated elements together (Figure 2 (b)), X_{1} \times X_{2} = \bigcup_{x_{2} \in X_{2}} X_{1} \times \{ x_{2} \}. The common result X_{1} \times X_{2} is denoted a product set with the component sets X_{1} and X_{2}.
As in the finite case, every element of a general, binary product set is uniquely specified with a pair of elements, one from the first component set, x_{1} \in X_{1}, and the other from the second component set, x_{2} \in X_{2}. Because of this, each variable taking values in the product set x \in X_{1} \times X_{2} is comprised of an ordered pair of component variables, x = ( x_{1}, x_{2} ), with x_{1} \in X_{1} and x_{2} \in X_{2}.
Iterating this construction allows us to define product sets from more than two components sets. For example, given three sets X_{1}, X_{2}, and X_{3} we can construct the three-component product space X_{1} \times X_{2} \times X_{3} in three equivalent different ways (Figure 3). First, we can construct the product set X_{1} \times X_{2}, replicate it once for each element x_{3} \in X_{3}, and then combine those replications together, X_{1} \times X_{2} \times X_{3} = \bigcup_{ x_{3} \times X_{3} } X_{1} \times X_{2} \times \{ x_{3} \}. Second, we can construct the product set X_{2} \times X_{3}, replicate it once for each element x_{1} \in X_{1}, and the aggregate the resulting elements, X_{1} \times X_{2} \times X_{3} = \bigcup_{ x_{1} \times X_{1} } \{ x_{1} \} \times X_{2} \times X_{3}. Third, we can construct the product set X_{1} \times X_{3}, replicate it once for each element x_{2} \in X_{2}, and then aggregate, X_{1} \times X_{2} \times X_{3} = \bigcup_{ x_{2} \times X_{2} } X_{1} \times \{ x_{2} \} \times X_{3}. All three constructions result in the same product space, where each element is uniquely specified by a triplet of component variables, x = (x_{1}, x_{2}, x_{3}).
More generally, given I component sets \{ X_{1}, \ldots, X_{i}, \ldots X_{I} \} we can construct a corresponding product set X_{1} \times \ldots \times X_{i} \times \ldots \times X_{I}, = \times_{i = 1}^{I} X_{i} where every product variable x \in \times_{i = 1}^{I} X_{i} is comprised of a ordered collection of component variables x = ( x_{1}, \ldots, x_{i}, \ldots, x_{I}) with x_{i} \in X_{i}. This ordered collection of component variables is known as an n-tuple variable or, more compactly, just an n-tuple. The term “n-tuple” is meant to generalize “couple” that denotes a pair of component variables and “triple” that denotes three component variables to an arbitrary number of component variables. Because their elements are specified by multiple variables, product sets are often referred to as multivariate sets.
When working with multiple product variables, we might be inclined to use integer indices to differentiate between them. These indices, however, are readily confused with the indices used to denote the component variables. In circumstances where numbering product variables is useful, I will use a comma to separate the indices, with the first always denoting the different variables and the latter always denoting the different components, x_{j} = ( x_{j, 1}, \ldots, x_{j, i}, \ldots, x_{j, I}). In other words, x_{j, i} refers to the ith component variable of the jth product variable.
1.3 Product Subsets
Just as elements from each of the component sets uniquely specifies an element from the corresponding product set, a subset from each of the component sets uniquely specifies a subset of the product set. These product subsets \mathsf{x} \subset \times_{i = 1}^{I} X_{i} are often written as \mathsf{x} = \mathsf{x}_{1} \times \cdots \times \mathsf{x}_{i} \times \cdots \times \mathsf{x}_{I} = \times_{i = 1}^{I} \mathsf{x}_{i} where \mathsf{x}_{i} \subset X_{i}.
The empty product set is given by aggregating the component empty sets, \emptyset = \times_{i = 1}^{I} \emptyset_{i}, while the full product set is given by aggregating the component full sets, X = \times_{i = 1}^{I} X_{i}. The product power set, however, is not a product of the component power sets, 2^{ \times_{i = 1}^{I} X_{i} } \ne \times_{i = 1}^{I} 2^{X_{i}}! Not every subset of \times_{i = 1}^{I} X_{i} is a product subset; indeed most subsets of a product set are not product subsets!
Unfortunately, most of the set operations are not compatible with the component structure of a product set. For instance, the complement of a product subset is not generally given by applying the complement operation to each of the component subsets, \mathsf{x}^{c} \ne \times_{i = 1}^{I} \mathsf{x}_{i}^{c}, although there are a few special cases where this is true.
Similarly, the union of two product subsets is not generally given by the product of the component unions. For two arbitrary product subsets \mathsf{x} = \times_{i = 1}^{I} \mathsf{x}_{i} and \mathsf{x}' = \times_{i = 1}^{I} \mathsf{x}'_{i} we will have \mathsf{x} \cup \mathsf{x}' \ne \times_{i = 1}^{I} \mathsf{x}_{i} \cup \mathsf{x}'_{i}.
The lone exception is the intersection of product subsets, which can always be derived from the intersection of the component subsets, \mathsf{x} \cap \mathsf{x}' = \times_{i = 1}^{I} \mathsf{x}_{i} \cap \mathsf{x}'_{i}. This singular compatibility also introduces a convenient geometric intuition to product subsets. Consider decomposing the product subset X_{1} \times X_{2} into replications of X_{1}, X_{1} \times X_{2} = \bigcup_{x_{2} \in X_{2}} X_{1} \times \{ x_{2} \}. Selecting the subset \mathsf{x}_{1} \subset X_{1} in every replication lifts \mathsf{x}_{1} into the product subset \mathsf{x}_{1} \times X_{2} \subset X_{1} \times X_{2}. At the same time, given the decomposition X_{1} \times X_{2} = \bigcup_{x_{1} \in X_{1}} \{ x_{1} \} \times X_{2} we can select the subset \mathsf{x}_{2} \subset X_{2} in every replication \{ x_{1} \} \times X_{2} to define the product subset X_{1} \times \mathsf{x}_{2} \subset X_{1} \times X_{2}. The intersection of these two lifted product subsets is then just the product of \mathsf{x}_{1} and \mathsf{x}_{2}, \begin{align*} (\mathsf{x}_{1} \times X_{2}) \cap (X_{1} \times \mathsf{x}_{2}) &= (\mathsf{x}_{1} \cap X_{1}) \times (X_{2} \cap \mathsf{x}_{2}) \\ &= (\mathsf{x}_{1}) \times (\mathsf{x}_{2}). \end{align*}
In other words, we can interpret the product subset \mathsf{x}_{1} \times \mathsf{x}_{2} as the rectangular overlap of the “shadows” that \mathsf{x}_{1} and \mathsf{x}_{2} cast into the full product set (Figure 4). Because of this geometric intuition, product subsets are sometimes referred to as rectangular subsets.
This geometric perspective can, for example, be used to better understand why the complement and union operations aren’t compatible with component structure. The product of complementary component subsets generally excludes all of the elements in the complement of the corresponding product subset (Figure 5). On the other hand, the product of the union of component subsets generally includes elements that are not in the union of the corresponding product subsets (Figure 6). Only when considering intersections do both constructions always give the same subset (Figure 7).
2 Product Structure
In order to elevate product sets to product spaces, we need to derive product structure from any structure endowed onto the component sets. Conveniently, these constructions are straightforward for our basic structures.
In this section I will always assume the ambient product set X = \times_{i = 1}^{I} X_{i} with component sets X_{i}.
2.1 Product Orderings
If each component set is equipped with a strict ordering, then we can unambiguously define a product variable x \in X to be smaller than another product variable x' \in X if all of the component elements in x are smaller than all of the corresponding component elements in x'. In other words, x < x' if and only if x_{i} < x'_{i} for all i \in {1, \ldots, I}.
On the other hand, if only some of the component elements in x are smaller than the corresponding component elements in x', while some are larger, then the comparison between the two product elements will be ambiguous. Consequently, a strict ordering on the component sets does not fully define a strict ordering on the product set.
That said, we can use strict component orderings to define a partial ordering of the product set, where any two product elements with mixed component orderings are arranged together. In the same way we can use partial component orderings to define a partial ordering of the product set. Either way, component orderings will generally define partial product orderings.
2.2 Product Algebras
When each component set is equipped with an individual algebraic operation, we can define a corresponding product operation by applying these component operations at the same time. For instance, if each component set is equipped with a binary operation \begin{alignat*}{6} \cdot_{i} :\; & X_{i} \times X_{i}& &\rightarrow& \; & X_{i} & \\ & x_{i}, x'_{i} & &\mapsto& & x_{i} \cdot x'_{i} &, \end{alignat*} then we can construct a product operation \cdot : X \times X \rightarrow X as x \cdot x' = ( x_{1} \cdot_{1} x'_{1}, \ldots, x_{i} \cdot_{i} x'_{i}, \ldots, x_{I} \cdot_{I} x'_{I} ).
Product operations acquire any properties that are shared by all of the component operations. For example, if all of the component operations are commutative then the product operation will also be commutative. Similarly, if all of the component operations are unital with identity elements x_{\text{Id}, i} then the product operation will also be unital with the composite identity element x_{\text{Id}} = (x_{\text{Id}, 1}, \ldots, x_{\text{Id}, i}, \ldots, x_{\text{Id}, I}).
2.3 Product Metrics
Product metrics can be constructed by summing over the outputs of component metrics. More formally, if each component set is equipped with a metric \begin{alignat*}{6} d_{i} :\; & X_{i} \times X_{i}& &\rightarrow& \; & \mathbb{R}^{+} & \\ & x_{i}, x'_{i} & &\mapsto& & d(x_{i}, x'_{i}) & \end{alignat*} then we can define a product metric as \begin{alignat*}{6} d :\; & X \times X& &\rightarrow& \; & \mathbb{R}^{+} & \\ & x, x' & &\mapsto& & \sum_{i = 1}^{I} d(x_{i}, x'_{i}). & \end{alignat*}
Critically, this product metric acquires all of the properties required of a metric from the component metrics. By construction, the product distances vanish if and only if all of the individual component distances vanish. This requires all of the component elements to be equal, which implies that the product elements are also equal. In other words, the product metric returns zero if and only if the two input product elements are the same, as required for a metric.
On the other hand, two input product elements are distinct if and only if at least one of the component element is distinct. In this case at least one of the component distances will be greater than zero. Consequently, the summed distances will be non-zero whenever the input product elements are distinct.
Symmetry of the product metric follows the commutativity of the component metrics, \begin{align*} d(x, x') &= \sum_{i = 1}^{I} d(x_{i}, x'_{i}) \\ &= \sum_{i = 1}^{I} d(x'_{i}, x_{i}) \\ &= d(x', x). \end{align*} Likewise for any three product elements x, x', x'' \in X we always have a triangle inequality, \begin{align*} d(x, x'') &= \sum_{i = 1}^{I} d(x_{i}, x''_{i}) \\ &\le \sum_{i = 1}^{I} d(x_{i}, x'_{i}) + d(x'_{i}, x''_{i}) \\ &\le \sum_{i = 1}^{I} d(x_{i}, x'_{i}) + \sum_{i = 1}^{I} d(x'_{i}, x''_{i}) \\ &\le d(x, x') + d(x', x''). \end{align*}
2.4 Product Topologies
If every component set is equipped with a component topology \mathfrak{t}_{i}, then we can define open component subsets \mathsf{x}_{i} \in \mathfrak{t}_{i}. Any combination of these open component subsets then defines an open product subset \times_{i = 1}^{I} \mathsf{x}_{i}. Because the component topologies all contain the component empty sets and component full sets, we will always be able to construct the product empty set and product full set from this procedure.
Moreover, because the component open subsets are closed under finite intersections, these product subsets will be as well. In particular, given any finite collection of open component subsets \{ \mathsf{x}_{1, i}, \ldots, \mathsf{x}_{j, i}, \ldots \mathsf{x}_{J, i} \} we have closure under intersections, \mathsf{x}_{\cup, i} \equiv \cap_{j = 1}^{J} \mathsf{x}_{j, i} \in \mathfrak{t}_{i}. Consequently, the intersection of any finite collection of open product subsets gives another open product subset, \begin{align*} \cap_{j} \mathsf{x}_{j} &= \cap_{j} \left( \times_{i = 1}^{I} \mathsf{x}_{j, i} \right) \\ &= \times_{i = 1}^{I} \left( \cap_{j} \mathsf{x}_{j, i} \right) \\ &= \times_{i = 1}^{I} \left( \mathsf{x}_{\cup, i} \right). \end{align*}
Unfortunately, the union of any open product subsets will not in general be another product subset. Combining the open product subsets with all of their unions, however, defines a collection of subsets that satisfies all of the properties of a topology. We refer to this topology as a product topology.
3 Prototypical Product Spaces
The most common product spaces we will encounter in practice are built up from the prototypical spaces that we reviewed in Chapter 2, Section 2, combining various integers and real lines together into larger spaces. That said, there are a few product spaces worth particular note.
3.1 Replicated Product Spaces
Often we are interested not in any single element of a space X but rather multiple elements of that space at the same time. The selection of I elements can be modeled by replicating the space I times ,and then using those replications as components of a product space, X^{I} = X \times \ldots \times X = \times_{i = 1}^{I} X. This construction is referred to as a replicated product space, identical product space or power space.
We have already have seen this construction in a few places. For example, we defined binary algebraic operator over the set X as mapping two elements of X into a single element of X. That input set of pairs of elements was denoted X \times X, which is just a replicated product set with a separate copy of X for each input.
Similarly, sequences of I elements from a given set, \{ x_{1}, \ldots, x_{i}, \ldots, x_{I} \}, can be defined as elements of the replicated power set X^{I}. Allowing I to become arbitrarily large then allows for the countably infinitely long sequences.
One potential difficulty that can arise when working with replicated product spaces is distinguishing between the different copies of the base space X that form the components. In particular, any notation that might differentiate the individual copies, such as ticks or integer indices, can also be confused as defining different spaces entirely. Depending on the context, for instance, X_{1} \times X_{2} might be used to denote both a product space comprised of two different spaces or a replicated product space comprised of two copies of the same space. To avoid any confusion, we have to be explicit about when we are assuming a general product space and when we are assuming a replicated product space.
3.2 Multivariate Real Numbers
Combining I real lines together defines the multivariate real numbers, \mathbb{R}^{I}. This is also referred to as a real space or an I-dimensional Euclidean space.
The multivariate real numbers inherit the identity crisis of the real lines from which they are built. If we take the rigid real line perspective then there will be infinitely many multivariate real numbers: different choices of component ordering, algebraic, and metric structures will define distinct product spaces. On the other hand, if we assume the flexible real line perspective then then multivariate real numbers will correspond to a single, flexible space. In this case, each different configuration of the component lines will define a different configuration of the corresponding product space. Following the real line terminology, I will refer to these as rigid real spaces and flexible real spaces, respectively.
To visually summarize the structure of a real space, we can extend grids defined over the component spaces across the other component spaces and then overlay them to form a rectangular mesh (Figure 8).
Combining interval subsets from each component real line [ x_{1, i}, x_{2, i} ] = \{ x_{i} \in X_{i} \mid x_{1, i} \le x_{i} \le x_{2, i} \}, defines a rectangular subset over the full product space, [ x_{1, 1}, x_{2, 1} ] \times \ldots [ x_{1, i}, x_{2, i} ] \times \ldots [ x_{1, I}, x_{2, I} ]. Because these rectangular subsets are compatible with all of the structures of a multivariate real space, they are particular useful for both theoretical and practical calculations.
4 Decomposing Product Spaces
Every element of a product space is uniquely specified by an element from each component space. Specifying all of the component elements at the same time, however, can be overwhelming, especially when we are working with many component spaces. Fortunately, we can always specify the component elements sequentially.
For example, if we decompose a two component product set X_{1} \times X_{2} into replications of the second component set, X_{1} \times X_{2} = \bigcup_{x_{1} \in X_{1} } \{ x_{1} \} \times X_{2}, then every element of X_{1} \times X_{2} can be specified by first distinguishing an element of the first component set, \tilde{x}_{1} \in X_{1}, and then an element in the corresponding replication of the second component set, x_{2} \in \{ \tilde{x}_{1} \} \times X_{2}. This gives the ordered pair (\tilde{x}_{1}, \tilde{x}_{2}) \in X_{1} \times X_{2}. Note that we’re using the \tilde{} notation here to denote bound variables as we make each choice of component elements.
At the same time, if we decompose the product set into X_{1} \times X_{2} = \bigcup_{x_{2} \in X_{2} } X_{1} \times \{ x_{2} \} then every element can be specified by first distinguishing an element of the second component set, \tilde{x}_{2} \in X_{2}, before fixing an element in the corresponding replication of the first component set, \tilde{x}_{1} \in X_{1} \times \{ x_{2} \}.
This sequential specification also has a nice geometric interpretation (Figure 9). Specifying \tilde{x}_{1} \in X_{1} and then \tilde{x}_{2} \in \{ \tilde{x}_{1} \} \times X_{2} corresponds to arriving at (\tilde{x}_{1}, \tilde{x}_{2}) by first moving along X_{1} and then moving along the replication \{ x_{1} \} \times X_{2}. Alternatively, specifying \tilde{x}_{2} \in X_{2} and then \tilde{x}_{1} \in X_{1} \times \{ \tilde{x}_{2} \} corresponds to moving along X_{2} before moving along \{ x_{1} \} \times X_{2}.
We have even more options for sequentially selecting component elements from a product set with three components. For instance, if we decompose the product set into replications of X_{1} \times X_{2} X_{1} \times X_{2} \times X_{3} = \bigcup_{ x_{3} \times X_{3} } X_{1} \times X_{2} \times \{ x_{3} \}. then we can specify an element by first taking an element of the third component set, \tilde{x}_{3} \in X_{3}, and then an element of the corresponding replication, (\tilde{x}_{1}, \tilde{x}_{2}) \in X_{1} \times X_{2} \times \{ x_{3} \}, to give (\tilde{x}_{1}, \tilde{x}_{2}, \tilde{x}_{3}) \in X_{1} \times X_{2} \times X_{3}. By decomposing X_{1} \times X_{2}, however, the latter specification can further be separated into \tilde{x}_{2} \in X_{2} \times \{ \tilde{x}_{3} \} and then \tilde{x}_{1} \in X_{1} \times \{ \tilde{x}_{2} \} \times \{ \tilde{x}_{3} \}, or \tilde{x}_{1} \in X_{1} \times \{ \tilde{x}_{3} \} and then \tilde{x}_{2} \in \{ \tilde{x}_{1} \} \times X_{2} \times \{ \tilde{x}_{3} \}. The different ways that we can decompose X_{1} \times X_{2} \times X_{3} allow us to specify an element of the product set by distinguishing component elements in any order.
This pattern immediately generalizes to any product space. Unfortunately, the generalization quickly become complicated because of all of the different ways that we can select from the available components; given I component spaces there are I! possible sequences that we could use! To represent how we can sequentially build up product elements from component elements, we’ll need some careful, if a bit ungainly, notation.
Let’s start with the I component spaces X_{1}, \ldots, X_{i}, \ldots, X_{I}, which together form the total product space \begin{align*} \times_{i = 1}^{I} X_{i} &= \times_{i \in (1, \ldots, I )} X_{i} \\ &= X_{1} \times \ldots \times X_{i} \times \ldots \times X_{I}. \end{align*} I will refer to this as the joint set.
Any collection of J < I component indices ( i_{1}, \ldots, i_{J} ) defines a smaller product set \times_{ i' \in ( i_{1}, \ldots, i_{J} ) } X_{i'} = X_{i_{1}} \times \ldots \times X_{i_{J}}. I will refer to these as marginal sets.
If we select the components ( i_{1}, \ldots, i_{J} ), then the remaining components, ( 1, \ldots, i_{1} - 1, i_{1} + 1, \ldots, i_{J} - 1, i_{J} + 1, \ldots, J ) define yet another smaller product set. Replicating this second product set once for each element of the first defines a collection of cross section sets (Figure 10), \begin{align*} \times_{i' = 1}^{I} X_{i'} \mid (x_{i_{1}}, \ldots, x_{i_{J}}) &\equiv \quad X_{1} \times \ldots \\ &\quad \times X_{i_{1} - 1} \times \{ x_{i_{1}} \} \times X_{i_{1} + 1} \times \ldots \\ &\quad \times X_{i_{J} - 1} \times \{ x_{i_{J}} \} \times X_{i_{J} + 1} \times \ldots \\ &\quad \times X_{I}. \end{align*} In other words, the elements of a cross section set are given by taking an element of the joint set and then fixing, or conditioning, the component elements of the corresponding marginal set.
A marginal set and its complementary collection of cross section sets can then be used to reconstruct the joint set, \times_{i = 1}^{I} X_{i} = \bigcup_{ (x_{i_{1}}, \ldots, x_{i_{J}}) \in \times_{ i' \in ( i_{1}, \ldots, i_{J} ) } X_{i'} } \left( \times_{i' = 1}^{I} X_{i'} \right) \mid (x_{i_{1}}, \ldots, x_{i_{J}}). This then allows us to specify an element of the joint set (\tilde{x}_{1}, \ldots, \tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}, \ldots, \tilde{x}_{I}) \in \times_{i = 1}^{I} X_{i}. by first specifying the component elements, (\tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}) \in \times_{ i' \in ( i_{1}, \ldots, i_{J} ) } X_{i'}, and then specifying the remaining component elements in the corresponding cross section set, \begin{align*} &(\tilde{x}_{1}, \ldots, \tilde{x}_{i_{1} - 1}, \tilde{x}_{i_{1} + 1}, \ldots, \tilde{x}_{i_{J} - 1}, \tilde{x}_{i_{J} + 1}, \ldots, \tilde{x}_{I} ) \\ &\hspace{35mm} \in \left( \times_{i' = 1}^{I} X_{i'} \right) \mid (\tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}). \end{align*} Because we have to account for any choice of marginal set, the notation here is far from elegant. Keep in mind, however, that all we’re doing is formalizing what happens when we select some component elements first and then the remaining elements second.
Given any partition of the component sets into groups, we can also apply this decomposition recursively to decompose the joint set into a sequence of collections of cross section sets and one terminating marginal set. Consider, for example, five component sets X_{1}, X_{2}, X_{3}, X_{4}, X_{5} which are partitioned into three groups, \{ X_{2}, X_{5} \}, \{ X_{3} \}, \{X_{1}, X_{4} \}. This partition motivates the decomposition \begin{align*} &X_{1} \times X_{2} \times X_{3} \times X_{4} \times X_{5} \\ &\hspace{10mm} = \bigcup_{ (x_{2}, x_{5}) \in X_{2} \times X_{5} } \bigcup_{ x_{3} \in X_{3} \mid (x_{2}, x_{5}) } X_{1} \times X_{4} \mid (x_{2}, x_{3}, x_{5}) \end{align*} and the corresponding sequential specification \begin{align*} (\tilde{x}_{2}, \tilde{x}_{5}) &\in X_{2} \times X_{5} \\ \tilde{x}_{3} &\in X_{3} \mid (\tilde{x}_{2}, \tilde{x}_{5}) \\ (\tilde{x}_{1}, x_{4}) &\in X_{1} \times X_{4} \mid (\tilde{x}_{2}, \tilde{x}_{3}, \tilde{x}_{5}). \end{align*}
In most applications we will want to completely decompose the joint set into individual component sets, allowing us to build a joint element up by specifying component elements one by one. For instance, working through the component spaces in order gives the specification \begin{alignat*}{3} \tilde{x}_{1} &\in X_{1} && \\ \tilde{x}_{2} &\in X_{2} &\mid& \; \tilde{x}_{1} \\ &\ldots \\ \tilde{x}_{i} &\in X_{i} &\mid& \; ( \tilde{x}_{1}, \ldots, \tilde{x}_{i} ) \\ &\ldots \\ \tilde{x}_{I - 1} &\in X_{I - 1} &\mid& \; ( \tilde{x}_{1}, \ldots, \tilde{x}_{I - 2} ) \\ \tilde{x}_{I} &\in X_{I} &\mid& \; ( \tilde{x}_{1}, \ldots, \tilde{x}_{I - 1} ). \end{alignat*} That said, we can work through the component spaces in any order. This flexibility allows us to construct joint elements in whichever way is most convenient in a given application.
Because we often take sequential specification of elements for granted, this formal, systematic treatment might appear to be a bit…excessive. To the contrary, this more careful perspective will help us understand some of the more subtle aspects of probability theory on product spaces, and how we can actually engineer sophisticated probability distributions in practice.
5 Transforming Product Spaces
We can always transform product spaces directly with monolithic maps that ignore any component structure. These functions map an entire input product set to an arbitrary output set, \begin{alignat*}{6} f :\; & \times_{i = 1}^{I} X_{i} & &\rightarrow& \; & Y & \\ & (x_{1}, \ldots, x_{i}, \ldots, x_{I}) & &\mapsto& & y = f(x_{1}, \ldots, x_{i}, \ldots, x_{I}) &. \end{alignat*}
For example, algebraic operations can be interpreted as functions from the input replicated product set X \times X to the output set X, \begin{alignat*}{6} f :\; & X \times X & &\rightarrow& \; & X & \\ & (x_{1}, x_{2}) & &\mapsto& & x = f(x_{1}, x_{2}) &. \end{alignat*} Metrics can also be interpreted as functions from that same input product set, \begin{alignat*}{6} d :\; & X \times X & &\rightarrow& \; & [0, \infty] & \\ & (x_{1}, x_{2}) & &\mapsto& & d(x_{1}, x_{2}) &. \end{alignat*}
The classification of these functions, and the construction of pushforward and pullback functions, follows exactly the same as for functions with general input spaces. We can say much more, however, about functions that naturally harmonize with the component structure of an input product space.
5.1 Component Transformations
Transformations between two product spaces can also be decomposed into simpler transformations. Any function between two product sets \begin{alignat*}{6} f :\; & \times_{i = 1}^{I} X_{i} & &\rightarrow& \; & \times_{j = 1}^{J} Y_{j} & \\ & (x_{1}, \ldots, x_{i}, \ldots, x_{I}) & &\mapsto& & (y_{1}, \ldots, y_{j}, \ldots, y_{J}) = f(x_{1}, \ldots, x_{i}, \ldots, x_{I}) & \end{alignat*} is equivalent to J functions that map the input product set into each of the individual output component sets, \begin{alignat*}{6} f_{j} :\; & \times_{i = 1}^{I} X_{i} & &\rightarrow& \; & Y_{j} & \\ & (x_{1}, \ldots, x_{i}, \ldots, x_{I}) & &\mapsto& & y_{j} = f_{j}(x_{1}, \ldots, x_{i}, \ldots, x_{I}) &. \end{alignat*} Pushforward and pullback maps for the complete function can then be derived from these component functions.
In general, these component functions mix the input components together to inform the behavior in each output component set. Some functions, however, limit each of the input component sets to informing only a single output component set. Specifically, if the input product set and output product set are built up from the same number of component sets I, then some functions will map only one input component into each of the output components at a time, \begin{alignat*}{6} f_{i} :\; & X_{i} & &\rightarrow& \; & Y_{i} & \\ & x_{i} & &\mapsto& & y_{i} = f_{i}(x_{i}) &. \end{alignat*} These component-preserving functions transform each component independently of the others.
One nice feature of component-preserving transformations is that they preserve the orientation of grids defined from any component metric structure. For instance, the function \begin{alignat*}{6} f :\; & \mathbb{R}^{2} & &\rightarrow& \; & \mathbb{R}^{2} & \\ & (x_{1}, x_{2}) & &\mapsto& & (y_{1}, y_{2}) = (x_{1}^{\frac{3}{2}}, x_{2}^{\frac{3}{2}}) & \end{alignat*} transforms x_{1} into y_{1} independently of the behavior of x_{2}, and transforms x_{2} into y_{2} independently of the behavior of x_{1}. While neither of these component transformations are isometries, the rectangular structure of the metric-informed grid is preserved (Figure 11 (a)).
On the other hand, the function \begin{alignat*}{6} f :\; & \mathbb{R}^{2} & &\rightarrow& \; & \mathbb{R}^{2} & \\ & (x_{1}, x_{2}) & &\mapsto& & (y_{1}, y_{2} = (x_{1} + x_{2}, x_{1} - x_{2}) & \end{alignat*} mixes the input components x_{1} and x_{2} together, skewing the product structure in the process. Consequently, grids built up from the component metric structures on the input and output spaces will appear warped relative to each other (Figure 11 (b)).
The behavior of component-preserving functions is completely determined by the behavior of the component functions. For example, a component-preserving function is injective, surjective, or bijective if and only if all of the component functions are injective, surjective, or bijective.
5.2 Projection Functions
The component-structure of a product space naturally motivates an important class of functions. Consider, for instance, the two-component product space X_{1} \times X_{2} and its decomposition into distinct replications of X_{1}, X_{1} \times X_{2} = \bigcup_{x_{2} \in X_{2}} X_{1} \times \{ x_{2} \}. If we ignore the x_{2} label, then the replications X_{1} \times \{ x_{2} \} become indistinguishable from each other, collapsing into a single copy of X_{1} (Figure 12). This collapse projects every element of the product set (x_{1}, x_{2}) \in X_{1} \times X_{2} into a component element x_{1} \in X_{1}.
At the same time, we can decompose the product set into replications of X_{2}, X_{1} \times X_{2} = \bigcup_{x_{1} \in X_{1}} \{ x_{1} \} \times X_{2}. Ignoring the x_{1} label collapses the replications \{ x_{1} \} \times X_{2} onto each other, projecting every product element (x_{1}, x_{2}) \in X_{1} \times X_{2} to the component x_{2} \in X_{2}.
More generally, every product set defines a collection of surjective projection functions that map the entire product set into the individual component sets by ignoring the other components, \begin{alignat*}{6} \varpi_{i} :\; & \times_{i' = 1}^{I} X_{i'} & &\rightarrow& \; & X_{i} & \\ & (x_{1}, \ldots, x_{i}, \ldots, x_{I}) & &\mapsto& & x_{i} &. \end{alignat*}
We can also construct more sophisticated multi-projection functions that return multiple component spaces at the same time. In particular, given J < I component indices ( i_{1}, \ldots, i_{J} ) we can define a projection function that maps the joint set into any marginal set, \begin{alignat*}{6} \varpi_{i_{1}, \ldots, i_{J}} :\; & \times_{i' = 1}^{I} X_{i'} & &\rightarrow& \; & \times_{ i' \in ( i_{1}, \ldots, i_{J} ) } X_{i'} & \\ & (x_{1}, \ldots, x_{I}) & &\mapsto& & (x_{i}, x_{j}, x_{k}) &. \end{alignat*}
Projection functions are particularly useful for succinctly expressing some of the more subtle product space behaviors that we have already discussed. As we saw in the previous section, for instance, every function with a product space input decomposes into component functions, \begin{alignat*}{6} f_{j} :\; & \times_{i = 1}^{I} X_{i} & &\rightarrow& \; & Y_{j} & \\ & (x_{1}, \ldots, x_{i}, \ldots, x_{I}) & &\mapsto& & y_{j} = f_{j}(x_{1}, \ldots, x_{i}, \ldots, x_{I}) &. \end{alignat*} Those component functions can be directly defined as the composition of f with each of the projection functions on the output space, f_{j} = \varpi_{j} \circ f.
Similarly, every cross section set can be defined as a level set of a particular multi-projection function, \times_{i' = 1}^{I} X_{i'} \mid (x_{i_{1}}, \ldots, x_{i_{J}}) = \varpi_{i_{1}, \ldots, i_{J}}^{-1}(x_{i_{1}}, \ldots, x_{i_{J}})! In other words, a cross section set can be interpreted as the subset of the joint set that projects to a particular element of a marginal set. This projection perspective not only clarifies how marginal and cross section sets are complementary to each other, but also provides a more compact way of denoting these sets.
5.3 Partial Evaluation
Fully evaluating a function on a product space requires specifying an element in every component space. For instance, in order to evaluate the function f: X_{1} \times X_{2} \rightarrow Y, we need to specify both \tilde{x}_{1} \in X_{1} and \tilde{x}_{2} \in X_{2}, f(\tilde{x}_{1}, \tilde{x}_{2}) = y \in Y.
Providing only one element leaves an empty slot in the input product set that we need to fill in order to complete the evaluation. For example, f(\tilde{x}_{1}, x_{2}) is missing an an element of X_{2} and f(x_{1}, \tilde{x}_{2}) is missing an element of X_{1}. That empty slot, however, defines a relationship between the missing input and the output set. Specifically, f(\tilde{x}_{1}, x_{2}) implicitly defines a function that maps elements of \{ \tilde{x}_{1} \} \times X_{2} to elements of Y, while f(x_{1}, \tilde{x}_{2}) implicitly defines a function that maps elements of X_{1} \times \{ \tilde{x}_{2} \} to elements of Y.
More generally, specifying the component elements ( \tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}} ) reduces to the product set \times_{i' = 1}^{I} X_{i'} to the cross section set \times_{i' = 1}^{I} X_{i'} \mid (\tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}). Likewise, inputting those component elements into a function \begin{alignat*}{6} f :\; & \times_{i = 1}^{I} X_{i} & &\rightarrow& \; & Y & \\ & (x_{1}, \ldots, x_{i}, \ldots, x_{I}) & &\mapsto& & y = f(x_{1}, \ldots, x_{i}, \ldots, x_{I}) & \end{alignat*} defines a new function that maps the remaining elements to an output element, \begin{alignat*}{6} f_{ \tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}} } :\; & \times_{i' = 1}^{I} X_{i'} \mid (\tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}) & &\rightarrow& \; & Y & \\ & (x_{1}, \ldots, x_{i_{1} - 1}, x_{i_{1} + 1}, \ldots, & &\mapsto& & y = f(x_{1}, \ldots, x_{i_{1} - 1}, \tilde{x}_{i_{1}}, x_{i_{1} + 1}, \ldots, & \\ & \;\, x_{i_{J} - 1}, x_{i_{J} + 1}, \ldots, x_{I} \quad\quad) & & & & \quad\quad\quad x_{i_{J} - 1}, \tilde{x}_{i_{J}}, x_{i_{J} + 1}, \ldots, x_{I} \quad\quad) &. \end{alignat*}
This procedure is known as partial evaluation generally, and Currying in the computer science literature particularly. The mathematical notation for a partially evaluated function can vary quite a bit. Besides f_{\tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}}, it is not uncommon to see notation like f(\cdot \mid \tilde{x}_{i_{1}}, \ldots, \tilde{x}_{i_{J}}), where \cdot represents the remaining unbound variables. One might also encounter notation that explicitly writes out all of the bound and unbound variables, f( x_{1}, \ldots, x_{i_{1} - 1}, \tilde{x}_{i_{1}}, x_{i_{1} + 1}, \ldots, x_{i_{J} - 1}, \tilde{x}_{i_{J}}, x_{i_{J} + 1}, \ldots, x_{I} ). While this latter notation is most direct, it quickly becomes ungainly when working with more than a few components.
Like the sequential specification of product set elements, the partial evaluation of functions is often taken for granted in practical applications. Explicitly acknowledging it, however, can help us better understand less obvious constructions.
For example, consider a set X equipped with a binary addition operator \begin{alignat*}{6} + :\; & X \times X& &\rightarrow& \; & X & \\ & x_{1}, x_{2} & &\mapsto& & x_{1} + x_{2} &. \end{alignat*} Partially evaluating this function on the first input component effectively defines a function \begin{alignat*}{6} t_{\tilde{x}_{1}} :\; &X& &\rightarrow& \; & X & \\ & x_{2} & &\mapsto& & \tilde{x}_{1} + x_{2} &. \end{alignat*} This new function translates each element of X by \tilde{x}_{1}. Unsurprisingly, t_{\tilde{x}_{1}} is referred to as a translation operator.
Similarly, if we have a set X equipped with a binary multiplication operator \begin{alignat*}{6} \cdot :\; & X \times X& &\rightarrow& \; & X & \\ & x_{1}, x_{2} & &\mapsto& & x_{1} \cdot x_{2} & \end{alignat*} then partial evaluation effectively defines a function \begin{alignat*}{6} s_{\tilde{x}_{1}} :\; &X& &\rightarrow& \; & X & \\ & x_{2} & &\mapsto& & \tilde{x}_{1} \cdot x_{2} &. \end{alignat*} This new function scales each element of X by \tilde{x}_{1}. Fittingly, s_{\tilde{x}_{1}} is often referred to as a scaling operator.
In many applications translations and scalings appear to be intuitive. Partial evaluation allows us to formalize that conceptual reasoning, which can then helps us recognize the assumptions needed for that intuitive to be well-defined. For example, translation isn’t well-defined on a space that isn’t equipped with the right algebraic structure!
6 Conclusion
The construction of product spaces defines a systematic way to work with multiple elements at the same time. Product spaces not only facilitate the development and manipulation of the sophisticated spaces we often need for applied mathematical modeling, but also provide a language for formalizing common computational techniques.
When working with more than a few component spaces, some of the details of the formal construction of product spaces – such as the sequential specification of product elements, projections, and partial evaluations – require some less-than-elegant notation. That said, this awkwardness is not due to any conceptual complexity so much as the difficulty in enumerating all of the ways that we can select from a general collection of component spaces.
Acknowledgements
I thank Alexander Noll, Pietro Monticone, and and Léo Burgund for helpful comments.
A very special thanks to everyone supporting me on Patreon: Adam Fleischhacker, Adriano Yoshino, Alan Chang, Alessandro Varacca, Alexander Bartik, Alexander Noll, Alexander Petrov, Alexander Rosteck, Anders Valind, Andrea Serafino, Andrew Mascioli, Andrew Rouillard, Andrew Vigotsky, Angie_Hyunji Moon, Ara Winter, Austin Rochford, Austin Rochford, Avraham Adler, Ben Matthews, Ben Swallow, Benjamin Glemain, Bradley Kolb, Brynjolfur Gauti Jónsson, Cameron Smith, Canaan Breiss, Cat Shark, Charles Naylor, Chase Dwelle, Chris Zawora, Christopher Mehrvarzi, Chuck Carlson, Colin Carroll, Colin McAuliffe, Cruz, Damien Mannion, Damon Bayer, dan mackinlay, Dan Muck, Dan W Joyce, Dan Waxman, Dan Weitzenfeld, Daniel Edward Marthaler, Daniel Rowe, Darshan Pandit, Darthmaluus , David Burdelski, David Galley, David Humeau, David Wurtz, dilsher singh dhillon, Doug Rivers, Dr. Jobo, Dr. Omri Har Shemesh, Ed Cashin, Ed Henry, Edgar Merkle, edith darin, Eric LaMotte, Erik Banek, Ero Carrera, Eugene O’Friel, Felipe González, Fergus Chadwick, Finn Lindgren, Florian Wellmann, Francesco Corona, Geoff Rollins, Greg Sutcliffe, Guido Biele, Hamed Bastan-Hagh, Haonan Zhu, Hector Munoz, Henri Wallen, hs, Hugo Botha, Håkan Johansson, Ian Costley, Ian Koller, idontgetoutmuch, Ignacio Vera, Ilaria Prosdocimi, Isaac Vock, J, J Michael Burgess, Jair Andrade, James Hodgson, James McInerney, James Wade, Janek Berger, Jason Martin, Jason Pekos, Jason Wong, Jeff Burnett, Jeff Dotson, Jeff Helzner, Jeffrey Erlich, Jesse Wolfhagen, Jessica Graves, Joe Wagner, John Flournoy, Jonathan H. Morgan, Jonathon Vallejo, Joran Jongerling, Joseph Despres, Josh Weinstock, Joshua Duncan, Joshua Griffith, Josué Mendoza, JU, Justin Bois, Karim Naguib, Karim Osman, Kejia Shi, Kevin Foley, Kristian Gårdhus Wichmann, Kádár András, lizzie , LOU ODETTE, Marc Dotson, Marcel Lüthi, Marek Kwiatkowski, Mark Donoghoe, Mark Worrall, Markus P., Martin Modrák, Matt Moores, Matthew, Matthew Kay, Matthieu LEROY, Maurits van der Meer, Merlin Noel Heidemanns, Michael DeWitt, Michael Dillon, Michael Lerner, Mick Cooney, Márton Vaitkus, N Sanders, Name, Nathaniel Burbank, Nic Fishman, Nicholas Clark, Nicholas Cowie, Nick S, Nicolas Frisby, Octavio Medina, Ole Rogeberg, Oliver Crook, Olivier Ma, Pablo León Villagrá, Patrick Kelley, Patrick Boehnke, Pau Pereira Batlle, Peter Smits, Pieter van den Berg , ptr, Putra Manggala, Ramiro Barrantes Reynolds, Ravin Kumar, Raúl Peralta Lozada, Riccardo Fusaroli, Richard Nerland, RLW, Robert Frost, Robert Goldman, Robert kohn, Robert Mitchell V, Robin Taylor, Ross McCullough, Ryan Grossman, Rémi , S Hong, Scott Block, Scott Brown, Sean Pinkney, Sean Wilson, Seth Axen, shira, Simon Duane, Simon Lilburn, Srivatsa Srinath, sssz, Stan_user, Stefan, Stephanie Fitzgerald, Stephen Lienhard, Steve Bertolani, Stone Chen, Susan Holmes, Svilup, Sören Berg, Tao Ye, Tate Tunstall, Tatsuo Okubo, Teresa Ortiz, Thomas Lees, Thomas Vladeck, Tiago Cabaço, Tim Radtke, Tobychev , Tom McEwen, Tony Wuersch, Utku Turk, Virginia Fisher, Vitaly Druker, Vladimir Markov, Wil Yegelwel, Will Farr, Will Tudor-Evans, woejozney, Xianda Sun, yolhaj , yureq , Zach A, Zad Rafi, and Zhengchen Cai.
License
A repository containing all of the files used to generate this chapter is available on GitHub.
The text and figures in this chapter are copyrighted by Michael Betancourt and licensed under the CC BY-NC 4.0 license:
https://creativecommons.org/licenses/by-nc/4.0/