how to prove it - ch5, sec5.3(Inverses of Functions) ex

This section is collection of some theorems about inverses of a funcion. Here they are, their proofs can be looked up in the book.

1. Suppose f:A -> B. f is one-to-one and onto iff $f^{-1}$:B -> A

2. Suppose f is a function from A to B and $f^{-1}$ is a function from B to A. Then $f^{-1}\circ f=i_A$ and $f\circ f^{-1}=i_B$

3. Suppose f:A -> B.
- If there is a function g:B -> A s.t. $g\circ f=i_A$ then f is one-to-one.
- If there is a function g:B -> A s.t. $f\circ g=i_B$ then f is onto

All of the above can be combined into this one.

4. Suppose f:A -> B. Then the following statements are equivalent.
- f is one-to-one and onto
- $f^{-1}$:B -.A
- There is a function g:B->A s.t. $g\circ f=i_A$ and $f\circ g=i_B$

Now, this one is used in proofs alot.

5. Suppose f:A->B, If there exists a function g:B->A s.t. $g\circ f=i_A$ and $f\circ g=i_B$. Then f is one-to-one and onto and $g=f^{-1}$

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

Ex-1: the person sitting immediately to the right of p

Ex-2: A\X

Ex-3: Consider, g(x) = $\frac{3x-5}{2}$.
Then $(g\circ f)\left(x\right)$
= g(f(x))
= g($\frac{2x+5}{3}$)
= $\frac{3\left(\frac{2x+5}{3}\right)-5}{2}$
= x

Thus $g\circ f=i_R$

Also, $(f\circ g)\left(x\right)$
= f(g(x))
= f($\frac{3x-5}{2}$)
= $\frac{2\left(\frac{3x-5}{2}\right)+5}{3}$
= x

Thus $f\circ g=i_R$

It follows from theorem#5 above that f is one-to-one and onto. and $f^{-1}\left(x\right)$ = g(x) = $\frac{3x-5}{2}$


Ex-4: Let g be a function from $R$ to $R$ defined as g(x) = $(\frac{x+3}{2}{)}^{\frac{1}{3}}$

Then, $(g\circ f)\left(x\right)$
= g(f(x))
= g($2x^3-3$)
= $(\frac{(2x^3-3)+3}{2}{)}^{\frac{1}{3}}$
= $(x^3{)}^{\frac{1}{3}}$
= x

Thus $g\circ f=i_R$

Also, $(f\circ g)\left(x\right)$
= f(g(x))
= f($(\frac{x+3}{2}{)}^{\frac{1}{3}}$)
= $2\left(\right(\frac{x+3}{2}{)}^{\frac{1}{3}}{)}^3-3$
= $2\left(\frac{x+3}{2}\right)-3$
= x

Thus $f\circ g=i_R$

Hence f is one-to-one and onto and $f^{-1}\left(x\right)$ = g(x) = $(\frac{x+3}{2}{)}^{\frac{1}{3}}$


Ex-5: Scratchwork:
y = $10^{2-x}$
taking log of both sides with base 10
log(y) = (2-x)log(10)
=> log(y) = 2-x
=> x = 2 - log(y)

Formal Proof:
Let $g:R^{+}\to R$ defined by g(x) = 2 - log(x)

It is easy to check that $g\circ f=i_R$ and $f\circ g=i_{R^{+}}$. Hence f is one-to-one and onto and $f^{-1}$ = g(x) = 2-log(x)


Ex-6: Scratchwork:
y = $\frac{3x}{x-2}$
=> xy - 2y = 3x
=> x(y-3) = 2y
=> x = $\frac{2y}{y-3}$

which is not defined for y = 3, clearly B = $R\backslash \left\{3\right\}$

(a),(b) B = $R\backslash \left\{3\right\}$ and consider g:B -> A defined as g(x) = $\frac{2x}{x-3}$.

Let x be an arbitrary element of A.
Then $(g\circ f)\left(x\right)$
= g(f(x))
= g($\frac{3x}{x-2}$)
= $\frac{2\left(\frac{3x}{x-2}\right)}{\left(\frac{3x}{x-2}\right)-3}$
= $\frac{6x}{3x-3(x-2)}$
= $\frac{6x}{6}$
= x

Thus $g\circ f=i_A$

Its trivial to check that $f\circ g=i_B$

Hence f is one-to-one and onto and $f^{-1}$ = g(x) = $\frac{2x}{x-3}$


