Question

Let A be a finite set and let f be a surjection from A to itself....

Let A be a finite set and let f be a surjection from A to itself. Show that f is an injection.

Use Theorem 1, 2 and corollary 1.

Theorem 1 : Let B be a finite set and let f be a function on B. Then f has a right inverse. In other words, there is a function g: A->B, where A=f[B], such that for each x in A, we have f(g(x)) = x.

Theorem 2: A right inverse for a function is an injection

Corollary 1: An injection from a finite set to itself is a surjection

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let f be a function from the set of students in a discrete mathematics class to...
Let f be a function from the set of students in a discrete mathematics class to the set of all possible final grades. (a) Under what conditions is f an injection? (b) Under what conditions is f a surjection? (please show all work)
Let A be a finite set and f a function from A to A. Prove That...
Let A be a finite set and f a function from A to A. Prove That f is one-to-one if and only if f is onto.
Let f be a function which maps from the quaternion group, Q, to itself by f...
Let f be a function which maps from the quaternion group, Q, to itself by f (x) = i ∙x, for i∈ Q and each element x in Q. Show all work and explain! (i) Is ? a homomorphism? (ii) Is ? a 1-1 function? (iii) Does ? map onto Q?
Let (G,·) be a finite group, and let S be a set with the same cardinality...
Let (G,·) be a finite group, and let S be a set with the same cardinality as G. Then there is a bijection μ:S→G . We can give a group structure to S by defining a binary operation *on S, as follows. For x,y∈ S, define x*y=z where z∈S such that μ(z) = g_{1}·g_{2}, where μ(x)=g_{1} and μ(y)=g_{2}. First prove that (S,*) is a group. Then, what can you say about the bijection μ?
Let (G,·) be a finite group, and let S be a set with the same cardinality...
Let (G,·) be a finite group, and let S be a set with the same cardinality as G. Then there is a bijection μ:S→G . We can give a group structure to S by defining a binary operation *on S, as follows. For x,y∈ S, define x*y=z where z∈S such that μ(z) = g_{1}·g_{2}, where μ(x)=g_{1} and μ(y)=g_{2}. First prove that (S,*) is a group. Then, what can you say about the bijection μ?
We denote |S| the number of elements of a set S. (1) Let A and B...
We denote |S| the number of elements of a set S. (1) Let A and B be two finite sets. Show that if A ∩ B = ∅ then A ∪ B is finite and |A ∪ B| = |A| + |B| . Hint: Given two bijections f : A → N|A| and g : B → N|B| , you may consider for instance the function h : A ∪ B → N|A|+|B| defined as h (a) = f (a)...
Let F be the set of all finite languages over alphabet {0, 1}. Show that F...
Let F be the set of all finite languages over alphabet {0, 1}. Show that F is countable
Prove that (Orbit-Stabilizer Theorem). Let G act on a finite set X and fix an x...
Prove that (Orbit-Stabilizer Theorem). Let G act on a finite set X and fix an x ∈ X. Then |Orb(x)| = [G : Gx] (the index of Gx).
Proposition 16.4 Let S be a non–empty finite set. (a) There is a unique n 2...
Proposition 16.4 Let S be a non–empty finite set. (a) There is a unique n 2 N1 such that there is a 1–1 correspondence from {1, 2,...,n} to S. We write |S| = n. Also, we write |;| = 0. (b) If B is a set and f : B ! S is a 1–1 correspondence, then B is finite and |B| = |S|. (c) If T is a proper subset of S, then T is finite and |T| <...
Let g be a function from set A to set B and f be a function...
Let g be a function from set A to set B and f be a function from set B to set C. Assume that f °g is one-to-one and function f is one-to-one. Using proof by contradiction, prove that function g must also be one-to-one (in all cases).