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

Ex-1:
(a) Prove that $F \neq \emptyset$.
Its clear that $B \subseteq A$ and $A \subseteq A$ and also A is closed under f, hence $A \in F$. So $F \neq \emptyset$

Prove that $\cap F$ is closure of B under f.

Step-I: Prove that $B \subseteq \cap F$
Since for every $C \in F$, $B \subseteq C$. Hence $B \subseteq \cap F$

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

Step-III: $\cap 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 $B \subseteq C$. Then $C \in F$ and hence $\cap F \subseteq C$. So $\cap F$ is indeed the smallest.

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

(b) Let C = $\cup_{n \in Z+} B_n$

Step-I: prove that $B \subseteq C$
Since $B_1 = B$ and $B_1 \subseteq C$, hence $B \subseteq C$

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. $x \in B_n$. Then $f(x) \in B_{n+1}$. Then $f(x) \in 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. $B \subseteq D$ and D is closed under f. We'll prove by induction that for any positive number n, $B_n \subseteq D$ and hence $C \subseteq D$.

Base case: for n = 1
$B_1 = B$, so $B_1 \subseteq D$

Induction step: Suppose n is arbitrary positive integer and $B_n \subseteq D$.

Let y be arbitrary element of $B_{n+1}$. Then we can choose some $x \in B_n$ s.t. f(x) = y. Since $B_n \subseteq D$, so $x \in D$ and hence $f(x) \in D$. Then $y \in D$. Since y is arbitrary, so $B_{n+1} \subseteq D$.

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_1$ = B = {0}
$B_2$ = {f(0)} = {1}
$B_3$ = {f(1)} = {2}
$B_4$ = {f(2)} = {3}
...

closure of {0} under f is $\cup_{n \in Z+}B_n$ = {0,1,2,3,...} = Set of all natural numbers.


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

Let $H$ = {C | $B \subseteq C \subseteq A$ and $\forall f \in F$, C is closed under f}

Step-I: prove that $H \neq \emptyset$
$B \subseteq A$ and $A \subseteq A$ and for every function f in $F$, A is closed under f. Hence $A \in H$. Thus $H \neq \emptyset$

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

Step-II: Prove that $B \subseteq \cap H$
Since for every $C \in H$, $B \subseteq C$. Hence $B \subseteq \cap H$

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

Step-IV: $\cap 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 $B \subseteq C$. Then $C \in H$ and hence $\cap H \subseteq C$. So $\cap H$ is indeed the smallest.

From Step I, II, III and IV its clear that $\cap 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 $R \subseteq S$, so $R^1 \subseteq S^1$

Induction step: let n be arbitrary positive integer and $R^n \subseteq S^n$

Now, Let (x,y) be arbitrary element of A X A s.t. $(x,y) \in R^{n+1}$

Since $R^{n+1}$ = $R^n \circ R$, so $(x,y) \in R^n \circ R$. Then we can choose some $z \in A$ s.t. $(x,z) \in R$ and $(z,y) \in R^n$. Then $(x,z) \in S$ and $(z,y) \in S^n$. Then $(x,y) \in S^n \circ S$. Then $(x,y) \in S^{n+1}$. Since (x,y) is arbitrary, so $R^{n+1} \subseteq S^{n+1}$.


Ex-8:
(a) Let n be arbitrary positive integer.
$R \cap S \subseteq R$, so using result of ex-7, $(R \cap S)^n \subseteq R^n$. Similarly, $(R \cap S)^n \subseteq S^n$. Thus $(R \cap S)^n \subseteq R^n \cap S^n$. 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 $(R \cap S)^2 = \emptyset$ and $R^2 \cap S^2$ = {(1,4)}

(b) $R \subseteq (R \cup S)$, so $R^n \subseteq (R \cup S)^n$. Similarly, $S^n \subseteq (R \cup S)^n$. Thus $R^n \cup S^n \subseteq (R \cup S)^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)}

$R^2$ = {(1,4)}
$S^2$ = {(2,4)}

$R^2 \cup S^2$ = {(1,4), (2,4)}

$R \cup S$ = {(1,2), (2,4), (2,3), (3,4)}
$(R \cup S)^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) \in R^n$ and
$(b,c) \in R^m$

Then $(a,c) \in R^m \circ R^n$. Then $(a,c) \in R^{m+n}$. Hence d(a,c) $\leq$ (m+n) = d(a,b) + d(b,c)

(b) TODO


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

