# Problem understanding a proof related to finite sets

$Theorem$

Let $n$ be a positive integer . Let $A$ be a set; let $a_0$ be an element of $A$. Then there exists a bijective correspondence $f$ of the set $A$ with the set $\{1,.......,n+1\}$ if and only if there exists a bijective correspondence $g$ of the set $A- a_0$ with the set $\{1,....,n\}$.

Proof -

Assume there is a bijective correspondence $f:A \to \{1,...,n+1\}$. If $f$ maps $a_0$ to the number $n+1$,things are especially easy; in that case, the restricted $f_{|A}-\{a_o\}$ is the desired bijective correspondence of $A-\{a_o\}$ with $\{1,.....,n\}$. Otherwise let $f(a_o)=m$, and let $a_0$ be the point of $A$ such that $f(a_1)= n+1$. Then $a_1 \neq a_0$. Define a new function $h: A\to \{1,.....,n+1\}$ by setting $h(a_0)=n+1$, $h(a_1)=m$, $h(x)=f(x)$ for $x \in A-\{a_0\}- \{a_1\}$.

It is easy to check that h is a bijection . Now restriction $h_{|A}-\{a_0\}$ is the desired bijection of $A-\{a_0\}$ with ${1,....,n}$.

Other side implication can be proved easily by defining a function $f:A\to \{1,....,n+1\}$ by setting $f(x)=g(x)$ for $x\in A-\{a_0\}$ , $f(a_0)= n+1$, where $g(x)$ is a bijective function.

$Doubt$

I kind of understand the proof but can't get the intuitive felling for it.
Any help will be appreciated.

• Where do you find it unintuitive? – Vim Aug 16 '18 at 4:03

Remark: A bijection between two finite sets $A,B$ exists iff they have the same cardinality $\vert A \vert = \vert B \vert$ i.e the same number of elements.
$\Rightarrow$: Let $\varphi$ be a bijection between $A$ and $\{1,...,n+1\}$ for an arbitrary $n \in \mathbb{N}$. Thus $A$ is a finite set and we have $\vert A \vert = n +1$. Now consider the set $A' := A - \{a_0\}$, obviously it applies that $\vert A' \vert = n = \vert \{1,...,n\} \vert$. Now since $A'$ has the same cardinality as $\{1,...,n\}$ there exists a bijection $\psi$ between $A'$ and $\{1,...,n\}$.
$\Leftarrow$: Let $\psi$ be a bjiection between $A' := A - \{a_0\}$ and $\{1,...,n\}$. From here on you can pretty much use the exact same argument we used in "$\Rightarrow$" and you are finished.