Is my Proof Valid for Bijection of Finite Sets?

• sleepingMantis
In summary, the conversation discussed a proof for the concept of the number of elements in a nonempty finite set being a well-defined concept. The proof involved showing that there exists a bijection between two sets if and only if they have the same number of elements. The conversation also addressed a mistake in the proof and provided a revised version.
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
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 ##.

sleepingMantis said:
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
sleepingMantis said:
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
sleepingMantis said:
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
@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:
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
PeroK said:
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?

sleepingMantis said:
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
PeroK said:
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##

sleepingMantis said:
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
PeroK said:
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.

sleepingMantis said:
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
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
PeroK said:
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!

1. What is a bijection of finite sets?

A bijection is a function that maps each element from one set to a unique element in another set. In other words, it establishes a one-to-one correspondence between the elements of two sets.

2. How do I prove that my function is a bijection?

To prove that a function is a bijection, you need to show that it is both injective and surjective. This means that each element in the domain is mapped to a unique element in the range, and every element in the range has at least one corresponding element in the domain.

3. Can a bijection exist between sets of different sizes?

Yes, a bijection can exist between sets of different sizes as long as there is a one-to-one correspondence between the elements of the two sets. This means that the size of the sets does not determine whether a bijection exists.

4. What is the significance of proving a bijection between finite sets?

Proving a bijection between finite sets is important in mathematics as it allows us to establish a relationship between the elements of two sets. This can help us understand the properties and characteristics of the sets and can also be used to solve various problems and equations.

5. Are there any specific techniques or methods for proving a bijection?

Yes, there are various techniques and methods for proving a bijection, such as using a proof by contradiction, using a direct proof, or using a proof by construction. It is important to carefully analyze the properties of the sets and choose the appropriate method for proving the bijection.

• Calculus and Beyond Homework Help
Replies
3
Views
1K
• Calculus and Beyond Homework Help
Replies
2
Views
909
• Precalculus Mathematics Homework Help
Replies
4
Views
2K
• Calculus and Beyond Homework Help
Replies
1
Views
567
• Topology and Analysis
Replies
2
Views
2K
• Calculus and Beyond Homework Help
Replies
4
Views
539
• Differential Equations
Replies
1
Views
760
• Calculus
Replies
5
Views
542
• Linear and Abstract Algebra
Replies
1
Views
1K
• Calculus and Beyond Homework Help
Replies
15
Views
2K