Question

Define the following order on the set Z × Z: (a, b) < (c, d) if either a < c or a = c and b < d. This is referred to as the dictionary order on Z × Z.

(a) Show that there are infinitely many elements (x, y) in Z × Z satisfying the inequalities (0, 0) < (x, y) < (1, 1).

(b) Show that Axioms O1–O3 ( Trichotomy, Transitivity, Addition for inequalities) are satisfied for this ordering.

(c) Give an example that shows that Axiom O4 (Multiplication for inequalities) is not satisfied for this ordering.

(d) Is the well-ordering axiom satisfied for Z × Z with the dictionary order?

Answer 1

Problem (a)

Consider the set  .

As defined above, is a infinite set.

And for any element , we have,

The first inequality is because and .

The second inequality is because .

So, there are infinitely many elements such that .

-------------------------------------------------------------------------------------------------------------------------

Problem (b)

By definition, if , then either or .

In any case, we have, . Keeping this in mind, let us proceed.

Law of trichotomy: Let .

We want to prove that exactly one of , or holds.

Case 1:

Then we have, .

Case 2:

Then we have, .

Case 3:

Then we have, .

Case 4:

Then we have, .

These are all the cases. And at least one of , or holds.

Now, we have to show that both of them cannot hold together. Suppose on the contrary that

and

Since , .

Since , .

Together, we have, .

Therefore, and , so

And and , so,

which is a contradiction.

So, exactly one of , or holds.

Law of transitivity: Let .

We want to prove that if , and , then .

Since , .

Since , .

Together, we have, .

Case 1:

Then we have, .

Case 2:

Since and , we have .

Now, and , so

And and , so,

This implies that .

Together, we have, and .

So, .

Addition for inequalities:

Let .

We want to prove that if and , then

i.e, .

Since , .

Since , .

Together, we have, .

Case 1:

Then we have, .

Case 2:

Since equality holds, we must have, and .

Now, and , so

And and , so,

This implies that .

Together, we have, and .

So, .

-------------------------------------------------------------------------------------------------------------------------

Problem (c)

Multiplication for inequalities does not hold true.

Suppose it holds true.

Consider the elements

Sine , we have,

Since , we have,

This is a contradiction since but .

So, multiplication for inequalities does not hold true.

-------------------------------------------------------------------------------------------------------------------------

Problem (d)

No, well ordering axiom does not hold true.

Suppose on the contrary that it holds true.

i.e., every non-empty subset of has a least element.

Consider the subset .

As it is non-empty, it contains a least element, say, .

i.e.,

So, well ordering axiom does not hold true for with the dictionary order.