Tuesday, July 13, 2010

how to prove it - ch6, sec6.5(Closures Again) ex

Ex-1:
(a) Prove that F.
Its clear that BA and AA and also A is closed under f, hence AF. So F

Prove that F is closure of B under f.

Step-I: Prove that BF
Since for every CF, BC. Hence BF

Step-II: Prove that F is closed under f.
Let x be an arbitrary element of F. Let C be arbitrary element of F. Then xC and hence f(x)C. Since C is arbitrary, so CFf(x)F and hence f(x)F. Thus F is closed under f.

Step-III: F is smallest set closed under f s.t. B is its subset.
Let C be some set s.t. C is closed under f and BC. Then CF and hence FC. So F is indeed the smallest.

From Step I, II and III its clear that F is closure of B under f.

(b) Let C = nZ+Bn

Step-I: prove that BC
Since B1=B and B1C, hence BC

Step-II: prove that C is closed under f
Let x be arbitrary element of C. Then we can choose some positive integer n s.t. xBn. Then f(x)Bn+1. Then f(x)C. Thus C is closed under f.

Step-III: prove that C is smallest set closed under f s.t. B is its subset
Let D be some other set s.t. BD and D is closed under f. We'll prove by induction that for any positive number n, BnD and hence CD.

Base case: for n = 1
B1=B, so B1D

Induction step: Suppose n is arbitrary positive integer and BnD.

Let y be arbitrary element of Bn+1. Then we can choose some xBn s.t. f(x) = y. Since BnD, so xD and hence f(x)D. Then yD. Since y is arbitrary, so Bn+1D.

From the three steps above, its proven that C is closure of B under f.


Ex-2: Using the terminology from ex-1, B = {0}.
Then, B1 = B = {0}
B2 = {f(0)} = {1}
B3 = {f(1)} = {2}
B4 = {f(2)} = {3}
...

closure of {0} under f is nZ+Bn = {0,1,2,3,...} = Set of all natural numbers.


Ex-3: We'll imitate the reasoning followed in ex-1(a).

Let H = {C | BCA and fF, C is closed under f}

Step-I: prove that H
BA and AA and for every function f in F, A is closed under f. Hence AH. Thus H

So, H is defined. We will prove that H is closure of B under F.

Step-II: Prove that BH
Since for every CH, BC. Hence BH

Step-III: Prove that H is closed under F.
Let x be an arbitrary element of H. Let C be arbitrary element of H. Then xC. Let f be arbitrary element of F. Then f(x)C. Since C is arbitrary, so CHf(x)H and hence f(x)H. Thus H is closed under f. Since f is arbitrary, so H is closed under F.

Step-IV: H is smallest set closed under F s.t. B is its subset.
Let C be some set s.t. C is closed under F and BC. Then CH and hence HC. So H is indeed the smallest.

From Step I, II, III and IV its clear that H is closure of B under F. Hence closure of B under F exists.


Ex-4,5,6: I could not solve ex-4 and 5,6 are dependant on it. TODO


Ex-7: We'll use induction to prove it.

Base case: n = 1, Since RS, so R1S1

Induction step: let n be arbitrary positive integer and RnSn

Now, Let (x,y) be arbitrary element of A X A s.t. (x,y)Rn+1

Since Rn+1 = RnR, so (x,y)RnR. Then we can choose some zA s.t. (x,z)R and (z,y)Rn. Then (x,z)S and (z,y)Sn. Then (x,y)SnS. Then (x,y)Sn+1. Since (x,y) is arbitrary, so Rn+1Sn+1.


Ex-8:
(a) Let n be arbitrary positive integer.
RSR, so using result of ex-7, (RS)nRn. Similarly, (RS)nSn. Thus (RS)nRnSn. However, the two are not equal as is evident from following counterexample.
A = {1,2,3,4}
R = {(1,2), (2,4)}
S = {(1,3), (3,4)}

Then (RS)2= and R2S2 = {(1,4)}

