Take the 2-minute tour ×
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.

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|improve this question

2 Answers 2

up vote 2 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|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|improve this answer

Your Answer

 
discard

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.