Question

To determine \(\left( {{Z^ + } \times {Z^ + }, \prec } \right)\) is a well ordered set.

Short answer

Hence, \(\left( {{Z^ + } \times {Z^ + }, < } \right)\)is a well ordered set.

Step-by-step solution

Given data

\( \prec \) is lexicographic order.

Concept used of set and subset

Set - A collection of objects. The specific objects within the set are called the elements or members of the set

Set\(A\)is said to be a subset of Set\(B\)if all the elements of Set\(A\)are also present in Set\(B\). In other words, set\(A\)is contained inside Set\(B\).

Prove for well ordered set

We need to show that every non empty subset of \({Z^ + } \times {Z^ + }\)has a least element under lexicographic order. Given such a subset \(S\), look at the set \({S_1}\) of positive integers that occur as first coordinates in elements of \(S\). Let \({m_1}\) be the least element of \({S_1}\), which exists since \({Z^ + }\)is well ordered under \( \le \). Let \({S^\prime }\) be the subset of \(S\) consisting of those pairs that have \({m_1}\) as their coordinate. Thus, \({S^\prime }\) is clearly non empty, and by the definition of lexicographic order every element of \({S^\prime }\) is less than every element in \(S - {S^\prime }\). Now let \({S_2}\) be the set of positive integers that occur as second coordinates in elements of \({S^\prime }\), and let \({m_2}\) be the least element of \({S_2}\). Then clearly the element \(\left( {{m_1},{m_2}} \right)\) is the least element of \({S^\prime }\) and hence is the least element of \(S\). Hence, \(\left( {{Z^ + } \times {Z^ + }, < } \right)\)is a well ordered set.