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 don't need to order the coordinates, we just need to label them. One coordinate belongs to $a$, the other coordinate belongs to $b$. Whether we call the $a$-coordinate the "first" or the "second" is immaterial, all that matters is that the labels be distinct. Note that the labels are also attached to the sets, so that is how we can tell which item goes with which set: the item labeled with $a$ goes with the set that is also labeled with $a$.2012-05-21
  • 0
    But knowing the labels, how do we actually *place* the objects in order?2012-05-21
  • 0
    "Place them" *where*? What "order"? What "objects"? We are constructing a set of functions with certain properties; we are not placing objects anywhere, and there is no order. We can select an arbitrary ordering of $\{a,b\}$ in order to establish a bijection between the set of functions $f\colon\{a,b\}\to X\cup Y$ with $f(a)\in X$ and $f(b)\in Y$ and a set of ordered pairs as per the Cartesian product, either $X\times Y$ (if we select the order that has $g(a)$ first and $g(b)$ second), or as $Y\times X$. There is a natural bijection between $X\times Y$ and $Y\times X$, so doesn't matter which.2012-05-21
  • 0
    In answer to the first line, I meant to ask how we "place" the second coordinates of the ordered pairs of a family in the order of their Cartesian product; if $z_a$ comes from $X$, and $z_b$ from $Y$, how we create ($z_a$, $z_b$) to represent an element of $X \times Y$, as opposed to creating ($z_b$, $z_a$) to represent the same (which is not the right "order").2012-05-21
  • 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
    My question is precisely how we employ "ab" order. Even in the specific case of indexing by the naturals, I don't see how we "look into" the ordered pairs to see which one comes first.2012-05-21
  • 0
    @user1296727: I’m afraid that I don’t understand the difficulty. You can always tell which component of an ordered pair is first and which is second; that’s why it’s an **ordered** pair. When you map $z$ to $\langle z_a,z_b\rangle$, you’re implicitly deciding that the $a$-indexed member of $z$ is going to be considered the first coordinate, and the $b$-indexed member the second. As I indicated above, you could have made the opposite decision. The point of ordered pairs really isn’t the order: it’s the fact that the order lets you distinguish the members of the pair. ...2012-05-21
  • 0
    ... Indexing by a two-element set does exactly the same thing. If you then want to impose a specific order, in addition to being able to label one element the $a$-component and the other the $b$-component, you simply decide whether to order $\{a,b\}$ as $a$-then-$b$ or as $b$-then-$a$.2012-05-21
  • 0
    Here is my question, rephrased: we're given some $a$ and some $b$, mapping to a *specific* $z_a$ and $z_b$. We don't know that the two ($z$'s) don't both belong to $X$, or $Y$. Given only the ordered pairs, *how do we know which $z$-value goes in which coordinate*? (Thanks, by the way.)2012-05-21
  • 0
    @user1296727: But we do know which of $z_a$ and $z_b$ is which. As I said above, an indexed family is really a function: $z$ is really $\{\langle a,z_a\rangle,\langle b,z_b\rangle$, with the condition that $z_a\in X$ and $z_b\in Y$. When you give me such a family, I see two ordered pairs. One has first component $a$, so I know that its second component is in $X$; the other has first component $b$, so I know that its second component is in $Y$. That was part of the definition of the set of indexed families making up $Z$.2012-05-21
  • 0
    Okay, but formally: how do form Z, and then pass from its families into ordered pairs (as a procedure, in formal language)? I've understood your point from the start - we *define* the mapping conveniently, and take the "appropriate" second coordinates - but I've had trouble parsing this in set-theoretical terms.2012-05-21
  • 0
    @user1296727: I thought that I’d done that pointing out that formally his indexed families are functions from $\{a,b\}$ to $X\cup Y$ such that $f(a)\in X$ and $f(b)\in Y$. However, I’ve now expanded on this a bit in my answer; see if the expansion helps.2012-05-21
  • 0
    In your second line of math, I'm looking for something very explicit about how you go from the two inner ordered pairs to the last one. This is the part which I cannot phrase in ZFC, and which makes me uncomfortable. Although I understand the idea, I'm trying to find out how we can use explicit statements in ZFC to read off the second coordinates, in ab order, and put them into an ordered pair. (Something like how I read off the second coordinates into $\beta$ in my original post.)2012-05-21
  • 0
    @user1296727: We don't need to read them "in $ab$ order". We only need to know which elements "belongs" to $a$ and which element "belongs" to $b$. We begin with a map $g\colon \{a,b\}\to\{X,Y\}$ with $g(a)=X$ and $g(b)=Y$ (if we start with two sets and two distinct elements, we can construct the sets $\{X,Y\}$ and $\{a,b\}$ using the axiom of pairs, and we can pick any injective function $\{a,b\}\to\{X,Y\}$ for our $g$). We then define the product as the set of all function $f\colon \{a,b\}\to X\cup Y$ such that $f(a)\in g(a)$ and $f(b)\in g(b)$. The order of $ab$ is immaterial.2012-05-21
  • 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
    What is a "natural" bijection?2012-05-21
  • 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) \}\}$