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!
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.)