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\}$.

  • $\begingroup$ Awsome! Thanks! $\endgroup$ – user36546 Sep 24 '12 at 4:51
  • $\begingroup$ Does author assume every element of $X$ and $Y$ is always a set? becasue he writes families like $z$ indexed by ${a, b}$ such that $z_a \in X$ and $z_b \in Y$ and we know every family is a collection of sets so $z_a$ and $z_b$ are sets $\endgroup$ – Omid Sadeghi Jan 17 at 19:43
  • 1
    $\begingroup$ @OmidSadeghi: If you’re working in $\mathsf{ZF}$ set theory, everything is a set. (In some other axiomatizations of set theory you also have proper classes.) In everyday mathematical usage you can have a family of any kinds of mathematical objects, so it doesn’t matter what the elements of $X$ and $Y$ are. $\endgroup$ – Brian M. Scott Jan 17 at 19:47
  • 1
    $\begingroup$ @brian-m-scott I read the Families chapter of the book again and now I think when Halmos writes about families, he means families of anything. I wrongly thought the chapter is only about families of sets. If we have families of anything then my last comment is irrelevant. And by the way, I have read before that in axiomatic set theory everything is a set but I think in Halmos's book this is not true at least until the Familes chapter that I have read. $\endgroup$ – Omid Sadeghi Jan 17 at 20:12

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)\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy