1
$\begingroup$

Q: Show that the lexicographic ordering $≤_l$ on $A\times B$ for $A$ well ordered by $≤$ and $B$ well-ordered by $≤'$ is well-ordered.

A: I have previously shown that this lexicographic ordering is totally ordered, and I am aware that any finite totally ordered set is well-ordered, but $A$ and $B$ aren't necessarily finite, so I'm not sure how to show that any subset of $A\times B$ has a least element. Any help is appreciated.

$\endgroup$
  • $\begingroup$ Go component by component. If $C\subset A\times B$ is non-empty, then its projection onto the first component is a non-empty subset of $A$. Therefore, this projection has a minimum $a$. Take the subset of $C$ of elements that have $a$ as their first component. This set is non-empty. Look at the projection onto the second component. This is a non-empty subset of $B$, which therefore, has a minimum $b$. Then $(a,b)\in C$. Show that $(a,b)$ is the minimum of $C$, and therefore $C$ has a minimum. $\endgroup$ – user647486 Apr 28 at 5:18
  • $\begingroup$ @user647486. Let A = {0,1} = B, C = { (0,1), (1,0), (1,1) }. Notice that (0,0) is not the minimum as you claimed. $\endgroup$ – William Elliot Apr 28 at 6:28
  • $\begingroup$ @WilliamElliot Run the algorithm that I said. Notice why you ran it wrong if you got $(0,0)$ $\endgroup$ – user647486 Apr 28 at 6:30
1
$\begingroup$

Let $\pi_A: A \times B \to A$ and $\pi_B: A \times B \to B$ be the projection maps.

Suppose $C \subseteq A \times B$ is non-empty, then $\pi_A[C]$ is a non-empty subset of $A$ and so has a $\le$-minimal element $a_0 \in \pi_A[C]$.

Then the set $(\{a_0 \} \times B) \cap C$ (all points of $C$ with first coordinate equal to $a_0$) is also non-empty and $\pi_B[(\{a_0 \} \times B) \cap C]$ has a $\le'$-minimum $b_0 \in B$.

Claim: $(a_0, b_0) = \min(C)$. To see this, let $(a,b)\in C$ be arbitrary. Then $a \in \pi_A[C]$ and so $a_0 \le a$ by minimility of $a_0$ in that set. If $a_0 < a$ we are done, as then $(a_0, b_0) \le_l (a,b)$ by the definition of the lexicographic order. So it remains to consider the case $a_0=a$, but then $(a,b) \in (\{a_0 \} \times B) \cap C$ and so $b \in \pi_B[(\{a_0 \} \times B) \cap C]$ and $b_0 \le' b$ by minimality of $b_0$ again. Now, from $a_0 \le a$ and $b_0 \le' b$ we conclude $(a_0, b_0) \le_l (a,b)$ again by the definition of $\le_l$. The claim has been shown.

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