Prove that an endomorphism is injective iff it is surjective

In summary, an endomorphism is a mathematical function that maps a set to itself. It can also be described as a special type of homomorphism where the domain and codomain are the same. An endomorphism is injective if it maps distinct elements in the domain to distinct elements in the codomain. This means that no two elements in the domain are mapped to the same element in the codomain. The injectivity of an endomorphism is related to its surjectivity, as an endomorphism is injective if and only if it is surjective. This concept has many real-world applications, such as in physics, computer science, and economics, where it is used to model physical systems, data encryption and compression
  • #1
Mr Davis 97
1,462
44

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?
 
Last edited:
Physics news on Phys.org
  • #2
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.
 
  • Like
Likes Mr Davis 97

Related to Prove that an endomorphism is injective iff it is surjective

1. What is an endomorphism?

An endomorphism is a mathematical concept that refers to a function that maps a set to itself. It is a special type of homomorphism, where the domain and codomain of the function are the same.

2. What does it mean for an endomorphism to be injective?

An endomorphism is injective if it maps distinct elements in the domain to distinct elements in the codomain. In other words, no two elements in the domain are mapped to the same element in the codomain.

3. How is the injectivity of an endomorphism related to its surjectivity?

An endomorphism is injective if and only if it is surjective. This means that the function is both one-to-one (injective) and onto (surjective), where every element in the codomain has a corresponding element in the domain that maps to it.

4. Can you prove that an endomorphism is injective if it is surjective?

Yes, this proof is commonly known as the "if and only if" proof. It involves showing that if an endomorphism is surjective, then it must also be injective, and vice versa.

5. What are some real-world applications of this concept?

The concept of an endomorphism and its properties (injectivity and surjectivity) are widely used in various fields of science and mathematics, such as physics, computer science, and economics. For example, in physics, endomorphisms are used to model physical systems and study their behavior. In computer science, they are used in data encryption and compression algorithms. In economics, they are used to analyze economic systems and market behavior.

Similar threads

  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
804
  • Calculus and Beyond Homework Help
Replies
3
Views
605
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Precalculus Mathematics Homework Help
Replies
4
Views
2K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
10
Views
2K
  • Linear and Abstract Algebra
Replies
10
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
2K
Back
Top