Function:
Suppose F is a relation from A to B. Then F is called a function from A to B if for every there is *exactly one* s.t. . In other words, F is a function if
This unique 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 for every .
Some Important Theorems:
1. Suppose f and g are functions from A to B. If then f = g
2. Suppose f:A -> B and g:B -> C. Then :A -> C and ()(a) = g(f(a)). Note that 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: is identity relation on . of a city c is the name of the city that is capital of the nation that has c.
Ex-6:
(x)
= f(g(x))
= f(2x - 1)
=
=
=
(x)
= g(f(x))
= g()
=
=
=
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 , so . Since f:A -> B, so we can choose some s.t. . Also, C x B. Then . Thus b = (f|C)(c).
Uniqueness:
Let c be an arbitrary clement of C. Assume b,d are arbitrary elements of B s.t. and . Then and . Since f is a function, so b = d.
Hence f|C is a function.
Now, prove that f(c) = f|C.
clearly . Since f:A->B, so and hence . Then . Thus . 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 . Then . Since (c,b) is arbitrary, so .
() Suppose .
Let (c,b) be an arbitrary element of g. Since , so and also . Then . Then . Since (c,b) is arbitrary, so .
Let (c,b) be an arbitrary element of f|C. Then and . Since and g:C -> B, so we can choose a particular s.t. . Since , so . Since and and and f is a function, so b = d. Since , so . Since (c,b) is arbitrary, so .
Hence g = f|C
(c) g:, g(x) = 2x + 3
h:, h(x) = 2x + 3
Prove that g = h| =
() Let (z,2z + 3) be arbitrary element of g. Since , so also. Then . Also . Thus . Hence
() Let (r,s) be arbitrary element of h|. Then and . Then and so . Since , so s = 2r + 3. Then . Since (r,s) is arbitrary so .
Hence g =
Ex-8: We will prove by contradiction that is the only relation on A that is equivalence relation on A and a function from A to A as well.
Proof: Suppose 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 as well. Since h is a function, so x = y. Then h is .
Ex-9:In this exercise f|C denotes restriction of f to C.
(a) Existence:
Let x be an arbitrary element of . Let us consider the two possible cases.
Case#1:
Then we can choose a particular s.t. . Then
Case#2:
Then we can choose a particular s.t. . Then
From above cases its proven that we can always find a s.t.
Uniqueness:
Let x be an arbitrary element of . Assume c,d be arbitrary elements of C s.t. and . Let us consider all the possible cases
Case#1: and
Then c = d
Case#2: and
Then c = d
Case#3: and
Since , so . Since , so . But A and B are disjoint, so x can't belong to both and hence this case is not possible
Case#4: and
This case is also not possible for the same reason as above
Hence c = d
Thus is a function from to C.
(b) () Suppose : -> C.
Let (a,c) be an arbitrary element of f|(). Then and . Then , so we can choose a particular s.t. . Then . Since , so . Then c = d. Hence . Thus . Since (a,c) is arbitrary, so
By a similar argument, we can prove that
Hence =
() Suppose = .
Existence:
Let x be an arbitrary element of . Then either or . In both the cases there exists some s.t. .
Uniqueness:
Let x be an arbitrary element of . Let c,d be arbitrary elements of C s.t. and . Now let us consider all possible cases
Case#1: and
Then c = d
Case#2: and
Then c = d
Case#3: and
Then . Since , so . By similar argument, . Since , so as well. Hence c = d
Case#4: and
By using similar argument as above, c = d
Hence : -> C
Ex-10:
(a) Existence:
Let b be an arbitrary element of B. Since Dom(S) = B, so we can choose some s.t.
Uniqueness:
Let b be an arbitrary element of B. Let c,d be arbitrary elements of C s.t. and . Since Ran(R) = B, so we can choose some s.t. . Then and . 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)}
= {(1,3)}
Ex-11:
(a) Suppose S is reflexive. Let x be an arbitrary element of A. , so because S is reflexive. Then . 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
(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 .
Since R is symmetric, so and hence . 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. and . Then we can choose u,v,w in A s.t.
f(u) = x
f(v) = y
f(w) = z and and .
Since R is transitive, so and hence . 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 .
Ex-13:
(a) Suppose R is reflexive. Let f be an arbitrary function in and let x be an arbitrary element of A. Then . Since R is reflexive, so . Since x is arbitrary so . 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 . Since R is symmetric, so . Then . 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 and . Since R is transitive, so . Then . Since (f,g) and (g,h) are arbitrary so S is transitive.
Ex-14:
(a) Let x be an arbitrary element of A.
Then, (x) = f(g(x)) = a = f(x).
(b) Let x be an arbitrary element of A. Then (x) = f(g(x)). Since = 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 , so . Thus .
(b) First, we prove that R is reflexive on .
Since for any arbitrary x in A, any arbitrary function f in , f(x) = f(x). Then . Since f is arbitrary, so R is reflexive.
Second, we prove that R is symmetric on .
Let (f,g) be an arbitrary ordered pair in R. Then we can choose an s.t. for every x > a, f(x) = g(x). Then g(x) = f(x) also. Then . Since (f,g) is arbitrary, so R is symmetric.
Third, we prove that R is transitive on .
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 . Since (f,g) and (g,h) are arbitrary, so R is transitive.
Hence R is equivalence relation on .
Ex-16:
(a) Proof for :
Let a = 3 and c = 8. Then for any x > a = 3,
|f(x)| = |7x + 3| = 7x + 3 < 7x + x = 8x < 8 = c|g(x)|
Hence
Proof for :
We'll prove it by contradiction. Assume . Then we can choose some and s.t.for every positive integer x > a, . For a x greater than a and 10c,
We have x > 10c
=> > 10cx ...(i)
Since
=>
=> ...(ii)
clearly there is a contradiction between eq (i) and (ii), so our assumption is correct and
(b) First, we prove that S is reflexive in .
For any arbitrary function and for any arbitrary x, clearly |f(x)| = |f(x)|. So . Then . Since f is arbitrary, so S is reflexive.
Second, we prove that S transitive in .
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.
and
Let e be the maximum of a and b. Let x be an arbitrary integer s.t. x > e. Then
and
Then . Since x is arbitrary, so . Thus . Since (f,g) and (g,h) are arbitrary, so S is transitive.
Hence S is a preorder.
(c) Since , so we can choose some and s.t. .
Since , so we can choose some and s.t. .
Let e be the maximum of a and b. Then for any arbitrary positive integer x > e,
|f(x)|
= (using triangle inequality)
=
Thus .
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 . 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 . 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 . 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 . So . Then g(x) = g(y). Since (x,y) is arbitrary so .
() Let (x,y) be arbitrary element of {}. Then g(x) = g(y). Then . Then . Since (x,y) is arbitrary so
Hence R = {}
Ex-18:
(a)Existence:
Let us consider h = {}
clearly as f(x) = f(x)
Uniqueness:
Let say there exists another function g s.t. g() = f(x).
Let (X,y) be arbitrary element of g. Since Dom(g) = A/R. So we can choose some s.t. and then . Then , where h is choosen above. so, . Also, clearly using the similar argument . 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 . Then . Then f(x) = f(y). Since x and y are arbitrary, so we can say that
Ex-19:
(a) Assume a function f s.t. f(x) =
Let (x,y) be arbitrary element of R.
Then x y(mod m)
so, we can choose some s.t.
x - y = km
=> x = y + km
=>
=>
Since is also an integer, so (mod m). Thus . Since R is equivalence relation, so . 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() = f(x) =
(b) We will prove it by contradiction. Assume there exists a function h:Z/R -> Z/R s.t. h() = .
Let (x,y) be arbitrary element in R. Then . Then . Then . Then .
Then (mod m)
So we can choose an integer k s.t.
= km ...(i)
Since 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
=
RHS is a constant, but LHS can't be, which is a contradiction and hence such a function as assumed can not exist.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment