Ex-1:
(a) Prove that .
Its clear that and and also A is closed under f, hence . So
Prove that is closure of B under f.
Step-I: Prove that
Since for every , . Hence
Step-II: Prove that is closed under f.
Let x be an arbitrary element of . Let C be arbitrary element of . Then and hence . Since C is arbitrary, so and hence . Thus is closed under f.
Step-III: 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 . Then and hence . So is indeed the smallest.
From Step I, II and III its clear that is closure of B under f.
(b) Let C =
Step-I: prove that
Since and , hence
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. . Then . Then . 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. and D is closed under f. We'll prove by induction that for any positive number n, and hence .
Base case: for n = 1
, so
Induction step: Suppose n is arbitrary positive integer and .
Let y be arbitrary element of . Then we can choose some s.t. f(x) = y. Since , so and hence . Then . Since y is arbitrary, so .
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, = B = {0}
= {f(0)} = {1}
= {f(1)} = {2}
= {f(2)} = {3}
...
closure of {0} under f is = {0,1,2,3,...} = Set of all natural numbers.
Ex-3: We'll imitate the reasoning followed in ex-1(a).
Let = {C | and , C is closed under f}
Step-I: prove that
and and for every function f in , A is closed under f. Hence . Thus
So, is defined. We will prove that is closure of B under .
Step-II: Prove that
Since for every , . Hence
Step-III: Prove that is closed under .
Let x be an arbitrary element of . Let C be arbitrary element of . Then . Let f be arbitrary element of . Then . Since C is arbitrary, so and hence . Thus is closed under f. Since f is arbitrary, so is closed under .
Step-IV: is smallest set closed under s.t. B is its subset.
Let C be some set s.t. C is closed under and . Then and hence . So is indeed the smallest.
From Step I, II, III and IV its clear that is closure of B under . Hence closure of B under 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 , so
Induction step: let n be arbitrary positive integer and
Now, Let (x,y) be arbitrary element of A X A s.t.
Since = , so . Then we can choose some s.t. and . Then and . Then . Then . Since (x,y) is arbitrary, so .
Ex-8:
(a) Let n be arbitrary positive integer.
, so using result of ex-7, . Similarly, . Thus . 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 and = {(1,4)}
(b) , so . Similarly, . Thus . 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)}
= {(1,4)}
= {(2,4)}
= {(1,4), (2,4)}
= {(1,2), (2,4), (2,3), (3,4)}
= {(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
and
Then . Then . 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 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 . Thus .
Induction step: Let n be a positive integer and = { | there is an R-path from a to b of length n}
() Let (a,b) be arbitrary element of . Then . Then we can choose some c s.t. and .
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 {(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 {(n+1,b)} is an R-path from a to c of length n. So, by induction hypothesis, . Also, , so . Thus . Hence
(b) From theorem 6.5.2,
() Let (a,b) be arbitrary element of S. Then we can choose some positive integer n s.t. . 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 . Then
Ex-11:
(a) We'll prove it by induction.
Base case: n = 1, Let (a,b) be arbitrary element of . Then and . 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 = { | there is a simple R-path from a to b of length atmost n}
Let (a,b) be arbitrary element of . Then and . then . Then we can choose some s.t. and . By induction hypothesis, we can find some simple R-path from a to c of length m s.t. .
Now let us define g = f {(m+1,b)}. Consider following cases..
case#1:
Then g is one-to-one and also a R-path from a to b of length m+1 and
case#2:
Then we can choose some 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 .
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 =
() Let (a,b) be arbitrary element of . Then and . Then we can choose some positive integer n s.t. . 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 and hence and so . Also from ex-10(a) and hence . Since and , so .
Ex-12:
(a) Since d(a,b) = n, so by definition of the distance as given in ex-9, and there don't exist any number m smaller than n s.t. .
Also since , so . Then . 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), . 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 . 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 .
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), .
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),
Thus . And then . Since d(a,a) = n, so . Then .
Using above reasoning by switching roles of f(i) and f(j), we can come to the conclusion that .
Since and , so . Since i and j are arbitrary positive integers smaller than n, so
Ex-13: Let be a simple R-path of length n where = {0,1,2,3,...,n}
Then size of Dom(f) = Size of = n+1
size of Ran(f) = size of A = m
Since f is one-to-one, so . Then . 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. .
Let (a,b) be arbitrary element of . 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 . Since (a,b) is arbitrary, so
Since n is arbitrary, so
So,
Then S = =
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. , (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. , (i+2)|(y+i)
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment