Principles of Mathematics in Operations Research

270 Solutions

Vx € R. Hence, ~ is not reflexive.

b) The statement

x ~ y =>• y ~ x, x ~ y and y ~ x => x ~ x; therefore, x ~ x, Vx € X

starts with the following assumption: Vx € X, 3y 6 X 3 x ~ y. If ~ is

symmetric and transitive and also has this additional property, then it is nec-

essarily reflexive. But if it does not have this property, then it is not reflexive.

9.8

a) We will make the proof by induction on n. If n = 1, X = X\ is countable by

hypothesis. Assume that the proposition is true for n = k, i.e. X\ x • • • x Xk

is countable. We will prove the proposition for n = k + 1, i.e. prove that

X = Xi x • • • x Xk x Xk+i is countable. Let Y = X\ x • • • x Xk- Then,

X = Y x Xk+i and Y is countable by the induction hypothesis. Then, the

elements of Y and Xk+i can be listed as sequences Y = {y\,y2, • • •}> ^Oc+i =

{xi,X2,...}. Now, for X = Y x Xk+i, we use Cantor's counting scheme and

see that X is countable.

b) Let X be countable. Then, X = {xi,X2,...}. Let A = {x2,X3,...}. Then, A
is a proper subset of X and / : X -> A defined by f(xn) = xn+i, n = 1,2,...
is one-to-one and onto. Thus, every countable set is numerically equivalent to
a proper subset of itself.

c) If / : X H-> Y is onto, then 3g : Y H4 X 3 f o g = idy. Moreover, g is
one-to-one. Let A — g(Y), then Ac X and g : Y H-> A is one-to-one and onto.
So, A ~ Y. Since A C X and X is countable, A is either finite or countable.
To see that A cannot be uncountable, we express X — {xi, X2,...}. If A is not
finite, then A = {xi 1 ,Xi 2 ,...}, where in's are positive integers and in ^ im
for n ^ m. Now, we define / : N »-» A by /(n) = Xjn. Then, / is one-to-one
and onto. If A is finite, A ~ y =^> Y" is finite; if A is countable, >1 ~ Y =*> Y
is countable. Thus, Y is at most countable.