how to prove it - a retrospection

I just finished working through velleman's how to prove it. All of my notes and solution to exercises can be found here. After reading it, here is what I think.

What I expected before I started reading it?
I expected to learn how mathematicians *think* when they encounter a conjecture. And, hoped that this would make it easy for me to read/understand any proof based books like cormen et al.

What I found?
Essential logic theory, A *solid* understanding of the abstract *structures* used in proofs and how these structures come from logic. You learn set, relations and functions for free as side effects :)

It helped a lot to have some understanding of (propositional)logic and quantifiers before I started reading this book. After working through this book when you will look at any proof, you will first understand the abstract structure behind the proof(in fact you'll just get it without even thinking about it) and then understand the specific details of the particular proof.

In short, I'm glad I read it. Thanks to Ravi for pointing me to it.

how to prove it - ch6, sec6.4(Strong Induction) ex

Strong induction is a variant of mathematical induction that is used to prove the goals of the form $\forall n \in N P(n)$.

To Prove a goal of the form $\forall n \in N P(n)$
Prove that $\forall n [(\forall k < n P(k)) \rightarrow P(n)]$, where n and k both are natural numbers. Note that no base case is necessary in a proof by strong induction.

Why it works?
If we proved $\forall n [(\forall k < n P(k)) \rightarrow P(n)]$. Then plugging n = 0, we get $(\forall k < 0 P(k)) \rightarrow P(0)$. Now, $\forall k < 0 P(k)$ is vacuously true as there are no natural numbers smaller than 0. Hence P(0) is true. Now keep applying the strong induction hypothesis to see that P(n) is true for any natural number.

Note:
I highly recommend that base case should atleast be checked if not proved. Because, not checking the base case, can lead to false proofs as following. (I'm taking ex-17(a) from section-6.1)

Q. Can you point out the error in following proof?

Theorem: Prove that for all $n \in N$, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$

Proof:

Let n be arbitrary natural number. Suppose, for all natural numbers k smaller than n,
$1.3^0 + 3.3^1 + 5.3^2 + .. + (2k+1)3^k = k3^{k+1}$

Since (n-1) < n, Then it follows from our assumption that
$1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1} = (n-1)3^n$

So, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n$
= $1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1} + (2n+1)3^n$
= $(1.3^0 + 3.3^1 + 5.3^2 + .. (2n-1)3^{n-1}) + (2n+1)3^n$
= $(n-1)3^n + (2n+1)3^n$
= $3n.3^n$
= $n3^{n+1}$

Hence, by the assumptions of strong induction, $1.3^0 + 3.3^1 + 5.3^2 + .. + (2n+1)3^n = n3^{n+1}$

Ans. To apply the induction hypothesis "for all natural numbers k smaller than n ..." to n-1, you need not only that (as you said) n-1 < n but also that n-1 is a natural number. That fails when n=0, so your argument doesn't cover the case n=0. – Andreas Blass [http://mathoverflow.net/questions/11964/strong-induction-without-a-base-case/]

============================================================================================


Ex-1

Givens:
$\forall n [(\forall k < n P(k)) \rightarrow P(n)]$
Q(n) = $\forall k < n P(k)$

(a) ($\rightarrow$) Suppose $\forall n Q(n)$. Let n be arbitrary. It follows from our assumption that Q(n+1). Then $\forall k < (n+1) P(k)$. In particular we can choose k = n to see that P(n). Since n is arbitrary, so $\forall n P(n)$

($\leftarrow$) Suppose $\forall n P(n)$. So for any n, for every k < n, P(k). Then $\forall k < n P(k)$. Then Q(n). Since n is arbitrary, so $\forall n Q(n)$

(b) Base case: For n = 0, Q(0) = $\forall k < 0 P(k)$ , since there is no k smaller than 0 so this statement is vacuously true.

Induction step: Let n be arbitrary natural number and Q(n). Then $\forall k < n P(k)$. Then it follows from the givens that P(n). Thus $\forall k < (n+1) P(k)$. So Q(n+1).


Ex-2 Let q be arbitrary natural number. Suppose, for all k < q, $\lnot \exists p \in N (\frac{p}{k} = \sqrt{2})$.

Assume, we can choose a natural number p s.t. $\frac{p}{q} = \sqrt{2}$. Then, following the logic used in theorem 6.2.5, we come to the conclusion that p and q both are even. Now, let us say p' = p/2 and q' = q/2. Then, $\frac{p'}{q'} = \sqrt{2}$. Since q' < q, so this contradicts with our induction hypothesis. Hence we can not choose such a natural number p. Hence $\forall k < (q+1) [\lnot \exists p \in N (\frac{p}{k} = \sqrt{2})]$. Since q is arbitrary, so $\sqrt{2}$ is irrational.


Ex-3
(a) Assume $\sqrt{6}$ is rational. Let S = { $q \in Z+ | \exists p \in Z+ (\frac{p}{q} = \sqrt{6})$ }. Then $S \neq \emptyset$. So, using well-ordering-property we can choose the smallest element of S, say q, and a positive integer p s.t. $\frac{p}{q} = \sqrt{6}$.
Then, $\frac{p^2}{q^2} = 6$
=> $p^2 = 6q^2$

so $p^2$ is even and hence p is even, then we can choose a p' such that p = 2p'.

Then, ${(2p')}^2 = 6q^2$
=> $4{(p')}^2 = 6q^2$
=> $2{(p')}^2 = 3q^2$

Then $3q^2$ is even and hence $q^2$ is even and hence q is even, then we can choose a q' such that q = 2q'.

Also, since $\frac{p}{q} = \sqrt{6}$
=> $\frac{p'}{q'} = \sqrt{6}$

so clearly $q' \in S$ and also $q' < q$. This contradicts with the assumption that q is smallest element of S and hence $\sqrt{6}$ is irrational.

(b) Assume $\sqrt{2} + \sqrt{3}$ is rational. Then we can choose positive integers p and q s.t.
$\frac{p}{q} = \sqrt{2} + \sqrt{3}$

On squaring both sides we get

$\frac{p^2}{q^2} = 2 + 3 + 2\sqrt{6}$
=> $\frac{p^2}{q^2} = 5 + 2\sqrt{6}$
=> $\sqrt{6} = \frac{p^2 - 5q^2}{2q^2}$

Then , $\sqrt{6}$ is rational. this is a contradiction with result proved in part(a). Hence $\sqrt{2} + \sqrt{3}$ is irrational.


Ex-4 Let n be arbitrary natural number s.t. $n \geq 12$. Suppose for every k < n, there is some combination of blue and red beads that is worth k credits.

Let us consider the following cases.

Case#1: $n \geq 15$
Then $(n-3) \geq 12$ and $(n-3) < n$. It follows from induction hypothesis that we can choose b blue and r red beads s.t. 3b + 7r = (n-3).
Then n = 3(b+1) + 7r.

Case#2: n = 12
n = 3(4) + 0(7)

Case#3: n = 13
n = 3(2) + 7(1)

Case#4: n = 14
n = 3(0) + 7(2)

Its clear from all these cases that for every $n \geq 12$ we can choose some combination of red and blue beads that worth n credits.


Ex-5 Let n be arbitrary natural number s.t. $n \geq 1$. Suppose for every k < n, $x^k + \frac{1}{x^k}$ is integer.

Now, from induction hypothesis, $x^{n-1} + \frac{1}{x^{n-1}}$ and $x + \frac{1}{x}$, both are integers.

Hence $(x^{n-1} + \frac{1}{x^{n-1}})(x + \frac{1}{x})$ is an integer
=> $x^n + \frac{1}{x^{n-2}} + x^{n-2} + \frac{1}{x^n}$ is an integer
=> $(x^n + \frac{1}{x^n}) + (x^{n-2} + \frac{1}{x^{n-2}})$ is an integer

Since (n-2) < n, so $(x^{n-2} + \frac{1}{x^{n-2}})$ is an integer. And hence, $x^n + \frac{1}{x^n}}$ is also an integer.


Ex-6
(a) Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} F_i = F_{k+2} - 1$

Now, $\sum_{i=0}^{n} F_i$
= $(\sum_{i=0}^{n-1} F_i) + F_n$ (apply induction hypothesis to get...)
= $F_{n+1} - 1 + F_n$
= $F_{n+1} + F_n - 1$
= $F_{n+2} - 1$

(b) Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} {(F_i)}^2 = F_kF_{k+1}$

Now, $\sum_{i=0}^{n} {(F_i)}^2$
= $(\sum_{i=0}^{n-1} {(F_i)}^2) + {(F_n)}^2$ (apply induction hypothesis to get...)
= $F_{n-1}F_n + {(F_n)}^2$
= $F_n(F_{n-1} + F_n)$
= $F_nF_{n+1}$

(c) Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} F_{2i+1} = F_{2k+2}$

Now, $\sum_{i=0}^{n} F_{2i+1}$
= $(\sum_{i=0}^{n-1} F_{2i+1}) + F_{2n+1}$ (apply induction hypothesis to get...)
= $F_{2(n-1)+2} + F_{2n+1}$
= $F_{2n} + F_{2n+1}$
= $F_{2n+2}$

(d) Scratchwork:
$\sum_{i=0}^{0} F_{2i} = 0 = F_{2.0 + 1} - 1$
$\sum_{i=0}^{1} F_{2i} = 1 = F_{2.1 + 1} - 1$
$\sum_{i=0}^{2} F_{2i} = 4 = F_{2.2 + 1} - 1$
$\sum_{i=0}^{3} F_{2i} = 12 = F_{2.3 + 1} - 1$
$\sum_{i=0}^{4} F_{2i} = 33 = F_{2.4 + 1} - 1$

easy guess... $\sum_{i=0}^{n} F_{2i} = F_{2n+1} - 1$

Proof:
Let n be arbitrary natural number. Suppose, for every k < n, $\sum_{i=0}^{k} F_{2i} = F_{2k+1} - 1$

Now, $\sum_{i=0}^{n} F_{2i}$
= $\sum_{i=0}^{n-1} F_{2i} + F_{2n}$ (apply induction hypothesis to get...)
= $(F_{2(n-1) + 1} - 1) + F_{2n}$
= $F_{2n-1} + F_{2n} - 1$
= $F_{2n+1} - 1$


Ex-7
(a) Let m be an arbitrary natural number greater than or equal to 1. Let n be an arbitrary natural number. Suppose for every k < n, $F_{m+k} = F_{m-1}F_k + F_mF_{n+1}$

Let us consider following cases.

Case#1: n = 0
Then LHS = $F_{m+0} = F_m$
RHS = $F_{m-1}F_0 + F_mF_{0+1}$ = $0 + F_mF_1$ = $F_m$
clearly LHS = RHS

Case#2: n = 1
Then LHS = $F_{m+1}$
RHS = $F_{m-1}F_1 + F_mF_2$ = $F_{m-1} + F_m$ = $F_{m+1}$
clearly LHS = RHS

Case#3: $n \geq 2$
$F_{m+n}$
= $F_{m+n-1} + F_{m+n-2}$ (apply induction hypothesis to get...)
= $(F_{m-1}F_{n-1} + F_mF_n) + (F_{m-1}F_{n-2} + F_mF_{n-1})$
= $F_{m-1}(F_{n-1} + F_{n-2}) + F_m(F_n + F_{n-1})$
= $F_{m-1}F_n + F_mF_{n+1}$

clearly, by strong induction, $F_{m+n} = F_{m-1}F_n + F_mF_{n+1}$

(b) Let m be an arbitrary natural number greater than or equal to 1. Let n be an arbitrary natural number greater than or equal to 1. Suppose for every k < n, $F_{m+k} = F_{m+1}F_{k+1} + F_{m-1}F_{n-1}$

Let us consider following cases.

Case#1: n = 2
LHS = $F_{m+2}$
RHS = $F_{m+1}F_3 - F_{m-1}F_1$ = $2F_{m+1} - F_{m-1}$ = $F_{m+1} + F_{m+1} - F_{m-1}$ = $F_{m+1} + F_m + F_{m-1} - F_{m-1}$ = $F_{m+1} + F_m$ = $F_{m+2}$
clearly, LHS = RHS

Case#2: n = 3
LHS = $F_{m+3}$
RHS = $F_{m+1}F_4 - F_{m-1}F_2$ = $3F_{m+1} - F_{m-1}$ = $2F_{m+1} + F_m + F_{m-1} - F_{m-1}$ = $2F_{m+1} + F_m$ = $F_{m+1} + F_{m+2}$ = $F_{m+3}$
clearly, LHS

Case#3: n > 3
$F_{m+n}$
= $F_{m+n-1} + F_{m+n-2}$ (apply induction hypothesis on both terms)
= $(F_{m+1}F_n - F_{m-1}F_{n-2}) + (F_{m+1}F_{n-1} - F_{m-1}F_{n-3})$
= $F_{m+1}(F_n + F_{n-1}) - F_{m-1}(F_{n-2} + F_{n-3})
= $F_{m+1}F_{n+1} - F_{m-1}F_{n-1}$

Its clearly from above 3 cases that for any natural number $n \geq 1$, $F_{m+n} = F_{m+1}F_{n+1} - F_{m-1}F_{n-1}$

(c) Let n be an arbitrary natural number. Suppose for every k < n, ${(F_k)}^2 + {(F_{k+1})}^2 = F_{2k+1}$

Let us consider following cases.

Case#1: n = 1
${(F_1)}^2 + {(F_2)}^2 = 1^2 + 1^2 = 1 + 1 = 2 = F_3 = F_{2(1)+1}$

Case#2: n = 2
${(F_2)}^2 + {(F_3)}^2 = 1^2 + 2^2 = 1 + 4 = 5 = F_5 = F_{2(2)+1}$

Case#3: n > 3
${(F_n)}^2 + {(F_{n+1})}^2$
= ${(F_{n-1} + F_{n-2})}^2 + {(F_n + F_{n-1})}^2$
= ${(F_{n-1})}^2 + {(F_{n-2})}^2 + 2F_{n-1}F_{n-2} + {(F_n)}^2 + {(F_{n-1})}^2 + 2F_nF_{n-1}$
= $({(F_{n-1})}^2 + {(F_{n-2})}^2) + ({(F_n)}^2 + {(F_{n-1})}^2) + 2(F_{n-1}F_{n-2} + F_nF_{n-1})$

In part(a) put m = n and n = n-2 to check that $F_{n-1}F_{n-2} + F_nF_{n-1} = F_{2n-2}$, so above term becomes...

= $({(F_{n-1})}^2 + {(F_{n-2})}^2) + ({(F_n)}^2 + {(F_{n-1})}^2) + 2F_{2n-2}$ (apply induction hypothesis to get)
= $(F_{2n-3}) + (F_{2n-1}) + 2F_{2n-2}$
= $(F_{2n-3} + F_{2n-2}) + (F_{2n-1} + F_{2n-2})$
= $F_{2n-1} + F_{2n}$
= $F_{2n+1}$

From above 3 cases, its clear that for all natural number n, ${(F_n)}^2 + {(F_{n+1})}^2 = F_{2n+1}$

(d) Let m be any arbitrary positive integer.

Let n be arbitrary positive integer and for every k < n, if m|k then $F_m|F_k$.

Now, let m|n. Then m = nk for some positive integer k.

Let us consider following possible cases

Case#1: k = 1
then m = n and clearly $F_m|F_n$

Case#2: k > 1
Then $F_n$
= $F_{km}$
= $F_{km - m + m}$
= $F_{m + (k-1)m}$ (apply part(a) result)
= $F_{m-1}F_{(k-1)m} + F_mF_{(k-1)m + 1}$

by induction hypothesis, $F_m |F_{(k-1)m}$. Hence $F_m |(F_{m-1}F_{(k-1)m})$. Also, $F_m|(F_mF_{(k-1)m + 1})$

So $F_m|F_n$

(e) Its trivial to prove the base cases with n = 1 and n = 2, I'm skiping them.

Let n be arbitrary natural number s.t. n > 2 and for every k < n,

$F_{2k-1} = \sum_{i=0}^{k-1} {2k-i-2}\choose{i}$ and
$F_{2k} = \sum_{i=0}^{k-1} {2k-i-1}\choose{i}$

Now, $F_{2n-1}$
= $F_{2n-2} + F_{2n-3}$
= $F_{2(n-1)} + F_{2(n-1)-1}$ (now apply induction hypothesis)
= $\sum_{i=0}^{n-2} {2(n-1)-i-1}\choose{i} + \sum_{i=0}^{n-2} {2(n-1)-i-2}\choose{i}$
= $\sum_{i=0}^{n-2} {2n-i-3}\choose{i} + \sum_{i=0}^{n-2} {2n-i-4}\choose{i}$

Let us look consider the 2nd term..
$\sum_{i=0}^{n-2} {2n-i-4}\choose{i}$ (let i = j-1)
= $\sum_{j=1}^{n-1}{2n-j-3}\choose{j-1}$ (let j = i)
= $\sum_{i=1}^{n-1}{2n-i-3}\choose{i-1}$

So, $F_{2n-1}$
= $\sum_{i=0}^{n-2} {2n-i-3}\choose{i} + \sum_{i=1}^{n-1}{2n-i-3}\choose{i-1}$
= $({2n-3}\choose{0} + \sum_{i=1}^{n-2} {2n-i-3}\choose{i}) + (\sum_{i=1}^{n-2}{2n-i-3}\choose{i-1} + {n-2}\choose{n-2})$
= $1 + \sum_{i=1}^{n-2} ({2n-i-3}\choose{i} + {2n-i-3}\choose{i-1}) + 1$
= $1 + \sum_{i=1}^{n-2} {2n-i-2}\choose{i} + 1$
= ${2n-0-2}\choose{0} + \sum_{i=1}^{n-2} {2n-i-2}\choose{i} + {2n-(n-1)-2}\choose{n-1}$
= $\sum_{i=0}^{n-1} {2n-i-2}\choose{i}$

Using similar steps we can get the result for $F_{2n}$


Ex-8:
(a) ($\rightarrow$) Suppose $a_0, a_1, a_2...$ is Gibonacci sequence.
clearly, $a_0 = c^0 = 1$
$a_1 = c^1 = c$
$a_2 = c^2$

It follows from the assumption that $a_2 = a_1 + a_0$
=> $c^2 = c + 1$
=> $c^2 - c - 1$

on solving above quadratic equation for c, we get that c is either $\frac{1 + \sqrt{5}}{2}$ or $\frac{1 - \sqrt{5}}{2}$

($\leftarrow$) Suppose c = $\frac{1 + \sqrt{5}}{2}$ or c = $\frac{1 - \sqrt{5}}{2}$, in both the cases
$c^2 = c + 1$
=> $c^n = c^{n-1} + c^{n-2}$
=> $a_n = a_{n-1} + a_{n-2}$

Hence $a_0, a_1, a_2...$ is Gibonacci sequence.

(b) Let n be an arbitrary natural number. Suppose for every k < n, $a_k = a_{k-1} + a_{k-2}$

Now, $a_{n-1} + a_{n-2}$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-1} + t{(\frac{1 - \sqrt{5}}{2})}^{n-1} + s{(\frac{1 + \sqrt{5}}{2})}^{n-2} + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-2}(\frac{1 + \sqrt{5}}{2} + 1) + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}(\frac{1 - \sqrt{5}}{2} + 1)$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-2}(\frac{3 + \sqrt{5}}{2}) + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}(\frac{3 - \sqrt{5}}{2})$
= $s{(\frac{1 + \sqrt{5}}{2})}^{n-2}{(\frac{1 + \sqrt{5}}{2})}^2 + t{(\frac{1 - \sqrt{5}}{2})}^{n-2}{(\frac{1 - \sqrt{5}}{2})}^2$
= $s{(\frac{1 + \sqrt{5}}{2})}^n + t{(\frac{1 - \sqrt{5}}{2})}^n$
= $a_n$

