Is my Proof Valid for Bijection of Finite Sets?

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.
  • #1
sleepingMantis
25
5
<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:
Physics news on Phys.org
  • #2
First you say that ##I_n =\{1, \dots, n\}##. Then you say ##I_n=\{a_1, \dots, a_n\}##. Which one is it?
 
  • Like
Likes sleepingMantis
  • #3
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 ##.
 
  • #4
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).
 
  • Like
Likes sleepingMantis
  • #5
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##.

And, as I said, that seems to me to jump to the answer without justification.

A better strategy is to look at what one-to-one and onto say about the relationship between ##m## and ##n##.
 
Last edited:
  • Like
Likes sleepingMantis
  • #6
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##?
 
  • Like
Likes sleepingMantis
  • #7
@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:
  • #8
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.
 
  • Like
Likes sleepingMantis
  • #9
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?
 
  • #10
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.
 
  • Like
Likes sleepingMantis
  • #11
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##
 
  • #12
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?
 
  • Like
Likes sleepingMantis
  • #13
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.
 
  • #14
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.
 
  • Like
Likes sleepingMantis
  • #15
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.
 
  • Like
Likes sleepingMantis
  • #16
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!
 

Related to Is my Proof Valid for Bijection of Finite Sets?

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.

Similar threads

  • 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
Replies
5
Views
542
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
15
Views
2K
Back
Top