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.