(c) Scratchwork:
$a_0 = s + t$ ...(i)

$a_1 = s(\frac{1 + \sqrt{5}}{2}) + t(\frac{1 - \sqrt{5}}{2})$
=> $2a_1 = (s+t) + \sqrt{5}(s-t)$
=> $s - t = \frac{2a_1 - a_0}{\sqrt{5}}$ ...(ii)

we can easily solve equation (i) and (ii) to get

s = $\frac{5a_0 + (2a_1 - a_0)\sqrt{5}}{10}$
t = $\frac{5a_0 - (2a_1 - a_0)\sqrt{5}}{10}$

Formal Proof:

Let s = $\frac{5a_0 + (2a_1 - a_0)\sqrt{5}}{10}$ and
t = $\frac{5a_0 - (2a_1 - a_0)\sqrt{5}}{10}$

its trivial to check that
$a_n = s{(\frac{1 + \sqrt{5}}{2})}^n + t{(\frac{1 - \sqrt{5}}{2})}^n$ holds true with chosen values of s and t for n = 0 and n = 1

from the result of part(b), $a_0, a_1, a_2, ...$ is Gibonacci sequence if $a_n = s{(\frac{1 + \sqrt{5}}{2})}^n + t{(\frac{1 - \sqrt{5}}{2})}^n$ for any real numbers s and t so it should be true for chosen values of s and t also.

Hence such s and t indeed exist.


Ex-9: In ex-18(c), put $a_0 = L_0 = 2$ and $a_1 = L_1 = 1$

Use s = $\frac{5a_0 + (2a_1 - a_0)\sqrt{5}}{10}$
t = $\frac{5a_0 - (2a_1 - a_0)\sqrt{5}}{10}$ to get

s = 1 and t = 1

thus the required formula is... for $n \geq 2$, $L_n = {(\frac{1 + \sqrt{5}}{2})}^n + {(\frac{1 - \sqrt{5}}{2})}^n$

And, from the analysis of ex-8(c) itself this should be correct.


Ex-10: Scratchwork:
Let us imitate ex-8(a) and assume $a_n = c^n$

Since, $a_n = 5a_{n-1} - 6a_{n-2}$
=> $c^n = 5c^{n-1} - 6c^{n-2}$
=> $c^2 = 5c - 6$
=> $c^2 - 5c + 6 = 0$
=> $c^2 - 2c - 3c + 6 = 0$
=> $c(c-2) - 3(c-2) = 0$
=> $(c-2)(c-3) = 0$

Thus either c = 2 or c = 3

Now imitate ex-8(b) to guess that

$a_n = s2^n + t3^n$, where s and t are some real numbers.

Since $a_0 = -1$, so $s + t = -1$ ... eq(i)

and since $a_1 = 0$, so $2s + 3t = 0$ ... eq(ii)

on solving eq(i) and (ii) we get

s = -3 and t = 2

So, $a_n = 2.3^n - 3.2^n$

Formal Proof:

The formula is $a_n = 2.3^n - 3.2^n$

Suppose for every k < n, $a_k = 2.3^k - 3.2^k$

Let us consider following cases

Case#1: n = 0
RHS = $2.3^0 - 3.2^0 = 2 - 3 = -1 = a_0$ = LHS

Case#2: n = 1
RHS = $2.3^1 - 3.2^1 = 0 = a_1$ = LHS

Case#3: n > 1
$5a_{n-1} - 6a_{n-2}$ (apply induction hypothesis to get)
= $5(2.3^{n-1} - 3.2^{n-1}) - 6(2.3^{n-2} - 3.2^{n-2})$
= $10.3^{n-1} - 15.2^{n-1} - 4.3^{n-1} + 9.2^{n-1}$
= $6.3^{n-1} - 6.2^{n-1}$
= $2.3^n - 3.2^n$
= $a_n$


Ex-11: clearly $a_0 = 0 = F_0$, $a_1 = 1 = F_1$ and $a_2 = 1 = F_2$.

Now let n be arbitrary natural number. suppose for every k < n, $a_k = F_k$

Now, $a_n$
$\frac{1}{2}a_{n-3} + \frac{3}{2}a_{n-2} + \frac{1}{2}a_{n-1}$
= $\frac{a_{n-3} + 3a_{n-2} + a_{n-1}}{2}$ (apply induction hypothesis to get)
= $\frac{F_{n-3} + 3F_{n-2} + F_{n-1}}{2}$
= $\frac{(F_{n-3} + F_{n-2}) + 2F_{n-2} + F_{n-1}}{2}$
= $\frac{F_{n-1} + 2F_{n-2} + F_{n-1}}{2}$
= $\frac{2(F_{n-1} + F_{n-2})}{2}$
= $F_n$

so for all natural number n, $a_n = F_n$


Ex-12: Scratchwork:

we need to prove that # of elements in $P_n = F_{n+2} = F_{n+1} + F_n$
This gives a hint that # of elements $P_n$ = # of elements in $P_{n-1}$ + in $P_{n-2}$

Let us check that for some values of n

$P_1$ = {$\emptyset$,{1}} , size = 2
$P_2$ = {$\emptyset$,{1},{2}}, size = 3
$P_3$ = {$\emptyset$,{1},{2},{3},{1,3}}, size = 5
$P_4$ = {$\emptyset$,{1},{2},{3},{4},{1,3},{1,4},{2,4}}, size = 8

clearly our guess about the sizes seems to be true.

Also, now its easy to see that for all n > 2

$P_n$ = $P_{n-1} \cup $ {$X \cup \{n\} | X \in P_{n-2}$} (TODO: prove it)

Formal Proof:

# of elements in $P_1 = 2 = F_3$
# of elements in $P_2 = 3 = F_4$

Let n be arbitrary natural number greater than 2.

Then $P_n = P_{n-1} \cup $ {$X \cup \{n\} | X \in P_{n-2}$}

thus, # of elements in $P_n$ = # of element in $P_{n-1}$ + in $P_{n-2}$ = $F_{n+1} + F_n$ = $F_{n+2}$

Hence, for any natural number n s.t. $n \geq 1$, # of elements in $P_n$ = $F_{n+2}$


Ex-13:
(a) Let us consider both the possible cases:
Case#1: $n \geq 0$
Then it follows directly from theorem-6.4.1(division theorem) that there exist integers q and r s.t. n = mq + r where $0 \leq r < m$

Case#2: n < 0
Then -n is +ve. Hence we can choose some integers q and r s.t. $0 \leq r < m$ and
-n = qm + r
=> n = -qm - r
=> n = -qm - r + m - m
=> n = -(q+1)m + (m-r)

Let q' = -(q+1) and r' = (m-r). clearly q' and r' are integers and $0 \leq r' < m$

so, n = q'm + r'

(b) We will prove it by contradiction. Let us assume there exist distinct integers $q_1, q_2$ and distinct integers $r_1, r_2$ s.t. $0 \leq r_1,r_2 < m$ and
$n = q_1m + r_1$ and
$n = q_2m + r_2$

so, $q_1m + r_1 = q_2m + r_2$
=> $m = \frac{r_2 - r_1}{q_1 - q_2}$

Since $0 \leq r_1,r_2 < m$, so $|r_2 - r_1| < m$.
Also, $|q_1 - q_2| > 1$

Thus $\frac{|r_2 - r_1|}{|q_1 - q_2|} < m$. So m can not be equal to $\frac{r_2 - r_1}{q_1 - q_2}$. So we have a contradiction and hence distinct $q_1, q_2$ and distinct $r_1, r_2$ are not possible. So for every n and m, there exist only unique integers q and r s.t. n = qm + r

(c) Let us choose m = 2. Then For every integer n, we can choose integers q and r s.t. n = 2q + r and $0 \leq r < 2$. So only 2 following cases are possible

Case#1: r = 0
Then n = 2q. Then n is even

Case#2: r = 1
Then n = 2q + 1. Then n is odd

Since n is arbitrary, so every integer is either even or odd.


Ex-14: Let a be maximum of 5k and k(k+1). Let n be an arbitrary integer greater than a. Using result of ex-13(a) we can choose some integers q and r s.t. n = kq + r and $0 \leq r < k$.

Assume $q \leq 4$. Then $n = kq + r \leq 4k + r \leq 5k \leq a$. Since $n \leq a$ is not possible by assumption, hence $q \geq 5$. Then from example-6.1.3 it follows that $2^q \geq q^2$.

Now, assume $q \leq k$. Then $n = kq + r \leq k^2 + r \leq k^2 + k = k(k+1) \leq a$. Since $n \leq a$ is not possible by assumption, hence $q \geq (k+1)$.

So, $q \geq (k+1)$
=> $q^2 \geq q(k+1) = qk + q > qk + r = n$

Thus $q^2 \geq n$

Since $2^q \geq q^2$, so $2^q \geq n$. Then $2^{(kq+r)} \geq 2^r.n^k$. Then $2^{(kq+r)} \geq n^k$. Thus $2^n \geq n^k$.


Ex-15:
(a) Suppose, for every m s.t. $m \geq 1$ and m < k, $a_1f_1 + a_2f_2 + .. + a_mf_m \in O(g)$.

Now |f|
= |$a_1f_1 + a_2f_2 + .. + a_kf_k$|
= |$(a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1}) + a_kf_k$|
$\leq |a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1}| + |a_kf_k|$

Since $f_k \in O(g)$ so we can choose some $a \in Z^+$ and $c \in R^+$ s.t. for every n > a, $|f_k(n)| \leq c|g(n)|$

By induction hypothesis, $a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1} \in O(g)$, so we can choose some $a' \in Z^+$ and $c' \in R^+$ s.t. for every n > a',
$|a_1f_1(n) + a_2f_2(n) + .. + a_{k-1}f_{k-1}(n)| \leq c'|g(n)|$

Let a'' be maximum of a and a'. Then for every n > a''

|f(n)|
$\leq |a_1f_1 + a_2f_2 + .. + a_{k-1}f_{k-1}| + |a_kf_k|$
$\leq c'|g(n)| + c|a_k||g(n)| = (c' + c|a_k|)|g(n)|$

Thus, $f \in O(g)$

(b) Using result of ex-14, for every positive integer k we can choose some positive integer a s.t. for every n > a, $2^n \geq n^k$. Then all of $1, n, n^2, n^3, ....$ are elements of $O(2^n)$ or O(g). So using result of part(a), f is also element of O(g).

Ex-16:
(a) We can choose integers s and t s.t. d = as + bt.

Also by division theorem we can choose integers q and r s.t. a = dq + r and $0 \leq r < d$.

Then a = (as + bt)q + r
=> a = asq + btq + r
=> r = (1-sq)a + (-tq)b

Then $r \in S$. Since d is smallest element of S, so $d \leq r$. But r < d. Hence, the only value possible for r is 0. Thus a = dq and Hence d|a. By similar argument we can prove that d|b also.

(b) We can choose integers s and t s.t. d = as + bt. Since c|a and c|b, so c|(as) and c|(bt) both. Hence c|(as+bt) and so c|d.


Ex-17:
(a) Suppose p divides ab. Let d be the greatest common divisor of a and p then by ex-16 we can choose integers s and t s.t.
d = as + pt

Since d is gcd of a and p, so it divides p. Since p is prime, so d is either 1 or p. Let us consider both the cases.

Case#1: d = 1
Then 1 = as + pt. Since p|ab, so we can choose some real number k s.t. ab = kp. Then a = $\frac{kp}{b}$.
Then 1 = $s\frac{kp}{b} + pt$
=> b = skp + ptb
=> b = (sk + tb)p

Thus p divides b.

Case#2: d = p
Then p = as + pt
=> a = $\frac{p(1-t)}{s}$

Thus p divides a.

From above 2 cases its clear that either p|a or p|b.

(b) Let n be an arbitrary natural number s.t. $n \geq 1$. Suppose for every $1 \leq k < n$, if p divides $a_1a_2a_3...a_k$ then $p|a_i$ for some i, $1 \leq i \leq k$.

Suppose p divides $a_1a_2a_3...a_n$.
=> p divides $(a_1a_2a_3...a_{n-1}).a_n$

then, by using result of ex-17(a) either p divides $a_1a_2a_3...a_{n-1}$ or p divides $a_n$. Let us consider both the cases.

Case#1: p divides $a_1a_2a_3...a_{n-1}$
Then, by induction hypothesis, we can choose some i, $1 \leq i \leq (n-1)$ s.t. p divides $a_i$

Case#2: p divides $a_n$

Thus we can choose some i, $1 \leq i \leq n$ s.t. p divides $a_i$


Ex-18: We will use induction over j.

Base case: j = 1. Suppose $p_1, q_1, q_2, ..., q_k$ are all prime numbers s.t. $p_1 = q_1q_2...q_k$. Since $p_1$ is prime, so clearly k = 1 and $p_1 = q_1$

Induction Step: Suppose j be an arbitrary integer s.t. $j \geq 1$ and for all $k \geq 1$ and for all non decreasing sequence of primes $p_1,p_2,...,p_j$ and $q_1,q_2,...,q_k$ if $p_1p_2...p_j = q_1q_2...q_k$ then both the sequences are same.

Now suppose $p_1,p_2,...,p_j,p_{j+1}$ and $q_1,q_2,...,q_k$ are non-decreasing sequences of primes s.t.
$p_1p_2...p_jp_{j+1} = q_1q_2...q_k$

clearly $p_{j+1}$ divides $q_1q_2...q_k$, so by result of ex-17(b) we can choose some i s.t. $p_{j+1} = q_i$. Since $q_i \leq q_k$,
so $p_{j+1} \leq q_k$ ... (i)

