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)(x)$
= g(f(x))
= g($\frac{2x+5}{3}$)
= $\frac{3(\frac{2x+5}{3})-5}{2}$
= x

Thus $g \circ f = i_R$

Also, $(f \circ g)(x)$
= f(g(x))
= f($\frac{3x-5}{2}$)
= $\frac{2(\frac{3x-5}{2})+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}(x)$ = 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)(x)$
= 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)(x)$
= f(g(x))
= f($(\frac{x+3}{2})^\frac{1}{3}$)
= $2((\frac{x+3}{2})^\frac{1}{3})^3 - 3$
= $2(\frac{x+3}{2}) - 3$
= x

Thus $f \circ g = i_R$

Hence f is one-to-one and onto and $f^{-1}(x)$ = 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^+ \rightarrow 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 \setminus \{3\}$

(a),(b) B = $R \setminus \{3\}$ 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)(x)$
= g(f(x))
= g($\frac{3x}{x-2}$)
= $\frac{2(\frac{3x}{x-2})}{(\frac{3x}{x-2})-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)(x)$
= $f_2(f_1(x))$
= $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)(x)$ = $g(h(x))$ = $g(5x)$ = 5x-7 = $f^{-1}(x)$


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}(b) = a$
Now, $(f \circ f^{-1})(b)$ = f($f^{-1}(b)$) = 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 $((f^{-1} \circ f) \circ f^{-1})(b)$ = $(i_A \circ f^{-1})(b)$
=> $f^{-1}((f \circ f^{-1})(b))$ = $f^{-1}(b)$

Thus, $(f \circ f^{-1})(b) = 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: ($\rightarrow$) 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 (f^{-1}(b) = a)$. Thus $f^{-1}$:B' -> A


Ex-13:
(a) Its trivial to see that $\forall x \in A \forall y \in A (xRy \rightarrow f(x) = f(y))$. 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 | f(x) = b$}
Let a be an arbitrary element of A. Then
$(g \circ h)([a]_R)$ = g(h($[a]_R$)) = g(f(a)) = {$x \in A | f(x) = f(a)$} = {$x \in A | (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)(b)$ = h(g(b)) = h({$x \in A | f(x) = b$})

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

Then $(h \circ g)(b)$ = 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 | f(x) = 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)(a)$ = $(g \circ f)(g(b))$ = $(g \circ (f \circ g))(b)$ = $(g \circ i_B)(b)$ = $g(i_B(b))$ = g(b) = a. Since a is arbitrary, so for any $x \in A'$, $(g \circ f)(x) = x$

(b) Its easy to see that $(f|A') \circ g = i_B$ and $g \circ (f|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|A')^{-1}$


Ex-15: Let A' = Ran(g). It follows from result of ex-14(b) that g = $(f|A')^{-1}$. Also, its trivial to find that Ran(g) = B, hence A' = B. Thus g = $(f|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)(b) \geq 0$ $\equiv$ $16 - 4b \geq 0$ $\equiv$ $b \leq 4$.

Hence B = {$x \in R | x \leq 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|A)^{-1}$.

$(f \circ g)(x) = 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)(x)$ = 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 | x \geq 2$} and $(f|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)(R)$ = g(f(R)) = g($R \setminus i_A$) = $(R \setminus 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)(R)$ = f(g(R)) = f($R \cup i_A$) = $(R \cup i_A) \setminus 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) \setminus i_A$ = R. Then $(f \circ g)(R) = 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 $F x F$ 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)(a)$

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

Thus $(g(b),a) \in h^{-1}$
=> $(a,g(b)) \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.