Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that a set A is infinite if and only if $A$ contains a proper subset $B$ that satisfies $|B|=|A|$.

For the first part, I tried the following: Since $A$ is infinite, it has a countable subset $S=\{a_n\}$ with $n$ in $\mathbb N$. Then we have a function $f:A\to A\setminus \{a_0\}$ such that $f(a_n) = a_{n+1}$ if $a$ is in $A$ and $a=a_n$ and $f(a)=a$ otherwise.

I don't know if this approach is correct, and need help proving part 2.

share|cite|improve this question
I edited your post for formatting and to clarify your definition of $f$. Please check to make sure I edited correctly. – Alex Becker Sep 27 '12 at 2:50
@AlexBecker thanks. – user40105 Sep 27 '12 at 3:34
up vote 1 down vote accepted

That approach is excellent: you have indeed shown that if $A$ is infinite, it admits a bijection with a proper subset.

Suppose that $f:A\to A$ is a bijection from $A$ to a proper subset of $A$. Pick $a_0\in A\setminus f[A]$. Given $a_n$, let $a_{n+1}=f(a_n)$; now prove that the map $n\mapsto a_n$ is a bijection from $\Bbb N$ into $A$.

share|cite|improve this answer
How could I prove part 2 : if there is B such that |B|= |A|, then A is infinite? I was thinking about using the Schroeder-Bernstein thm. – user40105 Sep 27 '12 at 3:37
@Clayton: I suggested a way in my second paragraph: the existence of such a $B$ is equivalent to the existence of a bijection $f$ from $A$ to a proper subset of $A$. – Brian M. Scott Sep 27 '12 at 3:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.