Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 3 down vote accepted

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

share|cite|improve this answer
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)\}$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.