3
$\begingroup$

Definitions: (From Categories for Types by Roy L. Crole.)

A preorder on a set $X$ is a binary relation $\leq$ on $X$ which is reflexive and transitive.

A preordered set $(X, \leq)$ is a set equipped with a preorder.... Where confusion cannot result, we refer to the preordered set $X$ or sometimes just the preorder $X$.

If $x \leq y$ and $y \leq x$ then we shall write $x \cong y$ and say that $x$ and $y$ are isomorphic elements.

Given two preordered sets $A$ and $B$, the point-wise order on the Cartesian product $A \times B$ is defined as $(a,b) \le (a',b')$ if and only if $a \le a'$ and $b \le b'$). The result is a preorder.

A subset $C$ of a preorder $X$ is called a chain if for every $x,y \in C$ we have $x \leq y$ or $y \leq x$.... We shall say that a preorder $X$ is a chain ... if the underlying set $X$ is such. (p.8)

Exercise:

Let $C$ and $C'$ be chains. Show that the set of pairs $(c, c')$, where $c \in C$ and $c' \in C'$, with the pointwise order is also a chain just in case at most one of $C$ or $C'$ has more than one element. (p.9)

Proposed Solution:

Suppose $C$ is a preorder with more than one element such that for every $a, b \in C, a \cong b$. Then by the definition given above, $C$ is a chain. Now suppose that $C'$ is a chain (without any additional properties). I claim that $C \times C'$ is a chain.

Proof

Let $(c_1, c'_1), (c_2, c'_2) \in C \times C'$. Then $c_1 \cong c_2$ and ($c'_1 \le c'_2$ or $c'_2 \le c'_1$). So $c_1 \le c_2$ and $c_2 \le c_1$. If $c'_1 \le c'_2$, then $(c_1, c'_1) \le (c_2, c'_2)$. If $c'_2 \le c'_1$, then $(c_2, c'_2) \le (c_1, c'_1)$.

Question: This seems to be a counterexample to the statement I am asked to prove. Is the question in error or am I missing something here?

1 Answers 1

2

Chains usually come up in the context of partial orders, and in that case your definition is equivalent to a chain being a totally ordered subset. This nLab page defines a chain as a totally ordered subset even in the context of preorders. And the statement you're asked to prove is true if chains are defined that way. So I wonder whether there's simply an "either" missing in the definition of a chain: "... for every $x,y\in C$ we have either $x\le y$ or $y\le x$."

  • 0
    @WillieWong I was able to view the n-Lab pages in Firefox9, but not IE9. Now I see that the definition of a chain as a totally ordered subset of a preorder means that $\le$ in the chain is antisymmetric. This means that whenever $x \le y$ and $y \le x$ then $x = y$. My proposed counterexample fails since $C$ is a chain with a single element.2012-07-26