Proving that injectivity implies surjectivity

  • Thread starter issacnewton
  • Start date
In summary: You would just need to prove that the definition of finite set is inductive. That is, you need to prove that there is a function ##g## that assigns to each natural number ##n## a set ##A_n## such that1) ##A_1## is finite (this will follow from the definition of finite set)2) For any natural number ##n##, if ##A_n## is finite, then ##A_{n+1}## is finiteWe will do the second part first. We need to define ##g##. Since we are using finite sets, let's say that ##g(n)## is the image under
  • #1
issacnewton
1,029
37
Homework Statement
Suppose ##A## and ##B## are finite sets and ##f: A \longrightarrow B ##. Prove that if ##|A| = |B| ## then ##f## is one to one if and only if ##f## is onto.
Relevant Equations
Definition of one to one and onto function
Since this is bi-conditional, we have two directions to prove. Given is ##|A| = |B|= n ##. Now suppose that ##f## is one to one. This means that given ##a_1, a_2 \in A## , if we have ##a_1 \ne a_2## then we have ##f(a_1) \ne (a_2) ##. So, we can not have any two elements in ##A## mapped to a single element in ##B##. This means that range of ##f## must have ##n## elements. But we are given that ## |B| = n##. So range of ##f## must be same as ##B##. This means that all elements of ##B## have some pre-image in ##A##. Which proves that ##f## is an onto function.
This was forward direction. I want to know if the reasoning is right here.

Thanks
 
Physics news on Phys.org
  • #2
IssacNewton said:
Homework Statement:: Suppose ##A## and ##B## are finite sets and ##f: A \longrightarrow B ##. Prove that if ##|A| = |B| ## then ##f## is one to one if and only if ##f## is onto.
Relevant Equations:: Definition of one to one and onto function

Since this is bi-conditional, we have two directions to prove. Given is ##|A| = |B|= n ##. Now suppose that ##f## is one to one. This means that given ##a_1, a_2 \in A## , if we have ##a_1 \ne a_2## then we have ##f(a_1) \ne (a_2) ##. So, we can not have any two elements in ##A## mapped to a single element in ##B##. This means that range of ##f## must have ##n## elements. But we are given that ## |B| = n##. So range of ##f## must be same as ##B##. This means that all elements of ##B## have some pre-image in ##A##. Which proves that ##f## is an onto function.
This was forward direction. I want to know if the reasoning is right here.

Thanks
The reasoning is correct, but are you sure you don't need a more formal proof? If you don't need a formal proof, then you can reduce your proof to simple counting. For example:

##f## is onto iff the range is all of ##B## iff the range has ##n## elements iff ##f## is one-to-one.

Do you need something more formal that that?
 
  • #3
Since I am doing this problem to practice my proof writing skills, I would appreciate more formal proof. I have studied about logic and quantifiers, so formal proof would be nice. I could not think of doing this more formally. Can you give any pointers ?
 
  • #4
IssacNewton said:
Since I am doing this problem to practice my proof writing skills, I would appreciate more formal proof. I have studied about logic and quantifiers, so formal proof would be nice. I could not think of doing this more formally. Can you give any pointers ?
Perhaps think about using the set ##I_n = \{1, 2 \dots n \}##.
 
  • #5
Since both ##A## and ##B## are finite sets, we have that ##A \thicksim I_n ## and ## B \thicksim I_n ##, which means that there are bijections from ##A## to ##I_n## and from ##B## to ##I_n##. Since ##\thicksim## relation is an equivalence relation, we also have ##A \thicksim B##. So, there exists a bijection from ##A## to ##B## as well. Since we have a natural number ##n## here, do you think using induction would be more formal way to go about ?
 
  • #6
IssacNewton said:
Since both ##A## and ##B## are finite sets, we have that ##A \thicksim I_n ## and ## B \thicksim I_n ##, which means that there are bijections from ##A## to ##I_n## and from ##B## to ##I_n##. Since ##\thicksim## relation is an equivalence relation, we also have ##A \thicksim B##. So, there exists a bijection from ##A## to ##B## as well. Since we have a natural number ##n## here, do you think using induction would be more formal way to go about ?
The idea was to use ##I_n## to show that ##f## is one-to-one iff it's onto.
 
  • #7
So, consider the forward direction. We assume that ##f## is one to one. There exists a bijection from ##A## to ##I_n##. And we have to prove that for any element in ##B##, there exists an element in ##A## such that they are mapped. So how would we use ##I_n## here ?
 
  • #8
