# set theoretic function, products of sets (product versus Cartesian product)

Regarding the products of functions in axiomatic set theory, two textbooks which I am reading (Halmos; Hrbacek/Jech) have said the following:

"There is a natural one-to-one correspondence between [the Cartesian product] and a certain set of families. Consider, indeed, any particular unordered pair $\{a,b\}$, with $a\neq b$, and consider the set $Z$ of all families $z$, indexed by $\{a,b\}$ such that $z_a \in X$ and $z_b \in Y$. If the function $f$ from $Z$ to $X \times Y$ is defined by $f(z) = (z_a, z_b)$, then $f$ is the promised one-to-one correspondence. The difference between $Z$ and $X \times Y$ if merely a matter of notation."

Hrbacek/Jech said as much, but reversed the bijection: they considered

"...a canonical one-to-one correspondence between ordered pairs and 2-tuples that preserves first and second coordinates. Define $\delta((a_0, a_1)) = \{(0, a_0), (1, a_1)\}$; then $\delta$ is a one-to-one mapping on $A_0 \times A_1$ onto $\prod_{0\leq i<2} A_i$ and $x$ is a first (second, respectively) coordinate of $(a_0, a_1)$ iff $x$ is a first (second, respectively) coordinate of $\{(0, a_0),(1,a_1)\}$."

(I had to change their notation a bit: the function maps to 2-term sequences, with each term a "coordinate.")

This is my question: in Halmos' case, how did we order the coordinates? I can see how we could remove the second coordinates from each ordered pair in the family systematically (put $\beta = \{ \bigcup_{x \in \{z_i\}} ( \bigcup_{x \in (i,z_i)} (i,z_i) - \bigcap_{x \in (i,z_i)} (i,z_i)): (i,z_i) \in f \}$), but I do not see how to reorder them into a new pair which recovers the order of the Cartesian product, since the index set was unordered. I like the H/J version, but want to see it made invertible.

-
We don't need to order the coordinates, we just need to label them. One coordinate belongs to $a$, the other coordinate belongs to $b$. Whether we call the $a$-coordinate the "first" or the "second" is immaterial, all that matters is that the labels be distinct. Note that the labels are also attached to the sets, so that is how we can tell which item goes with which set: the item labeled with $a$ goes with the set that is also labeled with $a$. – Arturo Magidin May 21 '12 at 2:16
But knowing the labels, how do we actually place the objects in order? – Chris May 21 '12 at 2:32
"Place them" where? What "order"? What "objects"? We are constructing a set of functions with certain properties; we are not placing objects anywhere, and there is no order. We can select an arbitrary ordering of $\{a,b\}$ in order to establish a bijection between the set of functions $f\colon\{a,b\}\to X\cup Y$ with $f(a)\in X$ and $f(b)\in Y$ and a set of ordered pairs as per the Cartesian product, either $X\times Y$ (if we select the order that has $g(a)$ first and $g(b)$ second), or as $Y\times X$. There is a natural bijection between $X\times Y$ and $Y\times X$, so doesn't matter which. – Arturo Magidin May 21 '12 at 2:34
In answer to the first line, I meant to ask how we "place" the second coordinates of the ordered pairs of a family in the order of their Cartesian product; if $z_a$ comes from $X$, and $z_b$ from $Y$, how we create ($z_a$, $z_b$) to represent an element of $X \times Y$, as opposed to creating ($z_b$, $z_a$) to represent the same (which is not the right "order"). – Chris May 21 '12 at 2:42
We select an arbitrary order for $\{a,b\}$, say by bijecting with $\{0,1\}$. If we happen to pick the "wrong" order, we can compose with the natural bijection $Y\times X\to X\times Y$ and get a natural bijection to $X\times Y$. – Arturo Magidin May 21 '12 at 2:47