(b) R(RS), so Rn(RS)n. Similarly, Sn(RS)n. Thus RnSn(RS)n. However, the two are not equal as is evident from following counterexample.
A = {1,2,3,4}
R = {(1,2), (2,4)}
S = {(2,3), (3,4)}

R2 = {(1,4)}
S2 = {(2,4)}

R2S2 = {(1,4), (2,4)}

RS = {(1,2), (2,4), (2,3), (3,4)}
(RS)2 = {(1,4),(2,4),(1,3)}

clearly the two are not equal.


Ex-9:
(a) Let d(a,b) = n and d(b,c) = m. Then
(a,b)Rn and
(b,c)Rm

Then (a,c)RmRn. Then (a,c)Rm+n. Hence d(a,c) (m+n) = d(a,b) + d(b,c)

(b) TODO


Ex-10:
(a) We'll prove it by induction.

Base case: n = 1
() Let (a,b) be arbitrary element of R1 that is R. Let us define a function f s.t. f(0) = a and f(1) = b. Clearly, f is R-path from a to b of length 1. So it exists
() Let f be an R-path from a to b of length 1. Then (f(0),f(1))R. Thus (a,b)R.

Induction step: Let n be a positive integer and Rn = {(a,b)AxA | there is an R-path from a to b of length n}

() Let (a,b) be arbitrary element of Rn+1. Then (a,b)RRn. Then we can choose some c s.t. (a,c)Rn and (c,b)R.
By induction hypothesis we can choose f, a R-path from a to c of length n. Then f(0) = a and f(n) = c. Then f{(n+1),b} is an R-path from a to b of length n+1.
() Let f be an R-path from a to b of length n+1. Let f(n) = c. Then f\{(n+1,b)} is an R-path from a to c of length n. So, by induction hypothesis, (a,c)Rn. Also, (f(n),f(n+1))R, so (c,b)R. Thus (a,b)RRn. Hence (a,b)Rn+1

(b) From theorem 6.5.2, S=nZ+Rn

() Let (a,b) be arbitrary element of S. Then we can choose some positive integer n s.t. (a,b)Rn. Then, by result proved in part(a), there exists an R-path from a to b of length n.

() Let n be arbitrary positive integer. Let f be an R-path from a to b of length n. Then (a,b)Rn. Then (a,b)S


Ex-11:
(a) We'll prove it by induction.

Base case: n = 1, Let (a,b) be arbitrary element of R1\iA. Then (a,b)R and ab. Let us define f s.t. f(0) = a and f(1) = b. clearly f is an R-path from a to b of length 1 and also f is one-to-one

Induction step: Let n be arbitrary positive integer. Let Rn\iA = {(a,b)AxA | there is a simple R-path from a to b of length atmost n}


Let (a,b) be arbitrary element of Rn+1\iA. Then (a,b)Rn+1 and ab. then (a,b)R1Rn. Then we can choose some cA s.t. (a,c)Rn and (c,b)R. By induction hypothesis, we can find some simple R-path from a to c of length m s.t. mn.
Now let us define g = f {(m+1,b)}. Consider following cases..

case#1: bRan(f)
Then g is one-to-one and also a R-path from a to b of length m+1 and (m+1)(n+1)

case#2: bRan(f)
Then we can choose some km s.t. f(k) = b. Let us define another function h s.t. h(x) = f(x) for {1,k}. Then h is one-to-one and an R-path from a to b of length k and kn+1.

from both the cases, its clear that there exists a simple R-path from a to b of length atmost n+1.

(b) From theorem 6.5.2, S = nZ+Rn

() Let (a,b) be arbitrary element of S\iA. Then (a,b)S and ab. Then we can choose some positive integer n s.t. (a,b)Rn. Using result of part-a, there exists a simple R-path from a to b of length atmost n.

() Let f be a simple R-path from a to b of length n. Then f is one-to-one, and hence f(0)f(n) and hence ab and so (a,b)iA. Also from ex-10(a) (a,b)Rn and hence (a,b)S. Since (a,b)S and (a,b)iA, so (a,b)S\iA.


