Prove that a set cannot have two different size $$ and $, ≠n$.

Question

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.

Answer 1

Here's the proof desiigner is alluding to:

Let $p(m)$ be the statement "If there is a bijection $f:[m]\to[n]$, then $m=n$" for $m\in\mathbb N$. We induct on $m$.

• Base case: For $m=0$, $[m]=\emptyset$ so a bijection $f:\emptyset\to[n]$ implies $[n]$ is also empty.
• Induction step: Suppose $p(m)$, we want to show a bijection $f:[m+1]\to[n]$ implies $m+1=n$. Since $m+1\ge1$, $1\in[m+1]$ so $f(1)\in[n]$. This means $[n]$ is inhabited so $n\ge 1$ and $[n-1]$ is defined. We show $m=n-1$.
  Define $f\restriction_{[m]}:[m]\to[n]\setminus\{f(m+1)\}$ to be the restriction of $f$ to $[m]$ with codomain $[n]\setminus\{f(m+1)\}$, which is bijective. Now we use the following Lemma:

  If $X$ is inhabited, then there is a bijection $f:X\setminus\{a\}\to X\setminus\{b\}$ for all $a,b\in X$.

In particular, there is a bijection $g:[n]\setminus\{f(m+1)\}\to[n]\setminus\{n\}$ with $[n]\setminus\{n\}=[n-1]$. Then $g\circ f\restriction_{[m]}$ is a bijection. By induction hypothesis, $m=n-1$ so $m+1=n$.

---

This proof is lifted from An Infinite Descent into Pure Mathematics by Clive Newstead, which can be found at https://infinitedescent.xyz/.