The textbook "Discrete Mathematics with Applications" by Thomas Koshy states a theorem (3.5):
For function $f: X \rightarrow Y$, where
- $X$ is the finite domain and
- $Y$ is the finite co-domain
Two finite sets have the same cardinality if and only if there exists
a bijection between them.
I can prove that if $f$ is a bijective function then $|X| = |Y|$.
However, I am struggling to understand Koshy's proof for the biconditional part.
For example, in the case below where $|X| = |Y|$, the sets have the same cardinality but are not bijective:
- $X = \{-2,-1,1,2\}$
- $Y = \{0, 1, 2, 4\}$
- $f(x) = x^2$
Any ideas if Koshy's proof is wrong, or if not, how one would go about proving this?
edit: adding Koshy's proof below
Let $X$ and $Y$ be two finite sets with $|X| = m$ and $|Y| = n$.
Let $X = \{x_1, . . . , x_m\}$.
Let $f : X → Y$ be bijective.
Since $f$ is injective, $f(x_1), . . . , f (x_m)$
are $m$ distinct elements in $Y$. Consequently, $m \leq n$. Since $f$ is surjective, every element $y$ in $Y$ has at least one input in $X$, so $n \leq m$. Thus $|X| = |Y|$.
Conversely, suppose $m = n$ and $Y = \{y_1, . . . , y_m\}$. Define a function $f : X \rightarrow Y$ by $f(x_i) = y_i$ for every $i$. We will now show that f is injective. Let $x_j$ and $x_k$ be two elements in $X$ such that $f (x_j) = f (x_k)$. Then, by definition,
$y_j = y_k$; so, $j = k$ and hence $x_j = x_k$. Therefore, $f$ is injective and hence, by Theorem 3.4, $f$ is bijective.
Theorem 3.4: Let $X$ and $Y$ be any two finite sets with $|X| = |Y| = n$. A function $f : X \rightarrow Y$ is injective if and only if $f$ is surjective.
Best Answer
You don't need all functions to be bijective, you just need for there to be at least 1.
$X, Y$ finite means we can write $$X = \{x_1, x_2, \ldots, x_m\} \qquad\text{and}\qquad Y = \{y_1, y_2, \ldots, y_n\}$$ for some $m,n\in \mathbb{N}$ such that $x_i$ are distinct for all $i$ and similarly for $y_i$. $|X| = |Y|$ means that $m=n$.
Define the natural bijection $f:X\to Y$ with $f(x_i) = y_i$ for all $i=1,2,\ldots, n$. It's easy to check this is injective, and it clearly has an inverse with a similar looking expression.
P.S. Imagine $f:\{0,1\}\to\{0,1\}$ with $f(x)=0$ for all $x$. This is not a bijection but the sets are clearly the same and so there's a bijection between them.