Ex-7:
(a) Let x be an arbitrary real number.
Then, $(f_2\circ f_1)\left(x\right)$
= $f_2\left(f_1\right(x\left)\right)$
= $f_2(x+7)$
= $\frac{x+7}{5}$
= f(x)

Since x is arbitrary, so $f_2\circ f_1$ = f

(b) Note: g means f-inverse-1 and h means f-inverse-2.
It is trivial to compute that
g(x) = x - 7
h(x) = 5x

$(g\circ h)\left(x\right)$ = $g\left(h\right(x\left)\right)$ = $g\left(5x\right)$ = 5x-7 = $f^{-1}\left(x\right)$


Ex-8: Prove that $f\circ f^{-1}=i_B$
(a) Let b be an arbitrary element of B. Then we can choose some $a\in A$ s.t. f(a) = b. Then $f^{-1}\left(b\right)=a$
Now, $(f\circ f^{-1})\left(b\right)$ = f($f^{-1}\left(b\right)$) = f(a) = b

Since b is arbitrary, so $f\circ f^{-1}=i_B$

(b) It is given that $f^{-1}\circ f=i_A$. Let b be an arbitrary element of B.
Then $\left(\right(f^{-1}\circ f)\circ f^{-1})\left(b\right)$ = $(i_A\circ f^{-1})\left(b\right)$
=> $f^{-1}\left(\right(f\circ f^{-1}\left)\right(b\left)\right)$ = $f^{-1}\left(b\right)$

Thus, $(f\circ f^{-1})\left(b\right)=b$

Since b is arbitrary, so $f\circ f^{-1}=i_B$


Ex-9: Suppose g:A->B s.t. $f\circ g=i_B$. Let b be an arbitrary element of B. Then $(b,b)\in i_B$. Then $(b,b)\in f\circ g$. Then, we can choose $a\in A$ s.t. $(b,a)\in g$ and $(a,b)\in f$. Thus f(a) = b. Since b is arbitrary, so f is onto.


Ex-10: ($\to$) Let (b,a) be an arbitrary ordered pair in B X A s.t. $(b,a)\in g$. Since $(b,b)\in i_B$, then $(b,b)\in f\circ g$. Then we can choose some $a_0\in A$ s.t. $(b,a_0)\in g$ and $(a_0,b)\in f$. Since $(b,a)\in g$, $(b,a_0)\in g$ and g is a function, so $a=a_0$. Hence $(a,b)\in f$ and then $(b,a)\in f^{-1}$.

($\leftarrow$) Let (b,a) be an arbitrary ordered pair in B X A s.t. $(b,a)\in f^{-1}$. Then $(a,b)\in f$. Since $(a,a)\in i_A$, then $(a,a)\in g\circ f$. Then we can choose some $b_0\in B$ s.t. $(a,b_0)\in f$ and $(b_0,a)\in g$. Since $(a,b)\in f$, $(a,b_0)\in f$ and f is a function, so $b=b_0$. Hence $(b,a)\in g$.


Ex-11:
(a) Since $f\circ g=i_B$, so by theorem 5.3.3(2) f is onto. Since f is one-to-one and onto, so $f^{-1}\circ f=i_A$.
Then, g = $i_A\circ g$ = $(f^{-1}\circ f)\circ g$ = $f^{-1}\circ (f\circ g)$ = $f^{-1}\circ i_B$ = $f^{-1}$

(b) Since $g\circ f=i_A$, so by theorem 5.3.3(1) f is one-to-one. Since f is one-to-one and onto, so $f\circ f^{-1}=i_B$.
Then, g = $g\circ i_B$ = $g\circ (f\circ f^{-1})$ = $(g\circ f)\circ f^{-1}$ = $i_A\circ f^{-1}$ = $f^{-1}$

(c) Since $f\circ g=i_B$, so by theorem 5.3.3(2) f is onto. We will prove by contradiction that f is not one-to-one. Assume f is one-to-one. Since f is one-to-one and $f\circ g=i_B$, using part(a) g = $f^{-1}$. Since f is one-to-one and onto, so $f^{-1}\circ f=i_A$. Then $g\circ f=i_A$, but this contradicts with the given. Hence the assumption is false and f is not one-to-one.

Since $f\circ g=i_B$, so by theorem 5.3.3(1) g is one-to-one. We will prove by contradiction that g is not onto. Assume g is onto. Then using part(2) f = $g^{-1}$. Since g is one-to-one and onto, so $g\circ g^{-1}=i_A$. Then $g\circ f=i_A$, but this contradicts with the given. Hence the assumption is false and g is not onto.


