Definition$\quad$ A set $S$ can be defined as infinite if there exists a mapping from $S$ to $S$ that is one-to-one but not onto. Otherwise, $S$ is finite.

Problem: Using the definition of infinite above, prove that if a set $S$ has an infinite subset, then $S$ is infinite.

My attempt: Suppose $T\subseteq S$, where $T$ is infinite. By the supplied definition of infinite, there exists a mapping $\eta\colon T\to T$ that is one-to-one but not onto. That is, for all $x_1,x_2\in T$, we have $\eta(x_1)=\eta(x_2)\to x_1=x_2$, but there exists $\tau\in T$ such that $\eta(x)\neq\tau$ for all $x\in T$.

Consider a one-to-one and onto mapping $\delta\colon S\setminus T\to S\setminus T$. There exists a mapping $\gamma\colon S\to S$ such that $$ \gamma\colon S\to S\equiv \begin{cases} \eta\colon T\to T &\text{if $x\in T$},\\[0.25em] \delta\colon S\setminus T\to S\setminus T &\text{if $x\in S\setminus T$}. \end{cases} $$ The mapping $\gamma\colon S\to S$ is one-to-one because $x_1,x_2\in T\cup S\setminus T\to x_1,x_2\in S$ and $\gamma(x_1)=\gamma(x_2)\to x_1=x_2$ because $\eta$ and $\delta$ are both one-to-one mappings. However, $\gamma$ is not onto because there exists an element in $S$, namely $\tau$ (since $\tau\in T\to\tau\in S$ because $T\subseteq S$), that is not mapped to. Hence, there exists a mapping $\gamma$ from $S$ to $S$ that is one-to-one but not onto when $T\subseteq S$ and $T$ is infinite. Thus, $S$ is infinite. $\Box$

Question: Is this a good/correct proof? If not, where did I go wrong? If it is correct, then is there a way I can improve it or is there a more elegant approach?

  • $\begingroup$ Looks good to me. The only thing I would change is to use the identity on $S\setminus T$ as $\delta$. $\endgroup$ – A.P. Apr 22 '15 at 17:33
  • 1
    $\begingroup$ I find it perfect. $\endgroup$ – ajotatxe Apr 22 '15 at 17:34
  • $\begingroup$ @A.P. I'm not sure what you mean exactly. What do you mean by "use the identity"? $\endgroup$ – fancynancy Apr 22 '15 at 17:34
  • $\begingroup$ I mean the map $x \mapsto x$. $\endgroup$ – A.P. Apr 22 '15 at 17:34
  • 1
    $\begingroup$ @A.P. Thanks for the input! That does it make it simpler since the identity mapping is always onto and one-to-one...I can make it more specific in that sense. :) $\endgroup$ – fancynancy Apr 22 '15 at 17:38

Looks good to me. The only thing I would change is to define $\delta$ as the identity on $S∖T$, i.e. as $$ \begin{align} \delta \colon S \setminus T &\to S \setminus T \\ x &\mapsto x \end{align} $$

  • $\begingroup$ I'm not looking for easy rep, but if you accept this (or any other) answer your question will not appear unanswered anymore, contributing to keep the site a bit more tidy. $\endgroup$ – A.P. Apr 22 '15 at 17:52
  • $\begingroup$ Could always make it CW $\endgroup$ – Daniel W. Farlow Apr 22 '15 at 18:00
  • $\begingroup$ @MagicMan I'm a bit ashamed about this, but I couldn't find the option. :P $\endgroup$ – A.P. Apr 22 '15 at 18:03

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.