Write an inductive proof that if there is a surjection $ f : \lceil m \rceil → \lceil n \rceil $ then $m ≥ n$. **Here's the problem:** Write an inductive proof that if there is a surjection $ f : \lceil m \rceil → \lceil n \rceil $ then $m ≥ n$. **Where I Am:** I assume that I should induct on $n$ and come to the conclusion that $m \ge n+1$. I'm also pretty sure I need to exploit the fact that if the cardinality of the codomain is less than or equal to the cardinality of the domain, then there exists a surjection between the two (because that's sort of the "theme" of the problem set). However, I'm not sure how to do in that in the context of an inductive proof, so any guidance here would be appreciated. Thanks!

You are going on right direction. I will use the notation $[n] = \\{1,2,\cdots,n\\}$.

Let assume that the inductive hypothesis holds. That is, for every $k\le n$ if there is a surjection $f$ from $[m]$ to $[k]$ then $m\ge k$.

Let the surjection $g:[m]\to [n+1]$ given. Consider the set $$A=\\{j\in [m] : g(j) = n+1\\}.$$ Since $g$ is onto, $A$ is not empty. Moreover, the restriction $g|_{[m]-A}:[m]-A\to[n]$ to $[m]-A$ is also surjective. Since $[m]-A$ is finite, you can find a natural number $p$ with $|[m]-A|=p$. If $h:[p]\to [m]-A$ is a surjection then the function $$g|_{[m]-A}\circ h : [p]\to [n]$$ is surjective so $p\ge n$. Since $m>p$ (why?) we get $m>n$, which implies $m\ge n+1$.