Tips for Bijection Proof

sleepingMantis
<Moderator's note: Moved from a technical forum.>

Hi PF,

I am learning how to prove things (I have minimal background in math). Would the following proof be considered valid and rigorous? If not any pointers or tips would be much appreciated!

Problem:

Prove that the notion of number of elements of a nonempty finite set is a well defined concept. More precisely, prove that there exists a bijection ## f : I_m → I_n## if and only if ##m = n##.

Relevant Definitions:

## I_n ## denotes the set: ## I_n = \{ j \in \mathbb{N} ; 1 \leq j \leq n \} ##

Attempt at proof:

First prove that ## f : I_m → I_n \Rightarrow m = n##:

Assume that ## f ## is a bijection from the set ## I_m ## to the set ## I_n ##, so that we can write ## f : I_m → I_n##

Writing ## I_n = \{ a_1, ..., a_n \} ## and similarly ## I_m = \{ b_1, ..., b_m \} ## for some ##m, n \in \mathbb{N} ##, since ## f ## is a bijection, for every element ## a_i \in I_n ## and every element ##b_k \in I_m## we have ## f(a_i) = b_k ## for some ##i, k##. Since ## f ## is one to one, it follows that ## |I_n| = |I_m| ##. Therefore ##m = n##.

------------------------

Now prove that ##n = m \Rightarrow f : I_m → I_n##:

Assume ## m = n ##.

Construct two sets, ##I_n = \{ a_1, ..., a_n \} ## and ## I_m = \{ b_1, ..., b_m \} ##. Since we have the same number of elements, we can create a bijection ##f: I_n → I_m ##.

so ##n = m \Rightarrow f : I_m → I_n##

Last edited by a moderator:

First you say that ##I_n =\{1, \dots, n\}##. Then you say ##I_n=\{a_1, \dots, a_n\}##. Which one is it?

sleepingMantis
sleepingMantis
I see, that is a mistake on my behalf.

I would instead write (edits in red):

------------------------

First prove that ## f : I_m → I_n \Rightarrow m = n##:

Assume that ## f ## is a bijection from the set ## I_m ## to the set ## I_n ##, so that we can write ## f : I_m → I_n##

Writing ## I_n = \{1, ..., n \} ## and similarly ## I_m = \{1, ..., m \} ## for some ##m, n \in \mathbb{N} ##.

Let the elements in ## I_m ## be denoted by ## a_i ## and let elements in ## I_n ## be denoted by ##b_k ##

Since ## f ## is a bijection, for every element ## a_i \in I_m ## and every element ##b_k \in I_n## we have ## f(a_i) = b_k ##
for some ##i, k##. Since ## f ## is one to one, it follows that ## |I_n| = |I_m| ##. Therefore ##m = n##.

------------------------

Now prove that ##n = m \Rightarrow f : I_m → I_n##:

Assume ## m = n ##.

Construct two sets, ##I_n = \{1, ..., n \} ## and ## I_m = \{1, ..., m \} ##. Since we have the same number of elements, we can create a bijection ##f: I_m → I_n ##.

Gold Member
I see, that is a mistake on my behalf.

I would instead write (edits in red):

------------------------

First prove that ## f : I_m → I_n \Rightarrow m = n##:

Assume that ## f ## is a bijection from the set ## I_m ## to the set ## I_n ##, so that we can write ## f : I_m → I_n##

Writing ## I_n = \{1, ..., n \} ## and similarly ## I_m = \{1, ..., m \} ## for some ##m, n \in \mathbb{N} ##.

Let the elements in ## I_m ## be denoted by ## a_i ## and let elements in ## I_n ## be denoted by ##b_k ##

Since ## f ## is a bijection, for every element ## a_i \in I_m ## and every element ##b_k \in I_n## we have ## f(a_i) = b_k ##
for some ##i, k##. Since ## f ## is one to one, it follows that ## |I_n| = |I_m| ##. Therefore ##m = n##.

------------------------

Now prove that ##n = m \Rightarrow f : I_m → I_n##:

Assume ## m = n ##.

Construct two sets, ##I_n = \{1, ..., n \} ## and ## I_m = \{1, ..., m \} ##. Since we have the same number of elements, we can create a bijection ##f: I_m → I_n ##.
Yes, it is a little sort of awkward but just construct a function , say assigning the first element of I_n to the first of I_m ( or rename the elements and reorder them).

