Principles of Mathematics in Operations Research

Solutions 269

Claim: bx = y.

Proof: If not, bx < y or bx > y. If bx < y, by (d) Vn G N, bx+lln <

y, x + 1/n G A. Contradiction to the upper bound x > x + 1/n. If bx > y,

then Claim: if u < x, u G A. Proof: u < x => u is nor an upper bound of A.

3weA3u<w=>w-u>0^> bw~u > 1 =>• |^ > 1 =*- bw > bu. So, u G A.

y < bx => use (e) Vn G N 9 y < bx~1/n; so x + 1/n g" A. Thus, x < x - 1/n

(u < x =$> u 6 A), Contradiction.

Hence, bx = y.

g) Let b > 1, y > 0 be fixed. Suppose x ^ x' B bx — y = bx.

Without loss of generality, we may assume that , x < x' =$• x' — x > 0 =>

frx-x _^ fox > fjx ^ Contradiction.

9.5

a) Vz G F, z^2 y 0 (if z = 0 => z^2 = 0. If z y 0 => z^2 y 0). Assume that

x ^ 0 =$> x^2 y 0. If y^2 >: 0 =4> a;^2 + y^2 y 0, Contradiction. So x = 0, then

x^2 + y^2 = 0 + y^2 = 0 => y = 0.

b) Trivial by induction.

9.6 Note that "a ~ 6 if a — 6 is divisible by TO" is different from saying '<2^

is an integer", since the above one is defined for all fixed m G Z including

m = 0, but the latter one is defined for all TO jt 0.

a) a ~ a, Va G Z ( take k = 0). Then, ~ is reflexive.

a~6=4>3A:GZ9a — 6 = mk. Then, b — a = m(—k) where — k G Z. Thus,

b ~ a, yielding that ~ is symmetric.

a ~ & and 6 ~ c => 3fci,/c2 € Z 9 a — b = k\m, b — c = k^m. Then,

a — c — (fci + k2)m where &i + fo G Z. Hence, a ~ c, meaning that ~ is

transitive.

Thus, ~ is an equivalence relation.

b) Case 1: TO = 0. Then, a ~ b o- a = b. So, [a] = {o}, and the number of
equivalence classes is 00.
Case 2: TO ^ 0. Then, a~6o3fcGZ3a = 6 + TO/C. Hence,

[a] = {a, a + m, a — m, a + 2m, a — 2m, • • • } ,

and the number of distinct equivalence classes is \m.

9.7
a) x ~ y =>• a; G [0,1] and ?/ G [0,1] =>• y ~ x (i.e. symmetric).
a; ~ y and y ~ z =$• x G [0,1] and y G [0,1] and z G [0,1] => x ~ 2: (i.e.
transitive).
If x ^ [0,1], then x ~ x does not hold. For reflexibility we want x ~ x to hold