Proving that injectivity implies surjectivity

[issacnewton]

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

 

[PeroK]

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?

 

[issacnewton]

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 ?

 

[PeroK]

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 \}$.

 

[issacnewton]

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 ?

 

[PeroK]

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.

 

[issacnewton]

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 ?

 

[PeroK]

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.

 

[Delta2]

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.

 

[issacnewton]

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$

 

[PeroK]

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!

 

[PeroK]

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.

 

[issacnewton]

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.

 

[PeroK]

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.

 

[issacnewton]

Yes, that's the problem. I thought I can prove part c independently. But now, I will try to prove first two parts.