sleepingMantis
Homework Helper
Gold Member
2022 Award
I see, that is a mistake on my behalf.

I would instead write (edits in red):

------------------------

First prove that ## f : I_m → I_n \Rightarrow m = n##:

Assume that ## f ## is a bijection from the set ## I_m ## to the set ## I_n ##, so that we can write ## f : I_m → I_n##

Writing ## I_n = \{1, ..., n \} ## and similarly ## I_m = \{1, ..., m \} ## for some ##m, n \in \mathbb{N} ##.

Let the elements in ## I_m ## be denoted by ## a_i ## and let elements in ## I_n ## be denoted by ##b_k ##

Since ## f ## is a bijection, for every element ## a_i \in I_m ## and every element ##b_k \in I_n## we have ## f(a_i) = b_k ##
for some ##i, k##. Since ## f ## is one to one, it follows that ## |I_n| = |I_m| ##. Therefore ##m = n##.

I'm not convinced by this. I would say that what you've done, roughly, is write down a number of statements then state the answer.

Also, your third statement in red is not phrased accurately. What you meant is something like:

Since ##f## is onto: ##\forall b_k \in I_n, \ \exists \ a_i \in I_m: \ f(a_i) = b_k##.

In fact, here's my summary of your proof:

1) Since ##f## is onto: ##\forall b_k \in I_n, \ \exists \ a_i \in I_m: \ f(a_i) = b_k##.

2) Since ##f## is one-to-one, ##|I_m| = |I_n|##, hence ##m = n##.

A better strategy is to look at what one-to-one and onto say about the relationship between ##m## and ##n##.

Last edited:
sleepingMantis
Homework Helper
Gold Member
2022 Award
Construct two sets, ##I_n = \{1, ..., n \} ## and ## I_m = \{1, ..., m \} ##. Since we have the same number of elements, we can create a bijection ##f: I_m → I_n ##.

Again this is more or less just stating the answer.

In this case, you could look for a specific bijection. Hint: if ##m = n##, what can you say about ##I_m## and ##I_n##?

sleepingMantis
sleepingMantis
@Math_QED , @WWGD , @PeroK

