prove 6 Prove that if R is a preorder on A then R R1 is an e

prove (6)

Prove that if R is a pre-order on A, then R R^-1 is an equivalence relation on A. Prove that the least upper bounds and the greatest lower bounds are unique whenever they exist. Prove that if R is a well order on A, then R is a total order which has the least upper bound, and the greatest lower bound properties. Prove that the notation lessthanorequalto on N is not continuous. Prove that the initial segments of N w.r.t. either lessthanorequalto or

Solution

Definition: The initial segment of the natural numbers determined by n

{0,1,2,…,n1}

is denoted N<n.

How to go about?

think about a natural way to associate each element with a natural number, and show that is a unique and order preserving way to do so.

Proof: Let us consider n. Let us note that it makes sense to consider the following functor on a restricted area. Then Seg n is set to Natural number.

A linear order is a partial order for which any two elements are comparable. So, we have to show that for any m and n in N, either m n or n m.

We prove this by induction on m.

Let P(m) be the assertion (n) (m n) (n m) ´ .

Since, for any n, 0 + n = n, it follows that 0 n, and so P(0) is true.

Let us assume P(m) is true for m = k.

We prove P(k 0 ) by first choosing any n. We must show k 0 n or n k 0 .

By the induction hypothesis, there are two cases, k n or n k:

(i) Suppose n k . Since k 0 = k + 1, we have k k 0 , so, by the transitivity of , n k 0 . So P(k 0 ) holds in this case.

(ii) Now suppose that k n.

Case (i) includes the case n = k, so we may assume k < n.

We shall show that k 0 n. Since k < n, it cannot be the case that n = 0.

Therefore, n has a unique predecessor p, i.e., n = p + 1.

The Inequality k < n = p + 1 is equivalent to k p, i.e., p = k + `, for some ` N.

Therefore, n = p + 1 = k + 1 + `, which implies k 0 n, as desired.

This completes the induction.

Strict linear ordering Often the fact that is a linear order is phrased in terms of <, which we then also call a (strict) linear ordering. In terms of <, the condition is phrased as follows: For any natural numbers m and n, exactly one of the following holds: m < n, m = n, or n < m.