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.


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

  • $\begingroup$ Where do you find it unintuitive? $\endgroup$ – 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.

  • $\begingroup$ Thanks......... $\endgroup$ – blue boy Aug 16 '18 at 4:40
  • 1
    $\begingroup$ you're welcome. If my answer helped you i'd appreciate it if you'd accept it. $\endgroup$ – Zest Aug 16 '18 at 4:52
  • $\begingroup$ Done........... $\endgroup$ – blue boy Aug 16 '18 at 5:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.