Wednesday, June 16, 2010

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 aA there is *exactly one* bB s.t. (a,b)F. In other words, F is a function if
  aA!bB((a,b)F)
This unique bB 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 bB for every aA.

Some Important Theorems:

1. Suppose f and g are functions from A to B. If aA(f(a)=g(a)) then f = g
2. Suppose f:A -> B and g:B -> C. Then gf:A -> C and (gf)(a) = g(f(a)). Note that gf 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: LH is identity relation on N. HL of a city c is the name of the city that is capital of the nation that has c.


Ex-6:
fg(x)
= f(g(x))
= f(2x - 1)
= 1(2x-1)2+2
= 14x2+1-4x+2
= 14x2-4x+3

gf(x)
= g(f(x))
= g(1x2+2)
= 21x2+2-1
= 2-x2-2x2+2
= -x2x2+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 CA, so cA. Since f:A -> B, so we can choose some bB s.t. (c,b)f. Also, (c,b) C x B. Then (c,b)fCxB. 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)fC and (c,d)fC. Then (c,b)f and (c,d)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))f. Since f:A->B, so f(c)B and hence (c,f(C))CxB. Then (c,f(c))fCxB. Thus (c,f(c))fC. So f(c) = (f|C)(c)

(b) () Suppose g = (f|C). Let (c,b) be an arbitrary element of g. It follows from the assumption that (c,b)(fC). Then (c,b)f. Since (c,b) is arbitrary, so gf.
() Suppose gf.
Let (c,b) be an arbitrary element of g. Since gf, so (c,b)f and also (c,b)CxB. Then (c,b)fCxB. Then (c,b)fC. Since (c,b) is arbitrary, so gfC.
Let (c,b) be an arbitrary element of f|C. Then (c,b)f and (c,b)CxB. Since cC and g:C -> B, so we can choose a particular dB s.t. (c,d)g. Since gf, so (c,d)f. Since (c,b)f and and (c,d)f and f is a function, so b = d. Since (c,d)g, so (c,b)g. Since (c,b) is arbitrary, so (fC)g.
Hence g = f|C

(c) g:ZR, g(x) = 2x + 3
h:RR, h(x) = 2x + 3

Prove that g = h|Z = hZxR

() Let (z,2z + 3) be arbitrary element of g. Since zZ, so zR also. Then (z,2z+3)h. Also (z,2z+3)ZxR. Thus (z,2z+3)hZ. Hence ghZ
() Let (r,s) be arbitrary element of h|Z. Then (r,s)h and (r,s)ZxR. Then rZ and so (r,2r+3)g. Since (r,s)h, so s = 2r + 3. Then (r,s)g. Since (r,s) is arbitrary so hZg.

Hence g = hZ


Ex-8: We will prove by contradiction that iA is the only relation on A that is equivalence relation on A and a function from A to A as well.
Proof: Suppose iA 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)h as well. Since h is a function, so x = y. Then h is iA.


Ex-9:In this exercise f|C denotes restriction of f to C.
(a) Existence:
Let x be an arbitrary element of AB. Let us consider the two possible cases.
Case#1: xA
Then we can choose a particular cC s.t. (x,c)f. Then (x,c)gf

Case#2: xB
Then we can choose a particular cC s.t. (x,c)g. Then (x,c)gf

From above cases its proven that we can always find a cC s.t. (x,c)gf

Uniqueness:
Let x be an arbitrary element of AB. Assume c,d be arbitrary elements of C s.t. (x,c)gf and (x,d)gf. Let us consider all the possible cases
Case#1: (x,c)g and (x,d)g
Then c = d

Case#2: (x,c)f and (x,d)f
Then c = d

Case#3: (x,c)f and (x,d)g
Since (x,c)f, so xA. Since (x,d)g, so xB. But A and B are disjoint, so x can't belong to both and hence this case is not possible

Case#4: (x,c)g and (x,d)f
This case is also not possible for the same reason as above

Hence c = d

Thus gf is a function from AB to C.
(b) () Suppose fg:AB -> C.
Let (a,c) be an arbitrary element of f|(AB). Then (a,c)f and (a,c)ABxC. Then aB, so we can choose a particular dC s.t. (a,d)g. Then (a,d)fg. Since (a,c)f, so (a,c)fg. Then c = d. Hence (a,c)g. Thus (a,c)gAB. Since (a,c) is arbitrary, so fABgAB
By a similar argument, we can prove that gABfAB
Hence fAB = gAB

() Suppose fAB = gAB.
Existence:
Let x be an arbitrary element of AB. Then either xA or xB. In both the cases there exists some cC s.t. (x,c)fg.

Uniqueness:
Let x be an arbitrary element of AB. Let c,d be arbitrary elements of C s.t. (x,c)fg and (x,d)fg. Now let us consider all possible cases
Case#1: (x,c)f and (x,d)f
Then c = d

Case#2: (x,c)g and (x,d)g
Then c = d

Case#3: (x,c)f and (x,d)g
Then xAB. Since (x,c)(AB)xC, so (x,c)fAB. By similar argument, (x,d)gAB. Since fAB=gAB, so (x,d)fAB as well. Hence c = d

Case#4: (x,c)g and (x,d)f
By using similar argument as above, c = d

Hence fg:AB -> C


Ex-10:
(a) Existence:
Let b be an arbitrary element of B. Since Dom(S) = B, so we can choose some cC s.t. (b,c)S