Ex-12:
(a) Since d(a,b) = n, so by definition of the distance as given in ex-9, (a,b)Rn and there don't exist any number m smaller than n s.t. (a,b)Rm.
Also since ab, so (a,b)iA. Then (a,b)Rn\iA. Then by result of ex-11(a) we can conclude that there is a simple R-path from a to b of length atmost n.
Now we will prove by contradiction that a simple R-path from a to b of length smaller than n can not exist and hence there is a simple R-path from a to b of length n.

Assume there is a simple R-path from a to b of length m and m < n. Then by ex-10(a), (a,b)Rm. But this is a contradiction as d(a,b) = n. Hence there is a simple R-path from a to b of length n.

(b) As d(a,a) = n, so (a,a)Rn. Then by ex-10(a), there is a R-path, let us call if f, from a to b of length n.
Then f(0) = a = f(n).

Let i and j be arbitrary positive integers smaller than n s.t. f(i) = f(j) = c where cA.

Since f(0) = a and f(i) = c, clearly f is an R-path of length i from a to c and hence by ex-10(a), (a,c)Ri.
Let us define h(x) = f(x+j). Then h(0) = f(j) = c and h(n-j) = f(n) = a. Clearly h is an R-path from c to a of length n-j and hence again by ex-10(a), (c,a)Rn-j
Thus (a,a)Rn-jRi. And then (a,a)Rn-j+i. Since d(a,a) = n, so (n-j+i)n. Then ij.

Using above reasoning by switching roles of f(i) and f(j), we can come to the conclusion that ji.

Since ij and ji, so i=j. Since i and j are arbitrary positive integers smaller than n, so i<nj<n(f(i)=f(j)i=j)


Ex-13: Let f:jnA be a simple R-path of length n where jn = {0,1,2,3,...,n}

Then size of Dom(f) = Size of jn = n+1
size of Ran(f) = size of A = m

Since f is one-to-one, so n+1m. Then n(m-1) . Thus n can atmost be m-1. Hence maximum possible length of a simple R-path is m-1.

Now we will prove that, for any n > m we can choose some l < m s.t. RnRl.
Let (a,b) be arbitrary element of Rn. Let d(a,b) = l. Then by ex-12(a), there is a simple R-path from a to b of length l. Then l < m. Since d(a,b) = l, hence (a,b)Rl. Since (a,b) is arbitrary, so RnRl
Since n is arbitrary, so n>ml<m(RnRl)

So, {Rnn>m}{Rn1nm}

Then S = {Rnn>1} = {Rn1nm}


Ex-14: Base case: n = 1, x = (1+1)! + 2 = 2! + 2 = 4
i can only be 0 in this case and clearly (i+2) = 2 divides (x+i) = 4

Induction step: Suppose n is an arbitrary positive integer, define x = (n+1)! + 2, s.t. for every i s.t. 0in-1, (i+2)|(x+i).

Let y = (n+2)! + 2. Let us consider following possible set of cases.

Case#1: i = n
Then (i+2) = (n+2) and (y+i) = (n+2)! + (n+2) = (n+2)[(n+1)!+1]. clearly (i+2)|(y+i)

Case#2: i < n
y+i = (n+2)! + 2 + i
= (n+2).(n+1)! + (2+i)
= (n+2)[(n+1)! + (2+i) - (2+i)] + (2+i)
= (n+2)[(n+1)! + (2+i)] - (n+2)(2+i) + (2+i)
= (n+2)(x+i) - [(n+2) - 1](2+i)
= (n+2)(x+i) - (n+1)(i+2)

by induction hypothesis, (i+2)|(x+i) and also (i+2)|[(n+1)(i+2)].

Thus (i+2)|(y+i)

Its clear from above cases that for every i s.t. 0in, (i+2)|(y+i)

No comments:

Post a Comment