1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that an endomorphism is injective iff it is surjective

  1. Feb 8, 2017 #1
    1. The problem statement, all variables and given/known data
    Prove that an endomorphism between two finite sets is injective iff it is surjective

    2. Relevant equations


    3. The attempt at a solution
    I can explain this in words. First assume that it is injective. This means that every element in the domain is mapped to a single, unique element in the codomain, with no overlap. Since the domain and the codomain are the same size, this means that the map would have to be surjective. In the other direction, assume that the map is surjective, which means that every element in the domain must be associated with a unique element in the codomian. Since they are the same size, this the map is injective.

    Is this acceptable? Is there a better, more mathematical way to come to these conclusions using the definitions of injective and surjective?
     
    Last edited: Feb 8, 2017
  2. jcsd
  3. Feb 8, 2017 #2

    fresh_42

    Staff: Mentor

    The surjectivity case looks a bit suspicious.
    codomain has an associated element in the domain and the same size guarantees that none in the domain can map to the same element of the codomain for all elements are targeted.
    If you like, you could put all this into formulas. Say we have a function ##f\, : \, X \longrightarrow Y## with ##|X|=|Y|=:n < \infty##. The definitions are:

    ##f## is injective, iff ##f(x)=f(y) \Longrightarrow x=y## and
    ##f## is surjective, iff ##\forall \; y\in Y \;\exists \; x\in X\, : \,f(x)=y## or likewise ##\forall \; y\in Y\, : \,f^{-1}(y) \neq \emptyset\,.##

    It might help in this case, to define numberings ##N_X\, : \, \{1,2,\ldots, n\} \longrightarrow X## and ##N_Y\, : \, \{1,2,\ldots, n\} \longrightarrow Y## and show that ##N_Y^{-1}\circ f \circ N_X## is a bijective. I'm not sure whether these extra mappings are actually needed, it's just an idea to formalize what you actually did in your reasoning.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Prove that an endomorphism is injective iff it is surjective
Loading...