Given any it is easy to show that there are a finite number of such that x < y. Now, given any there are an infinite number of such that x < y. For example, let y = 3 x 2. The set of x such that x < y is all elements below y or to the left of y. So we have 3 x 1 and 3 x 0 are less than y, but we also have the sets , , and , all three of which are countably infinite.

Another way to approach this is to look at the sets N and N x N in terms of elements that have immediate predecessors. All elements in N except 0 have immediate predecessors. However all elements in N x N of the form y x 0 (an infinite number of them) have no immediate predecessors. Thus there is no bijection between the two sets and thus they don't have the same order type.

-Dan