A question about Cartesian Products of Families

Question

I am reading Halmos' Naive Set Theory, and am quite puzzled with the way he defines a Cartesian Product of a Family. He says: "the Cartesian Product of the family is, by definition, the set of all families {x_i} with x_i ∈ X_i for each i in I." Now, by this definition then, if I define some family {A_i} with i belonging to the index set 2. So that {A_i} is the set A₀ and A₁. Then the Cartesian Product of this family is, by definition, the set containing all the functions x from the index set 2 to the set {A_i} for every i in 2. Now, let A₀ be the set {a,b} and A₁ the set {c,d}. First then, the set containing all the functions from 2 to A₀ is the set {{(0,a),(1,a)},{(0,a),(1,b)},{(0,b),(1,a)},{(0,b),(1,b)}}. And secondly, the set containing all the functions from 2 to A₁ is the set {{(0,c),(1,c)},{(0,c),(1,d)},{(0,d),(1,c)},{(0,d),(1,d)}}. So that the Cartesian Product of whole {A_i} is the union of those two sets which is: {{(0,a),(1,a)},{(0,a),(1,b)},{(0,b),(1,a)},{(0,b),(1,b)},{(0,c),(1,c)},{(0,c),(1,d)},{(0,d),(1,c)},{(0,d),(1,d)}}. BUT, Halmos later in the same section defines the Cartesian Product of a {A_i} with i ∈ 2 to be the same as A₀ × A₁ which is the set {(a,c),(a,d),(b,c),(b,d)}, WHICH IS definitely not the set we found earlier. Where is my logic flawed? It would be most helpful if someone explained this to me explicitly. Thank you in advance.

Answer 1

I agree with you that Halmos's discussion is not so easy...

Consider a simple example with set $A= \{ a,b \}$ and $B= \{ l,m \}$.

The cartesian product $A \times B = \{ (x,y) \mid x \in A \text { and } y \in B \}$ will have four pairs.

Consider now a function $x : A \to B$; e.g. $x= \{ (a,l), (b,m) \}$ which has two elements.

If $x' = \{ (a,l), (b,l) \}$ is another such function, we have that $x \cup x' = \{ (a,l), (b,m), (b,l) \}$ (which is not a function); thus, collecting together all such functions, the result will contain all pairs, and thus will be exactly the set $A \times B$.

---

Let start again from Halmos' definition (page 34): $x$ is a function from the domain $I$, the index set to $X$ (the range of the function is the indexed set).

The function itself is called a family and the value of function $x$ is at index $i$, called a term, is denoted by $x_i$.

Thus, for a family we have: $\{ A_i \}_{i \in I} = \{ (i, A(i)) \mid i \in I \}$.

Now we can to move to page 37 and consider "the family of sets $\{ X_i \}_{(i \in I)}$".

If $I= \{ a,b,c \}$, we want that the "generalized" cartesian product of $\{ X_i \}_{(i \in I)}$ will be made of "uples" $\{x_a,x_b,x_c \}$ where $x_i \in X_i$.

But such an uple is a function $x : I= \{ a,b,c \} \to \bigcup X_i$ with the condition that $x(i)=x_i \in X_i$.

Thus, de corresponding definition will be:

$\Pi_{i \in I} \{ X_i \} = \{ x \mid (x: I \to \bigcup_{i \in I} X_i \text { and } (x(i) \in X_i) \}$.

Using the $x_i$ notation: $\Pi_{i \in I} \{ X_i \} = \{ x_i \mid \forall i(i \in I \to x_i \in X_i) \}$.

Using the index set $I$ and the three sets: $X_a= \{ l,m \}, X_b= \{ l, n \}, X_c= \{ l \}$, we can compute all elements of $\Pi \{X_i \}$:

$\{ \{ (a,l), (b,l), (c,l) \}, \{ (a,l), (b, n), (c,l) \}, \{ (a,m), (b,l), (c,l) \}, \{ (a,m), (b,n), (c,l) \} \}.$

As we can see, due to the fact that the index set $I$ has three elements, all elements of the cartesian product are "three-uples".

If we apply the definition to a couple of sets $X_0= \{ a,b \}$ and $X_1 = \{ l,m \}$, i.e. to the family $\{ X_i \}$ indexed by $I = \{ 0,1 \}$, what we get is:

$\Pi \{ X_i \} = \{ (0,a), (1,l) \}, \{ (0,a), (1,m) \}, \{ (0,b), (1,l) \}, \{ (0,b), (1,m) \}.$

Now, if you compare it with the corresponding example $A \times B$ above, you can see that the two sets are not equal (but they are "structurally" so).

The link between the two definitions is given by Halmos in the first lines of page 36 with the "natural one-to-one correspondence between the cartesian product of two sets and a certain set of families."

Answer 2

First, let me use your example to show what Halmos's definition means. So $I=2$, $A_0=\{a,b\}$, and $A_1=\{c,d\}$. According to Halmos, the cartesian product of this family is the set of families $\langle x_i\rangle_{i\in I}$, with the same index set $I=2$, that satisfy $x_i\in A_i$ for each $i\in I$. (Note that $x$ and $A$ here both have the subscript $i$. Note also that I'm using the angle-bracket notation $\langle\cdots\rangle$ for families.) So an element of this family would be a family $\langle x_0,x_1\rangle$ consisting of $x_0\in A_0$ and $x_1\in A_1$. That means $x_0$ can be $a$ or $b$ while $x_1$ can be $c$ or $d$. The elements of the cartesian product are therefore the four families $\langle a,c\rangle,\langle b,c\rangle,\langle a,d\rangle,\langle b,d\rangle$.

That looks pretty good, in that those four families look like the four elements you were expecting in $A_0\times A_1$, but there's one detail that deserves to be straightened out. Most authors (I haven't checked Halmos) define $I$-indexed families to be certain functions. In particular, a $2$-indexed family, like $\langle a,c\rangle$, is not strictly speaking the same thing as an ordered pair, like $(a,c)$. So the cartesian product of a $2$-indexed family $\langle A_0,A_1\rangle$ is not the same set as $A_0\times A_1$. (And I hope Halmos doesn't say it is, unless he has a different notion of "family" than what I've described.) But there's an obvious one-to-one correspondence between the two, namely to change angle-brackets to parentheses.