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!

  • $\begingroup$ What are $m, n$? If they are natural numbers then the notation , $\lceil m \rceil$ seems redundant. Or does it mean something else? $\endgroup$ – Ishfaaq Apr 9 '15 at 2:09
  • $\begingroup$ Yes, it's somewhat redundant. $m=\{0,1,2,...,m-1\}$ and $n$ is defined in the same manner. $\endgroup$ – thisisourconcerndude Apr 9 '15 at 2:10
  • $\begingroup$ Notation for $\mathbb Z mod n$ or $n\mathbb Z$. $\endgroup$ – Alan Apr 9 '15 at 2:26

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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.