Consider the divides relation on A = {1, 2, 4, 8, .... 2^n}, where n is a nonnegativee integer. Prove that?

Question

this relation is a total order on A. First prove that divides is a partial order on A, for some n .

Answer 1

A = {2^k: k∈ℤ ∧ 0≤k≤n}

First, we show that | is a partial order. There are three things to check: reflexivity, transitivity, and antisymmetry.

Reflexivity: let x∈A. Then x = 1*x, so x | x. Since this is true for all x∈A, | is reflexive.

Transitivity: let x, y, z∈A. Suppose x | y and y | z. Then y=jx and z=ky for some integers k and j. Then z = ky = k(jx) = (kj)x, and kj is an integer, so x | z. Therefore, ∀x, y, z∈A, (x | y ∧ y | z) ⇒ x | z, so | is reflexive

Antisymmetry: Let x, y∈A. Suppose x | y and y | x. Then y=kx and x=jy for some integers k and j. Now, since all the elements of A are positive, x and y are both positive thus both x/y and y/x are positive. Since x=jy, j=y/x and since y=kx, k=y/x, so j and k are both positive. Since they are integers, both j and k are greater than or equal to 1. However, j = y/x = 1/(x/y) = 1/k, so if k>1, j<1 -- a contradiction. Therefore k=1, so y=1*x = x. Therefore, ∀x, y∈A, (x | y ∧ y | x) ⇒ x=y, so | is antisymmetric

(BTW, that mess about showing j and k are both positive was necessary. | is not antisymmetric on integers in general, since -1 | 1 and 1 | -1, but 1≠-1).

Having verified that | is a partial order, we now show that it is total -- i.e. ∀x, y∈A, x | y ∨ y | x. Suppose x, y∈A -- then x=2^j and y=2^k, where j and k are both nonnegative integers. Now, either j≥k or k≥j. Suppose j≥k, then j-k is a nonnegative integer, so 2^(j-k) is an integer. Then note that since y*2^(j-k) = 2^k * 2^(j-k) = 2^j = x, y | x. Conversely, suppose k≥j -- then k-j is a nonnegative integer, so 2^(k-j) is an integer. So x*2^(k-j) = 2^j * 2^(k-j) = 2^k = y, so x | y. In either case, either x | y or y | x, so the relation | is total on A.

Therefore, | is a total order on A.