How to prove that a set is infinite iff it is Dedekind infinite? I need to prove the following:

A set $X$ is infinite if and only if it is equipotent to a proper subset of itself

Here, $X$ is defined to be infinite if $|X|$ is not a non-negative integer or equivalently, there is no bijection $\mathbb{N}_n \rightarrow X$ for $n\in \mathbb{Z}^\ge$.
My attempt:
The given statement is equivalent to:

$X$ is equipotent to a proper subset of itself $\Leftrightarrow$ $X$ is infinite


Case '$\Rightarrow$':
$X$ is equipotent to a proper subset of itself means that if $A \subset X$, then there exists a bijection $A\rightarrow X$. Therefore, $|A|=|X|$.
But $A\subset X$ implies $|A|<|X|$
This is a contradiction but I am not doing a proof by contradiction so I this outcome is strange to me.
I know that $|A|<|X|$ then no bijection $A \rightarrow X$ can exist. But the bijection must exist since we assumed $A$ and $X$ are equipotent. How do I resolve this and complete the proof?

Case '$\Leftarrow$'
I am stumped by the solution provided:

The main problem I have is the inductive proof showing that $A$ is a denumerable subset. 
In the base case, the set $A$ has only 1 element, namely $a_1$, so, I don't see how it is possible to build a bijection $\mathbb{Z}^+\rightarrow \{x_1\}$
I don't even understand the inductive step as I don't know when the inductive hypothesis is used. In fact, I am not able to discern what the inductive hypothesis is. 
It would be helpful if some one could explain how this proof is trying to show the existence of a denumberable subset for any given indefinite set as well as state what the $P(n), P(k)$ and $P(k+1)$ for this proof by induction are.
 A: I am going to replace some definitions by obviously equivalent ones. The benefit will be that the proofs are easier to understand. I am writing down very detailed proofs that you would not normally find in a college-level math textbook.
Definition: For $n \in \mathbb{N}$ define $[n] = \{k \in \mathbb{N} \mid k < n\}$.
Definition: The image of a map $f : X \to Y$ is the set $\mathrm{im}(f) = \{y \in Y \mid \exists x \in X \,.\, f(x) = y\}$.
Definition: A set $X$ is infinite when for every $n \in \mathbb{N}$ and every map $f : [n] \to X$ there is some $x \in X$ which is not in the image of $f$.
Lemma 1: An infinite set $X$ contains an element.
Proof. Because $X$ is infinite there is $x \in X$ which is not in the image of the unique map $[0] \to X$. QED.
Lemma 2: If $X$ is infinite then there exists a map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for every $n \in \mathbb{N}$ and every $f : [n] \to X$.
Proof. For every $n \in \mathbb{N}$ and $f : [n] \to X$ the set $X \setminus \mathrm{im}(f)$ contains an element because $X$ is infinite. By the axiom of choice there exists a choice map $c$ such that $c(n,f) \in X \setminus \mathrm{im}(f)$ for all $n$ and $f$. QED.
Here is an informal explanation of the map $c$. Given an infinite set $X$ and any elements $x_0, \ldots, x_{n-1} \in X$, we may view the tuple $(x_0, \ldots, x_n)$ as a map $f : [n] \to X$ where $f(k) = x_k$. By a slight abuse of notation we can then write $c(n,f)$ as $c(x_0, \ldots, x_{n-1})$. Now we see that $c$ accepts finitely many elements of $X$ and returns an element in $X$ which is different from all of them.
Proposition 1: If $X$ is infinite then there exists an injective map $i : \mathbb{N} \to X$.
Proof. By Lemma 1 there is $x \in X$ and let $c$ be the map from Lemma 2. Define $i$ by recursion:
\begin{align*}
i(0) &= x \\
i(n) &= c(i(0), \ldots, i(n-1)) \qquad\qquad \text{for $n \geq 1$}
\end{align*}
Clearly, $i$ is injective because $i(n)$ is chosen so that it is different from $i(0), i(1), \ldots, i(n-1)$. QED.
Proposition 2: If $X$ is infinite then it is in bijection with some proper subset $Y \subseteq X$.
Proof. Suppose $X$ is infinite. We seek a proper subset $Y \subseteq X$ and a bijection $f : X \to Y$. Let $i$ be the map from Proposition 1. Define
$$Y = X \setminus \{i(0)\}$$
and define $b : X \to Y$ by
$$b(x) = \begin{cases}
x & \text{if $x \not\in \mathrm{im}(i)$}\\
i(n+1) & \text{if $x = i(n)$ for a (unique) $n \in \mathbb{N}$}
\end{cases}
$$
in words, $b$ takes $i(0)$ to $i(1)$, $i(1)$ to $i(2)$, and so on, and does not move elements which are outside the image of $i$. Clearly, $b$ is injective because $i$ is. It is surjective because the only element not in the image of $b$ is $i(0)$. QED.
Proposition 3: If $X$ is a set and $b : X \to Y$ a bijection from $X$ to a proper subset $Y \subseteq X$, then there is an injective map $j : \mathbb{N} \to X$.
Proof.
Because $Y$ is a proper subset there exists $x \in X \setminus Y$. We define a map $j : \mathbb{N} \to X$ by recursion:
\begin{align*}
j(0) &= x \\
j(n) &= b(j(n-1)) \qquad\qquad\text{for $n \geq 1$}
\end{align*}
To prove that $j$ is injective, it suffices to verify that $j(m) \neq j(n)$ for all $m < n$. We do this by induction on $m$:


