Question on one to one correspondence implies same cardinality, for finite sets I have been taking for granted the fact that given two finite sets $A$ and $B$, if there exists a bijective map then the number of elements in $A$ and $B$ are the same, because I thought this was a trivial fact.  
But then the same doesn't really hold (in some sense) when $A$ and $B$ have infinite elements, because if $A = 2 \mathbb{N}$ and $B = \mathbb{N}$ surely there is a bijective map from $A$ to $B$, but $A$ is a strict subset of $B$. 
This made me think that perhaps in the proof of the fact that given two finite sets $A$ and $B$ the existence of a bijective map implies $|A| = |B|$, the assumption that $|A|$ and $|B|$ are finite must be used.
I was wondering if someone could tell me how to prove this fact(this very basic fact!) and point to me where the assumption is being used. Thank you very much!
 A: One usually defines the number of elements in a finite set $A$ to be the natural number $n$ such that there is a bijection from $\{0,1,\dots,n-1\}$ to $A$.  Once one accepts this definition, it's clear that, if $A$ has $n$ elements (as defined here) and if we have a bijection $f:A\to B$, then $B$ also has $n$ elements, because we can just compose the bijections $\{0,1,\dots,n-1\}\to A\to B$.  
There is, however, a catch here, namely "once one accepts this definition".  The "definition" tacitly presupposes that, given a finite set $A$, there exists exactly one natural number $n$ for which there is a bijection $\{0,1,\dots,n-1\}\to A$; without this presupposition, "the number of elements of $A$" would not be well-defined.  So I need to justify the presupposition.
Half of it, the existence of the desired $n$, is just the usual definition of what it means for $A$ to be finite, so this half is no problem.  Now consider the other half, the uniqueness; what could go wrong here? In principle, there might be two distinct natural numbers $m$ and $n$ such that both $\{0,1,\dots,m-1\}$ and $\{0,1,\dots,n-1\}$ admit bijections to $A$.  If that happened, then composing one of those bijections with the inverse of the other, we'd get a bijection $\{0,1,\dots,m-1\}\to\{0,1,\dots,n-1\}$.  To complete the proof of the uniqueness presupposition, and thus to justify the first paragraph of this answer, it suffices to show that, if $m$ and $n$ are two distinct natural numbers, there cannot be a bijection $\{0,1,\dots,m-1\}\to\{0,1,\dots,n-1\}$.
For this, it suffices to show that there cannot be a one-to-one map $\{0,1,\dots,n\}\to\{0,1,\dots,n-1\}$. (If $m$ and $n$ are different, we can assume, by interchanging their names if necessary, that $m>n$, and then any bijection, indeed any one-to-one map $\{0,1,\dots,m-1\}\to\{0,1,\dots,n-1\}$ would restrict to a one-to-one map $\{0,1,\dots,n\}\to \{0,1,\dots,n-1\}$.)  The non-existence of such a one-to-one map, a fact often called the pigeon-hole principle, is proved by a rather straightforward induction on $n$ (which I won't write out here, since this answer is already rather long).
It is this fact, the pigeonhole principle, that ultimately accounts for why the result applies only to finite sets $A$. The analog of the pigeonhole principle for infinite sets, which would say that you can't map "$X$ plus one extra element" one-to-one into $X$, is simply false. (This observation is sometimes called "Hilbert's hotel" --- the pigeons have become guests and the pigeonholes have become hotel rooms.)
A: Remember, the statement

$|A|=|B|$

is just shorthand for the statement

"There exists a bijection $f\colon A \to B$."

In particular, as there is a bijection $f\colon 2\mathbb{N} \to \mathbb{N}$, it follows from definition that $|2\mathbb{N}|=|\mathbb{N}|$.
Infinite sets of the same cardinality can be properly contained within one another. What you may have noticed, however, is if $A\subseteq B$ are finite sets, and $|A|=|B|$, then $A = B$.
A: There is indeed a hidden property of finite sets in your basic fact. Consider the following property P(E) of a set $E$: 

$P(E)$: If a subset $S$ of $E$ has the same cardinality as $E$, then $S = E$.

Then $P(E)$ holds if and only if $E$ is finite. See this page for various proofs.