Uniqueness:
Let b be an arbitrary element of B. Let c,d be arbitrary elements of C s.t. (b,c)S and (b,d)S. Since Ran(R) = B, so we can choose some aA s.t. (a,b)R. Then (a,c)SR and (a,d)SR. 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)}
SR = {(1,3)}


Ex-11:
(a) Suppose S is reflexive. Let x be an arbitrary element of A. f(x)B, so (f(x),(f(x)))S because S is reflexive. Then (x,x)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)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)R.
Since R is symmetric, so (v,u)R and hence (y,x)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)S and (y,z)S. Then we can choose u,v,w in A s.t.
f(u) = x
f(v) = y
f(w) = z and (u,v)R and (v,w)R.
Since R is transitive, so (u,w)R and hence (x,z)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)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)B. Since R is reflexive, so (f(x),f(x))R. Since x is arbitrary so (f,f)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))R. Since R is symmetric, so (g(x),f(x))R. Then (g,f)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))R and (g(x),h(x))R. Since R is transitive, so (f(x),h(x))R. Then (f,h)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, (fg)(x) = f(g(x)) = a = f(x).

(b) Let x be an arbitrary element of A. Then (fg)(x) = f(g(x)). Since (fg) = 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 x>0(x=x), so (x,x)R. Thus (f,g)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)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 aR s.t. for every x > a, f(x) = g(x). Then g(x) = f(x) also. Then (g,f)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)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 fO(g):
Let a = 3 and c = 8. Then for any x > a = 3,
|f(x)| = |7x + 3| = 7x + 3 < 7x + x = 8x < 8x2 = c|g(x)|
Hence fO(g)

Proof for gO(f):
We'll prove it by contradiction. Assume gO(f). Then we can choose some az+ and cR+ s.t.for every positive integer x > a, x2c7x+3. For a x greater than a and 10c,
We have x > 10c
=> x2 > 10cx ...(i)

Since x2c7x+3
=> x2c7x+3x
=> x210cx ...(ii)

clearly there is a contradiction between eq (i) and (ii), so our assumption is correct and gO(f)

(b) First, we prove that S is reflexive in F.
For any arbitrary function fF and for any arbitrary x, clearly |f(x)| = |f(x)|. So fO(f). Then (f,f)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.
x>a(f(x)cg(x)) and
x>b(g(x)dh(x))

Let e be the maximum of a and b. Let x be an arbitrary integer s.t. x > e. Then
f(x)cg(x) and
g(x)dh(x)

Then f(x)cdh(x). Since x is arbitrary, so fO(h). Thus (f,h)S. Since (f,g) and (g,h) are arbitrary, so S is transitive.

Hence S is a preorder.

(c) Since f1O(g), so we can choose some aZ+ and cR+ s.t. x>a(f1(x)cg(x)).
Since f2O(g), so we can choose some bZ+ and dR+ s.t. x>b(f2(x)dg(x)).

Let e be the maximum of a and b. Then for any arbitrary positive integer x > e,
|f(x)|
= sf1(x)+tf2(x) (using triangle inequality)
sf1(x)+tf2(x)
cg(x)+dg(x) = (c+d)g(x)

Thus fO(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)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)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)R. Since (x,y) and (y,z) are arbitrary, so R is transitive.

Hence R is equivalence relation on A.

(b) () Let (x,y) be arbitrary element of R. Since R is equivalence relation, hence symmetric. Then (y,x)R. So [x]R=[y]R. Then g(x) = g(y). Since (x,y) is arbitrary so R{(x,y)AxAg(x)=g(y)}.
() Let (x,y) be arbitrary element of {(x,y)AxAg(x)=g(y)}. Then g(x) = g(y). Then [x]R=[y]R. Then (x,y)R. Since (x,y) is arbitrary so {(x,y)AxAg(x)=g(y)}R

Hence R = {(x,y)AxAg(x)=g(y)}


Ex-18:
(a)Existence:
Let us consider h = {(X,y)A/RxBxX(f(x)=y)}

clearly ([x]R,x)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 xA s.t. [x]R=X and then y=f(x). Then (X,y)h, where h is choosen above. so, gh. Also, clearly using the similar argument hg. 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 xAyA(xRyf(x)=f(y))


Ex-19:
(a) Assume a function f s.t. f(x) = [x2]R
Let (x,y) be arbitrary element of R.
Then x y(mod m)
so, we can choose some kZ s.t.
x - y = km
=> x = y + km
=> x2=y2+k2m2+2ykm
=> x2-y2=m(k2m+2yk)

Since (k2m+2yk) is also an integer, so x2y2(mod m). Thus (x2,y2)R. Since R is equivalence relation, so [x2]R=[y2]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) = [x2]R

(b) We will prove it by contradiction. Assume there exists a function h:Z/R -> Z/R s.t. h([x]R) = [2x]R.
Let (x,y) be arbitrary element in R. Then [x]R=[y]R. Then h([x]R)=h([y]R). Then [2x]R=[2y]R. Then (2x,2y)R.
Then 2x2y(mod m)

So we can choose an integer k s.t.
2x-2y = km ...(i)

Since (x,y)R also so x y(mod m). Hence we can choose an integer l s.t. (x - y) = lm ...(ii)

From eq(i) and eq(ii) we get
2x-2yx-y = kl

RHS is a constant, but LHS can't be, which is a contradiction and hence such a function as assumed can not exist.

No comments:

Post a Comment