Exercise 5.5

Which of the following subsets of ω can be expressed as the cartesian product of subsets of ?

(a)
{xxi is an integer for all i}.
(b)
{xxi i for all i}.
(c)
{xxi is an integer for all i 100}.
(d)
{xx2 = x3}.

Answers

(a) Let X = {x ωxi is an integer for all i} and Y = ω, noting that . We claim that X = Y .

Proof. Consider any x X so that xi for any i +. It is then immediately obvious that x ω = Y . Hence X Y since x was arbitrary.

Now consider any x Y = ω so that xi for every i +. Again it is obvious by the definition of X that x X. Hence Y X since x was arbitrary. This shows that X = Y , as desired. □

(b) Let X = {x ωxi i for all i} and define Y i = {x x i} for i +, noting that obviously each Y i . Then let Y = Y 1 × Y 2 ×. We claim that X = Y .

Proof. First consider x X so that xi i for any i +. Then, for any i + clearly xi Y i by definition since xi i (and also xi ). Hence it follows that x = (x1,x2,) Y 1 × Y 2 × = Y . Since x was arbitrary, this shows that X Y .

Now suppose that x Y so that xi Y i for every i +. Consider any such i + so that xi Y i. Then, by definition xi i. Since i was arbitrary, this shows that x X by definition. Hence Y X since x was arbitrary so that X = Y . □

(c) Define X = {x ωxi is an integer for all i 100}. Also define Y i = when i < 100 and Y i = when i 100 (and i + for both), noting that of course Y i for either case. Let Y = Y 1 × Y 2 ×, and we claim that X = Y .

Proof. Consider any x X so that xi for all i 100. Suppose i +. If i < 100 then clearly xi = Y i since x ω. If i 100 then we have that xi = Y i. Hence in either case xi Y i so that x Y 1 × Y 2 × = Y since i was arbitrary. Since x was arbitrary, this shows that X Y .

Now consider any x Y and any i + where i 100. Then xi Y i = so that xi is an integer. From this it follows that x X by definition since obviously x ω (since xi Y i = when i < 100). Hence Y X since x was arbitrary. This completes the proof that X = Y . □

(d) We claim that X = {x ωx2 = x3} cannot be expressed as the cartesian product of subsets of .

Proof. Suppose to the contrary that there are Xi for i + where X = X1 × X2 ×. Let (a,a,) denote the sequence (x1,x2,) where xi = a for all i +. We then have that (1,1,) and (2,2,) are both in X since clearly x2 = x3 in both. Hence we have that 1 and 2 are both in Xi for every i + since X = X1 × X2 ×. Now define

yi = { 1i2 2 i = 2

for i +. Clearly y = (y1,y2,) X1 × X2 × since both 1 and 2 are in each Xi. However, it is also clear that yX by definition since y2 = 21 = y3. This contradicts the fact that X = X1 × X2 ×, which shows the desired result. □

User profile picture
2019-12-01 00:00
Comments