1
$\begingroup$

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.

  • 0
    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$.2012-05-21

3 Answers 3

4

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

  • 0
    @user1296727: I’ve added yet more detail; see if this resolves your question.2012-05-21
2

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.

  • 0
    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).2012-05-21
0

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