Ex-12: Let B' = Ran(f). We'll prove that $f^{-1}$:B' -> A.
Existence:
Let b be an arbitrary element of B'. Since B' = Ran(f), so we can choose some $a\in A$ s.t. $(a,b)\in f$. Then $(b,a)\in f^{-1}$.

Uniqueness:
Let b be an arbitrary element of B' and $a_1$, $a_2$ be two arbitrary elements of A s.t. $(b,a_1)\in f^{-1}$ and $(b,a_2)\in f^{-1}$. Then $(a_1,b)\in f$ and $(a_2,b)\in f$. Since f is one-to-one, so $a_1=a_2$.

Hence $\forall b\in B\exists !a\in A\left(f^{-1}\right(b)=a)$. Thus $f^{-1}$:B' -> A


Ex-13:
(a) Its trivial to see that $\forall x\in A\forall y\in A(xRy\to f(x)=f(y\left)\right)$. So f is compatible with R. By using result of ex-18(a) in section-5.1 there exists a function h:A/R -> B s.t. for all $x\in A$, h($[x{]}_R$) = f(x)

(b) It follows straightforward from the result of ex-16, sec-5.2 that h is one-to-one.

Proof for h is onto:
Let b be an arbitrary element of B. Since f is onto, so we can choose $a\in A$ s.t. f(a) = b. clearly $a\in [a{]}_R$, so h($[a{]}_R$) = f(a) = b. Hence, h is onto.

(c) Let g(b) = {$x\in A\mid f\left(x\right)=b$}
Let a be an arbitrary element of A. Then
$(g\circ h)\left(\right[a{]}_R)$ = g(h($[a{]}_R$)) = g(f(a)) = {$x\in A\mid f\left(x\right)=f\left(a\right)$} = {$x\in A\mid (x,a)\in R$} = $[a{]}_R$. Thus, $g\circ h$ = $i_{A/R}$

Let b be an arbitrary element of B. Then
$(h\circ g)\left(b\right)$ = h(g(b)) = h({$x\in A\mid f\left(x\right)=b$})

Since f is onto, so we can choose some $a\in A$ s.t. f(a) = b. Then
{$x\in A\mid f\left(x\right)=b$} = {$x\in A\mid f\left(x\right)=f\left(a\right)$} = {$x\in A\mid xRa$} = $[a{]}_R$

Then $(h\circ g)\left(b\right)$ = h($[a{]}_R$) = f(a) = b. Thus $h\circ g$ = $i_B$

Since $g\circ h$ = $i_{A/R}$ and $h\circ g$ = $i_B$, so $h^{-1}$(b) = g(b) = {$x\in A\mid f\left(x\right)=b$}


NOTE: In all the exercises below, f|A denotes restriction of f to set A.


Ex-14:
(a) Let a be an arbitrary element of A'. Then we can choose some $b\in B$ s.t. g(b) = a.
Now $(g\circ f)\left(a\right)$ = $(g\circ f)\left(g\right(b\left)\right)$ = $(g\circ (f\circ g\left)\right)\left(b\right)$ = $(g\circ i_B)\left(b\right)$ = $g\left(i_B\right(b\left)\right)$ = g(b) = a. Since a is arbitrary, so for any $x\in Aʹ$, $(g\circ f)\left(x\right)=x$

(b) Its easy to see that $(f\mid Aʹ)\circ g=i_B$ and $g\circ (f\mid Aʹ)=i_{Aʹ}$. Hence by theorem 5.3.4, f|A' is one-to-one and onto function from A' to B. And g = $(f\mid Aʹ{)}^{-1}$


Ex-15: Let A' = Ran(g). It follows from result of ex-14(b) that g = $(f\mid Aʹ{)}^{-1}$. Also, its trivial to find that Ran(g) = B, hence A' = B. Thus g = $(f\mid B{)}^{-1}$


Ex-16:
(a) Let b be some real number s.t. f(x) = b.
Then $4x-x^2=b$
=> $x^2-4x+b=0$

This quadratic equation has real roots if $(-4{)}^2-4(1\left)\right(b)\ge 0$ $\equiv$ $16-4b\ge 0$ $\equiv$ $b\le 4$.

Hence B = {$x\in R\mid x\le 4$}

