# One-to-one correspondence between a Cartesian product and a set of families

On Halmos' "Naive Set Theory" he states that there's a natural one-to-one correpondence between a set $X \times Y$ 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.

Trying to come to grips with this, I used two families $z'$ and $z''$, with $Z=\{z', z''\}$.

In this example we could have

$$z'=\{(a, G_{a}), (b, G_{b})\} \ \ \ \ \ \ \ \ \text{and} \ \ \ \ \ \ \ \ z''=\{(a, H_{a}),(b, H_{b})\};$$

and then, $$z'_{a}=G_{a}\ ,\ \ \ z'_{b}=G_{b}\ ,\ \ \ z''_a=H_a\ ,\ \ \ z''_b=H_b.$$

I presumed in this case $$X=\{G_a, H_a \}$$ $$Y=\{G_b, H_b \}$$ $$X\times Y=\{(G_a, G_b), (G_a, H_b), (H_a, G_b), (H_a, H_b)\}.$$

But, $f(z')=(G_a, G_b)$ and $f(z'')=(H_a, H_b)$ and thus, $f$ wouldn't be a one-to-one correspondence. Where's the mistake? Thanks.

If it'd be of any help, there's a link to another question on this section.

-

It appears to me that you’ve misunderstood what Halmos is saying. The givens are $X$ and $Y$, so any example should start with them: both $Z$ and the function $f$ are constructed from $X$ and $Y$. Here’s an example.

Let $X=\{0,1,2\}$ and $Y=\{3,4\}$, so that $$X\times Y=\Big\{\langle0,3\rangle,\langle0,4\rangle,\langle1,3\rangle,\langle1,4\rangle,\langle2,3\rangle,\langle2,4\rangle\Big\}\;.$$

A pair indexed by $\{a,b\}$ is formally a set of the form $\big\{\langle a,x\rangle,\langle b,y\rangle\big\}$; the set $Z$ of all such families is then the set whose elements are:

\begin{align*} &\big\{\langle a,0\rangle,\langle b,3\rangle\big\},\big\{\langle a,0\rangle,\langle b,4\rangle\big\},\\ &\big\{\langle a,1\rangle,\langle b,3\rangle\big\},\big\{\langle a,1\rangle,\langle b,4\rangle\big\},\\ &\big\{\langle a,2\rangle,\langle b,3\rangle\big\},\big\{\langle a,2\rangle,\langle b,4\rangle\big\}\;. \end{align*}

The function $f:Z\to X\times Y$ then does the following:

\begin{align*} &\big\{\langle a,0\rangle,\langle b,3\rangle\big\}\mapsto\langle0,3\rangle\\ &\big\{\langle a,0\rangle,\langle b,4\rangle\big\}\mapsto\langle0,4\rangle\\ &\big\{\langle a,1\rangle,\langle b,3\rangle\big\}\mapsto\langle1,3\rangle\\ &\big\{\langle a,1\rangle,\langle b,4\rangle\big\}\mapsto\langle1,4\rangle\\ &\big\{\langle a,2\rangle,\langle b,3\rangle\big\}\mapsto\langle2,3\rangle\\ &\big\{\langle a,2\rangle,\langle b,4\rangle\big\}\mapsto\langle2,4\rangle\;. \end{align*}

This is the desired bijection.

The point that he’s making is that there’s really not much difference between an ordered pair and a function whose domain is a two-element set: each gives a way of representing a pair of objects in a manner that allows us to distinguish one from the other, even when they’re the ‘same’, as in an ordered pair $\langle1,1\rangle$ and a function $\big\{\langle a,1\rangle,\langle b,1\rangle\big\}$.

-
Awsome! Thanks! – Fred Sep 24 '12 at 4:51

The mistake is that $Z$ doesn't contain all the possible $\{a,b\}$-indexed families with $a$-element in $X$ and $b$-element in $Y$. We need to include also $z'''=\{(a,H_a),(b,G_b)\}$ and $z''''=\{(a,G_a),(b,H_b)\}$.

-