Thank you for the comments. The first part of my revised proof is below (i.e. ## f:I_m \rightarrow I_n \Rightarrow m=n ##). I will post the second part once I get this bit right.

Problem:
Prove that there exists a bijection ##f: I_m \rightarrow I_n ## if and only if ## m=n ##.

Relevant Definitions:

A function is injective if ## \forall a, b \in X, f(a) = f(b) \Rightarrow a = b ##

A function is surjective if ## \forall b \in B, \exists a \in A ## such that ## b = f(a) ##

A function is bijective if it is injective and surjective.

Attempt at Proof:

First prove that ## f:I_m \rightarrow I_n \Rightarrow m=n ##:

Let ## I_m = \{ j \in \mathbb{N} | 1 \leq j \leq m \} ## and let ## I_n = \{ k \in \mathbb{N} | 1 \leq k \leq n \} ##.

Assume that ##f## is a bijective function such that ##f: I_m \rightarrow I_n ##.

##(1) ## Since ##f## is injective, ## \forall a, b \in I_m, f(a) = f(b) \Rightarrow a = b##. That is, every element of ##I_n## corresponds to at most one element in ##I_m##.

##(2) ## Since ##f## is surjective, ##\forall b \in I_n, \exists a \in I_m## such that ## b = f(a) ##. That is, every element of ##I_n## corresponds to atleast one element in ##I_m##.

We can construct a function that satisfies the above conditions as following: suppose ##f## assigns the first element in ##I_m## to the first element in ##I_n##, the second element in ##I_m## to the second element in ##I_n## and so on.

This allows both of the properties to be true, and it follows that every element in ##I_m## maps to exactly one element in ##I_n##. This is because if ##m > n##, ##(1)## would be violated. If ##m < n## then ##(2)## would be violated.

It follows that ##m=n##.

Last edited:
Homework Helper
Gold Member
2022 Award
That, I'm sorry to say, is not a proof. What you are missing is an idea that directly relates the property of being injective to the number of elements in each set.

Hint: for any function the image is a subset of the range.

sleepingMantis
sleepingMantis
That, I'm sorry to say, is not a proof. What you are missing is an idea that directly relates the property of being injective to the number of elements in each set.

Hint: for any function the image is a subset of the range.

Thank you, I see I am missing a fair bit of intuition.

Would the key idea be that an injective function maps distinct elements in the domain to distinct elements in the image?

Then the issue with my proof is that I am mixing up the range and the image?

Homework Helper
Gold Member
2022 Award
Thank you, I see I am missing a fair bit of intuition.

Would the key idea be that an injective function maps distinct elements in the domain to distinct elements in the image?

Then the issue with my proof is that I am mixing up the range and the image?
This whole area of mathematics is anti intuitive in my opinion. The concept that the number of elements in a finite set is well defined is so simple and intuitive that normally it is assumed.

When you try to prove it, you are forced to abandon any intuition and work from axiomatic deduction.

In fact, if I'm honest, I'm not sure I could give a totally acceptable proof, as I don't know what we can and cannot assume has already been proved.

You need to be aware that this level of mathematics is perhaps a very difficult place to start.

That said I think what you are missing is a wider range of mathematical ideas. For example:

##m = n## iff ##m \le n## and ##n \le m##.

That might be useful here.

sleepingMantis
sleepingMantis
This whole area of mathematics is anti intuitive in my opinion. The concept that the number of elements in a finite set is well defined is so simple and intuitive that normally it is assumed.

When you try to prove it, you are forced to abandon any intuition and work from axiomatic deduction.

In fact, if I'm honest, I'm not sure I could give a totally acceptable proof, as I don't know what we can and cannot assume has already been proved.

You need to be aware that this level of mathematics is perhaps a very difficult place to start.

That said I think what you are missing is a wider range of mathematical ideas. For example:

##m = n## iff ##m \le n## and ##n \le m##.

That might be useful here.

Thank you for your thoughts. I think I will try and develop a wider set of tools, maybe with another book. The book I am using seems to assume a number of things (for example it assumed I knew what a bijection was, but did not state the definition anywhere).

All it says before asking the question is:

A set ##A## is finite if ##A = ∅## or if there exists a bijection ##f : I_n → A##, for some ##n ∈ N##. If ##A = ∅ ## is finite and ##f : I_n → A## is a bijection, then letting ##a_j = f (j )## we write ##A = \{a_1 , . . . , a_n \}## and say that ##n## is the number of elements of ##A##

Homework Helper
Gold Member
2022 Award
Thank you for your thoughts. I think I will try and develop a wider set of tools, maybe with another book. The book I am using seems to assume a number of things (for example it assumed I knew what a bijection was, but did not state the definition anywhere).

All it says before asking the question is:

A set ##A## is finite if ##A = ∅## or if there exists a bijection ##f : I_n → A##, for some ##n ∈ N##. If ##A = ∅ ## is finite and ##f : I_n → A## is a bijection, then letting ##a_j = f (j )## we write ##A = \{a_1 , . . . , a_n \}## and say that ##n## is the number of elements of ##A##

That's useful context. A further hint is to think about subsets.
Which book is this and who is it aimed at?

sleepingMantis
sleepingMantis
That's useful context. A further hint is to think about subsets.
Which book is this and who is it aimed at?

Thanks, I will ponder on this problem further.

This is the book: book. I think it is aimed at maybe first year undergraduates in discrete math.

Homework Helper
Gold Member
2022 Award
Thanks, I will ponder on this problem further.

This is the book: book. I think it is aimed at maybe first year undergraduates in discrete math.

I notice that one of the reviews suggests it's not for beginners. in any case, you might need something lighter to get you started.

I suggest you have look round the Internet For free resources on sets, mappings and an introduction to pure maths. See how they compare.

sleepingMantis
Homework Helper
Gold Member
2022 Award
Ps here is my proof for the converse.

If ##m = n##, then ##I_n## and ##I_m## are the same set. And the identity mapping is a bijection.

sleepingMantis
sleepingMantis
Ps here is my proof for the converse.

If ##m = n##, then ##I_n## and ##I_m## are the same set. And the identity mapping is a bijection.

Thanks for the help and guidance!