If X is infinite and $x_0$ ∈ X , then X – {$x_0$} is still infinite proof

elementary-set-theory

I am a student and I was reading this proof for the question
(book : zgkp you feng lin, shwu yeng_t lin set theory with applications) :

enter image description here

Note that definition 1 is Dedekind definition for infinite sets.

I cannot understand the basis of the proof. Why we consider two cases for this?

I need a deep explanation 😉

Best Answer

I’m not sure what it is that you don’t understand. We need to show that there is an injection $g:X\setminus\{x_0\}\to X\setminus\{x_0\}$ such that $g[X\setminus\{x_0\}]\subsetneqq X\setminus\{x_0\}$. The only thing that we know is that $X$ is infinite, i.e., that there is an injection $f:X\to X$ such that $f[X]\subsetneqq X$, so somehow we will have to use $f$ to construct the desired $g$. It turns out that how we do this depends on whether or not $x_0\in f[X]$.

If $x_0\notin f[X]$ we can just let $g$ be the restriction $f\upharpoonright X\setminus\{x_0\}$; that’s Case $\mathit 2$ of the proof. If $x_0\in f[X]$, however, this might not work. To see why, take $X=\Bbb N$ (which for me includes $0$), let $x_0=1$, and let

$$f:\Bbb N\to\Bbb N:x\mapsto x+1\,.$$

If $g=f\upharpoonright(\Bbb N\setminus\{1\})$, then

$$\begin{align*} g[\Bbb N\setminus\{1\}]&=f[\Bbb N\setminus\{1\}]\\ &=\{f(0)\}\cup\{f(n):2\le n\in\Bbb N\}\\ &=\{1\}\cup\{n\in\Bbb N:n\ge 3\}\\ &\not\subseteq\Bbb N\setminus\{1\}\,; \end{align*}$$

that is, the restriction of $f$ to $\Bbb N\setminus\{1\}$ is not a function from $\Bbb N\setminus\{1\}$ to $\Bbb N\setminus\{1\}$.

Case $\mathit 1$ of the proof shows how to construct $g$ in order to avoid this problem. We still take $g$ to be mostly the restriction of $f$ to $X\setminus\{x_0\}$, but if $x_1\ne x_0$, as is the case in my example, we have to define $g(x_1)$ in some other way to ensure that $g(x_1)\in X\setminus\{x_0\}$.

In my example $x_1$ is $0$, since $f(0)=1=x_0$, and we redefine $g(0)$ to be some $x_2$ that is not $1$ (since $1$ isn’t in $\Bbb N\setminus\{1\}$, the desired codomain of $g$) and is not in $f[\Bbb N]$ (so that it won’t conflict with $f(n)$ for any other $n\in\Bbb N\setminus\{1\}$). In this example the only possibility is $x_2=0$, since $f[\Bbb N]=\Bbb N\setminus\{0\}$. Thus, we let $g(0)=0$ and let $g(n)=f(n)=n+1$ if $n\ge 2$, so that

$$\begin{align*} g[\Bbb N\setminus\{1\}]&=\{g(0)\}\cup\{g(n):2\le n\in\Bbb N\}\\ &=\{0\}\cup\{f(n):n\ge 2\}\\ &=\{0\}\cup\{n\in\Bbb N:n\ge 3\}\\ &=\Bbb N\setminus\{1,2\}\\ &\subsetneqq\Bbb N\setminus\{1\}\,. \end{align*}$$

Related Question