Is the axiom of choice necessary here?

In the book Analysis I by Terence Tao, there is the following exercise: 《Let $X $ be a set, show that $X $ is infinite if and only if there exists a proper subset $Y $ of $X $ which has the same cardinality as $X $. (This exercise requires the Axiom of Choice)》

My attempt:

• If $X $ is finite, then it is trivial (by induction on the number of elements)

• If $X $ is infinite, then pick $x_0 $ in $X $, we will show a bijection between $X $ and $Y=X\setminus \{x_0\} $. Take a sequence $(x_n ) $ of distinct elements of $Y $: (the definition of the sequence is by induction) If we have already defined $x_i $ for all $0\leq i \leq n $ for some $n $, then take $x_{n+1} $ to be any element in the non-empty set $Y\setminus \{x_1,\ldots , x_n\} $. Then take the bijection $f:X\to Y $ defined by $f (x)=x $ if $x\neq x_i $ for all $i \geq 0$ and $f (x_i)=x_{i+1} $ otherwise.

I don't see where we used the axiom of choice...

You use the axiom of choice while constructing the sequence $(x_n \mid n \in \mathbb N)$. To make this more apparent, we need to be a bit more formal in how you obtain such a sequence:

Consider the set $S$ of all finite sequences $\vec{y} = (y_n \mid n \le m)$ such that $y_0 = x_0$ as fixed above and such that for all $n < m$ $y_{n+1} \in X \setminus \{ y_0, \ldots, y_n \}$. Now consider the relation $R$ on $S \times S$ given by $$ (y_0, \ldots, y_m) R (z_0, \ldots, z_l) : \iff l > m \wedge \forall n \le m \colon y_n = z_n, $$

in simpler words: $\vec{y}R\vec{z}$ iff $\vec{z}$ is an end-extension of $\vec{y}$.

Your induction proves that for all $\vec{y} \in S$ there is some $\vec{z} \in S$ such that $\vec{y} R \vec{z}$. The axiom of choice (it suffices to have the axiom of dependent choice) now allows you to pick an infinite sequence $( \vec{y}_n \mid n \in \mathbb N)$ such that for all $n \in \mathbb N$ $$ \vec{y}_n R \vec{y}_{n+1}. $$

If you now let $x_n$ be the $n$-th element of $\vec{y}_n$, the resulting sequence $(x_n \mid n \in \mathbb N)$ is as desired.

Note that this doesn't prove that some form of choice is necessary. It only highlights where you implicitly use the axiom of (dependent) choice. To see that, in general, we need some form of choice here is much harder and (for the moment) you really shouldn't worry about that.

the definition of the sequence is by induction

Well, no, not really - you haven't shown how to define the sequence at all, since the choice of $x_n$ given $x_0, ..., x_{n-1}$ isn't unique. What you can prove by induction is that for each $n$, there is a sequence of $n$-many distinct elements of $X$, but this doesn't give you a way to get an infinite sequence of elements of $X$; this is exactly the sort of thing, in fact, that choice is needed for.