Also, $q_k$ divides $p_1p_2...p_jp_{j+1}$, so by result of ex-17(b) we can choose some i s.t. $q_k = p_i \leq p_{j+1}$. Thus $q_k \leq p_{j+1}$... (ii)

From (i) and (ii), its clear that $p_{j+1} = q_k$.

Then $p_1p_2...p_j = q_1q_2...q_{k-1}$. By induction hypothesis both these sequences are same and hence the sequences $p_1,p_2,...,p_j,p_{j+1}$ and $q_1,q_2,...,q_k$ are same.


Ex-19: Scratchwork:
$a_0 = 1$
$a_1 = 1 + a_0 = 2$
$a_2 = 1 + a_0 + a_1 = 4$
$a_3 = 1 + a_0 + a_1 + a_2 = 8$
$a_4 = 1 + a_0 + a_1 + a_2 + a_3 = 16$

we can guess that $a_n = 2^n$

There is another way to find it. Let us look at that

$a_{n+1} = 1 + \sum_{i=0}^{n}a_i$
=> $a_{n+1} = 1 + \sum_{i=0}^{n-1}a_i + a_n$
=> $a_{n+1} = a_n + a_n$
=> $a_{n+1} = 2a_n$
=> $a_{n+1} = 2^2a_{n-1}$
=> $a_{n+1} = 2^3a_{n-2}$
=> $a_{n+1} = 2^4a_{n-3}$
...
...
=> $a_{n+1} = 2^{n+1}a_{n-n}$
=> $a_{n+1} = 2^{n+1}a_0$
=> $a_{n+1} = 2^{n+1}$

Formal Proof:

The formula is, for any natural number n, $a_n = 2^n$

Base case: n = 0, $a_0 = 1 = 2^0$

Induction step: Suppose for arbitrary natural number n, $a_n = 2^n$

Now, $a_{n+1}$
= $1 + \sum_{i=0}^{n}a_i$
= $1 + \sum_{i=0}^{n-1}a_i + a_n$
= $a_n + a_n$
= $2a_n$
= $2.2^n$
= $2^{n+1}$


Ex-20: Scratchwork:
Let $F_n$ denotes nth fibonacci number.

$a_0 = 1 = \frac{F_2}{F_1}$
$a_1 = 1 + 1 = 2 = \frac{F_3}{F_2}$
$a_2 = 1 + \frac{1}{2} = \frac{3}{2} = \frac{F_4}{F_3}$
$a_3 = 1 + \frac{2}{3} = \frac{5}{3} = \frac{F_5}{F_4}$
$a_4 = 1 + \frac{3}{5} = \frac{8}{5} = \frac{F_6}{F_5}$
$a_5 = 1 + \frac{5}{8} = \frac{13}{8} = \frac{F_7}{F_6}$

easy enough to guess that $a_n = \frac{F_{n+2}}{F_{n+1}}$

Proof:

Suppose for every k < n, $a_k = \frac{F_{k+2}}{F_{k+1}}$

Now, $a_n$
= $1 + \frac{1}{a_{n-1}}$ (apply induction hypothesis to get)
= $1 + \frac{F_n}{F_{n+1}}$
= $\frac{F_{n+1} + F_n}{F_{n+1}}$
= $\frac{F_{n+2}}{F_{n+1}}$

how to prove it - ch6, sec6.1(Proof by mathematical Induction) ex

This scetion introduces another proof technique, called Mathematical Induction, to prove the statements P(n) where n is arbitrary natural number. That is n = {0, 1, 2, 3, 4, ...}. Here is how you do it.

To Prove a goal of the form $\forall n \in N P(n)$:
First prove P(0), and then prove $\forall n \in N (P(n) \rightarrow P(n+1))$. The first of these proofs is sometimes called the *base case* and the second the *induction step*. Premise of the induction step is called the *induction hypothesis*.

Form of the final proof:
Base case: [Proof of P(0) goaes here]
Induction Step: [Proof of $\forall n \in N (P(n) \rightarrow P(n+1))$ goes here]

Why Mathematical Induction works?
Well, certainly P(0) is true because we prove it in the base case. Also, we prove that $\forall n \in N (P(n) \rightarrow P(n+1))$. So P(0) -> P(1). Then P(1) -> P(2). Then P(2) -> P(3). It goes on. Continuing in this way, you should be able to see that by repeatedly applying the induction step you can show that P(n) must be true for every natural number.

A small variation in the problem might be to prove the goal of the form, for all natural number n $\geq$ k, k is a natural number, P(n). Then simply the base case becomes n = k instead of n = 0.

=============================================================================================

Ex-1:
Base case: For n = 0, both sides are 0 and hence same.

Induction Step:
Let n be an arbitrary natural number s.t. 0 + 1 + 2 + ... + n = $\frac{n(n+1)}{2}$

Now, 0 + 1 + 2 + ... + n + (n+1)
= $\frac{n(n+1)}{2}$ + (n+1)
= $\frac{(n+2)(n+1)}{2}$


