How do you prove that If X is an infinite set, then there is a denumerable subset Y of X such that X and X-Y are equipotent? How do you prove that If X is an infinite set, then there is a denumerable subset Y of X such that X and X-Y are equipotent?
 A: HINT: If $X$ is uncountable, you can use any countable subset $Y$ of $X$; see this question and its answer. If $X$ is countably infinite, let $f:\Bbb N\to X$ be a bijection, and consider the subset $f[E]$ of $X$, where $E=\{2n:n\in\Bbb N\}$.
A: Without the Axiom of Choice, it is consistent that there  exists a set $S$ such (1) $S$ is not a bijective image of any bounded subset of $\mathbb N, $ and (2)  $ S $ has no countably infinite subset. Such a set is not Dedekind-infinite.  The Axiom of Choice implies that any $X$ which is not a bijective image of a bounded subset of $\mathbb N$ is Dedekind-infinite.
The def'n of "$X$ is Dedekind-infinite" is that  there exists a bijection from $ X $ to a proper subset of $ X. $
Suppose that $X$ is Dedekind-infinite and that $f:X\to U $is a bijection with $ U\subsetneqq X.$  Then take any $x_1\in X$ \ $U .$ For  $n\in N,$  let $x_{n+1}=f(x_n).$
We have $x_n\ne x_m $ whenever $ n\ne m. $
Proof: If not, take the least $ n $ such that $\exists m>n\;(x_n=x_m). $ Then $x_n=x_m=f(x_{m-1})\in U,$  so $n>1$.... [ because  $x_1\not \in U \;$]....     so $f(x_{n-1})=x_n=x_m=f(x_{m-1}). $ But then  $f(x_{n-1})=f(x_{m-1}), $ which   implies $x_{n-1}=x_{m-1}, $ which  contradicts the minimality of $n.$
Now, for brevity, let $Z=\{x_n:n\in N\}$  and  $Y= \{x_{2n-1}: n\in N\}.$  Let $g(x)=x$ for $x\in X$ \ $Z $ and $g(x_n)=x_{2n} $ for $n\in N.$ Then $g:X\to X$ \  $Y$ is a surjection.... I will leave it to you to confirm that $g$ is $1$-to-$1$. 
