0
$\begingroup$

I know the definitions of these two terms, but I saw this question in one of my former exams from "Discrete math". The question stated :

"What is the difference between product order and lexicographic order, and give an example that shows the difference?"

Could someone clear this out for me, I would be very grateful.

$\endgroup$
2
$\begingroup$

Suppose that $\le$ is a linear order on a set $X$. The lexicographic order on $X\times X$ is a linear order; you should try to prove this if you’ve not already done so or seen a proof of it. The product order on $X\times X$ is not a linear order, provided that $X$ has at least two elements. To see this, let $x$ and $y$ be distinct elements of $X$, and let $\le_p$ be the product order on $X\times X$. Then $\langle x,y\rangle\not\le_p\langle y,x\rangle$, and $\langle y,x\rangle\not\le_p\langle x,y\rangle$, so the pairs $\langle x,y\rangle$ and $\langle y,x\rangle$ are not comparable with respect to $\le_p$.

$\endgroup$
0
$\begingroup$

Take the usual order on integers. In the lexicographical order: $\langle 1,4\rangle < \langle 2,4 \rangle$. In the product order these two elements are not comparable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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