Mr Davis 97 said:
Homework Statement
Prove that an endomorphism between two finite sets is injective iff it is surjective
Homework Equations
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?
The surjectivity case looks a bit suspicious.
In the other direction, assume that the map is surjective, which means that every element in the
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.
This the map is injective.
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.