In the Halmos version, a typical family $z$ has the form $z=\{z_a,z_b\}$, with $z_a\in X$ and $z_b\in Y$. Formally this means that $z$ is a function from $\{a,b\}$ to $X\cup Y$ with the property that $z_a=z(a)\in X$ and $z_b=z(b)\in Y$. The ‘ordering’ of the coordinates is supplied by the fact that one is an $a$-coordinate and one is a $b$-coordinate, and therefore they can be distinguished. The family $z$ for which $z_a=0$ and $z_b=1$, for instance, is not the same as the family for which $z_a=1$ and $z_b=0$ (assuming that $0,1\in X\cap Y$ so that these families make sense).

When we define the function $f:Z\to X\times Y$ by $f(z)=\langle z_a,z_b\rangle$, we’re implicitly making the $a$-indexed element of $z$ the first coordinate and the $b$-indexed element the second coordinate. If you write out $z$ as a function from $\{a,b\}$ to $X\cup Y$, you have $z=\{\langle a,z_a\rangle,\langle b,z_b\rangle\}$, and $f$ simply strips off the first coordinates and forms an ordered pair out of the second coordinates in $ab$ order: $\{\langle a,z_a\rangle,\langle b,z_b\rangle\}\mapsto\langle z_a,z_b\rangle$. We could just as well define $f$ by $f(z)=\langle z_b,z_a\rangle$, implicitly making the $b$-coordinate the first coordinate, and the $a$-coordinate the second.

The only real difference between what Halmos is doing here and what Hrbacek and Jech do is that H&J fix the index set to be $\{0,1\}$ instead of allowing an arbitrary two-element index set, and then they use the natural order on their index set.

Added: In formal terms Halmos is starting with $$Z=\Big\{\big\{\langle a,x\rangle,\langle b,y\rangle\big\}:x\in X\text{ and }y\in Y\Big\}\;,$$ though he actually writes $z=\{z_a,z_b\}$ for the function $z=\big\{\langle a,x\rangle,\langle b,y\rangle\big\}$ such that $x=z_a$ and $y=z_b$. He then defines

$$f:Z\to X\times Y:\big\{\langle a,x\rangle,\langle b,y\rangle\big\}\mapsto\langle x,y\rangle\;;$$

this is certainly not at all problematic, since the first component of some $f(z)$ is unambiguously identified as the second component of the member of $z$ whose first component is $a$. If you want the gory details, given $z\in Z$ and the usual definition of ordered pair, $f(z)=\langle x,y\rangle$ iff

\begin{align*} \exists u\in z&\exists v\in u\,\exists w\in u\Big(\forall t(t\in v\leftrightarrow t=a)\land a\in w\land x\in w\Big)\\ &\land\exists u\in z\,\exists v\in u\,\exists w\in u\Big(\forall t(t\in v\leftrightarrow t=b)\land b\in w\land y\in w\Big)\;.\tag{1} \end{align*}

Abbreviate $(1)$ as $\varphi(x,y,z)$. Then

$$f=\Big\{\langle x,y\rangle:\exists z\in Z\big(\varphi(x,y,z)\big)\Big\}$$

In his indexed family notation that’s

$$f:Z\to X\times Y:\{z_a,z_b\}\mapsto\langle z_a,z_b\rangle\;.$$

His version works because the indices $a$ and $b$ on $z_a$ and $z_b$ are understood to be recoverable $-$ $z$ really is a function from $\{a,b\}$ to $x\cup Y$ (with the additional property that $f(a)\in X$ and $f(b)\in Y$).

