If A is infinite, does there have to exist a subset of A that is equivalent to A?

I was reading Rudin and there is an alternative definition of infinite set (the first definition is "not finite"): A is infinite if it is equivalent to one of its subset. Then I was wondering the converse: if A is infinite, does there have to exist a subset of A that is equivalent to A?

Great question! It turns out the answer is: sort of! It depends on exactly what axioms for set theory we use - specifically, whether or not we accept (an extremely weak form of) the axiom of choice.

In ZF alone - that is, set theory without any form of the axiom of choice - it is consistent that there are infinite sets which are strictly larger than all of their proper subsets ("infinite, Dedekind finite sets"). It is even possible to have sets which are infinite, but cannot be partitioned into two infinite pieces ("amorphous sets")!

Here's a proof that every infinite set has a proper subset of the same size. Let $A$ be infinite. Since $A$ is infinite, we know $A$ has at least $n$ elements, for every $n\in\mathbb{N}$ (the proof is a very silly induction argument :P).

Now let $X_n$ be the set of all length-$n$ sequences of distinct elements of $A$. So, for instance, $X_1=\{\langle a\rangle: a\in A\}$. Note that each element of $X_n$ comes equipped with an ordering (this was missing in my original write-up, but it's crucially important). $X_n\not=\emptyset$ for each $n$, so - and here we use the axiom of choice - we may pick a family of representatives, $x_n\in X_n$. Then $B=\bigcup_{n\in\mathbb{N}} x_n$ is a subset of $A$ equinumerous with the natural numbers! (This is a good exercise.)

Now we're done: it's easy to see that the natural numbers are equinumerous with e.g. the even numbers, so $B$ is equinumerous with a proper subset $B'\subset B$; so $A=B\cup (A\setminus B)$ is equinumerous with $B'\cup (A\setminus B)$, which is a proper subset of $A$.

The proof that we need the axiom of choice here is extremely hard, and requires a powerful set-theoretic technique called forcing.

Yes. Assuming the axiom of choice, if $A$ is infinite then $A$ contains a countably infinite subset $S=\{s_1,s_2,...\}$. Construct a bijection $f:A\to A-\{s_1\}$ by $f(s_i)=s_{i+1}$ for $s_i\in S$ and $f(a)=a$ if $a\notin S$.