(b) Scratchwork:
Using ex-14 result, basically we want to find a function g:R -> R s.t. $f\circ g=i_R$. Then A = Ran(g) and g = $(f\mid A{)}^{-1}$.

$(f\circ g)\left(x\right)=x$
=> f(g(x)) = x

Let g(x) = y, then
f(y) = x
=> $4y-y^2=x$

one root of above quadratic equation is, y = g(x) = $2+\sqrt{4-x}$

Formal Proof:
Let g(x) = $2+\sqrt{4-x}$.

$(f\circ g)\left(x\right)$ = f(g(x)) = f($2+\sqrt{4-x}$) = $4(2+\sqrt{4-x})-(2+\sqrt{4-x}{)}^2$ = $8+4\sqrt{4-x}-(4+4-x+4\sqrt{4-x})$ = x

Hence $f\circ g=i_R$

It follows from ex-14 result that A = Ran(g) = {$x\in R\mid x\ge 2$} and $(f\mid A{)}^{-1}$(x) = g(x) = $2+\sqrt{4-x}$


Ex-17: Scratchwork:
If we prove that $g\circ f=i_P$ and $f\circ g=i_S$, then it follows from theorem 5.3.3 and 5.3.5 that f is one-to-one and onto and g = $f^{-1}$

Formal Proof:
Proof for $g\circ f=i_P$:
Let R be an arbitrary element of $P$.
Then, $(g\circ f)\left(R\right)$ = g(f(R)) = g($R\backslash i_A$) = $(R\backslash i_A)\cup i_A$ = R. Since R is arbitrary, so $g\circ f=i_P$

Proof for $f\circ g=i_S$:
Let R be an arbitrary element of $S$.
Then, $(f\circ g)\left(R\right)$ = f(g(R)) = f($R\cup i_A$) = $(R\cup i_A)\backslash i_A$

Since R is strict partial order on A, hence irreflexive and hence R and $i_A$ are disjoint. Then $(R\cup i_A)\backslash i_A$ = R. Then $(f\circ g)\left(R\right)=R$. Since R is arbitrary, so $f\circ g=i_S$

Then it follows from theorem 5.3.3 and 5.3.5 that f is one-to-one and onto and g = $f^{-1}$


Ex-18:
(a) First, we prove that R is reflexive on $F$
Let f be an arbitrary function in $F$. Let h = $i_A$. Then $h^{-1}\circ f\circ h$ = f. Hence fRf. Since f is arbitrary, so R is reflexive.

Second, we prove that R is symmetric on $F$
Let (f,g) be arbitrary ordered pair in $FxF$ s.t. $(f,g)\in R$. Then we can choose a function $h\in P$ s.t. f = $h^{-1}\circ g\circ h$. Then $h\circ f=g\circ h$. Then $g=h\circ f\circ h^{-1}$. Let j = $h^{-1}$. Then g = $j^{-1}\circ f\circ j$. Hence $(g,h)\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 elements of R. So we can choose functions u,v in $P$ s.t.
f = $u^{-1}\circ g\circ u$ and g = $v^{-1}\circ h\circ v$.

Then f = $u^{-1}\circ g\circ u$ = $u^{-1}\circ (v^{-1}\circ h\circ v)\circ u$ = $(v\circ u{)}^{-1}\circ h\circ (v\circ u)$. Let j = $v\circ u$. Then f = $j^{-1}\circ h\circ j$. Hence $(f,h)\in R$. Hence R is transitive.


Thus R is equivalence relation on $F$.

(b) Suppose fRg, then we can choose $h\in P$ s.t. f = $h^{-1}\circ g\circ h$.

Then $f\circ f$
= $(h^{-1}\circ g\circ h)\circ (h^{-1}\circ g\circ h)$
= $h^{-1}\circ (g\circ g)\circ h$

Hence $(f\circ f)R(g\circ g)$

(c) Suppose f has a fixed point and fRg. Then we can choose some $a\in A$ s.t. f(a) = a. We can choose $h\in P$ s.t. f = $h^{-1}\circ g\circ h$.
So f(a) = $(h^{-1}\circ g\circ h)\left(a\right)$

Let h(a) = b. Then
f(a) = $(h^{-1}\circ g)\left(b\right)$
=> a = $h^{-1}\left(g\right(b\left)\right)$

Thus $\left(g\right(b),a)\in h^{-1}$
=> $(a,g(b\left)\right)\in h$.

we assumed h(a) = b, that is $(a,b)\in h$

Since h is one-to-one, hence g(b) = b. So g has a fixed point.