Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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. –  Code-Guru Jul 25 '12 at 0:59
    
@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? –  joriki Jul 25 '12 at 1:37
    
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.) –  Code-Guru Jul 25 '12 at 13:44
    
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. –  Code-Guru Jul 25 '12 at 13:46
    
@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. –  Willie Wong Jul 26 '12 at 15:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.