IssacNewton said:
So, consider the forward direction. We assume that ##f## is one to one. There exists a bijection from ##A## to ##I_n##. And we have to prove that for any element in ##B##, there exists an element in ##A## such that they are mapped. So how would we use ##I_n## here ?
Let's see where we are. You gave an argument in your original post. There was nothing wrong with that argument, per se. But, I believe your argument was no different from the argument I gave in post #2. Sure, you did a lot more handwaving and introduced some things like ##a_1 \ne a_2## and so on. But, fundamentally, there was no substance behind what you did, other than what I did in post #2 without all the fuss.

If you acccept that we can count, then my argument in post #2 is perfectly adequate. But, you are perhaps studying the subject where you need more than that. I.e. you have to prove in some sense that counting works!

So, under the assumption that we are not allowed to count, we need something more fundamental. The only thing I know more fundamental than counting is the bijections to ##I_n## etc.

If all we know is that there exists a bijection from ##A## to ##I_n## and from ##B## to ##I_n##, then that's not much help. Why? Because it says nothing about any other functions. It doesn't, for example, say that there isn't a bijection from ##A## to ##I_{n+1}##.

So, what theorems have you proved so far that might be useful here? What mathematical machinery do you have at your disposal? Assuming again that simple counting is not allowed.

If you want a low-level proof of this sort of thing all you have are your definitions, axioms and theorems. Your proof may use those and only those. I'm not taking your course and I don't know what you've proved so far, which makes it difficult to help. The onus is on you to produce the machinery that you have at your disposal.
 
  • #9
I was inspired by the set ##I_n## to use induction on the number of elements ##n##. But induction is an axiom of Peano arithmetic I am not so sure if it can be used here.
 
  • #10
I am not doing any course. I am solving this problem from a book "How to prove it: A structured approach" by Daniel Velleman. ( 2ed.) There are following chapters in this book
1) Sentential Logic
2) Quantificational Logic
3) Proofs
4) Relations
5) Functions
6) Mathematical Induction
7) Infinite Sets

Author is a set theorist and this is a book to prepare students to proof oriented mathematics. I have solved all problems from first 6 chapters and the problem I stated here is from the last chapter. Since author is a set theorist, most of the problems he has chosen make heavy use of set theory. So, the machinery used here is highly rigorous. All the machinery is developed in first two chapters and third chapter discusses strategies to be used for different kinds of proofs. I am myself a teacher of physics, but since I like pure mathematics, I do these problems. Coming from more applied background of physics, I don't have mathematical "maturity" and hence struggle to formulate proofs. Though I learned a great deal from the above book. When I was in college, I once tried to read a book on pure mathematics by G.H. Hardy ( He was from Cambridge, UK). I could not understand the head or tail of his reasoning. So, I wanted to develop some background required to read such books. People working in pure mathematics take lot of things for granted since they are communicating with other pure mathematicians. So, this is my background here. I learned in this book, that whenever we have a mathematical statement involving a natural number (like cardinality of a finite set here), its useful to use induction on ##n##
 
  • Like
Likes Delta2
  • #11
IssacNewton said:
I am not doing any course. I am solving this problem from a book "How to prove it: A structured approach" by Daniel Velleman. ( 2ed.) There are following chapters in this book
1) Sentential Logic
2) Quantificational Logic
3) Proofs
4) Relations
5) Functions
6) Mathematical Induction
7) Infinite Sets

Author is a set theorist and this is a book to prepare students to proof oriented mathematics. I have solved all problems from first 6 chapters and the problem I stated here is from the last chapter. Since author is a set theorist, most of the problems he has chosen make heavy use of set theory. So, the machinery used here is highly rigorous. All the machinery is developed in first two chapters and third chapter discusses strategies to be used for different kinds of proofs. I am myself a teacher of physics, but since I like pure mathematics, I do these problems. Coming from more applied background of physics, I don't have mathematical "maturity" and hence struggle to formulate proofs. Though I learned a great deal from the above book. When I was in college, I once tried to read a book on pure mathematics by G.H. Hardy ( He was from Cambridge, UK). I could not understand the head or tail of his reasoning. So, I wanted to develop some background required to read such books. People working in pure mathematics take lot of things for granted since they are communicating with other pure mathematicians. So, this is my background here. I learned in this book, that whenever we have a mathematical statement involving a natural number (like cardinality of a finite set here), its useful to use induction on ##n##
This is very specific material though. I did a degree in pure maths, but I never studied anything where the basic notion of counting was dubious. I.e. the proof in post #2 would have been valid in any course I ever took.