*

*if $m = 0$ then $j(0) = x$ is different from $j(n) = b(j(n-1))$ because $b(j(n-1)) \in Y$ and $x \not\in Y$.

*for the induction step, suppose we had $j(m) = j(n)$ for some $0 < m < n$. Then we would have $b(j(m-1)) = j(m) = j(n) = b(j(n-1))$ and because $b$ is a bijection it would follow that $j(m-1) = j(n-1)$, which is impossible by the induction hypothesis for $m-1$. Therefore it must be the case that $j(m) \neq j(n)$.
QED.
Theorem: A set is infinite if, and only if, it is equipotent with some proper subset.
Proof.
If $X$ is infinite then we apply Propostion 2 to get a proper subset $Y \subseteq X$ which is equipotent with $X$.
Conversely, suppose we have a bijection $b : X \to Y$ for a proper subset $Y \subseteq X$. By Proposition 3 there is an injective map $j : \mathbb{N} \to X$. To see that $X$ is infinite, consider any $n \in \mathbb{N}$ and $f : [n] \to X$. There are $n+1$ distinct elements $j(0), j(1), \ldots, j(n) \in X$, and so at least one of them is not in $\mathrm{im}(f)$ because $\mathrm{im}(f)$ has at most $n$ elements. QED.
A: Let me address quickly the first part of the proof, $\Rightarrow$. You don't need to do it by contradiction. You can show that if $f\colon X\to A$ is a bijection, where $A$ is a proper subset of $X$, then there is an injection from $\Bbb N$ into $X$, and therefore $X$ is infinite.
To your second question, perhaps it would have been better to say "recursive construction", since many people only see "induction" as a method for proving statements and not for constructing mathematical objects (which they would say is a recursive definition).
The inductive step says, suppose that $\{a_1,\ldots,a_k\}$ is a defined set, let's define $\{a_1,\ldots,a_k,a_{k+1}\}$. How do we define it? We simply choose an element from $X\setminus\{a_1,\ldots,a_k\}$. Why can we do it? Because $X$ is infinite and we only removed a finite set from $X$.
You might argue, what is $a_{k+1}$? Which element is it? Well, you can't quite pinpoint that element, because you have to make some arbitrary choice and you have to appeal to the axiom of choice. Namely, we first fix some "black box operation" that given a non-empty subset of $X$, it will give us back an element of that subset. And then we use this black box to choose $a_{k+1}$.
So no one is constructing a bijection between an infinite set and a singleton. We construct an infinite set, then we show that this set is denumerable. But that's quite simple because we literally chose for each $n$ a different element, so the map $k\mapsto a_k$ is necessarily an injection.
A: In the case $\Rightarrow$ you are actually arguing by contradiction. Note that $A\subset X, A\ne X\implies |A|< |X|$ if $X$ is finite. In other case you may have $|A|=|X|.$ For example, $\mathbb{N}\subset \mathbb{Z}.$
Now consider the case $\Leftarrow.$ The denumerable subset $A$ is constructed by induction. You start consider any element in $X,$ say $a_1,$ and you have the subset $A_1.$ Now, you assume you have constructed a subset $A_k$ with $k$ different elements. (This is the induction hypothesis, $P(k)$.) Now from $A_k$ you construct a set $A_{k+1}$ with $k+1$ different elements (that is, you prove $P(k+1)$. Note that $A\ne A_k$ for any $k.$ It is $A=\bigcup_{k\in \mathbb{N}} A_k.$