Base case: n = 1
($\rightarrow$) Let (a,b) be arbitrary element of $R^1$ 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
($\leftarrow$) Let f be an R-path from a to b of length 1. Then $(f(0),f(1)) \in R$. Thus $(a,b) \in R$.

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

($\rightarrow$) Let (a,b) be arbitrary element of $R^{n+1}$. Then $(a,b) \in R \circ R^n$. Then we can choose some c s.t. $(a,c) \in R^n$ and $(c,b) \in 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 \cup${(n+1),b} is an R-path from a to b of length n+1.
($\leftarrow$) Let f be an R-path from a to b of length n+1. Let f(n) = c. Then $f \setminus${(n+1,b)} is an R-path from a to c of length n. So, by induction hypothesis, $(a,c) \in R^n$. Also, $(f(n),f(n+1)) \in R$, so $(c,b) \in R$. Thus $(a,b) \in R \circ R^n$. Hence $(a,b) \in R^{n+1}$

(b) From theorem 6.5.2, $S = \cup_{n \in Z+} R^n$

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

($\leftarrow$) Let n be arbitrary positive integer. Let f be an R-path from a to b of length n. Then $(a,b) \in R^n$. Then $(a,b) \in S$


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

Base case: n = 1, Let (a,b) be arbitrary element of $R^1 \setminus i_A$. Then $(a,b) \in R$ and $a \neq b$. 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 $R^n \setminus i_A$ = {$(a,b) \in AxA$ | there is a simple R-path from a to b of length atmost n}


Let (a,b) be arbitrary element of $R^{n+1} \setminus i_A$. Then $(a,b) \in R^{n+1}$ and $a \neq b$. then $(a,b) \in R^1 \circ R^n$. Then we can choose some $c \in A$ s.t. $(a,c) \in R^n$ and $(c,b) \in R$. By induction hypothesis, we can find some simple R-path from a to c of length m s.t. $m \leq n$.
Now let us define g = f $\cup$ {(m+1,b)}. Consider following cases..

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

case#2: $b \in Ran(f)$
Then we can choose some $k \leq m$ 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 $k \leq n+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 = $\cup_{n \in Z+} R^n$

($\rightarrow$) Let (a,b) be arbitrary element of $S \setminus i_A$. Then $(a,b) \in S$ and $a \neq b$. Then we can choose some positive integer n s.t. $(a,b) \in R^n$. Using result of part-a, there exists a simple R-path from a to b of length atmost n.

($\leftarrow$) Let f be a simple R-path from a to b of length n. Then f is one-to-one, and hence $f(0) \neq f(n)$ and hence $a \neq b$ and so $(a,b) \notin i_A$. Also from ex-10(a) $(a,b) \in R^n$ and hence $(a,b) \in S$. Since $(a,b) \in S$ and $(a,b) \notin i_A$, so $(a,b) \in S \setminus i_A$.


Ex-12:
(a) Since d(a,b) = n, so by definition of the distance as given in ex-9, $(a,b) \in R^n$ and there don't exist any number m smaller than n s.t. $(a,b) \in R^m$.
Also since $a \neq b$, so $(a,b) \notin i_A$. Then $(a,b) \in R^n \setminus i_A$. 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) \in R^m$. 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) \in R^n$. 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 $c \in A$.

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) \in R^i$.
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) \in R^{n-j}$
Thus $(a,a) \in R^{n-j} \circ R^i$. And then $(a,a) \in R^{n-j+i}$. Since d(a,a) = n, so $(n-j+i) \geq n$. Then $i \geq j$.

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

Since $i \geq j$ and $j \geq i$, so $i = j$. Since i and j are arbitrary positive integers smaller than n, so $\forall i < n \forall j < n (f(i)=f(j) \rightarrow i=j)$


Ex-13: Let $f:j_n \rightarrow A$ be a simple R-path of length n where $j_n$ = {0,1,2,3,...,n}

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

Since f is one-to-one, so $n+1 \leq m$. Then $n \leq (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. $R^n \subseteq R^l$.
Let (a,b) be arbitrary element of $R^n$. 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) \in R^l$. Since (a,b) is arbitrary, so $R^n \subseteq R^l$
Since n is arbitrary, so $\forall n > m \exists l < m (R^n \subseteq R^l)$

So, $\cup \{R^n | n > m\} \subseteq \cup \{R^n | 1 \leq n \leq m\}$

Then S = $\cup \{R^n | n > 1\}$ = $\cup \{R^n | 1 \leq n \leq m\}$


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. $0 \leq i \leq n-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. $0 \leq i \leq n$, (i+2)|(y+i)