The problem I'm dealing with is the following.

Show that every set $I$ which satisfies the conditions $$\emptyset\in I,\quad (\forall x)[x\in I\Rightarrow\{x\}\in I]$$ is Dedekind-infinite.

Where Dedekind-infinite is defined as follows.

A set is Dedekind-infinite if there exists an injection $$f:A\rightarrow B\subset A$$ from A into a proper subset of itself.

My attempt to solve this was to construct a function $$f(x): \begin{cases} x&\text{if } x\in R\subset I \\ \{x\}&\text{if } x\in I\backslash R \end{cases}$$ where my thought was that I would map $R\subset I$ onto itself, and $I\backslash R$ onto something else. This doesn't fulfil the criteria as I must map all of $I$ injectively into $R$. Now I'm stuck with the thought that if I map something onto $R$ then I can't map more into $R$. Of course $I$ is infinite in size, but I don't know how to exploit this in order to obtain a satisfactory injection.

  • $\begingroup$ Actually the injection is very easy: simply consider $f(x)= \{ x\}$ (i.e. $R= \emptyset$). $\endgroup$ – Crostul Sep 3 '16 at 9:40
  • $\begingroup$ @Crostul Mustn't $R$ be any subset of $I$ according to the definition? Also: $f(x)$ doesn't map every element of $I$ injectively into $R$. In fact it doesn't map any element into $R$. Am I wrong? $\endgroup$ – Logarithmic Derivative Sep 3 '16 at 9:54

You can use:


which is an injection from $I$ to $I\backslash\{\emptyset\}$. The function is well defined since $\forall x\left[x \in I \implies \{x\} \in I\right]$. $I\backslash\{\emptyset\}$ is a proper subset of $I$ since $\emptyset\in I$

  • $\begingroup$ I must be missing something obvious. Please observe my comment to Crostul! $\endgroup$ – Logarithmic Derivative Sep 3 '16 at 10:00
  • $\begingroup$ I now see that the answer was obvious. My apologies. Thank you anyway! $\endgroup$ – Logarithmic Derivative Sep 3 '16 at 10:05

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.