Discrete Math Problems

stacy947

New member
Joined
Dec 1, 2014
Messages
2
1. (a) Let A be a set. Prove that if f :A → A satisfies f ◦f = 1A, then P = { { x, f(x) } | x ∈ A }, is a partition of A.

(b) Let A be a set, and let f :A → A. Prove that if there exists a positive integer n such that f^n = 1A, then f is bijective.

(c) How many bijective functions f :{1,2,3,4,5,6,7} → {1,2,3,4,5,6,7} satisfy f = f^(-1)?

2. Let f :N → N be the function for which f(n) = n + 1 for each n ∈ N. Note that f is injective. Find all left inverses of f.

3. (a) Let A and B be sets. Prove that the relation R = { (f, g) ∈ F(A, B) | Ker(f) = Ker(g) } on the set F(A, B) of all functions from A to B is an equivalence relation.
(b) Let A = {1,2,3,4,5} and B = {1,2,3}. For f =
1 2 3 4 5
1 1 3 1 1
what is |[f]R|?. Give one element g ∈ [f]R with g/= f.
 
Last edited by a moderator:
1. (a) Let A be a set. Prove that if f :A → A satisfies f ◦f = 1A, then P = { { x, f(x) } | x ∈ A }, is a partition of A.

(b) Let A be a set, and let f :A → A. Prove that if there exists a positive integer n such that f^n = 1A, then f is bijective.

(c) How many bijective functions f :{1,2,3,4,5,6,7} → {1,2,3,4,5,6,7} satisfy f = f^(-1)?

2. Let f :N → N be the function for which f(n) = n + 1 for each n ∈ N. Note that f is injective. Find all left inverses of f.

3. (a) Let A and B be sets. Prove that the relation R = { (f, g) ∈ F(A, B) | Ker(f) = Ker(g) } on the set F(A, B) of all functions from A to B is an equivalence relation.
(b) Let A = {1,2,3,4,5} and B = {1,2,3}. For f =
1 2 3 4 5
1 1 3 1 1
what is |[f]R|?. Give one element g ∈ [f]R with g/= f.
What are your thoughts? What have you tried? How far have you gotten? Where are you stuck?

Please be complete. Thank you! ;)
 
What are your thoughts? What have you tried? How far have you gotten? Where are you stuck?

Please be complete. Thank you! ;)

For 1b) I can see that it must be invertible thus bijective, but not sure how to prove

For 1c) 7^7?

For 2) g(n) = n - 1?

3a)
Clearly for any function f we have ker(f) = ker(f), so (f,f) ∈ R.
If f and g are function and (f,g) ∈ R we have ker(f) = ker(g). Clearly this means that ker(g) = ker(f), therefore (g,f) ∈ R.
Let f, g and h be function and suppose (f,g),(g,h) ∈ R. Then ker(f) = ker(g) and ker(g) = ker(h). Therefore, ker(f) = ker(h), so (f,h) ∈ R.
This shows that R is an equivalence relation.
 
For 1b) I can see that it must be invertible thus bijective, but not sure how to prove

For 1c) 7^7?

For 2) g(n) = n - 1?

3a)
Clearly for any function f we have ker(f) = ker(f), so (f,f) ∈ R.
If f and g are function and (f,g) ∈ R we have ker(f) = ker(g). Clearly this means that ker(g) = ker(f), therefore (g,f) ∈ R.
Let f, g and h be function and suppose (f,g),(g,h) ∈ R. Then ker(f) = ker(g) and ker(g) = ker(h). Therefore, ker(f) = ker(h), so (f,h) ∈ R.
This shows that R is an equivalence relation.

1b) Suppose y is in A. Let x=f^{n-1}(y). What is f(x)? Next supuse f(a)=f(b). What happens when you apply f^{n-1}?

1c) You need to count how many functions (i.e. special ordered pairs of AxA) satisfy f(a)=b iff f(b)=a. So how many functions S satisfy (a,b) is a point in S implies (b,a) is in S

3) The words 'clearly' probably shouldn't be in your proofs. An argument on the basis of them being sets is fine, though your teacher may want you to say something about the meaning of kernel.
 
Top