I am working some problems out of my textbook for Discrete Mathematics II and was wondering if someone could tell me how to think through and go about solving the following type of problems (there are 10, this is 1 example):
Let $S=\{1,2,3,4\}$. With respect to the lexicographic order based on the usual "less than" relation, find all pairs in $S \times S$.
(a) less than $(2,3)$.
(b) greater than $(3,1)$.
In both, am I looking at everything less than $(2,3)$ as in: $\{\emptyset\}$, $\{1,1\}$, $\{1,2\}$, $\{1,3\}$, $\{1,4\}$, $\{2,1\}$, $\{2,2\}$?
You’re not looking for subsets of $S$ at all: you’re looking for elements of $S\times S$, the set being ordered lexicographically. I’ll do (a) completely; then you can use that as a model to try (b).
I’ll write $\prec$ for the lexicographic order on $S\times S$: if $\langle a,b\rangle,\langle c,d\rangle\in S\times S$,
For (a) you need to find the ordered pairs $\langle a,b\rangle\in S\times S$ such that $\langle a,b\rangle\prec\langle 2,3\rangle$. Go back to the definition: what does it mean to say that $\langle a,b\rangle\prec\langle 2,3\rangle$? It means that either $a<2$, or $a=2$ and $b<3$. The $a<2$ possibility gets you the pairs $\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle$, and $\langle 1,4\rangle$, and the $a=2$ and $b<3$ possibility gets you the pairs $\langle 2,1\rangle$ and $\langle 2,2\rangle$. Thus, the complete list of members of $S\times S$ that are less than $\langle 2,3\rangle$ in the lexicographic order is
$$\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle,\langle 1,4\rangle,\langle 2,1\rangle,\langle 2,2\rangle\;.$$