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$