I would say that a book like this doesn't prepare students for proof-oriented mathematics, but is actually the reverse. You need experience of proof-oriented mathematics if you want to study the fundamentals of set theory.

For example, if you study group theory (in a formal, rigorous approach) you will have to do proofs based on definitions, axioms and theorems; but, you will still be allowed to count!

I would say 1) it's difficult or impossible to study set-theorectic material until you have experience in pure mathematics (groups, real analysis etc.) Hence your problems.

2) Studying set-theorectic material is then an optional direction you can take - but only really once you have mastered pure mathematics.

PS to use a physics analogy: what you are doing is a bit like trying to learn QM as a prerequisite to studying classical mechanics. Or, GR as a prerequisite to Newtonian gravity!
 
  • #12
PPS that said: are you sure that the proof I gave in post #2 is not acceptable? You'd have to ask Velleman I guess. Certainly my argument in post #2 would be valid in any course on group theory, for example. No one is going to question that there are no proper subsets of a finite set with the same cardinality. That's just a given, really. Trying to prove something like that is a different game altogether.
 
  • #13
Yes, maybe I was misled by this book as author is set theorist. In modern mathematics, everything is reduced to sets. So, I thought, to be rigorous, I have to eventually involve that machinery. But people like Gauss studied pure maths even before the sets were introduced. So, we sure can do proofs without lot of set machinery. When I visit sites like math.stackexchange.com, I get the sense that a rigorous proof should involve lot of set machinery. Since I am not a math professor, I don't know what is the general opinion among mathematicians. I am not saying that your proof in #2 is not acceptable. I am self learning this material. Since you said that my reasoning in #1 is valid, I am satisfied with that. I used to communicate with Dr Velleman. I will also ask him about this.
 
  • #14
IssacNewton said:
Yes, maybe I was misled by this book as author is set theorist. In modern mathematics, everything is reduced to sets. So, I thought, to be rigorous, I have to eventually involve that machinery. But people like Gauss studied pure maths even before the sets were introduced. So, we sure can do proofs without lot of set machinery. When I visit sites like math.stackexchange.com, I get the sense that a rigorous proof should involve lot of set machinery. Since I am not a math professor, I don't know what is the general opinion among mathematicians. I am not saying that your proof in #2 is not acceptable. I am self learning this material. Since you said that my reasoning in #1 is valid, I am satisfied with that.
Here's the real problem. I found a pdf of the book and you're doing question 11c. And you're stuck. And I asked what you have already proved and you've said nothing. Then I look at the question and I see parts 11a and 11b are exactly what you need to solve 11c:

11. SupposeAandBare finite sets andf:A→B.
(a) Prove that if|A|<|B|thenfis not onto.(b) Prove that if|A|>|B|thenfis not one-to-one. (This is sometimescalled thePigeonhole Principle, because it means that ifnpigeonsare put intompigeonholes, wheren>m, then some pigeonhole mustcontain more than one pigeon.)
(c) Prove that if|A|=|B|thenfis one-to-one ifffis onto.∗

The answer is use what you proved in 11a and 11b.
 
  • Like
Likes Delta2
  • #15
Yes, that's the problem. I thought I can prove part c independently. But now, I will try to prove first two parts.
 

FAQ: Proving that injectivity implies surjectivity

1. What is injectivity and surjectivity?

Injectivity and surjectivity are two concepts in mathematics that describe the relationship between two sets. Injectivity means that each element in the first set maps to a unique element in the second set. Surjectivity means that every element in the second set has at least one corresponding element in the first set.

2. Why is it important to prove that injectivity implies surjectivity?

Proving that injectivity implies surjectivity is important because it helps us understand the relationship between two sets and how their elements are mapped to each other. It also allows us to make conclusions about the properties of a function based on its injectivity and surjectivity.

3. How can we prove that injectivity implies surjectivity?

To prove that injectivity implies surjectivity, we need to show that for every element in the second set, there exists at least one element in the first set that maps to it. This can be done by using the definition of injectivity and surjectivity, and by using logical reasoning and mathematical operations.

4. What are some examples of functions that are injective but not surjective?

An example of a function that is injective but not surjective is f(x) = x^2, where the domain is all real numbers and the range is all positive real numbers. Another example is g(x) = e^x, where the domain is all real numbers and the range is all positive real numbers.

5. Can a function be surjective but not injective?

Yes, a function can be surjective but not injective. An example of such a function is h(x) = x^3, where the domain and range are both all real numbers. In this case, every element in the range has at least one corresponding element in the domain, but not every element in the domain maps to a unique element in the range.

Back
Top