Is there reason for concern with this proof that "there is a bijective function from $\{1,...,m\}$ to $\{1,...,n\}$ only if $m = n$"?

Question

I am trying to prove that the notion of cardinality for finite sets (defined as the $n$ in $\{1,...,n\}$ with which a given finite set is in bijective correspondence) is well-defined. To that end, it's necessary for me to verify that

Let $m,n$ be positive naturals. Then there is a bijective function from $\{1,...,m\}$ to $\{1,...,n\}$ only if $m = n$.

I was initially of the opinion that this answer resolved my problems, but I am no longer so certain. I am making a new question just because the answerer is not active and, therefore, I thought this was the best way to get a consensus answer. Below I give my objections to the accepted answer (perhaps my objections are ill-founded, in which case, I'd appreciate it if someone can set me straight). Ostensibly, the argument (when the answerer writes, "it suffices") proves $\operatorname{Card}{\{1,...,m\}} = \operatorname{Card}{\{1,...,n\}}$ but there are two problems with that:

(1) We are using this theorem/lemma to prove that $\operatorname{Card} X$ is well-defined in the first place! Thus we cannot make mention of the notion which is not, as yet, well-defined.

(2) Even if (1) were not a problem, $\operatorname{Card}{\{1,...,m\}} = \operatorname{Card}{\{1,...,n\}}$ just means, by definition, that both have a bijection to some $\{1,...,k\}$, which is to say (by composition of bijections) there is a bijection between $\{1,...,m\}$ and $\{1,...,n\}$. But that was our hypothesis in the first place, and is certainly not the claim that $m = n$!

I am suspicious that perhaps my issue here is with the dubious ellipsis in the $\{1,...,m\}$ etc. set definitions, and that if I could make that more precise then I would be able to show that which I want to show.

Answer 1

In the context of proving a statement like this, you are correct that you should really never be using the notation "Card" as if it were a function. But the proof still works when you interpret it appropriately as always referring to some specific natural number for which you have a bijection. Here's how you do that, going line-by-line through Clive Newstead's answer:

Since $f^{-1}$ is injective, it suffices to prove that if there is an injection $f : X \to Y$ then $\mathrm{Card}(X) \le \mathrm{Card}(Y)$. This can be done by induction on $\mathrm{Card}(X)$, and is fairly tedious.

Here instead of referring to $\mathrm{Card}(X)$ and $\mathrm{Card}(Y)$, you should refer to specific natural numbers that are in bijection with $X$ and $Y$. That is, it suffices to prove that if $i$ and $j$ are natural numbers and $f:X\to Y$ is an injection where $X$ is in bijection with $\{1,\dots,i\}$ and $Y$ is in bijection with $\{1,\dots,j\}$, then $i\leq j$. This can be done by induction on $i$.

For the induction step, fix $n \in \mathbb{N}$ and suppose that, whenever there exists an injection $f : X' \to Y'$ with $\mathrm{Card}(X') = n$, then $\mathrm{Card}(X') \le \mathrm{Card}(Y')$.

Again, here $\mathrm{Card}(X') = n$ just means there is a bijection between $X'$ and $\{1,\dots,n\}$, and $\mathrm{Card}(X') \le \mathrm{Card}(Y')$ means that $n\leq m$ for any $m$ such that $Y'$ is in bijection with $\{1,\dots,m\}$.

Take a set $X$ of cardinality $n+1$ and suppose $f : X \to Y$ is an injection; you need to use the induction hypothesis to prove that $\mathrm{Card}(X) \le \mathrm{Card}(Y)$.

Again here what you want to prove is that if $Y'$ is in bijection with $\{1,\dots,j\}$ then $n+1\leq j$.

To do this, take an element $x_0 \in X$; note this exists since $\mathrm{Card}(X) > 0$.

Here $\mathrm{Card}(X)$ just refers to $n+1$.

• Deduce that $\mathrm{Card}(X \setminus \{ x_0 \}) \le \mathrm{Card}(Y \setminus \{ f(x_0) \})$. To do this, you will need to prove the more general fact that if $A$ is a set and $a \in A$ then $\mathrm{Card}(A \setminus \{ a \}) = \mathrm{Card}(A) - 1$.

Here what you want to prove is that if $A$ is a set that is in bijection with $\{1,\dots,m\}$ for some $m\in\mathbb{N}$ and $a\in A$ then $A\setminus \{a\}$ is in bijection with $\{1,\dots,m-1\}$. So in particular, $X \setminus \{ x_0 \}$ is in bijection with $n$ and $\mathrm{Card}(Y \setminus \{ f(x_0) \})$ is in bijection with $j-1$, and then the induction hypothesis tells you that $n\leq j-1$.