elementary set theory - Prove that a set cannot have two different size $𝑚$ and $𝑛, 𝑚≠n$.

We define the number of elements in set by bijections as follows:

$|X| = n$ means that there exists a bijection from X to the set $\{1,2 \dots, n\}$.

I already showed that:

• if $X$ and $Y$ have same size, then there exists a bijection from $X$ to $Y$


• if $X$ has size $n$, and there exist a bijection from $X$ to $Y$, then $Y$ has size $n$ too.

Now, I want to prove following:

Prove that a set cannot have two different size $m$ and $n$, $m \neq$n.

Be careful not use the intuitive notion of "size" but only the definition via bijections. Procced by induction.

In the book is the solution (without base case), but I am not sure. So, I write them down and write my explenation. I write number to each step, if you do not agree then please write why.

PROOF: It suffices to prove that there is no bijection from the set $\{1,2, \dots, n\}$ onto a proper subset $A \subset \{1,2, \dots, n\}$.

(1) To reason why it is possible is that, by definition if there is no bijection between two sets, then the size of these sets cannot be same.

Proceed by induction on $n$. The case $n=1$ is clear.

(2) There is only one proper subset of $\{1\}$, nameley $\emptyset$. So we need show there is no bijection beetween $\{1\}$ to $\emptyset$. So let $f: \{1\} \rightarrow \emptyset$. Since $\{1\} \times \emptyset = \emptyset = f$, so $f$ is not function neither bijection.

Suppose there were such a bijection $f: \{1,2,\dots,n\} \rightarrow A, n > 1$.

(3) From this sentence, I know that proof is given by contradiction.

If $f(n) = n$ or $n \notin A$ then $f$ restricted to $\{1,2, \dots, n-1\}$ gives a bijection of $\{1,2\dots,n-1\}$ to its proper subset.

(4) In the proof is not explicitly written induction hypothesis, but it may look as "Suppose for $n-1$ there is no bijection between $\{1,2, \dots,n-1\}$ to $A \subset \{1,2, \dots,n-1\}$". So, we reach a contradiction in this case.

If $f(n) = i \neq n$ and $f(j) = n$ for some $j < n$ then define $g(j) = i, g(k) = f(k)$ for $k\neq j, n$. This g is again a bijection of $\{1,2, \dots, n-1\}$ on its proper subset.

(5) Again, we reached a contradiction. Clearly $f(n) = n$ or $f(n) \neq n$ so we consider all possibilities.