Ex-2: Base case: For n = 0, both sides are 0 and hence same
Induction Step:
Let n be an arbitrary natural number s.t. $0^2 + 1^2 + 2^2 + ... + n^2 = \frac{(n(n+1)(2n+1)}{6}$

Now, $0^2 + 1^2 + 2^2 + ... + n^2 + (n+1)^2$
= $\frac{(n(n+1)(2n+1)}{6} + (n+1)^2$
= $\frac{(n+1)(n+2)(2n+3)}{6}$


Ex-3: Base case: For n = 0, both sides are 0 and hence same
Induction Step:
Let n be an arbitrary natural number s.t. $0^3 + 1^3 + 2^3 + ... + n^3 = [\frac{(n(n+1)}{2}]^2$

Now, $0^3 + 1^3 + 2^3 + ... + n^3 + (n+1)^3$
= $[\frac{(n(n+1)}{2}]^2 + (n+1)^3$
= $\frac{(n+1)^2(n^2 + 4(n+1))}{4}$
= $[\frac{(n+1)(n+2)}{2}]^2$


Ex-4: Scratchwork:
P(1) = 1, P(2) = 4, P(3) = 9, P(4) = 16...

its easy to guess that P(n) = $n^2$. Let us try to prove it now.

Formal Proof:

Base case: For n = 1, LHS = 1 and RHS = $1^2$ = 1. cleary LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. $n \geq 1$ and 1 + 3 + 5 ... + (2n-1) = $n^2$

Now, 1 + 3 + 5 + ... + (2n-1) + (2n+1)
= $n^2 + 2n + 1$
= $(n+1)^2$


Ex-5: Base case: For n = 0, both sides are 0 and hence same

Induction step:
Let n be arbitrary natural number s.t. 0.1 + 1.2 + 2.3 + ... + n(n+1) = $\frac{n(n+1)(n+2)}{3}$

Now, 0.1 + 1.2 + 2.3 + ... + n(n+1) + (n+1)(n+2)
= $\frac{n(n+1)(n+2)}{3}$ + (n+1)(n+2)
= $\frac{(n+1)(n+2)(n+3)}{3}$


Ex-6: Scratchwork: My guess using results of ex1,5 is $\frac{n(n+1)(n+2)(n+3)}{4}$
Formal Proof:

Base case: For n = 0, both sides are 0 and hence same.

Induction step:
Let n be arbitrary natural number s.t. 0.1.2 + 1.2.3 + 2.3.4 + ... + n(n+1)(n+2) = $\frac{n(n+1)(n+2)(n+3)}{4}$

Now, 0.1.2 + 1.2.3 + 2.3.4 + ... + n(n+1)(n+2) + (n+1)(n+2)(n+3)
= $\frac{n(n+1)(n+2)(n+3)}{4}$ + (n+1)(n+2)(n+3)
= $\frac{(n+1)(n+2)(n+3)(n+4)}{4}$


Ex-7: Guess is $\frac{3^{n+1} - 1}{2}$

Base case: For n = 10, LHS = RHS = 1

Induction step:
Let n be arbitrary natural number s.t. $3^0 + 3^1 + 3^2 + ... + 3^n = \frac{3^{n+1} - 1}{2}$

$3^0 + 3^1 + 3^2 + ... + 3^n + 3^{n+1}$
= $\frac{3^{n+1} - 1}{2} + 3^{n+1}$
= $\frac{3^{n+2} - 1}{2}$


Ex-8: Base case: For n = 1, LHS = 1 - 1/2 = 1/2 and RHS = 1/2. clearly both sides are equal

Induction Step:
Let n be arbitrary natural number s.t. $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + ... + \frac{1}{2n-1} - \frac{1}{2n} = \frac{1}{n+1} + \frac{1}{n+2} + ... + \frac{1}{2n}$

Now, $1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + ... + \frac{1}{2n-1} - \frac{1}{2n} + \frac{1}{2n+1} - \frac{1}{2n+2}$
= $\frac{1}{n+1} + \frac{1}{n+2} + ... + \frac{1}{2n} + \frac{1}{2n+1} - \frac{1}{2n+2}$
= $\frac{1}{n+2} + ... + \frac{1}{2n} + \frac{1}{2n+1} - \frac{1}{2n+2} + \frac{1}{n+1}$
= $\frac{1}{n+2} + ... + \frac{1}{2n} + \frac{1}{2n+1} + \frac{1}{2n+2}$


Ex-9:
(a) Base case: For n = 0, clearly 2 divides $0^2 + 0 = 0$
Induction Step:
Let n be arbitrary natural number s.t. $2 | n^2 + n$. Then we can choose some integer k s.t. $n^2 + n = 2k$

$(n+1)^2 + (n+1)$
= $n^2 + 2n + 1 + n + 1$
= $(n^2 + n) + 2(n+1)$
= 2(k + n + 1)

clearly, $2 | [(n+1)^2 + (n+1)]$

(b) Base case: For n = 0, clearly 6 divides $0^3 - 0 = 0$
Induction Step:
Let n be arbitrary natural number s.t. $6|(n^3 - n)$. Then we can choose some integer k s.t. $n^3 - n = 6k$

Now, $(n+1)^3 - (n+1)$
= $n^3 + 1 + 3n^2 + 3n - n - 1$
= $(n^3 - n) + 3(n^2 + n)$

In Part(a) we prove that $n^2 + n$ is always divisible by 2. so we can choose some integer l s.t. $n^2 + n = 2l$

So, $(n+1)^3 - (n+1)$
= $(n^3 - n) + 3(n^2 + n)$
= 6k + 3(2l)
= 6(k+l)

clearly 6 divides $(n+1)^3 - (n+1)$


Ex-10: Base case: For n = 0, clearly 64 divides $9^0 - 8(0) - 1 = 0$
Induction step:
Let n be arbitrary natural number s.t. 64 divides $9^n - 8n - 1$. Then we can choose some integer k s.t. $9^n - 8n - 1 = 64k$

Now, $9^{n+1} - 8(n+1) - 1$
= $9.9^n - 8n -9$
= $9(9^n - 8n - 1) + 64n$
= 9(64k) + 64n$
= 64(9k + 1)

clearly 64 divides $9^{n+1} - 8(n+1) - 1$


Ex-11: Base case: For n = 0, clearly 9 divides $4^0 + 6(0) - 1 = 0$
Induction step:
Let n be arbitrary natural number s.t. 9 divides $4^n + 6n - 1$. Then we can choose some integer k s.t. $4^n + 6n - 1 = 9k$

Now, $4^{n+1} + 6(n+1) - 1$
= $4.4^n + 6n + 6 - 1$
= $4(4^n + 6n - 1) - 18n + 9$
= $4(9k) - 9(2n - 1)$
= $9(4k - 2n + 1)$

clearly 9 divides $4^{n+1} + 6(n+1) - 1$


Ex-12: Base case: For n = 0, clearly (a-b) divides $(a^0 - b^0) = 0$
Induction step:
Let n be arbitrary natural number s.t. (a-b) divides $a^n - b^n$. Then we can choose some integer k s.t. $a^n - b^n = (a-b)k$

Now, $a^{n+1} - b^{n+1}$
= $a(a^n - b^n) + ab^n - b^{n+1}$
= $a(a^n - b^n) + b^n(a-b)$
= $(a-b)(ka + b^n)$


clearly (a-b) divides $a^{n+1} - b^{n+1}$


Ex-13: Base case: For n = 0, clearly (a+b) divides $a^{2(0) + 1} + b^{2(0) + 1} = (a+b)$
Induction step:
Let n be arbitrary natural number s.t. (a+b) divides $a^{2n+1} + b^{2n+1}$

Now, $a^{2(n+1)+1} + b^{2(n+1)+1}$
= $a^{2n+3} + b^{2n+3}$
= $a^2(a^{2n+1} + b^{2n+1}) - a^2b^{2n+1} + b^{2n+3}$
= $a^2(a+b)k - b^{2n+1}(a^2 - b^2)$
= $(a+b)(a^2k - b^{2n+1}(a-b))$

clearly (a+b) divides $a^{2(n+1)+1} + b^{2(n+1)+1}$


Ex-14: Base case: For n = 10, $2^{10} = 1024 > 10^3 = 1000$
Induction step:
Let n be arbitrary natural number s.t. $2^n > 10^n$

Now, $2^{n+1}$
= $2.2^n$
> $2n^3$ = $n^3 + n^3$ = $n^3 + 10n^2$ (bacause $n \geq 10$)
= $n^3 + 3n^2 + 3n^2 + n^2$
> $n^3 + 3n^2 + 3n + 1$ = $(n+1)^3$

clearly $2^{n+1} > (n+1)^3$


Ex-15: Base case: For n = 0, clearly $0 \equiv 0 (mod 3)$
Inductive step:
Let n be a arbitrary natural number s.t. $n \equiv 0 (mod 3)$ or $n \equiv 1 (mod 3)$ or $n \equiv 2 (mod 3)$. Let us consider all the possible cases for (n+1)

Case#1: $n \equiv 0 (mod 3)$
Then we can choose some integer k s.t. n = 3k. Then (n + 1) = 3k + 1. Then $(n+1) - 1 = 3k$. Thus $(n+1) \equiv 1 (mod 3)$

Case#2: $n \equiv 1 (mod 3)$
Then we can choose some integer k s.t. (n-1) = 3k. Then (n+1) = 3k+2. Then $(n+1) - 2 = 3k$. Thus $(n+1) \equiv 2 (mod 3)$

Case#3: $n \equiv 2 (mod 3)$
Then we can choose some integer k s.t. (n-2) = 3k. Then (n+1) = 3k+3. Then $(n+1) - 0 = 3(k+1)$. Thus $(n+1) \equiv 0 (mod 3)$

Thus $(n+1) \equiv 0 (mod 3)$ or $(n+1) \equiv 1 (mod 3)$ or $(n+1) \equiv 2 (mod 3)$


Ex-16: Base case: For n = 1. LHS = $2.2^1$ = 4, RHS = $(1)2^{1+1} = 4$. clearly LHS = RHS
Induction Step:
Let n be arbitrary natural number s.t. $2.2^1 + 3.2^2 + 4.2^3 + ... + (n+1)2^n = n2^{n+1}$

Now, $2.2^1 + 3.2^2 + 4.2^3 + ... + (n+1)2^n + (n+2)2^{n+1}$
= $n2^{n+1} + (n+2)2^{n+1}$
= $n2^{n+1} + n2^{n+1} + 2^{n+2}$
= $n2^{n+2} + 2^{n+2}$
= $(n+1)2^{n+2}$


Ex-17:
(a) Base case is not proved.

(b) Scratchwork:
I could not actually guess it. So I solved it. However, after finding the answer, it seems it was so easy to guess :)

P(n) = $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n$
3P(n) = $1.3^1 + 3.3^2 + ... + (2n-1)3^n + (2n+1)3^{n+1}$

P(n) - 3P(n) = $1.3^0 + 2.3^1 + 2.3^2 + .... + 2.3^n - (2n+1)3^{n+1}$
P(n) - 3P(n) = $-1.3^0 + 2(3^0 + 3^1 + 3^2 + ... + 3^n) - (2n+1)3^{n+1}$ ,now use result of ex-7
P(n) - 3P(n) = $-1 + 2\frac{3^{n+1} - 1}{2} - (2n+1)3^{n+1}$
2P(n) = $1 - 2\frac{3^{n+1} - 1}{2} + (2n+1)3^{n+1}$
2P(n) = $1 - 3^{n+1} + 1 + (2n+1)3^{n+1}$
2P(n) = $2 + 2n3^{n+1}$
P(n) = $1 + n3^{n+1}$

So, $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n = 1 + n3^{n+1}$

Formal Proof:

Base case: For n = 0. LHS = $1.3^0$ = 1, RHS = $1 + (0)3^{0+1}$ = 1 + 0 = 1

Induction step:
Let n be arbitrary natural number s.t. $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n = 1 + n3^{n+1}$

Now, $1.3^0 + 3.3^1 + 5.3^2 + ... + (2n+1)3^n + (2n+3)3^{n+1}$
= $1 + n3^{n+1} + (2n+3)3^{n+1}$
= $1 + n3^{n+1} + 2n3^{n+1} + 3.3^{n+1}$
= $1 + 3n3^{n+1} + 3^{n+2}$
= $1 + (n+1)3^{n+2}$


Ex-18: Note that even/odd is defined to natural numbers $\geq$ 1
Base case: for n = 1, clearly 1 is odd and $a^1 = a < 0$

Induction step:

Let n be an arbitrary natural number. if n is even then $a^n > 0$ or if n is odd then $a^n < 0$. Let us consider both the cases

Case#1: n is even and $a^n > 0$
(n+1) is odd. And $a^{n+1}$ = $a.a^n$. Since a is negative and $a^n$ is positive, so $a^{n+1} < 0$

Case#2: n is odd and $a^n < 0$
(n+1) is even. And $a^{n+1}$ = $a.a^n$. Since a is negative and also $a^n$ is negative, so $a^{n+1} > 0$


Ex-19:
(a) Base case: For n = 1, 0 < a < b
Induction step:
Let n be arbitrary natural number greater thant or equal to 1 s.t. $0 < a^n < b^n$.

clearly, $0 < a^{n+1}$.

Now, $b^{n+1} = bb^n > ba^n > aa^n = a^{n+1}$
Thus, $0 < a^{n+1} < b^{n+1}$

(b) TODO

(c) We'll prove the inequality directly.
inequality to prove is, $ab^n + ba^n < a^{n+1} + b^{n+1}$. it can rewritten as $a^{n+1} + b^{n+1} - ab^n - ba^n > 0$

Now $a^{n+1} + b^{n+1} - ab^n - ba^n$
= $a^{n+1} - ab^n + b^{n+1} - ba^n$
= $a(a^n - b^n) - b(a^n - b^n)$
= $(a-b)(a^n - b^n)$
= $(b-a)(b^n - a^n)$

from part(a), $a^n < b^n$
=> $(b^n - a^n) > 0$

also (b-a) > 0

Hence $a^{n+1} + b^{n+1} - ab^n - ba^n$ = $(b-a)(b^n - a^n)$ > 0

(d) Base case: For n = 2,
$(\frac{a+b}{2})^2 = \frac{a^2 + b^2}{4} + \frac{2ab}{4}$

In part(c), putting n = 1 gives
$ab + ba < a^2 + b^2$
=> $2ab < a^2 + b^2$

So, $(\frac{a+b}{2})^2$
= $\frac{a^2 + b^2}{4} + \frac{2ab}{4}$
< $\frac{a^2 + b^2}{4} + \frac{a^2 + b^2}{4}$ = $\frac{a^2 + b^2}{2}$

Induction step:
Let n be arbitrary natural number greater than or equal to 2 s.t. $(\frac{a+b}{2})^n < \frac{a^n + b^n}{2}$

Multiplying both sides of above inequality with $\frac{a+b}{2}$, we get

$(\frac{a+b}{2})^{n+1} < \frac{a^n + b^n}{2}.\frac{a+b}{2}$
=> $(\frac{a+b}{2})^{n+1} < \frac{a^{n+1} + b^{n+1} + ba^n + ab^n}{4}$

from part(c), $ab^n + ba^n < a^{n+1} + b^{n+1}$
so, $\frac{a^{n+1} + b^{n+1} + ba^n + ab^n}{4} < \frac{2(a^{n+1} + b^{n+1})}{4} = \frac{a^{n+1} + b^{n+1}}{2}$

Hence, $(\frac{a+b}{2})^{n+1} < \frac{a^{n+1} + b^{n+1}}{2}$

how to prove it - ch5, sec5.2(One-to-one and Onto) ex

This section talks about definition of a one-to-one and/or onto function. The logic formulae for them are used to prove whether a function is one-to-one and/or onto.

One-To-One:
A function f:A -> B is called one-to-one if $\lnot \exists a_1 \in A \exists a_2 \in A (f(a_1) = f(a_2) \land a_1 \neq a_2)$. That is, there don't exists two different elements in A whose value of f is same.
Its easy to see that positive version of above formula(which is used more for proofs) is $\forall a_1 \in A \forall a_2 \in A (f(a_1) = f(a_2) \rightarrow a_1 = a_2)$

Onto:
A function f:A -> B is called onto if $\forall b \in B \exists a \in A (f(a) = b)$ or that every element b in B has some element a in A s.t. $(a,b) \in f$. That means, Ran(f) = B.

One-to-One functions are also called injections and Onto functions are also called surjections. The functions that are both one-to-one and onto are called one-to-one correspondence or bijections.

===========================================================================================

Ex-1:
(a) Its not One-to-one as f(1) = f(2) = f(3). It is Onto.
(b) not a function
(c) It is one-to-one but not onto


Ex-2:
(a) Not a function
(b) g is not one-to-one as (ab,a) and (ac,a) both are in g. However, g is onto.
(c) Its both one-to-one and onto.


Ex-3:
(a) Its not one-to-one as f(a) = f(b). However, it is onto.
(b) Its not one-to-one as f(0) = f(2) = 0. It is not onto either as proven below.
We'll prove it by contradiction. Assume its onto. Let c be arbitrary real number. Then we can choose a real number x s.t.
$x^2 -2x = c$
=> $x^2 - 2x - c = 0$

For this quadratic equation, D = (4 + 4c), which is negative for any c < -1, Hence no real roots possible if c < 1, which is a contradiction and the function is not onto.
(c) Its not one-to-one as f(2.1) = f(2.2) = 2. However, it is onto.


Ex-4:
(a) It is one-to-one but not onto as there are many cities which are not capital of any nation.
(b) It is both one-to-one and onto.
(c) It is also both one-to-one and onto.


Ex-5:
(a) Prove that f is one-to-one.
Let x,y be arbitrary elements of A s.t. f(x) = f(y).
=> $\frac{x + 1}{x - 1} = \frac{y + 1}{y - 1}$
=> $\frac{(x + 1) + (x - 1)}{(x + 1) - (x - 1)} = \frac{(y + 1) + (y - 1)}{(y + 1) - (y - 1)}$
=> x = y

So, If f(x) = f(y) then x = y. Since x and y are arbitrary, so f is one-to-one.

Prove that f is onto.
Scratchwork: For any arbitrary b in A, we want to find out an a in A s.t. f(a) = b
=> $\frac{a + 1}{a - 1} = b$
=> $\frac{(a + 1) + (a - 1)}{(a + 1) - (a - 1)} = \frac{b + 1}{b - 1}$
=> $a = \frac{b + 1}{b - 1}$

Formal Proof: Let b be an arbitrary element of A. Let us choose x = $\frac{b + 1}{b - 1}$.
Then f(x)
= $\frac{\frac{b + 1}{b - 1} + 1}{\frac{b + 1}{b - 1} - 1}$
= $\frac{2b}{2}$
= b

Since b is arbitrary, so f is Onto.

(b) ($\rightarrow$) Let (x,y) be an arbtirary element in $f \circ f$.
So, y =$(f \circ f)(x)$
= f(f(x))
= f($\frac{x + 1}{x - 1}$)
= $\frac{\frac{x + 1}{x - 1} + 1}{\frac{x + 1}{x - 1} - 1}$
= x

So, y = x. Then $(x,y) \in i_A$.

($\leftarrow$) Let (x,x) be an arbitrary element of $i_a$. Since $(f \circ f)(x)$ = x, so $(x,x) \in f \circ f$. Since x is arbitrary, so $i_A \subseteq f \circ f$.

Hence $f \circ f = i_A$


Ex-6:
(a) f(2) = {$y \in R | y^2 < 2$}
(b) It is ont-to-one but not onto, for example There does not exist any real number s.t. f(x) = {1,2,3}


Ex-7:
(a) f({{1,2},{3,4}}) = {1,2} $\cup$ {3,4} = {1,2,3,4}
(b) It is not one-to-one because f({{1,2},{3}}) = f({{1},{2,3}}) = {1,2,3}. However, it is onto.


Ex-8:
(a) Suppose $g \circ f$ is onto. Let c be an arbitrary element of C, then we can choose some $a \in A$ s.t. $(g \circ f)(a) = c$. Then g(f(a)) = c. Let f(a) = b, then g(b) = c. So, for any arbitrary $c \in C$ we can choose $b \in B$ s.t. g(b) = c. Hence g is onto.

(b) Suppose $g \circ f$ is one-to-one. Let x and y be arbitrary elements of A s.t. f(x) = f(y) = u.
Now $(g \circ f)(x)$ = g(f(x)) = g(u)
Also $(g \circ f)(y)$ = g(f(y)) = g(u)

Since $g \circ f$ is one-to-one, so x = y. Since x and y are arbitrary, so f is one-to-one.


Ex-9:
(a) Suppose f is onto and g is not one-to-one.
Since g is not one-to-one, so we can choose some $b_1$ and $b_2$ in B s.t. $g(b_1) = g(b_2)$ but $b_1 \neq b_2$. Since f is onto, so we can choose $a_1$ and $a_2$ in A s.t. $f(a_1) = b_1$ and $f(a_2) = b_2$ and $a_1 \neq a_2$. Thus $(g \circ f)(a_1)$ = $(g \circ f)(a_2)$ and $a_1 \neq a_2$. Thus $g \circ f$ is not one-to-one

(b) Suppose f is not onto and g is one-to-one. We will prove by contradiction that $g \circ f$ is not onto. Assume $g \circ f$ is onto.
Since f is not onto, so we can choose a $b \in B$ s.t. there is no $a \in A$ s.t. f(a) = b. Let g(b) = c. Since $g \circ f$ is onto, we can choose some $a \in A$ s.t. $(g \circ f)(a) = c$. Then g(f(a)) = c. But such $a$ is not possible. This is a contradiction. Hence $g \circ f$ is not onto.


Ex-10: Note: In this exercise f|C denotes the restriction of f to C.
(a) Suppose f is one-to-one. Let c and d be arbitrary elements of C s.t. (f|C)(c) = (f|C)(d) = b, where b is some element of B. Since, $C \subseteq A$, so c and d are elements of A also. Then f(c) = b and f(d) = b. Since f is one-to-one so c = d. Since c and d are arbitrary, so If f is one-to-one, then so is f|C.

(b) Suppose f|C is onto. Let b be arbitrary element of B. Since f|C is onto, so we can choose some c in C s.t. (f|C)(c) = b. Then f(c) = b. Since c is arbitrary, so If f|C is onto, then so is f.

(c) Let A = B = $R$ and C = $R^+$. For (a), use f(x) = |x| and for (b) use f(x) = x


Ex-11:
(a) Suppose A has more than one element. Then we can find two different arbitrary elements x and y in A s.t. $x \neq y$. Since f(x) = f(y) = b, so f is not one-to-one.

(b) Suppose B has more than one element. Then we can choose another element $c \in B$ s.t. $b \neq c$. Then there does not exist any $x \in A$ s.t. f(x) = c. Hence f is not onto.


Ex-12: ($\rightarrow$) Suppose $f \cup g$ is one-to-one. We will prove it by contradiction that Ran(f) and Ran(g) are disjoint. Assume Ran(f) and Ran(g) are not disjoint. Then we can choose some $c \in C$ s.t. there exist $a \in A$ and $b \in B$ s.t. f(a) = c and g(b) = c. Then $(f \cup g)(a) = (f \cup g)(b) = c$. But $f \cup g$ is one-to-one, so this is contradiction. Hence Ran(f) and Ran(g) are disjoint.
($\leftarrow$) Suppose Ran(f) and Ran(g) are disjoint. Let x and y be arbitrary elements of $A \cup B$ s.t. $(f \cup g)(x) = (f \cup g)(y) = c$, where $c \in C$. Then either $(x,c) \in f$ or $(x,c) \in g$ and either $(y,c) \in f$ or $(y,c) \in g$. Let us consider all the cases

Case#1: $(x,c) \in f$ and $(y,c) \in f$
Since f is one-to-one, so x = y

Case#2: $(x,c) \in g$ and $(y,c) \in g$.
Since g is one-to-one so x = y

Case#3: $(x,c) \in f$ and $(y,c) \in g$
Since Ran(f) and Ran(g) are not disjoint, so this case is not possible

Case#4: $(x,c) \in g$ and $(y,c) \in f$
Since Ran(f) and Ran(g) are not disjoint, so this case is not possible

From all these cases, it is clear that x = y. Since x and y are arbitrary, so f is one-to-one.

Hence, $f \cup g$ is one-to-one iff Ran(f) and Ran(g) are disjoint.


Ex-13: Suppose S is one-to-one.

First, we prove that for every $a \in A$, there exists atleast one $b \in B$ s.t. $(a,b) \in R$.
Let a be arbitrary element of A. Since $S \circ R$ is a function, so there exists unique $c \in C$ s.t. $(a,c) \in S \circ R$. Then we can choose some $b \in B$ s.t. $(b,c) \in S$ and $(a,b) \in R$.

Second, we prove that such a $b \in B$ is unique.
Let there exists another element $d \in B$ s.t. $(a,d) \in R$. Since Ran(R) = Dom(S) = B, so we can choose some $c_0 \in C$ s.t. $(d,c_0) \in S$. Then $(a,c_0) \in S \circ R$. Since $S \circ R$ is a function and $(a,c) \in S \circ R$ and $(a,c_0) \in S$, so $c = c_0$. Then $(d,c) \in S$ and $(b,c) \in S$. Since S is one-to-one, so b = d. Hence b is unique.

Hence If S is one-to-one, then R: A -> B


Ex-14:
(a) Suppose R is reflexive and f is onto. Let b be an arbitrary element of B. Since f is onto, so we can choose some $a \in A$ s.t. f(a) = b. Since R is reflexive, so $(a,a) \in R$ and hence $(b,b) \in S$. Since b is arbitrary, so S is reflexive on B.

(b) Suppose R is transitive and f is one-to-one. Let (x,y) and (y,z) be arbitrary elements of S. So there exist unique(unique because f is function) u,v and w s.t. f(u) = x, f(v) = y, f(w) = z and $(u,v) \in R$, $(v,w) \in R$. Since R is transitive, so $(u.w) \in R$. Then $(x,z) \in S$. Since (x,y) and (y,z) are arbitrary, so S is transitive.


Ex-15:
(a) Let X be arbitrary element of A/R, so we can choose some $x \in A$ s.t. X = $[x]_R$. Then g(x) = X. Since X is arbitrary, so g is onto
(b) ($\rightarrow$) Suppose g is one-to-one. Since R is equivalence relation and hence reflexive, so $i_A \subseteq R$.
Let (x,y) be arbitrary element of R. Then y = $[x]_R$.. Then g(x) = $[x]_R$ = g(y). But g is one-to-one, so x = y. Hence $R \subseteq i_A$.
Thus R = $i_A$

($\leftarrow$) Suppose R = $i_A$. Let x,y be arbitrary elements of A s.t. g(x) = g(y). Then $[x]_R = [y]_R$. Then $y \in [x]_R$. Then $(y,x) \in R$. Then x = y and hence g is one-to-one

So g is one-to-one iff R = $i_A$


Ex-16: ($\rightarrow$) Suppose h is one-to-one. Let x,y be arbitrary elements of A s.t. f(x) = f(y). Then h($[x]_R$) = h($[y]_R$). Since h is one-to-one so $[x]_R = [y]_R$. Then xRy
($\leftarrow$) Suppose $\forall x \in A \forall y \in A (f(x) = f(y) \rightarrow x = y)$. Let $[x]_R$, $[y]_R$ are arbitrary elements of A/R s.t. h($[x]_R$) = h($[y]_R$). Then f(x) = f(y). Then xRy and then $[x]_R = [y]_R$.

Hence h is one-to-one iff $\forall x \in A \forall y \in A (f(x) = f(y) \rightarrow x = y)$


Ex-17: Suppose f is onto, g:B -> C , h:B -> C and $g \circ f$ = $h \circ f$.
(a) ($\rightarrow$) Let (b,c) be arbitrary element in g. Since f is onto so we can choose $a \in A$ s.t. f(a) = b. So $(a,c) \in g \circ f$. Then $(a,c) \in h \circ f$. Then $(b,c) \in h$. Hence $g \subseteq h$
($\leftarrow$) Using a similar argument, we can prove that $h \subseteq g$.
Hence h = g

(b) [this one is copied from solutions given in the book]
Let $c_1$ and $c_2$ be two distinct elements of C. Suppose $b \in B$. Let g and h be functions from B to C s.t. $\forall x \in B (g(x) = c_1)$, $\forall x \in B \setminus \{b\} (h(x) = c_1)$ and h(b) = $c_2$. Then $g \neq h$, so $g \circ f \neq h \circ f$ and therefore we can choose some $a \in A$ s.t. g(f(a)) $\neq$ h(f(a)). But by definition of g and h, there is only one $x \in B$ s.t. g(x) $\neq$ h(x) is x = b, so it follows that f(a) = b. Since b was arbitrary, so f is onto.


Ex-18:
(a) Suppose f is one-to-one, g:A -> B, h:A -> B and $f \circ g = f \circ h$.
($\rightarrow$) Let (a,b) be arbitrary element of g. So we can choose $c \in C$ s.t. $(b,c) \in f$. Then $(a,c) f \circ g$. Then $(a,c) f \circ h$. Then we can choose a $b_0 \in B$ s.t. $(a,b_0) \in f$. Since f is one-to-one, so $b = b_0$. Hence $(a,b) \in h$. Thus $g \subseteq h$.
($\leftarrow$) Using a similar argument, $h \subseteq g$.

Thus g = h.

(b) Let $b_1$ and $b_2$ be arbitrary elements of B s.t. f($b_1$) = f($b_2$). Let us define g,h s.t. $\forall x \in A (g(x) = b_1)$ and $\forall x \in A (h(x) = b_2)$.
Now for every $x \in A$, $(f \circ g)(x)$ = f(g(x)) = f($b_1$) = f($b_2$) = f(h(x)) = $(f \circ h)(x)$. Thus $f \circ g$ = $f \circ h$. Then g = h. Then for any $x \in A$, g(x) = h(x) and hence $b_1$ = $b_2$. Since $b_1$ and $b_2$ are arbitrary, so f is one-to-one.


Ex-19:
(a) Proof for hRf:
Consider j: R -> R defined as j(x) = $(x-1)^2 + 1$

Let x be an arbitrary real number, then $(j \circ f)(x)$ = j(f(x)) = $j(x^2 + 1)$ = $x^4 + 1$ = h(x). Since x is arbitrary, so h = $j \circ f$. Hence hRf.

Proof for gRf is not true:
We will prove it by contradiction. Assume we can choose a function $j \in F$ s.t. g = $j \circ f$. Let x be an arbitrary real number. Then, g(x) = $(j \circ f)(x)$
=> $x^3 + 1$ = $j(x^2 + 1)$
=> j(x) = $\sqrt{x - 1}^3 + 1$

But then j is undefined for anything less than 1 and then $j \notin F$, which is a contradiction. Hence such a function can't exist and hence gRf is not true.

(b) First, we prove that R is reflexive.
Let f be an arbitrary function in $F$. Let x be an arbitrary real number. Then $(i_R \circ f)(x)$ = $i_R(f(x))$ = f(x). Since x is arbitrary, so f = $i_R \circ f$. Thus fRf. Since f is arbitrary, so R is reflexive on $F$.

Second, we prove that R is transitive.
Let (f,g) and (g,h) be arbitrary elements of R. Then we can choose two functions $j_1$ and $j_2$ s.t. f = $j_1 \circ g$ and g = $j_2 \circ h$. Let x be arbitrary real number. Then $(j_1 \circ g)(x)$ = $j_1(g(x))$ = $j_1(j_2(h(x)))$ = $(j_1 \circ j_2)(h(x))$. Let j = $j_1 \circ j_2$. Then $(j_1 \circ g)(x)$ = $(j \circ h)(x)$. Since x is arbitrary, so f = $j \circ h$. Thus fRh. So R is transitive.

Hence R is preorder.

(c) Let f be an arbitrary function in $F$. Let x be an arbitrary real number. $(f \circ i_R)(x)$ = f($i_R(x)$) = f(x). Since x is arbitrary, so f = $f \circ i_R$. So $(f,i_R) \in R$.

(d) Suppose f is arbitrary function in $F$.
($\rightarrow$) Suppose $i_RRf$. Then we can choose $j \in F$ s.t. $i_R = j \circ f$. Let x and y be arbitrary real numbers s.t. f(x) = f(y).
Then x = $i_R(x)$ = $(j \circ f)(x)$ = j(f(x)) = j(f(y)) = $(j \circ f)(y)$ = $i_R(y)$ = y. Thus x = y and hence f is one-to-one.

($\leftarrow$) Suppose f is one-to-one. Let A = Ran(f) and h = $f^{-1} \cup ((R \setminus A) X \{0\})$.
Proof for h:R -> R :
Existence And Uniqueness: Let x be an arbitrary real number. Let us consider following exhaustive set of cases.

Case#1: $x \in A$
Then we can choose a unique(unique because f is one-to-one) real number y s.t. f(y) = x. Then $(y,x) \in f$. Then $(x,y) \in f^{-1}$. Then $(x,y) \in h$. So h(x) = y.

Case#2: $x \notin A$
Then $x \in R \setminus A$. Then $(x,0) \in ((R \setminus A) X \{0\})$. Then $(x,0) \in h$. So h(x) = 0

hence h is a function from R to R.

Proof for $i_R = h \circ f$:
Let x be an arbitrary real number. Then $(h \circ f)(x)$ = h(f(x)) = x = $i_R(x)$. Since x is arbitrary, so $i_R = h \circ f$

Hence $i_RRf$

(e) Let f be an arbitrary element in $F$. Using result of Ex.14(a) of section 5.1, g = $g \circ f$. Hence gRf.

(f) Suppose g is a constant function, then we can choose a real number c s.t. for every real number x, g(x) = c.

($\rightarrow$) Suppose $\forall f \in F (fRg)$. Then we can choose some function j s.t. f = $j \circ g$. Let x be an arbitrary real number. Then f(x) = $(j \circ g)(x)$ = j(g(x)) = j(c) = constant. Hence f is a constant function.

($\leftarrow$) Suppose f is a constant function. Then there is some real number d s.t. for every real number x, f(x) = d. Let us define a function j s.t. j(c) = d. Let x be an arbitrary real number. Then $(j \circ g)(x)$ = j(g(x)) = j(c) = d = f(x). Since x is arbitrary so f = $j \circ g$. Hence fRg.

(g) Proof for ": set of all one-to-one functions from $R$ to $R$ is the largest element of $F/S$ ":
Let $[g]_S$ be the set of all one-to-one functions in $F$. Using result of part(d), we know that $i_RRg$. Hence we can choose a $j_1 \in F$ s.t. $i_R = j_1 \circ g$.
Let f be an arbitrary function in $F$. Then using result of part(c) $fRi_R$. Then we can choose a function $j_2 \in F$ s.t. $f = j_2 \circ i_R$. Let us define a function h = $j_2 \circ j_1$. Let x be an arbitrary real number.
Then $(h \circ g)(x)$
= h(g(x))
= $(j_2 \circ j_1)(g(x))$
= $j_2(j_1(g(x)))$
= $j_2((j_1 \circ g)(x))$
= $j_2(i_R(x))$
= $(j_2 \circ i_R)(x)$
= f(x)

Thus f = $h \circ g$. Hence fRg. And, so $[f]_S T [g]_S$. Since f is arbitrary so $\forall f \in F ([f]_S T [g]_S)$, where $[g]_S$ is set of all one-to-one functions in $F$. Hence Set of all one-to-one functions in $F$ is the largest element of $F/S$ in T.

Proof for ": set of all constant functions from $R$ to $R$ is the smallest element of $F/S$ ":
Let g be a constant function and f be an arbitrary function in $F$. Using the result of part(e) gRf. Then $[g]_S T [f]_S$. Hence set of all constant functions is smallest element of $F/S$

how to prove it - ch5, sec5.1(Functions) ex

Function:
Suppose F is a relation from A to B. Then F is called a function from A to B if for every $a \in A$ there is *exactly one* $b \in B$ s.t. $(a,b) \in F$. In other words, F is a function if
  $\forall a \in A \exists ! b \in B ((a,b) \in F)$
This unique $b \in B$ is called "the valuf of F at a", "the image of a under F", "the result of applying F on a" or just "F of a" or F(a).

If F is a function from A to B, its denoted by, F:A -> B

Often a function f from A to B is specified by giving a rule that can be used to determine f(a). However, one should always remember that such a rule is not mandatory and any subset of A X B that satisfies the requirements of function definition, is a function from A to B.

Note that, a relation is a function can be proved by proving the existence and uniqueness of a $b \in B$ for every $a \in A$.

Some Important Theorems:

1. Suppose f and g are functions from A to B. If $\forall a \in A (f(a) = g(a))$ then f = g
2. Suppose f:A -> B and g:B -> C. Then $g \circ f$:A -> C and ($g \circ f$)(a) = g(f(a)). Note that $g \circ f$ is also the composition of g and f, so all the properties of composition are still valid.

=============================================================================================

Ex-1:
(a) Yes
(b) No, because f(1) is not unique
(c) Yes


Ex-2:
(a) No, f(d) is undefined
(b) No, for example f(ab) = a = b
(c) Yes


Ex-3:
(a) f(a) = b, f(b) = b, f(c) = a
(b) f(2) = 2*2 - 2(2) = 0
(c) f(pi) = f(3.14) = 3, f(-pi) = f(-3.14) = -4


Ex-4:
(a) Rome
(b) {1,2,3}\{1,3} = {2}
(c) f(2) = (3,1)


Ex-5: $L \circ H$ is identity relation on $N$. $H \circ L$ of a city c is the name of the city that is capital of the nation that has c.


Ex-6:
$f \circ g$(x)
= f(g(x))
= f(2x - 1)
= $\frac{1}{(2x-1)^2 + 2}$
= $\frac{1}{4x^2 + 1 - 4x + 2}$
= ${\frac{1}{4x^2 - 4x + 3}$

$g \circ f$(x)
= g(f(x))
= g($\frac{1}{x^2 + 2}$)
= $2\frac{1}{x^2 + 2} - 1$
= $\frac{2 - x^2 - 2}{x^2 + 2}$
= $\frac{-x^2}{x^2 + 2}$


Ex-7: Note: in this exercixe I'm denoting restriction of f to C as f|C
(a) Existence:
Let c be an arbitrary element of C. Since $C \subseteq A$, so $c \in A$. Since f:A -> B, so we can choose some $b \in B$ s.t. $(c,b) \in f$. Also, $(c,b) \in$ C x B. Then $(c,b) \in f \cap C x B$. Thus b = (f|C)(c).
Uniqueness:
Let c be an arbitrary clement of C. Assume b,d are arbitrary elements of B s.t. $(c,b) \in f|C$ and $(c,d) \in f|C$. Then $(c,b) \in f$ and $(c,d) \in f$. Since f is a function, so b = d.

Hence f|C is a function.

Now, prove that f(c) = f|C.
clearly $(c,f(c)) \in f$. Since f:A->B, so $f(c) \in B$ and hence $(c,f(C)) \in C x B$. Then $(c,f(c)) \in f \cap C x B$. Thus $(c,f(c)) \in f|C$. So f(c) = (f|C)(c)

(b) ($\rightarrow$) Suppose g = (f|C). Let (c,b) be an arbitrary element of g. It follows from the assumption that $(c,b) \in (f|C)$. Then $(c,b) \in f$. Since (c,b) is arbitrary, so $g \subseteq f$.
($\leftarrow$) Suppose $g \subseteq f$.
Let (c,b) be an arbitrary element of g. Since $g \subseteq f$, so $(c,b) \in f$ and also $(c,b) \in C x B$. Then $(c,b) \in f \cap C x B$. Then $(c,b) \in f|C$. Since (c,b) is arbitrary, so $g \subseteq f|C$.
Let (c,b) be an arbitrary element of f|C. Then $(c,b) \in f$ and $(c,b) \in C x B$. Since $c \in C$ and g:C -> B, so we can choose a particular $d \in B$ s.t. $(c,d) \in g$. Since $g \subseteq f$, so $(c,d) \in f$. Since $(c,b) \in f$ and and $(c,d) \in f$ and f is a function, so b = d. Since $(c,d) \in g$, so $(c,b) \in g$. Since (c,b) is arbitrary, so $(f|C) \subseteq g$.
Hence g = f|C

(c) g:$Z \rightarrow R$, g(x) = 2x + 3
h:$R \rightarrow R$, h(x) = 2x + 3

Prove that g = h|$Z$ = $h \cap Z x R$

($\rightarrow$) Let (z,2z + 3) be arbitrary element of g. Since $z \in Z$, so $z \in R$ also. Then $(z,2z + 3) \in h$. Also $(z,2z+3) \in Z x R$. Thus $(z,2z+3) \in h|Z$. Hence $g \subseteq h|Z$
($\leftarrow$) Let (r,s) be arbitrary element of h|$Z$. Then $(r,s) \in h$ and $(r,s) \in Z x R$. Then $r \in Z$ and so $(r,2r+3) \in g$. Since $(r,s) \in h$, so s = 2r + 3. Then $(r,s) \in g$. Since (r,s) is arbitrary so $h|Z \subseteq g$.

Hence g = $h|Z$


Ex-8: We will prove by contradiction that $i_A$ is the only relation on A that is equivalence relation on A and a function from A to A as well.
Proof: Suppose $i_A$ is not the only such relation. Assume there is another relation h which is equivalence relation on A and a function as well. Let (x,y) be an arbitrary element in h. Since h reflexive, so $(x,x) \in h$ as well. Since h is a function, so x = y. Then h is $i_A$.


Ex-9:In this exercise f|C denotes restriction of f to C.
(a) Existence:
Let x be an arbitrary element of $A \cup B$. Let us consider the two possible cases.
Case#1: $x \in A$
Then we can choose a particular $c \in C$ s.t. $(x,c) \in f$. Then $(x,c) \in g \cup f$

Case#2: $x \in B$
Then we can choose a particular $c \in C$ s.t. $(x,c) \in g$. Then $(x,c) \in g \cup f$

From above cases its proven that we can always find a $c \in C$ s.t. $(x,c) \in g \cup f$

Uniqueness:
Let x be an arbitrary element of $A \cup B$. Assume c,d be arbitrary elements of C s.t. $(x,c) \in g \cup f$ and $(x,d) \in g \cup f$. Let us consider all the possible cases
Case#1: $(x,c) \in g$ and $(x,d) \in g$
Then c = d

Case#2: $(x,c) \in f$ and $(x,d) \in f$
Then c = d

Case#3: $(x,c) \in f$ and $(x,d) \in g$
Since $(x,c) \in f$, so $x \in A$. Since $(x,d) \in g$, so $x \in B$. But A and B are disjoint, so x can't belong to both and hence this case is not possible

Case#4: $(x,c) \in g$ and $(x,d) \in f$
This case is also not possible for the same reason as above

Hence c = d

Thus $g \cup f$ is a function from $A \cup B$ to C.
(b) ($\rightarrow$) Suppose $f \cup g$:$A \cup B$ -> C.
Let (a,c) be an arbitrary element of f|($A \cap B$). Then $(a,c) \in f$ and $(a,c) \in A \cap B x C$. Then $a \in B$, so we can choose a particular $d \in C$ s.t. $(a,d) \in g$. Then $(a,d) \in f \cup g$. Since $(a,c) \in f$, so $(a,c) \in f \cup g$. Then c = d. Hence $(a,c) \in g$. Thus $(a,c) \in g \cap A \cap B$. Since (a,c) is arbitrary, so $f|A \cap B \subseteq g|A \cap B$
By a similar argument, we can prove that $g|A \cap B \subseteq f|A \cap B$
Hence $f|A \cap B$ = $g|A \cap B$

($\leftarrow$) Suppose $f|A \cap B$ = $g|A \cap B$.
Existence:
Let x be an arbitrary element of $A \cup B$. Then either $x \in A$ or $x \in B$. In both the cases there exists some $c \in C$ s.t. $(x,c) \in f \cup g$.

Uniqueness:
Let x be an arbitrary element of $A \cup B$. Let c,d be arbitrary elements of C s.t. $(x,c) \in f \cup g$ and $(x,d) \in f \cup g$. Now let us consider all possible cases
Case#1: $(x,c) \in f$ and $(x,d) \in f$
Then c = d

Case#2: $(x,c) \in g$ and $(x,d) \in g$
Then c = d

Case#3: $(x,c) \in f$ and $(x,d) \in g$
Then $x \in A \cap B$. Since $(x,c) \in (A \cap B) x C$, so $(x,c) \in f|A \cap B$. By similar argument, $(x,d) \in g|A \cap B$. Since $f|A \cap B = g|A \cap B$, so $(x,d) \in f|A \cap B$ as well. Hence c = d

Case#4: $(x,c) \in g$ and $(x,d) \in f$
By using similar argument as above, c = d

Hence $f \cup g$:$A \cup B$ -> C


Ex-10:
(a) Existence:
Let b be an arbitrary element of B. Since Dom(S) = B, so we can choose some $c \in C$ s.t. $(b,c) \in S$

Uniqueness:
Let b be an arbitrary element of B. Let c,d be arbitrary elements of C s.t. $(b,c) \in S$ and $(b,d) \in S$. Since Ran(R) = B, so we can choose some $a \in A$ s.t. $(a,b) \in R$. Then $(a,c) \in S \circ R$ and $(a,d) \in S \circ R$. So c = d.

Hence S:B -> C

(b) Here is such an example.
A = {1}
B = {1,2}
C = {3}

S = {(1,3),(2,3)}
R = {(1,1),(1,2)}
$S \circ R$ = {(1,3)}


Ex-11:
(a) Suppose S is reflexive. Let x be an arbitrary element of A. $f(x) \in B$, so $(f(x),(f(x))) \in S$ because S is reflexive. Then $(x,x) \in R$. Since x is arbitrary, so R is reflexive.

Using similar arguments, we can prove part(b) and part(c) also


Ex-12:
(a) No, Here is the counterexample.
A = {1,2}
B = {3,4,5}
f = {(1,3),(2,4)}
R = {(1,1),(2,2),(1,2)}

S = {(3,4),(3,3),(4,4)}, Its not reflexive as $(5,5) \notin S$

(b) Yes, Proof:
Suppose R is symmetric. Let (x,y) be arbitrary element of S, then we can choose u and v in A s.t.
f(u) = x
f(v) = y and $(u,v) \in R$.
Since R is symmetric, so $(v,u) \in R$ and hence $(y,x) \in S$. Since (x,y) is arbitrary, so S is symmetric.

(c) Yes, Proof:
Suppose R is transitive. Let (x,y) and (y,z) be arbitrary ordered pairs in B x B s.t. $(x,y) \in S$ and $(y,z) \in S$. Then we can choose u,v,w in A s.t.
f(u) = x
f(v) = y
f(w) = z and $(u,v) \in R$ and $(v,w) \in R$.
Since R is transitive, so $(u,w) \in R$ and hence $(x,z) \in S$. Thus S is transitive.

Note: The book solution says its not and counterexample given is wrong as R given in the example is not transitive because R = {(1,2),(3,4)} and $(1,4) \notin R$.


Ex-13:
(a) Suppose R is reflexive. Let f be an arbitrary function in $F$ and let x be an arbitrary element of A. Then $f(x) \in B$. Since R is reflexive, so $(f(x),f(x)) \in R$. Since x is arbitrary so $(f,f) \in S$. And since f is arbitrary, so S is reflexive.

(b) Suppose R is symmetric. Let (f,g) is an arbitrary ordered pair in S. Let x be an arbitrary element of A. Then $(f(x),g(x)) \in R$. Since R is symmetric, so $(g(x),f(x)) \in R$. Then $(g,f) \in S$. Since (f,g) is arbitrary so S is symmetric.

(c) Suppose R is transitive. Let (f,g) and (g,h) be ordered pairs in S. Let x be an arbitrary element of A. Then $((f(x),g(x)) \in R$ and $(g(x),h(x)) \in R$. Since R is transitive, so $(f(x),h(x)) \in R$. Then $(f,h) \in S$. Since (f,g) and (g,h) are arbitrary so S is transitive.


Ex-14:
(a) Let x be an arbitrary element of A.
Then, $(f \circ g)$(x) = f(g(x)) = a = f(x).

(b) Let x be an arbitrary element of A. Then $(f \circ g)$(x) = f(g(x)). Since $(f \circ g)$ = f, so f(g(x)) = f(x). Since g is arbitrary, so it can be a constant function. Let g(x) = b. Then f(b) = f(x). Since f(b) is constant and x is arbitrary, so f is a constant function.


Ex-15:
(a) Since $\forall x > 0 (|x| = x)$, so $(|x|,x) \in R$. Thus $(f,g) \in R$.

(b) First, we prove that R is reflexive on $F$.
Since for any arbitrary x in A, any arbitrary function f in $F$, f(x) = f(x). Then $(f,f) \in R$. Since f is arbitrary, so R is reflexive.

Second, we prove that R is symmetric on $F$.
Let (f,g) be an arbitrary ordered pair in R. Then we can choose an $a \in R$ s.t. for every x > a, f(x) = g(x). Then g(x) = f(x) also. Then $(g,f) \in R$. Since (f,g) is arbitrary, so R is symmetric.

Third, we prove that R is transitive on $F$.
Let (f,g) and (g,h) be arbitrary ordered pairs in R. Then we can choose real numbers a and b s.t. for every
x > a, f(x) = g(x) and
x > b, g(x) = h(x).

Let c = maximum of a and b. Then for every x > c, f(x) = g(x) = h(x). Then $(f,h) \in R$. Since (f,g) and (g,h) are arbitrary, so R is transitive.

Hence R is equivalence relation on $F$.



Ex-16:
(a) Proof for $f \in O(g)$:
Let a = 3 and c = 8. Then for any x > a = 3,
|f(x)| = |7x + 3| = 7x + 3 < 7x + x = 8x < 8$x^2$ = c|g(x)|
Hence $f \in O(g)$

Proof for $g \notin O(f)$:
We'll prove it by contradiction. Assume $g \in O(f)$. Then we can choose some $a \in z^+$ and $c \in R^+$ s.t.for every positive integer x > a, $|x^2| \leq c|7x + 3|$. For a x greater than a and 10c,
We have x > 10c
=> $x^2$ > 10cx ...(i)

Since $|x^2| \leq c|7x + 3|$
=> $x^2 \leq c|7x + 3x|$
=> $x^2 \leq 10cx$ ...(ii)

clearly there is a contradiction between eq (i) and (ii), so our assumption is correct and $g \notin O(f)$

(b) First, we prove that S is reflexive in $F$.
For any arbitrary function $f \in F$ and for any arbitrary x, clearly |f(x)| = |f(x)|. So $f \in O(f)$. Then $(f,f) \in S$. Since f is arbitrary, so S is reflexive.

Second, we prove that S transitive in $F$.
Let (f,g) and (g,h) be two arbitrary elements in S. Then we can choose some positive integers a,b and positive real numbers c,d s.t.
$\forall x > a (|f(x)| \leq c|g(x)|)$ and
$\forall x > b (|g(x)| \leq d|h(x)|)$

Let e be the maximum of a and b. Let x be an arbitrary integer s.t. x > e. Then
$|f(x)| \leq c|g(x)|$ and
$|g(x)| \leq d|h(x)|$

Then $|f(x)| \leq cd|h(x)|$. Since x is arbitrary, so $f \in O(h)$. Thus $(f,h) \in S$. Since (f,g) and (g,h) are arbitrary, so S is transitive.

Hence S is a preorder.

(c) Since $f_1 \in O(g)$, so we can choose some $a \in Z^+$ and $c \in R^+$ s.t. $\forall x > a (|f_1(x)| \leq c|g(x)|)$.
Since $f_2 \in O(g)$, so we can choose some $b \in Z^+$ and $d \in R^+$ s.t. $\forall x > b (|f_2(x)| \leq d|g(x)|)$.

Let e be the maximum of a and b. Then for any arbitrary positive integer x > e,
|f(x)|
= $|sf_1(x) + tf_2(x)|$ (using triangle inequality)
$\leq s|f_1(x)| + t|f_2(x)|$
$\leq c|g(x)| + d|g(x)|$ = $(c+d)|g(x)|$

Thus $f \in O(g)$.


Ex-17:
(a) First, we prove that R is reflexive on A.
Let x be an arbitrary element of A. Then g(x) = g(x). Then $(x,x) \in R$. Since x is arbitrary, so R is reflexive.

Second, we prove that R is symmetric on A.
Let (x,y) be arbitrary element of R. Then g(x) = g(y). Then g(y) = g(x). Then $(y,x) \in R$. Since (x,y) is arbitrary, so R is symmetric.

Third, we prove that R is transitive on A.
Let (x,y) and (y,z) be arbitrary elements of R. Then g(x) = g(y) = g(z). Then $(x,z) \in R$. Since (x,y) and (y,z) are arbitrary, so R is transitive.

Hence R is equivalence relation on A.

(b) ($\rightarrow$) Let (x,y) be arbitrary element of R. Since R is equivalence relation, hence symmetric. Then $(y,x) \in R$. So $[x]_R = [y]_R$. Then g(x) = g(y). Since (x,y) is arbitrary so $R \subseteq \{(x,y) \in AxA | g(x) = g(y)\}$.
($\leftarrow$) Let (x,y) be arbitrary element of {$(x,y) \in AxA | g(x) = g(y)$}. Then g(x) = g(y). Then $[x]_R = [y]_R$. Then $(x,y) \in R$. Since (x,y) is arbitrary so $\{(x,y) \in AxA | g(x) = g(y)\} \subseteq R$

Hence R = {$(x,y) \in AxA | g(x) = g(y)$}


Ex-18:
(a)Existence:
Let us consider h = {$(X,y) \in A/R x B | \exists x \in X (f(x) = y)$}

clearly $([x]_R,x) \in h$ as f(x) = f(x)

Uniqueness:
Let say there exists another function g s.t. g($[x]_R$) = f(x).
Let (X,y) be arbitrary element of g. Since Dom(g) = A/R. So we can choose some $x \in A$ s.t. $[x]_R = X$ and then $y = f(x)$. Then $(X,y) \in h$, where h is choosen above. so, $g \subseteq h$. Also, clearly using the similar argument $h \subseteq g$. So h = g. hence h is unique.

(b) Let x,y be arbitrary elements of A s.t. xRy. Since R is symmetric, so yRx also. Hence $[x]_R = [y]_R$. Then $h[x]_R = h[y]_R$. Then f(x) = f(y). Since x and y are arbitrary, so we can say that $\forall x \in A \forall y \in A (xRy \rightarrow f(x) = f(y))$


Ex-19:
(a) Assume a function f s.t. f(x) = $[x^2]_R$
Let (x,y) be arbitrary element of R.
Then x $\equiv$ y(mod m)
so, we can choose some $k \in Z$ s.t.
x - y = km
=> x = y + km
=> $x^2 = y^2 + k^2m^2 + 2ykm$
=> $x^2 - y^2 = m(k^2m + 2yk)$

Since $(k^2m + 2yk)$ is also an integer, so $x^2 \equiv y^2$(mod m). Thus $(x^2,y^2) \in R$. Since R is equivalence relation, so $[x^2]_R = [y^2]_R$. So f(x) = f(y). Since x and y are arbitrary so f is compatible with R.

So using the result of Ex-18(a), we can say that there exists an unique function h s.t. h($[x]_R$) = f(x) = $[x^2]_R$

(b) We will prove it by contradiction. Assume there exists a function h:Z/R -> Z/R s.t. h($[x]_R$) = $[2^x]_R$.
Let (x,y) be arbitrary element in R. Then $[x]_R = [y]_R$. Then $h([x]_R) = h([y]_R)$. Then $[2^x]_R = [2^y]_R$. Then $(2^x,2^y) \in R$.
Then $2^x \equiv 2^y$(mod m)

So we can choose an integer k s.t.
$2^x - 2^y$ = km ...(i)

Since $(x,y) \in R$ also so x $\equiv$ y(mod m). Hence we can choose an integer l s.t. (x - y) = lm ...(ii)

From eq(i) and eq(ii) we get
$\frac{2^x - 2^y}{x - y}$ = $\frac{k}{l}$

RHS is a constant, but LHS can't be, which is a contradiction and hence such a function as assumed can not exist.

how to prove it - ch4, sec4.6(Equivalence Relations)

Equivalence Relation: A relation which is reflexive, symmetric and transitive.

It turns out that every equivalence relation on a set A determines a partitions of A, whose elements are the equivalence classes for the equivalence relation. Let us define them precisely.

Partition on A: A subset $F$ of power set of A, $P(A)$, is called a partition on A if it has following three properties.

- $\cup F$ = A
- $F$ is pairwise disjoint, that means $\forall X \in F \forall Y \in F (X \neq Y \rightarrow X \cap Y = \emptyset)$. Simply speaking, every two different elements of $F$ are disjoint
- $\forall X \in F (X \neq \emptyset)$

Equivalence Classes: Suppose R is an equivalence relation on A, and $x \in A$. Then the equivalence class of x with respect to R is the set
$[x]_R$ = {$y \in A$ | yRx }
If R is clear from the context, then we just write $[x]$. The set of all equivalence classes of elements of A is called A modulo R, and is denoted by A/R.
A/R = {[$x]_R | x \in A$} = {$X \subseteq A | \exists x (X = [x]_R)$}

There are some interesting theorems proved. I'll note them down here for the reference purposes.

Theorem: Suppose R is an equivalence relation on A, then A/R is a partition of A

it can be proved using following lemmas.
lemma1: For every $x \in A$, $x \in [x]$
lemma2: For every $x \in A$ and $y \in A$, $y \in [x]$ iff [y] = [x]. That is, all the equivalence classes are disjoint

Theorem: Suppose A is a set and $F$ is a partition of A. Then there is an equivalence relation R on A s.t. A/R = $F$
and it happens to be R = $\cup_{X \in F}(X x X)$


=================================================================================

Ex-1: {{1}, {2}, {3}}
{{1,2}, {3}}
{{1}, {2,3}}
{{1,3}, 2}
{{1,2,3}}


Ex-2: {(1,1),(2,2),(3,3)}
{(1,1),(2,2),(3,3),(1,2),(2,1)}
{(1,1),(2,2),(3,3),(2,3),(3,2)}
{(1,1),(2,2),(3,3),(1,3),(3,1)}
{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3),(2,1),(3,2),(3,1)}


Ex-3:
(a) Yes, it is equivalence relation. The equivalence classes are sets of all the words that start with a, sets of all the words that start with b,...

(b) It is not an equivalence relation as its not transitive. For example $(ab,bc) \in S$ and $(bc,cd) \in S$ but $(ab,cd) \notin S$

(c) Yes, it is equivalence relation. words of same length would fall into same equivalence class.


Ex-4:
(a) Its not equivalence relation as its not symmetric. For example $(5,3) \in R$ but $(3,5) \notin R$

(b) Yes, its an equivalence relation. Equivalence classes would be, set of all the real numbers such that their difference is any rational number.

(c) Yes, its an equivalence relation. Let us see example of an equivalence class..
[1] = {..., $\frac{1}{10000}$, $\frac{1}{1000}$, $\frac{1}{100}$, $\frac{1}{10}$, 1, 10, 100, 1000, 10000, ...}

In general for any real number x, the equivalence class would look like
[x] = {..., $\frac{x}{10000}$, $\frac{x}{1000}$, $\frac{x}{100}$, $\frac{x}{10}$, x, x*10, x*100, x*1000, x*10000, ...}


Ex-5: P = set of all people
B = {$(p,q) \in P x P$ | p and q have same birthday }
$P_d$ = {$p \in P$ | p has birthday on day d}

by definition of equivalence classes
P/B = {$X \subseteq P | \exists x (X = [x])$}

Now $P_d$ would be a equivalence class if there exists a person p s.t. [p] = $P_d$ i.e. there is atleast one person who was born on day d. So, if we make the assumption that for all the days there is atleast one person who was born on that day then P/B = {$P_d | d \in D$}.


Ex-6: Clearly the relation is reflexive as one triangle is similar to itself. Its symmetric because if a triangle x is similar to y, then y is similar to x also. Its also transitive because if x and y are similar triangles, y and z are similar triangles then clearly x and z are also similar triangles. Thus similarity relation is equivalence relation on set of triangles.


Ex-7: Proof for R is symmetric:
Let x,y be arbitrary elements of A s.t. $(x,y) \in R$. Then we can choose a $X \in F$ s.t. $(x,y) \in X x X$, that is $x \in X$ and $y \in X$. Thus $(y,x) \in X x X$, and so $(y,x) \in R$. Since x,y are arbitrary so R is symmetric

Proof for R is transitive:
Let x,y,z be arbitrary element of A s.t. $(x,y) \in R$ and $(y,z) \in R$. Then we can choose $X_1 \in F$ s.t. $(x,y) \in X_1 x X_1$ and $X_2 \in F$ s.t. $(y,z) \in X_2 x X_2$. Thus $x \in X_1$ and $y \in X_1$, $y \in X_2$ and $z \in X_2$. Since $F$ is a partition, so pairwise disjoint. Since $y \in X_1$ and $y \in X_2$, so $X_1 = X_2$. Thus $z \in X_1$, hence $(x,z) \in X_1 x X_1$ and hence $(x,z) \in R$. Since x,y,z are arbitrary so R is transitive


Ex-8: ($\rightarrow$) Suppose A/R = A/S. Let (x,y) be an arbitrary ordered pair in R. Then $x \in [x]_R$ and $y \in [y]_R$. Since A/R = A/S, so $[x]_R \in A/S$ and $[y]_R \in S$. Thus $(x,y) \in A/S$. Since (x,y) is arbitrary so $R \subseteq S$
($\leftarrow$) Using a similar argument as above, we can prove that $S \subseteq R$
Thus R = S


Ex-9: ($\rightarrow$) Let (x,y) be an arbitrary element of S. Then we can choose an $X \in F$ s.t. $(x,y) \in X x X$. Since $F$ = A/R, so X is an equivalence class of R on A. Thus X = $[x]_R$ = $[y]_R$, hence $(x,y) \in R$.
($\leftarrow$) Let (x,y) be an arbitrary element of R. Then we can choose an $X \in A/R$ s.t. $x \in X$ and $y \in X$. Since $F$ = A/R and $(x,y) \in X x X$, so $(x,y) \in \cup_{X \in F}(X x X)$. Thus $(x,y) \in S$. Since (x,y) is arbitrary so $R \subseteq S$

Thus S = R


Ex-10:
(a) Proof for $C_m$ is reflexive:
Let x be an arbitrary real number. since (x - x = 0*m), so $(x,x) \in C_m$. Since x is arbitrary, so $C_m$ is reflexive.

Proof for $C_m$ is symmetric:
Let x and y be arbitrary real numbers s.t. $(x,y) \in C_m$. Then we can choose a $k \in Z$ s.t. (x - y = km). Then (y - x = -km). Since $-k \in Z$, so $(y,x) \in C_m$. Since x,y are arbitrary so $C_m$ is symmetric

(b) For $C_2$:
Let us see an example.. [1] = {....-7,-5,-3,-1,1,3,5,7,.....} = {$n \in Z$ | |n|%2 = 1}
Now you can see that $C_2$ has two equivalence classes which are

{$n \in Z$ | |n|%2 = 1}, basically all odd integers
{$n \in Z$ | |n|%2 = 0}, all even integers

For $C_3$:
It has 3 equivalence classes
{$n \in Z$ | n % 3 = 0 }, all integers divisible by 3
{$n \in Z$ | |n| % 3 = 1 }
{$n \in Z$ | |n| % 3 = 2 }

Its easy to see that $C_m$ will have m equivalence classes


Ex-11: Since n is integer, so either its even or its odd. Let us consider both the cases
Case#1: n is even
Then, we can choose a $k \in Z$ s.t. n = 2k. Then $n^2$ = $(2k)^2$ = $4k^2$. Then $n^2 - 0$ is divisible by 4. So $n \equiv 0$ (mod 4)

Case#2: n is odd
Then, we can choose a $k \in Z$ s.t. n = (2k + 1). then $n^2$ = $(2k+1)^2$ = $4k^2 + 4k + 1$. Then $n^2 - 1$ = $4(k^2 + k)$, which is clearly divisible by 4. So $n \equiv 1$ (mod 4)

Thus if n is an integer then either $n \equiv 0$ (mod 4) or $n \equiv 1$ (mod 4)


Ex-12: Suppose $a \equiv c$ (mod m) and $b \equiv d$ (mod m). clearly we can choose some $k,l \in Z$ s.t.
a - c = km ...(i) and
b - d = lm ...(ii)

adding eq (i) and (ii) we get
a + b - c - d = (k+l)m
=> (a+b) - (c+d) = (k+l)m

Since $k+l \in Z$, so clearly $(a+b) \equiv (c+d)$ (mod m)

From eq (i), a = km + c ...(iii)
From eq (ii),b = lm + d ...(iv)

On multiplying eq (iii) and (iv) we get
ab = (km + c)(lm + d)
=> ab = kl$m^2$ + clm + cd + kdm
=> ab - cd = (klm + kd + cl)m

Since (klm + kd + cl) is integer, so $ab \equiv cd$ (mod m)


Ex-13:
(a) Let x be an arbitrary element of B. clearly $(x,x) \in B x B$. Since $B \subseteq A$, so $x \in A$ hence $(x,x) \in R$. So $(x,x) \in R \cap B x B$. Thus $(x,x) \in S$. Since x is arbitrary so S is reflexive on B.
Let x,y be arbitrary elements of B s.t. $(x,y) \in S$. Then $(x,y) \in R$. Since R is equivalence relation, hence symmetric and so $(y,x) \in R$. Also $(y,x) \in B x B$. Thus $(y,x) \in R \cap B x B$. So $(y,x) \in S$. Since x,y are arbitrary so S is symmetric.
Let x,y,z be arbitrary elements of B s.t. $(x,y) \in S$ and $(y,z) \in S$. So $(x,y) \in R$ and $(y,z) \in R$, hence $(x,z) \in R$. Also $(x,z) \in B x B$. Thus $(x,z) \in R \cap B x B$. So $(x,z) \in S$. Since x,y,z are arbitrary so S is transitive.
Thus S is equivalence relation on B.

(b) Let x be an arbitrary element of B. Let y be arbitrary element of $[x]_S$. Then
$y \in [x]_S$ iff
$(y,x) \in S$ iff
$(y,x) \in R \land (y,x) \in B x B$ iff
$y \in [x]_R \land y \in B$ iff
$y \in [x]_R \cap B$

Since y is arbitrary, so $[x]_S$ = $[x]_R \cap B$


Ex-14:
(a) Let X be an arbitrary set from $P(A)$. $X \triangle X$ = $(X \setminus X) \cup (X \setminus X)$ = $\emptyset$. Since $\emptyset \subseteq B$, so $(X,X) \in R$. Since X is arbitrary, so R is reflexive on $P(A)$
Let (X,Y) be an arbitrary ordered pair in $P(A) x P(A)$ s.t. $(X,Y) \in R$. Then $X \triangle Y \subseteq B$, then $(X \setminus Y) \cup (Y \setminus X) \subseteq B$, then $(Y \setminus X) \cup (X \setminus Y) \subseteq B$, then $(Y,X) \subseteq B$. Thus $(Y,X) \in R$. Since (X,Y) is arbitrary so R is symmetric.
Let (X,Y) and (Y,Z) be two arbitrary ordered pairs in $P(A) x P(A)$ s.t. $(X,Y) \in R$ and $(Y,Z) \in R$. Then $X \triangle Y \subseteq B$ and $Y \triangle Z \subseteq B$. Then
$(X \setminus Y) \cup (Y \setminus X) \subseteq B$ ...(i) and
$(Y \setminus Z) \cup (Z \setminus Y) \subseteq B$ ...(ii)

We will prove that $X \triangle Z \subseteq B$. Let x be an arbitrary element of $X \triangle Z$. Then either $x \in X \setminus Z$ or $x \in Z \setminus X$. Let us consider both the cases
Case#1: $x \in X \setminus Z$
Then $x \in X$ and $x \in Z$. Now either $x \in Y$ or $x \notin Y$, so either $x \in Y \setminus Z$ or $x \in X \setminus Y$. It follows from eq(i) and eq(ii) that $x \in B$.

case#2: $x \in Z \setminus X$
By a similar argument as above, $x \in B$.

Since x is arbitrary, so $X \setminus Z \subseteq B$

Since X,Y,Z are arbitrary so R is transitive on $P(A)$

Since R is reflexive, symmetric and transitive so R is equivalence relation on $P(A)$

(b) We will prove it by contradiction. Suppose X be arbitrary element of $P(A)$. Assume Y,Z be two different arbitrary elements of $[X]_R$. s.t. $Y \cap B = \emptyset$ and $Z \cap B = \emptyset$.
Since $Y \in [X]_R$, so $(Y,X) \in R$.
Since $Z \in [X]_R$, so $(Z,X) \in R$. Since R is equivalence relation and hence symmetric, so $(X,Z) \in R$. Since $(Y,X) \in R$ and $(X,Z) \in R$ and R is transitive, so $(Y,Z) \in R$.
Then, $Y \triangle Z \subseteq B$
Since Y and Z are different, so $Y \triangle Z$ has to be non-empty. Then we can choose some $x \in Y \triangle Z$. Since $Y \triangle Z \subseteq B$, so $x \in B$. Since $x \in Y \triangle Z$, so either $x \in Y \setminus Z$ or $x \in Z \setminus Y$. Let us consider both the cases

Case#1: $x \in Y \setminus Z$
Then $x \in Y$ and $x \notin Z$. Now since $Y \cap B = \emptyset$, so $x \notin B$. And that is a contradiction, hence this case is not possible.

Case#2: $x \in Z \setminus Y$
Then $x \in Z$ and $x \notin Y$. Now since $Z \cap B = \emptyset$, so $x \notin B$. And that is a contradiction. hence this case is not possible.

Since none of the cases are possible, so such x can not exist and hence $Y \triangle Z = \emptyset$. Then $Y = Z$.

Since X is arbitrary so, for every $X \in P(A)$ there is exactly one $Y \in [X]_R$ such that $Y \cap B = \emptyset$


Ex-15: First, we will prove that $\cup (F \cup G)$ = $A \cup B$.
($\rightarrow$) Let x be an arbitrary element of $\cup (F \cup G)$. Then we can choose some $X \in F \cup G$ s.t. $x \in X$. Now either $X \in F$ or $X \in G$. Let us choose both the cases.
Case#1: $X \in F$
Then $x \in \cup F$, then $x \in A$. Thus $x \in A \cup B$

Case#2: $X \in G$
Then $x \in \cup G$, then $x \in B$. Thus $x \in A \cup B$

Since $x \in A \cup B$ and x is arbitrary, so $\cup (F \cup G) \subseteq A \cup B$

($\leftarrow$) Let x be an arbitrary element of $A \cup B$. Let us consider both the cases
Case#1: $x \in A$
Then $x \in \cup F$. Then we can choose $X \in F$ s.t. $x \in X$. Since $X \in F$, so $X \in F \cup G$. Thus $x \in \cup (F \cup G)$

Case#2: $x \in B$
Then $x \in \cup G$. Then we can choose $X \in G$ s.t. $x \in X$. Since $X \in G$, so $X \in F \cup G$. Thus $x \in \cup (F \cup G)$

Since $x \in \cup (F \cup G)$ and x is arbitrary, so $A \cup B \subseteq \cup (F \cup G)$

Thus, $\cup (F \cup G)$ = $A \cup B$

Second, we will prove that $F \cup G$ is pairwise disjoint
Let X,Y be two arbitrary elements of $F \cup G$ s.t. $X \neq Y$. Let us consider following exhaustive set of cases
Case#1: $X \in F$ and $Y \in F$
Since F is a partition, so $X \cap Y = \emptyset$

Case#2: $X \in G$ and $Y \in G$
Since G is a partition, so $X \cap Y = \emptyset$

Case#3: $X \in F$ and $Y \in G$
Then $X \in P(A)$ and $Y \in P(B)$, so $X \subseteq A$ and $Y \subseteq B$. Since A and B are disjoint, so $X \cap Y = \emptyset$

Case#3: $X \in G$ and $Y \in F$
Then $X \in P(B)$ and $Y \in P(A)$, so $X \subseteq B$ and $Y \subseteq A$. Since A and B are disjoint, so $X \cap Y = \emptyset$

Thus X and Y are disjoint. Since X and Y are arbitrary, so $F \cup G$ is pairwise disjoint

Third, we will prove that every element in $F \cup G$ is non-empty.
Let X be an arbitrary element of $F \cup G$. Then either $X \in F$ or $X \in G$. Since F and G both are partitions so in any of the two cases $X \neq \emptyset$. Since X is arbitrary so every element in $F \cup G$ is non-empty

Hence, $F \cup G$ is a partition of $A \cup B$


Ex-16:
(a) First, we prove that $R \cup S$ is reflexive on $A \cup B$
Let x be an arbitrary element of $A \cup B$. Then either $x \in A$ or $x \in B$. Then either $(x,x) \in R$ or $(x,x) \in S$. Then $(x,x) \in R \cup S$. Since x is arbitrary, so $R \cup S$ is reflexive on $A \cup B$

Second, we prove that $R \cup S$ is symmetric on $A \cup B$
Let (x,y) be an arbitrary ordered pair in $R \cup S$. Then either $(x,y) \in R$ or $(x,y) \in S$. Then either$(y,x) \in R$ or $(y,x) \in S$. Then $(y,x) \in R \cup S$. Since (x,y) is arbitrary so $R \cup S$ is symmetric on $A \cup B$

Third, we prove that $R \cup S$ is transitive on $A \cup B$
Let (x,y) and (y,z) be arbitrary elements of $R \cup S$. Then, following cases are possible.
Case#1: $(x,y) \in R$ and $(y,z) \in R$
Then $(x,z) \in R$

Case#2: $(x,y) \in S$ and $(y,z) \in S$
Then $(x,z) \in S$

Case#3: $(x,y) \in R$ and $(y,z) \in S$
Then $x \in A$ and $y \in A$, $y \in B$ and $z \in B$. Since A and B are disjoint, y can't be element of both and hence this case is not possible

Case#4: $(x,y) \in S$ and $(y,z) \in R$
Then $x \in B$ and $y \in B$, $y \in A$ and $z \in A$. Since A and B are disjoint, y can't be element of both and hence this case is not possible

Thus either $(x,z) \in R$ or $(x,z) \in S$. Thus $(x,z) \in R \cup S$. Since (x,y) and (y,z) are arbitrary so $R \cup S$ is transitive

Hence $R \cup S$ is an equivalence relation on $A \cup B$

(b) First, we prove that for all $x \in A$, $[x]_{R \cup S}$ = $[x]_R$.
Suppose x is arbitrary element of A.
($\rightarrow$) Let y be an arbitrary element of $[x]_{R \cup S}$. Then $(y,x) \in R \cup S$. Then either $(y,x) \in R$ or $(y,x) \in S$. Since $x \in A$, so $(y,x) \notin S$. Thus $(y,x) \in R$. Hence $y \in [x]_R$. Since y is arbitrary so $[x]_{R \cup S} \subseteq [x]_R$
($\leftarrow$) Let y be an arbitrary element of $[x]_R$. Then $(y,x) \in R$, then $(y,x) \in R \cup S$. So $y \in [x]_{R \cup S}$. Since y is arbitrary, so $[x]_R \subseteq [x]_{R \cup S}$

Hence $[x]_{R \cup S}$ = $[x]_R$.

By using a similar argument, we can prove that for all $y \in B$, $[y]_{R \cup S}$ = $[y]_R$

(c) ($\rightarrow$) Let X be an arbitrary element of $(A \cup B)/(R \cup S)$. Then we can choose some $x \in A \cup B$ s.t. X = $[x]_{R \cup S}$. Then using the result of part(b), either $x \in A$ and $X = [x]_R$ or $x \in B$ and $X = [x]_S$. Then either $X \in A/R$ or $X \in B/S$. Thus $X \in (A/R) \cup (B/S)$. Since X is arbitrary, so $(A \cup B)/(R \cup S) \subseteq (A/R) \cup (B/S)$

($\leftarrow$) Let X be an arbitrary element of $(A/R) \cup (B/S)$. Then either $X \in (A/R)$ or $X \in (B/S)$. Then either we can choose some $x \in A$ s.t.$X = [x]_R$ or we can choose some $x \in B$ s.t. $[x]_S$. Using results of part(b), It follows from both the cases that $X = [x]_{R \cup S}$ whether $x \in A$ or $x \in B$. Thus $X \in (A \cup B)/(R \cup S)$. Since X is arbitrary, so $(A/R) \cup (B/S) \subseteq (A \cup B)/(R \cup S)$

Thus, $(A \cup B)/(R \cup S)$ = $(A/R) \cup (B/S)$

Ex-17: First, we prove that $\cup (F.G)$ = A.
($\rightarrow$) Let x be an arbitrary element of $\cup (F.G)$. Then we can choose some $Z \in F.G$ s.t. $x \in Z$. Since $Z \in F.G$, then we can choose some $X \in F$ and $Y \in Z$ s.t. Z = $X \cap Y$. Then $x \in X$ and $x \in Y$. Then $x \in \cup F$ and $x \in \cup G$. Since $\cup F$ = $\cup G$ = A, so $x \in A$. Since x is arbitrary, so $\cup (F.G) \subseteq A$
($\leftarrow$) Let x be an arbitrary element of A. Since A = $\cup F$ = $\cup G$, so $x \in \cup F$ and $x \in \cup G$. Then we can choose some $X \in F$ and $Y \in G$ s.t. $x \in X$ and $x \in G$. Then $x \in X \cap Y$. Let Z = $X \cap Y$, so $x \in Z$. Then $x \in \cup (F.G)$. Since x is arbitrary so $A \subseteq \cup (F.G)$.

Thus $\cup (F.G)$ = A


Ex-18: Basically for every element X in $F$ and for every element Y in $G$, create $X \cap Y$. Ignore $\emptyset$ and rest are all elements of $F.G$.
So potentially, $F.G$ = {$R^{-} \cap Z$, $R^{-} \cap (R \setminus Z)$, $R^{+} \cap Z$, $R^{+} \cap (R \setminus Z)$, {0}$\cap Z$, {0} $\cap (R \setminus Z)$}
= {$Z^{-}$, $R^{-} \setminus Z$, $Z^{+}$, $R^{+} \setminus Z$, {0}, $\emptyset$}

remove all empty sets, we get

$F.G$ = {$Z^{-}$, $R^{-} \setminus Z$, $Z^{+}$, $R^{+} \setminus Z$, {0}}


Ex-19:
(a) First, we prove the T is reflexive.
Let x be an arbitrary element of A. Then $(x,x) \in R$ and $(x,x) \in S$. Then $(x,x) \in R \cap S$. Then $(x,x) \in T$. Since x is arbitrary, so T is reflexive on A.

Second, we prove that T is symmetric.
Let (x,y) be an arbitrary element of T. Then $(x,y) \in R$ and $(x,y) \in S$. Since R,S are symmetric so $(y,x) \in R$ and $(y,x) \in S$. Then $(y,x) \in R \cap S$. Thus $(y,x) \in T$. Since (x,y) is arbitrary so T is symmetric on A

Third, we prove that T is transitive.
Let (x,y) and (y,z) be two arbitrary elements of T. Then $(x,y) \in R$ and $(y,z) \in R$, $(x,y) \in S$ and $(y,z) \in S$. Since R,S are transitive so $(x,z) \in R$ and $(x,z) \in S$. Then $(x,z) \in R \cap S$. Thus $(x,z) \in T$. Since (x,y) and (y,z) are arbitrary so T is transitive on A.

Hence T is an equivalence relation on A.

(b) Let x be an arbitrary element of A. Let y be an arbitrary element of $[x]_T$.
so $y \in [x]_T$ iff
$(y,x) \in T$ iff
$(y,x) \in R \cap S$ iff
$(y,x) \in R \land (y,x) \in S$ iff
$y \in [x]_R \land y \in [x]_S$ iff
$y \in [x]_R \cap [x]_S$

Since y is arbitrary, so $[x]_T$ = $[x]_R \cap [x]_S$

(c) Let X be an arbitrary element of $P(A)$.
Then $X \in A/T$ iff
$\exists x \in A (X = [x]_T)$ iff (using part(b) result)
$\exists x \in A (X = [x]_R \cap [x]_S)$ iff
$X \in (A/R).(A/S)$

Since X is arbitrary so (A/T) = (A/R).(A/S)


Ex-20: First, we prove that $\cup (F \otimes G)$ = $A x B$
($\rightarrow$) Let p be an arbitrary element of $\cup (F \otimes G)$. Then we can choose some $Z \in F \otimes G$ s.t. $p \in Z$. Since $Z \in F \otimes G$, so we can choose some $X \in F$ and $Y \in G$ s.t. Z = $X x Y$. Thus $p \in X x Y$. Since $X \in F$, so $X \in P(A)$ and hence $X \subseteq A$. By a similar argument $Y \subseteq B$. Thus $p \in A x B$. Since p was arbitrary, so $F \otimes G \subseteq A x B$
($\leftarrow$) Let (x,y) be an arbitrary element of $A x B$. Then, $x \in A$ and $y \in B$. Then $x \in \cup F$ and $y \in \cup G$. Then we can choose some $X \in F$ s.t. $x \in X$ and we can choose some $Y \in G$ s.t. $y \in Y$. Thus $(x,y) \in X x Y$. So $(x,y) \in \cup (F \otimes G)$. Since (x,y) is arbitrary so $A x B \subseteq \cup (F \otimes G)$

Thus $\cup (F \otimes G)$ = $A x B$

Second, we prove that $F \otimes G$ pairwise disjoint.
Suppose Z and W be two arbitrary elements of $F \otimes G$ s.t. $Z \neq W$. Then we can choose some $X_1 \in F$, $X_2 \in F$, $Y_1 \in G$, $Y_2 \in G$ s.t. $Z = X_1 x Y_1$ and $W = X_2 x Y_2$. Since $Z \neq W$, so either $X_1 \neq X_2$ or $Y_1 \neq Y_2$. Let us consider both the cases
Case#1: $X_1 \neq X_2$
Since $F$ is a partition, so $X_1 \cap X_2 = \emptyset$. Then it follows that $Z \cap W = \emptyset$

Case#2: $Y_1 \neq Y_2$
Since $G$ is a partition, so $Y_1 \cap Y_2 = \emptyset$. Then it follows that $Z \cap W = \emptyset$

Thus Z and W are disjoint. Since Z and W are arbitrary, so $F \otimes G$ is pairwise disjoint

Third, we prove that every element of $F \otimes G$ is non-empty
Let Z be an arbitrary element of $F \otimes G$. Then we can choose some $X \in F$ and $Y \in G$ s.t. $Z = X x Y$. Since $F$ and $G$ are partitions, so $X \neq \emptyset$ and $Y \neq \emptyset$. Thus $X x Y \neq \emptyset$. So $Z \neq \emptyset$. Since Z is arbitrary, so every element of $F \otimes G$ is non-empty

Hence $F \otimes Z$ is a partition of $A x B$


Ex-21: $F \otimes F$ = $(F x F) \setminus \{\emptyset\}$
So $F \otimes F$ = {$R^{-} x R^{-}, R^{-} x R^{+}, R^{-} x \{0\}, R^{+} x R^{-}, R^{+} x R^{+}, R^{+} x \{0\}, \{0\} x R^{-}, \{0\} x R^{+}, \{(0,0\}$}

Let us describe them in terms of xy-plane(in turn in terms of 4 quadrants of the plane).
$R^{-} x R^{-}$ is 3rd(bottom left) quadrant
$R^{-} x R^{+}$ is 2nd(top left) quadrant
$R^{-} x \{0\}$ is negative X-axis
$R^{+} x R^{-}$ is 4th(bottom right) quadrant
$R^{+} x R^{+}$ is 1st(top right) quadrant
$R^{+} x \{0\}$ is positive X-axis
$\{0\} x R^{-}$ is negative Y-axis
$\{0\} x R^{+}$ is positive Y-axis
{(0,0)} is origin


Ex-22:
(a) First, we prove that T is reflexive on A x B.
Let (x,y) be an arbitrary element of (A x B). Then $(x,x) \in R$ and $(y,y) \in S$. Then $((x,y),(x,y)) \in T$. Since (x,y) is arbitrary so T is reflexive.

Second, we prove that T is symmetric on A x B.
Let ((x,y),(u,v)) be an arbitrary element of T. Then $(x,u) \in R$ and $(y,v) \in S$. Then $(u,x) \in R$ and $(v,y) \in S$. Thus $((u,v),(x,y)) \in T$. Since ((x,y),(u,v)) is arbitrary so T is symmetric.

Third, we prove that T is transitive on A x B.
Let ((x,y),(u,v)) and ((u,v),(l,m)) be arbitrary elements of T. Then $(x,u) \in R$ and $(u,l) \in R$, $(y,v) \in S$ and $(v,m) \in S$. Then $(x,l) \in R$ and $(y,m) \in S$. Then $((x,y),(l,m)) \in T$. Thus T is transitive.

Hence, T is equivalence relation on A x B.

(b) Suppose $a \in A$ and $b \in B$. Let (x,y) be an arbitrary element of A x B. Then
$(x,y) \in [(a,b)]_T$ iff
$((x,y),(a,b)) \in T$ iff
$(x,a) \in R \land (y,b) \in S$ iff
$x \in [a]_R \land y \in [b]_S$ iff
$(x,y) \in [a]_R x [b]_S$

Since (x,y) is arbitrary, so $[(a,b)]_T$ = $[a]_R x [b]_S$

(c) RHS
= (A/R) $\otimes$ (B/S)
= {$Z \in P(A x B) | \exists a \in A \exists b \in B (Z = [a]_R x [b]_S)$} , now using result of part(b)
= ($Z \in P(A x B) | \exists (a,b) \in (A x B) (Z = [(a,b)]_T)$}
= (A x B)/T
= LHS


Ex-23:
(a) Suppose R is compatible with S. Let T be a relation on A/S, defined as follow
T = {$(X,Y) \in A/S x A/S | \exists x \in X \exists y \in Y (xRy)$}

Let x,y be two arbitrary elements of A. Then
$[x]_S T [y]_T$ iff
$\exists a \in [x]_S \exists b \in [y]_S (aRb)$ iff
$\exists a \in A \exists b \in A (a \in [x]_S) \land (b \in [y]_S) \land (aRb)$ iff
$\exists a \in A \exists b \in A (aSx) \land (bSy) \land (aRb)$ iff (since R is compatible with S)
$xRy$

So T satisfies the given property and hence such a relation exists.

(b) Suppose x,y,a,b are arbitrary elements on S s.t. (xSa) and (ySb). Let (xRy). Then $([x]_S,[y]_S) \in T$. Since (xSa), so $[x]_S = [a]_S$. Since (ySb), so $[y]_S = [b]_S$. Thus $([a]_S,[b]_S) \in T$. Then (aRb). So, If (xRy) then (aRb). Using a similar argument we can prove that If (aRb) then (xRy). Hence (xRy) iff (aRb). Thus R is compatible with S.


Ex-24:
(a) First, we prove that S is reflexive on A.
Let x be an arbitrary element of A. Since R is reflexive, so $(x,x) \in R$. And also $(x,x) \in R^{-1}$. Thus $(x,x) \in R \cap R^{-1}$. So $(x,x) \in S$. Since x is arbitrary, so S is reflexive.

Second, we prove that S is symmetric on A.
Let (x,y) be arbitrary element of S. Then $(x,y) \in R$ and $(x,y) \in R^{-1}$. Then $(y,x) \in R^{-1}$ and $(y,x) \in R$. Then $(y,x) \in R \cap R^{-1}$. Thus $(y,x) \in S$. Since (x,y) is arbitrary so S is symmetric.

Third, we prove that S is transitive on A.
Let (x,y) and (y,z) be arbitrary elements of S. Then $(x,y) \in R$ and $(x,y) \in R^{-1}$, $(y,z) \in R$ and $(y,z) \in R^{-1}$. Since $(x,y) \in R$ and $(y,z) \in R$ and R is transitive, so $(x,z) \in R$. Since $(x,y) \in R^{-1}$ and $(y,z) \in R^{-1}$, so $(y,x) \in R$ and $(z,y) \in R$. Since R is transitive, so $(z,x) \in R$ and hence $(x,z) \in R^{-1}$. So $(x,z) \in R \cap R^{-1}$. Thus $(x,z) \in S$. So S is transitive.

Hence S is equivalence relation on A.

(b) we can use the result from Ex23(a), the statement in question can be proved by just proving that R is compatible with S.
Let x,y,a,b be arbitrary elements of A s.t. (xSa) and (ySb). Let (xRy). Since (xSa), so $x R^{-1} a$ and hence (aRx). Since (aRx) and (xRy) and R is transitive, so (aRy). Since (ySb), so (yRb). Since (aRy) and (yRb) and R is transitive, so (aRb). So, If (xRy) then (aRb). Using a similar argument we can prove that If (aRb) then (xRy). Thus R is compatible with S.

(c) First, we prove that T is reflexive on (A/S).
Let x be an arbitrary element of A. Since R is reflexive, so (xRx). Then $[x]_S T [x]_S$. Since x is arbitrary, so T is reflexive on (A/S).

Second, we prove that T is anti-symmetric on (A/S).
Let x, y be arbitrary elements of A s.t. $[x]_S T [y]_S$ and $[y]_S T [x]_S$. Then (xRy) and (yRx). Then (xRy) and ($x R^{-1}$). Then (xSy). Then, $[x]_S = [y]_S$. Thus, T is anti-symmetric on (A/S).

Third, we prove that T is transitive on (A/S).
Let x,y,z be arbitrary elements of A s.t. $[x]_S T [y]_S$ and $[y]_S T [z]_S$. Then (xRy) and (yRz). Since R is transitive, so (xRz). Then $[x]_S T [z]_S$. Thus T is transitive on (A/S).

Hence, T is partial order on (A/S).


Ex-25:
(a) First, we prove that R is reflexive on A.
Let X be an arbitrary element of A. Its clear that $(X,X) \in R$. Thus R is reflexive.

Second, we prove that R is transitive on A.
Let (X,Y) and (Y,Z) be arbitrary elements of R. Then Y has atleast as many elements as X and Z has atleast as many elements as Y, so Z has atleast as many elements as X. Then $(X,Z) \in R$. Thus R is transitive.

Hence R is preorder on A.

(b) S = $R \cap R^{-1}$ = {$(X,Y) \in$ A x A | X and Y has same number of elements}

Since A = $P(I)$ and I has 100 elements, so no element in A contains more than 100 elements.

A/S = {$\emptyset$,
{elements of A containing 1 element},
{elements of A containing 2 elements},
...,
...,
{elements of A containing 100 elements}}
Clearly, A/S contain 101 elements.

And, if (X R Y) then $[X]_S T [Y]_S$. Then
T = {$([X]_S,[Y]_S)$ | Y has atleast as many elements as X}


Ex-26:
(a) First, we prove that R is reflexive on $P$.
Let $F$ be an arbitrary partition on A. It follows from the definition of "refine" that $F$ refines itself. Then $(F,F) \in R$. Since $F$ is arbitrary, so R is reflexive.

Second, we prove that R is anti-symmetric on $P$.
Let $F$ and $G$ be arbitrary partitions on A s.t. $(F,G) \in R$ and $(G,F) \in R$. So $F$ refines $G$ and $G$ refines $F$. Its not possible unless $F = G$. Thus $F = G$. So, R is anti-symmetric.

Third, we prove that R is transitive on $P$.
Let $F$, $G$ and $H$ be arbitrary partitions on A s.t. $(F,G) \in R$ and $(G,H) \in R$. Let X be arbitrary element of $F$, Y be arbitrary element of $G$ and Z be arbitrary element of $H$. Then $X \subseteq Y$ and $Y \subseteq Z$. Then $X \subseteq Z$. Since X and Z are arbitrary, so $F$ refines $H$. Hence $(F,H) \in R$. Thus R is transitive.

Hence, R is partial order on $P$.

(b) ($\rightarrow$) Suppose $S \subseteq T$. Let $[x]_S$ be an arbitrary element of $F$, that is A/S. Let a be an arbitrary element of $[x]_S$. Then $(a,x) \in S$. Since $S \subseteq T$, so $(a,x) \in T$. Thus $a \in [x]_T$. So $[x]_S \subseteq [x]_T$. Since $[x]_T \in A/T$, so $[x]_T \in G$. Since $[x]_S$ is arbitrary, so $F$ refines $G$.
($\leftarrow$) Suppose (A/S) refines (A/T). Let (x,y) be an arbitrary element of S. clearly, $[x]_S = [y]_S$. Since $[x]_S \in A/S$ and (A/S) refines (A/T), so we can choose some $[z]_T \in A/T$ s.t. $[x]_S \subseteq [z]_T$. So $x \in [z]_T$ and hence $(x,z) \in T$. Since $[x]_S = [y]_S$, so $(y,z) \in T$. Since T is equivalence relation, so its symmetric and transitive, thus it follows from $(x,z) \in T$ and $(y,z) \in T$ that $(x,y) \in T$. Since (x,y) is arbitrary so $S \subseteq T$

Thus $S \subseteq T$ iff (A/S) refines (A/T)

(c) First, we prove that $F.G$ is a lower bound of {$F,G$}.
So we need to prove that $(F.G,F) \in R$ and $(F.G,G) \in R$. Let Z be an arbitrary element of $F.G$, then by its definition we can choose some $X \in F$ and $Y \in G$ s.t. $Z = X \cap Y$. Then $Z \subseteq X$ and $Z \subseteq Y$. That means $F.G$ refines $F$ and $G$ both. Thus $(F.G,F) \in R$ and $(F.G,G) \in R$. Hence $F.G$ is a lower bound of set {$F,G$}

Second, we prove that $F.G$ is largest of all the lower bounds of {$F.G$}.
Let $H$ be an arbitrary lower bound of {$F,G$}. Let Z be an arbitrary element of $H$. It follows that we can choose some $X \in F$ and $Y \in G$ s.t. $Z \subseteq X$ and $Z \subseteq Y$. Then $Z \subseteq X \cap Y$. Since $X \cap Y \in F.G$, so $H$ refines $F.G$. Then $(H,F.G) \in R$. Since $H$ is arbitrary so $F.G$ is largest of all lower bounds of {$F,G$}.

Hence $F.G$ is greatest lower bound of {$F,G$}.