1
$\begingroup$

Prove that if $n \in \Bbb N$, $f: I_n \to B$, and $f$ is onto, then $B$ is finite and $|B|\leq n$.

Notes on notation:

For each natural number $n$, $I_n = \{i \in \mathbb{Z} \mid i \leq n\}$.

$A \sim B$ indicates that $A$ is equinumerous to $B$.

$f: I_n \rightarrow B$ means there is a function from $I_n$ to $B$.

  • 2
    What have you got so far? Which bit did you get stuck on?2012-12-04

2 Answers 2

1

For each $b\in B$ let $g(b)=\min\{i\in I_n:f(i)=b\}$; since $f$ maps $I_n$ onto $B$, $g$ is well-defined. Now show that $g$ is one-to-one and conclude that $|B|\le|I_n|=n$.

  • 0
    @Eev: In words: let $g(b)$ be the smallest integer in $I_n$ that is mapped to $b$ by $f$.2012-12-03