Need help proving this lexicographic relation is a partial order

Question

Suppose $R$ is a partial order on $A$ and $S$ is a partial order on $B$. Call $L$ a Relation on $A \times B$ s.t.

$L = \{(a, b),(a'b') ∈ (A \times B) \times (A \times B) | aRa'$, $and$ $if a = a' then$ $bSb'\}$.

Prove $L$ is a partial order on $A \times B$.

I've written a proof but I believe it's flawed:

• Reflexivity

  Suppose $R$, $S$, defined as above. Let $a$, $b$ be arbitrary elements and $(a,b) ∈ A \times B$. This is to say that $a ∈ A$ and $b ∈ B$. Since $R$ is partial on $A$, $(a,a) ∈ R$ and since $S$ is partial on $B$, $(b,b) ∈ S$. By the definition of $L$, $((a,b),(a,b)) ∈ L$ and since $a$, $b$ arbitrary, $L$ must be reflexive.

• Transitivity

  Let the ordered pairs $(a,b)$, $(a',b')$, and $(c,d)$ be each in $A \times B$, where $a$, $b$, $a'$, $b'$, $c$, and $d$ are arbitrary. By definition, $((a,b),(a',b')) ∈ L$ and $((a'b'), (c,d)) ∈ L$. This further implies that $aRa'$ and $a'Rc$. Since $R$ is transitive, $aRc$. It also follows that because $R$ is partial, $aRa'$ and $a'Rc$ imply that $a = c$ and hence, by the definition of $L$, $bSb'$ and $b'Sd$. $S$ is transitive, so $bSd$. Therefore, since $(a,c) ∈ R$ and $(b,d) ∈ S$, $((a,b),(c,d)) ∈ L$. Thus $L$ is transitive.

• Antisymmetry

  Assume $a$, $b$, $a'$, $b'$ arbitrary. Let $(a, b)$ and $(a', b')$ be each in $A \times B$. By definition of $L$, $((a, b)$, $(a', b')) ∈ L$ and $((a',b')$, $(a,b)) ∈ L$. Because $R$ is a partial order on $A$, it follows that $aRa'$ and $a'Ra$, which means that $a = a'$. Thus by the same reasoning, $b = b'$. So $((a,b), (a',b')) = ((a',b'), (a, b))$. Since $a$, $a'$, $b$, $b'$ were arbitrary, $L$ can be called antisymmetric.

My main concern lies in the transitivity proof, where I conclude that $a =c$. Can I do that?

Answer 1

Your argument for reflexivity isn’t precisely wrong, but it’s written a bit clumsily. First, what you need to prove is that if $x$ is an arbitrary element of $A\times B$, then $\langle x,x\rangle\in L$, so you should be starting with an arbitrary $\langle a,b\rangle\in L$, not with an arbitrary $a\in A$ and $b\in B$. The two have the same ultimate effect, but the logic of the argument is much clearer when the argument is written to emphasize what is actually being shown (rather than something equivalent to it). Secondly, you didn’t make clear why it’s important that $b\mathrel{S}b$: this is because $a=a$, so that we have to invoke the ‘and if $a=a'$ then $b\mathrel{S}b'$’ part of the definition of $L$.

Because expressions like $\big\langle\langle a,b\rangle,\langle a',b'\rangle\big\rangle\in L$ are a bit unwieldy, I’ll write $\langle a,b\rangle\mathrel{L}\langle a,b\rangle$ instead.

Let $\langle a,b\rangle$ be an arbitrary element of $A\times B$; we need to show that $\langle a,b\rangle\mathrel{L}\langle a,b\rangle$. By definition this will be the case if $a\mathrel{R}a$ and (since $a=a$) $b\mathrel{S}b$. Since $R$ and $S$ are reflexive, $a\mathrel{R}a$ and $b\mathrel{S}b'$, so $\langle a,b\rangle\mathrel{L}\langle a,b\rangle$ by the definition of $L$, which is therefore reflexive.

There are definitely problems with your argument for antisymmetry. You write:

Assume $a,b,a',b'$ arbitrary. Let $(a,b)$ and $(a',b')$ be each in $A\times B$. By definition of $L$, $((a,b),(a',b'))\in L$ and $((a',b'), (a,b))\in L$.

First, here again you should be starting with elements of $A\times B$, not with elements of $A$ and $B$. More important, they cannot be arbitrary, since you’re interested only in one particular case, namely, the one in which each of them is in the relation $L$ to the other. Thus, you need to start with something like this:

Let $\langle a,b\rangle,\langle a',b'\rangle\in A\times B$ be such that $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$ and $\langle a',b'\rangle\mathrel{L}\langle a,b\rangle$; we need to show that $\langle a,b\rangle=\langle a',b'\rangle$. Since $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$, we know that $a\mathrel{R}a'$, and since $\langle a',b'\rangle\mathrel{L}\langle a,b\rangle$, we also know that $a'\mathrel{R}a$. The relation $R$ is antisymmetric, so $a=a'$.

Now $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$ and $a=a'$, so by the definition of $L$ we know that $b\mathrel{S}b'$. Similarly, from the fact that $\langle a',b'\rangle\mathrel{L}\langle a,b\rangle$ and $a'=a$ we know that $b'\mathrel{S}b$. Finally, $S$ is antisymmetric, so $b=b'$, and hence $\langle a,b\rangle=\langle a',b'\rangle$, as desired. This shows that $L$ is antisymmetric.

Your argument for transitivity starts out better, since you begin by choosing elements of $A\times B$ instead of their components, but your choices are not arbitrary, since transitivity imposes a requirement only on some triplets of elements. However, you were right to suspect that there might be problems with it: you haven’t correctly taken into account the definition of $L$. The key point is that in deciding whether $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$ for some $\langle a,b\rangle,\langle a',b'\rangle\in A\times B$, the second components $b$ and $b'$ come into play if and only if $a=a'$. When $a\ne a'$, they’re irrelevant, and when $a=a'$, they’re crucial.

Let $\langle a,b\rangle,\langle a',b'\rangle,\langle c,d\rangle\in A\times B$ be such that $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$ and $\langle a',b'\rangle\mathrel{L}\langle c,d\rangle$; we want to show that $\langle a,b\rangle\mathrel{L}\langle c,d\rangle$. Since $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$, we know that $a\mathrel{R}a'$, and since $\langle a',b'\rangle\mathrel{L}\langle c,d\rangle$, we know that $a'\mathrel{R}c$. $R$ is transitive, so $a\mathrel{R}c$. If $a\ne c$, we can immediately conclude that $\langle a,b\rangle\mathrel{L}\langle c,d\rangle$, as desired. If $a=c$, however, we cannot, because in that case we must also show that $b\mathrel{S}d$ in order to conclude that $\langle a,b\rangle\mathrel{L}\langle c,d\rangle$.

Suppose, then, that $a=c$. We’ve already seen that $a\mathrel{R}a'$ and $a'\mathrel{R}c=a$, so the antisymmetry of $R$ implies that $a=a'$. Combining this with the hypothesis that $\langle a,b\rangle\mathrel{L}\langle a',b'\rangle$, we conclude that $b\mathrel{S}b'$. (Note: When $a\ne a'$ there is no requirement that this to be true; that’s why we had to show that $a=a'$ before drawing this conclusion about $b$ and $b'$.) Similarly, $\langle a',b'\rangle\mathrel{L}\langle c,d\rangle$, and $a'=c$, so $b'\mathrel{S}d$. Now at last we can use the transitivity of $S$ to conclude that $b\mathrel{S}d$ and hence that $\langle a,b\rangle\mathrel{L}\langle c,d\rangle$, as desired.

Thus, in all cases $\langle a,b\rangle\mathrel{L}\langle c,d\rangle$, and $L$ is transitive.

And now that we’ve shown that $L$ is reflexive, antisymmetric, and transitive, we’re entitled to say that $L$ is a partial order on $A\times B$.