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 $\neg \exists a_1\in A\exists a_2\in A\left(f\right(a_1)=f(a_2)\wedge a_1\ne 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\left(f\right(a_1)=f(a_2)\to a_1=a_2)$

Onto:
A function f:A -> B is called onto if $\forall b\in B\exists a\in A\left(f\right(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) ($\to$) Let (x,y) be an arbtirary element in $f\circ f$.
So, y =$(f\circ f)\left(x\right)$
= 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)\left(x\right)$ = 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) = {}
(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)\left(a\right)=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)\left(x\right)$ = g(f(x)) = g(u)
Also $(g\circ f)\left(y\right)$ = 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\left(b_1\right)=g\left(b_2\right)$ but $b_1\ne b_2$. Since f is onto, so we can choose $a_1$ and $a_2$ in A s.t. $f\left(a_1\right)=b_1$ and $f\left(a_2\right)=b_2$ and $a_1\ne a_2$. Thus $(g\circ f)\left(a_1\right)$ = $(g\circ f)\left(a_2\right)$ and $a_1\ne 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)\left(a\right)=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\ne 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\ne c$. Then there does not exist any $x\in A$ s.t. f(x) = c. Hence f is not onto.


Ex-12: ($\to$) 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)\left(a\right)=(f\cup g)\left(b\right)=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)\left(x\right)=(f\cup g)\left(y\right)=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) ($\to$) 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: ($\to$) 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\left(f\right(x)=f(y)\to 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\left(f\right(x)=f(y)\to x=y)$


Ex-17: Suppose f is onto, g:B -> C , h:B -> C and $g\circ f$ = $h\circ f$.
(a) ($\to$) 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\left(g\right(x)=c_1)$, $\forall x\in B\backslash \left\{b\right\}\left(h\right(x)=c_1)$ and h(b) = $c_2$. Then $g\ne h$, so $g\circ f\ne h\circ f$ and therefore we can choose some $a\in A$ s.t. g(f(a)) $\ne$ h(f(a)). But by definition of g and h, there is only one $x\in B$ s.t. g(x) $\ne$ 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$.
($\to$) 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\left(g\right(x)=b_1)$ and $\forall x\in A\left(h\right(x)=b_2)$.
Now for every $x\in A$, $(f\circ g)\left(x\right)$ = f(g(x)) = f($b_1$) = f($b_2$) = f(h(x)) = $(f\circ h)\left(x\right)$. 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)\left(x\right)$ = 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)\left(x\right)$
=> $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)\left(x\right)$ = $i_R\left(f\right(x\left)\right)$ = 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)\left(x\right)$ = $j_1\left(g\right(x\left)\right)$ = $j_1\left(j_2\right(h\left(x\right)\left)\right)$ = $(j_1\circ j_2)\left(h\right(x\left)\right)$. Let j = $j_1\circ j_2$. Then $(j_1\circ g)\left(x\right)$ = $(j\circ h)\left(x\right)$. 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)\left(x\right)$ = f($i_R\left(x\right)$) = 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$.
($\to$) Suppose $i_{R}Rf$. 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\left(x\right)$ = $(j\circ f)\left(x\right)$ = j(f(x)) = j(f(y)) = $(j\circ f)\left(y\right)$ = $i_R\left(y\right)$ = 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 \left(\right(R\backslash A\left)X\right\{0\left\}\right)$.
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\backslash A$. Then $(x,0)\in \left(\right(R\backslash A\left)X\right\{0\left\}\right)$. 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)\left(x\right)$ = h(f(x)) = x = $i_R\left(x\right)$. Since x is arbitrary, so $i_R=h\circ f$

Hence $i_{R}Rf$

(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.

($\to$) Suppose $\forall f\in F\left(fRg\right)$. 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)\left(x\right)$ = 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)\left(x\right)$ = 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_{R}Rg$. 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) $fR{i}_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)\left(x\right)$
= h(g(x))
= $(j_2\circ j_1)\left(g\right(x\left)\right)$
= $j_2\left(j_1\right(g\left(x\right)\left)\right)$
= $j_2\left(\right(j_1\circ g\left)\right(x\left)\right)$
= $j_2\left(i_R\right(x\left)\right)$
= $(j_2\circ i_R)\left(x\right)$
= f(x)

Thus f = $h\circ g$. Hence fRg. And, so $\left[f{]}_{S}T\right[g{]}_S$. Since f is arbitrary so $\forall f\in F\left(\right[f{]}_{S}T\left[g{]}_S\right)$, 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 $\left[g{]}_{S}T\right[f{]}_S$. Hence set of all constant functions is smallest element of $F/S$