When is a set infinite Prove a set A is infinite if and only if it has a subset B ⊂ A such that B $\neq$ A and
|B| = |A|.
For the direction where we have B as a subset of A and have |B| = |A| and need to prove A is infinite,
I want to say that this should work-
Say A is finite. Then B is finite, by way of being a proper subset of A. Therefore, cardinalities of A and B cannot be the same since there exists no bijection between them. This is a contradiction to our hypothesis that they are indeed the same. Hence, A must be infinite.
For the direction where we show if A is infinite, then there must exist B (a proper subset) such that cardinalities of A and B are same, I said this:
If there exists a proper subset B such that cardinalities of A and B are not same, then there exists no bijection between A and B. This is true for finite sets. Now how do I move to say that this must mean infinite sets do not have this property?
NOTE: I'm taking an introductory level class in proof writing and there has been no mention of the axiom of choice.
 A: Thanks for warning us not to use the axiom of choice, since that makes for such an easy proof of a countably infinite subset (which is the crux of the problem) one could be forgiven for not knowing a choice-free strategy to prove the same.
If $A$ is infinite $\Bbb N$ can either be injected or surjected to $A$, respectively implying $A$ has an infinite subset or $A$ is countable. In the latter case $A$ is countably infinite and can be bijected with $\Bbb N$, so either way $A$ has a subset we can biject with $\Bbb N$, say $\{f(n)|n\in\Bbb N\}$.
Finally, $B:=A\backslash\{f(0)\}$ bijects with $A$; in the $B\to A$ direction send $f(n)$ to $f(n-1)$, or any other element of $B$ to itself.
A: The usual proof uses the fact that $A$ has a proper subset that is countable. Call it $C$ and label its elements $c_1,c_2\dots$.
Then we can construct a bijection $A \rightarrow A\setminus \{c_1\}$. The function is defined by $f(x)=x$ if $x$ is not in $C$ and $f(c_n)=c_{n+1}$
Now in order to show the countable subset exists just build it with induction.
