can somebody help me correct my attempts at proving the following result? Much appreciated.
Theorem. Suppose $X$ is a nonempty finite set. Let $n$ be the least natural number such that there is a one-to-one function $f: X \rightarrow $ {$1,2,3,...,n$}. With the number of elements in $X$ being |$X$|$=n$, prove that $f$ must be onto.
My Attempt:
Suppose for contradiction that $f$ is not onto,then there exist some elements in the codomain {$1,2,3,...,n$} such that no elements of the domain map to them. Let $1 \le i \le n$ be the largest element of the codomain such that $i \notin ran(f)$.
[case $i=n$]. If $i=n$, then by definition $n \notin ran(f)$.Since n is the least natural number that ensures $f$ to be one-to-one, it must be the case that $n \in ran(f)$ providing the contradiction sought.
[case $i<n$] the book gives the hint :
if $i<n$,let $a \in X$ be such that $f(a)=n$.Define a one-to-one function $g : X\rightarrow$ {$1,2,...,n-1$}.
Hence i thought : With $i<n$ and by definition $i \notin ran(f)$ but $n \in ran(f)$,there is an element $a \in X$ such that $f(a)=n$. With $|X|=n$,the number of elements in the domain and codomain are the same,therefore if there is no element in $X$ that maps to $i \in $ {$1,2,3,...,n-1$} then $f$ cannot be one-to-one...but where is g?
this feels wrong but i do not know what to do! Any help appreciated.
Since the mapping $f:X \rightarrow Y$ is one-one, by definition it means that
${ \forall a,b\in X,\;\;a\neq b\Rightarrow f(a)\neq f(b)}$. Since the size of $X$ is $n$ it further means that $n$ different elements of $X$ map into $n$ different elements of $Y$. The size of $Y$ is also $n$ meaning that the mapping is also 'onto' since all elements of $Y$ have a pre-image in $X$.