Proving that there is no surjective function from $\mathbb{E}_n$ to $\mathbb{E}_m$

69 Views Asked by At

The question asks to prove that there is no surjective function $f : \mathbb{E}_n \rightarrow \mathbb{E}_m$ with $n,m \in \mathbb{N}$ and $n<m$.

The hint suggests using complete induction to $n$ or $m$. How would I do this? I am completely stumped on this question.

Edit: In the book it states that $\mathbb{E}_n = \{j \in \mathbb{Z}|1\leq j \leq n \} = \{1,2,...,n\}$

1

There are 1 best solutions below

0
On

I'm sure there's answers on this site to you question of why there aren't surjections from $\{1,\ldots,n\}\to\{1,\ldots,m\}$ if $m>n$.

Here's a hint anyway,

Suppose you have, $m>n\in\Bbb{N}$ and a map $f:\Bbb{E}_n\to\Bbb{E}_m$, using the notation above.

Consider the image of $f$, that is $\,f(\Bbb{E}_n)\subseteq \Bbb{E}_m$, and consider the size of this set.

It should be clear for finite sets that if $A\subseteq B$, then $|A|\leq |B|$. I guess more generally this follows from a definition using the inclusion map.

What can you conclude about the map $\,f$ if you apply this to the set inclusion $\,f(\Bbb{E}_n)\subseteq \Bbb{E}_m$.