Proof of the Non-Existence of an Injection from a Larger to Smaller Set w/o Notion of Cardinality

Question

The following is the question I would like some guidance concerning:

Let $i,j\in N$ such that $i>j$. Prove that there is no injective function $f$ from {$1,...,i$} to {$1,...,j$}.

There are numerous proofs for this online which utilize the notion of cardinality, which is what I understand concerns the size of finite sets. I am not allowed to use such a notion. I have attempted 'adapting' proofs that are inspired by posts such as:

There exists no injective function from the power set of A to A

But haven't been successful because in this question we cannot assume one set is the power set of another, and so the strategy of constructing a particular set to prove a given proposition does not work.

I welcome any and all comments.

Answer 1

Let $I = \{1,\ldots,i\}$ and $J = \{1,\ldots,j\}$ be sets with $i > j$ and suppose $f : I \to J$ is an injective function. Then for every $n,m \in I$, with $n \ne m$, we know $f(n), f(m) \in J$ and $f(n) \ne f(m)$.

But since we have $i$ elements in $I$ which $f$ maps to at most $j$ elements in $J$, by the pigeonhole principle, there exist distinct $m,n \in I$ such that $f(m) = f(n)$. This contradicts injectivity of $f$.

Answer 2

We can prove this by simultaneous induction on $i$ and $j$.

Suppose the claim fails. Let $j_0$ be the least natural number such that for some $i>j_0$, there is an injection from $\{1, . . . , i\}$ into $\{1, . . . , j_0\}$. Let $i_0$ be the least such natural number, and $f$ such an injection. Clearly we have $i_0>1$, so in particular $\{1, . . . , i_0\}$ is nonempty.

So what? Well, without loss of generality, $f(i_0)=j_0$. Now think about $\{1, . . . , i_0-1\}$. Restricting $f$ to this set gives an injection from $\{1, . . . , i_0-1\}$ to $\{1, . . . , j_0-1\}$. But $j_0-1<i_0-1$, and this contradicts the assumed minimality of $j_0$, so we're done.