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$

 

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

 

[WWGD]

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).

 

[PeroK]

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

 

[PeroK]

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

 

[PeroK]

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]

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?

 

[PeroK]

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]

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$

 

[PeroK]

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]

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.

 

[PeroK]

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.

 

[PeroK]

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]

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!