But, why I know how to prove it.
Lemma, if there exist an injection
f:Nm→Nn therefore
m≤n.
Base case n=1, if m>n, then there is atleast two elements in N_m that map to the single element in N_n. So, f(1)=f(2)=1, which isn't a injection, contradictions.
Inductive hypothesis, is that if there exist an injection
f:Nm→Nk then
m≤k.
Consider two cases, either f(i)<k+1 for all i in N_m. Then, considering
m≤k it must be true that
m≤k+1, as from f(i) everything injectively maps to N_k and so if
m≤k+1( if this was false than there must be an element mapped to k+1, which would mean a contradiction.)
Now consider the other case i.e.
f(i0)=k+1 where i_0 is in N_(m). Consider a function g where g(i)=i if
i<i0 and g(i)=i+1 if
i0≥i, where
g:Nm−1→Nm.
Lastly, consider the composite function
f∘g:Nm−1→Nk, this is an injection since its a composite of injection, since f is a injection and g is a injection(if, I wanted to be spammy I would prove this). So
m−1≤k, therefore
m≤k+1.
In both cases,
m≤k+1 and since these are the only two cases, QED.
P.S. Yeah, pretty impressed that I can prove it. Even in both cases i.e. induction on co domain, which is a bit easier as all you defined is a flip function. But, yeah I know how counting works and I don't know if there is branch of maths that is as obessively good as this I might do a PhD in it, I thought this was combinatorics?. But, I just love functions and injections and bijections and proofs that use it. Sort of like counting arguments but when they have a purpose. Amazing.
Can't explain how amazing this is. It basically tells you why counting works which is pretty impressive. As from this lemma then its pretty easy to prove a ton of other stuff like pigeonhole priniciple and even how to count infinite sets as its not that hard to extend this lemma. But, so far this is probably my favourite theorem and proof I have seen in the limited experience of uni maths I have. But, still I could talk about this for days.