I want to show that there is no bijection from finite set $X$ to the set $X - \{x\}$. But I don't want to use any of the rules of cardinality or Cantor–Bernstein–Schroeder theorem etc.
Is there a more basic proof ?
Answer
Well you can prove this by induction on the number of elements in $X$.
If $X$ has one element, then this is obvious, because then $X=\{x\}$ and $X\setminus\{x\}=\varnothing$. Clearly there is no injection from a non-empty set into the empty set.
Suppose this holds for sets of $n$ elements, i.e. if there is an injection from a set of $n$ element into itself then it is a surjection. Let $X$ be a set of $n+1$ elements, and pick some $x\in X$.
Let $X'=X\setminus\{x\}$, then $X'$ is a set with $n$ elements. If there was an injection $f\colon X\to X'$ then the restriction of $f$ to $X'$ (denoted by $f\upharpoonright X'$) is an injection from $X'$ into itself, so by our induction hypothesis it has to be surjective. Let $x'=f(x)$ then $x'\in X'$.
Because $f\upharpoonright X'$ is surjective there is some $y\in X'$ such that $f(y)=x'$, but now we have that $f(y)=f(x)$ and since $f$ was injective we have that $y=x$ which is a contradiction because $x\notin X'$. Therefore there is no such injection.
No comments:
Post a Comment