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.