Examine my proof: A bijection exists between any two finite nonempty sets that share the same number of elements I was told to prove or disprove that if the two finite, nonempty sets $X$ and $Y$ have the same number of elements, then there is a one-to-one function from each element of $X$ to each element of $Y$.
I was trying to prove it using mathematical induction in the following way:
Base Case: There is a bijection between $\{x\}$ and $\{y\}$: $f(x)=y$, $f^{-1} (y)=x$.
Assumption: There is a bijection between the sets $A$ and $B$, and $A$ and $B$ are finite, nonempty and have the same number of elements.
Inductive Step: Therefore, $A\cup\{x\}$ and $B\cup\{y\}$ have a bijection if $x\not\in A$ and $y\not\in B$.
Here's me proving the inductive step:
A pair of functions $f$ and $f^{-1}$ exists that links every element of $A$ to $B$ and $B$ to $A$.
With it, a bijection $g$ and $g^{-1}$ can be constructed between $A\cup\{x\}$ and $B\cup\{y\}$. If $a\in A\cup\{x\}$ and $b\in B\cup\{y\}$, then $g$ is defined as follows:


*

*$g(a) = f(a)$ if $a\neq x$

*$g(a) = y$ if $a=x$

*$g^{-1} (b) = f^{-1} (b)$ if $b\neq y$

*$g^{-1} (b) = x$ if $b=y$
Then $y$ has only one input in $A$ that points to it, so $g$ is one-to-one.
Exactly the same can be said about $g^{-1}$. $x$ has only one input in $B$, so $g^{-1}$ is one-to-one as well.
Lastly, since $g(x)=y$, and $g^{-1} (y) = x$, $f$ and $f^{-1}$ are inverses, $g$ and $g^{-1}$ are inverses.
Are there logical holes in this attempted proof?
 A: I think the ideas in your proof are basically ok, but there are  nevertheless a couple of problems with it:


*

*As the proof is worded you've strictly speaking proved the result only for the particular sets $\ A\ $ and $\ B\ $ which you've built up from your initial single-element sets by adding a succession of elements $\ x\ $ and $\ y\ $ to them.  A proper proof for any arbitrary pair of sets with the same number of elements should be worded slightly differently.

*(Relating to the issues raised by Brian Moehring in his comment) In using a proof by induction, you've implicitly assumed that two finite sets with the same number of elements must both contain exactly $\ n\ $ elements for some positive integer $\ n\ $.  Since that assumption is actually correct, there's nothing really wrong with it, but a set's containing exactly $\ n\ $ elements means precisely that there's a bijection between that set and the set $\{1,2, \dots, n\}\ $, and if there is such a pair of bijections $\ \varphi_A:A\rightarrow\{1,2, \dots, n\}\ $ and $\ \varphi_B:B\rightarrow\{1,2, \dots, n\}\ $, then $\ \varphi_B^{-1}\varphi_A\ $ is a bijection from $\ A\ $ to $ \ B\ $ and $\ \varphi_A^{-1}\varphi_B\ $ is a bijection from $\ B\ $ to $ \ A\ $.  Your desired conclusion therefore follows almost immediately from the definition of what it means to contain the same number of elements, thus making all the extra steps necessary to complete a proof by induction unnecessary.


A proper wording of your induction hypothesis, as referred to in item $1$ above, would be something like: "Let $\ n\ $ be any positive integer such that there is a bijection between any pair of sets which both contain exactly $\ n\ $ elements."  To prove the induction step you would then have to take any pair of sets $\ A\ $ and $\ B\ $ which both contain exactly $\ n+1\ $ elements, and prove that there's a bijection between them. As pointed out in item $2$ above, you don't actually need to invoke the the induction hypothesis to draw this conclusion, but you could do so if you wish by simply removing one element $\ x\ $ from $\ A\ $ and one element $\ y\ $ from $\ B\ $.  Since $\ A\setminus\{x\}\ $ and $\ B\setminus\{y\}\ $ both contain exactly $\ n\ $ elements, they satisfy the conditions of the induction hypothesis, and you can then proceed to construct the bijection from $\ A\ $ to $\ B\ $ in exactly the same way that you did in your proof.