-
My question is precisely how we employ "ab" order. Even in the specific case of indexing by the naturals, I don't see how we "look into" the ordered pairs to see which one comes first. – Chris May 21 '12 at 1:00
@user1296727: I’m afraid that I don’t understand the difficulty. You can always tell which component of an ordered pair is first and which is second; that’s why it’s an ordered pair. When you map $z$ to $\langle z_a,z_b\rangle$, you’re implicitly deciding that the $a$-indexed member of $z$ is going to be considered the first coordinate, and the $b$-indexed member the second. As I indicated above, you could have made the opposite decision. The point of ordered pairs really isn’t the order: it’s the fact that the order lets you distinguish the members of the pair. ... – Brian M. Scott May 21 '12 at 1:08
... Indexing by a two-element set does exactly the same thing. If you then want to impose a specific order, in addition to being able to label one element the $a$-component and the other the $b$-component, you simply decide whether to order $\{a,b\}$ as $a$-then-$b$ or as $b$-then-$a$. – Brian M. Scott May 21 '12 at 1:09
Here is my question, rephrased: we're given some $a$ and some $b$, mapping to a specific $z_a$ and $z_b$. We don't know that the two ($z$'s) don't both belong to $X$, or $Y$. Given only the ordered pairs, how do we know which $z$-value goes in which coordinate? (Thanks, by the way.) – Chris May 21 '12 at 1:18
@user1296727: But we do know which of $z_a$ and $z_b$ is which. As I said above, an indexed family is really a function: $z$ is really $\{\langle a,z_a\rangle,\langle b,z_b\rangle$, with the condition that $z_a\in X$ and $z_b\in Y$. When you give me such a family, I see two ordered pairs. One has first component $a$, so I know that its second component is in $X$; the other has first component $b$, so I know that its second component is in $Y$. That was part of the definition of the set of indexed families making up $Z$. – Brian M. Scott May 21 '12 at 1:24

In Halmos's setting, we start with a function $g\colon \{a,b\}\to \{X,Y\}$ with $g(a)=X$ and $g(b)=Y$; this gives us the indexing of our pair.

We then want to establish a natural bijection between the set of all function $f\colon\{a,b\}\to X\cup Y$ with $f(a)\in g(a)$ and $f(b)\in g(b)$, and the set of ordered pairs $X\times Y$.

We can select an arbitrary order of $\{a,b\}$; this is equivalent to a bijection $h$ between $\{a,b\}$ and the set $\{0,1\}$ with its usual order. Using $h$, we can define the ordered pair as $(f(h(0)),f(h(1)))\in g(h(0))\times g(h(1))$.

Because there is a natural bijection between $X\times Y$ and $Y\times X$, it really does not matter whether our $h$ has $a\lt b$ or $b\lt a$; if it is the "wrong" order as far as what we are writing, composing with the natural bijection $Y\times X\to X\times Y$ gives a (natural) bijection between our set of functions and our set of pairs.

-
What is a "natural" bijection? – Chris May 21 '12 at 2:55
The term is somewhat informal in this setting, but it means the same thing as it means in the first line of the Halmos quote you give; basically, that any outside choices you might make in the definition of the function don't really change the outcome. If you are familiar with the isomorphisms between a finite dimensional vector space an its dual, the isomorphism $V\to V^*$ is not "natural" (it depends on a choice of basis), but the isomorphism $V\to V^{**}$ is natural (it does not depend on what basis we pick). – Arturo Magidin May 21 '12 at 2:58

(Basically going on what Brian wrote, I put this up for consideration.)

Given the set $Z$ of families $z$ mapping from $I = \{a,b\}$ to $X \cup Y$ such that $z_a \in X$ and $z_b \in Y$, for any element $z \in Z$, we define $f(z): Z \to X \times Y$ as follows:

Put $P(z) = \{p \in X\cup Y : \exists u \in z \hspace{2mm} \exists v \in u \hspace{2mm} \exists w \in u (\forall t(t \in v \iff t = a) \land a \in w \hspace{1.5mm} \land p \in w) \}$, and put $Q(z) = \{q \in X\cup Y : \exists u \in z \hspace{1.5mm} \exists v \in u \hspace{1.5mm} \exists w \in u (\forall t(t \in v \iff t = b) \land b \in w \hspace{1.5mm} \land q \in w) \}$. Then $z_a = \bigcup P(z)$, and $z_b = \bigcup Q(z)$; therefore we put

$f(z) = \{\{\bigcup P(z)\}, \{\bigcup P(z), \bigcup Q(z) \}\}$

-