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 ;)


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*}$$

  • $\begingroup$ Now I can imagine that , Complete and neat , Thanks! $\endgroup$ – program_craft Apr 12 at 2:38
  • $\begingroup$ @program_craft: You’re welcome! $\endgroup$ – Brian M. Scott Apr 12 at 2:48

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.