Examine my proof: A bijection exists between any two finite nonempty sets that share the same number of elements

Question

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:

1. $g(a) = f(a)$ if $a\neq x$
2. $g(a) = y$ if $a=x$
3. $g^{-1} (b) = f^{-1} (b)$ if $b\neq y$
4. $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?

Answer 1

I think the ideas in your proof are basically ok, but there are nevertheless a couple of problems with it:

1. 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.
2. (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.