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
    Thanks for the info. I was wondering if the definition for chain should be an exclusive or, not the typical inclusive or. For clarification, I have added some links to the Google Books copy of the text I am using. Also, the browser on the computer I am using was unable to render the mathematical notation on that nLab page. I'll try to access it from another computer tomorrow.2012-07-25
  • 0
    @Code-Guru: Unfortunately it seems that the exercise itself is on p. 12 or 13, which I can't access in Google Books. To the downvoter: What's wrong with this answer?2012-07-25
  • 0
    This is the second half of Exercise 1.2.11 on page 9. I apologize for not being entirely clear about where to look for it. (I am quite new to Google Books, so I don't know if there is a way to create a link to a specific line on a page.)2012-07-25
  • 0
    Also, I am having problems viewing the nLab page you linked. On two of the computers I have used, I get "[Math Processing Error]" instead of the mathematical notation.2012-07-25
  • 0
    @Code-Guru: [Math Processing Errors] are often (a) issues with connections to the MathJax or jsMath scripts the site is using or (b) issue with outdated scripts that are in your cache. Try to clear the cache in your web browser. If it doesn't work, [ask Andrew Stacey](http://ncatlab.org/nlab/show/Andrew+Stacey).2012-07-26
  • 0
    Correction: nLab doesn't run on MathJax or jsMath; it runs on a backend converter making TeX inputs into MathML. So I am not sure why you are seeing [Math Processing Error] all over the place.2012-07-26
  • 0
    @WillieWong Thanks for the info. I shot an email to Andrew Stacey to see if there is anything he can do on his end.2012-07-26
  • 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