1
$\begingroup$

I am having a lot of trouble starting this proof. I would greatly appreciate any help I can get here. Thanks.

Let $n\in \mathbb{N}$. Prove that any injective function from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n\}$ is bijective.

$\endgroup$
  • $\begingroup$ This is often taken to be the definition of a finite set. $\endgroup$ – Baby Dragon Mar 27 '13 at 17:37
  • $\begingroup$ @BabyDragon: That defines a so-called Dedekind-finite set. This concept is equivalent to finiteness in the presence of the Axiom of Choice, but not otherwise. $\endgroup$ – Henning Makholm Mar 27 '13 at 18:44
  • $\begingroup$ @HenningMakholm Thank you. That is interesting. $\endgroup$ – Baby Dragon Mar 27 '13 at 18:45
  • $\begingroup$ @BabyDragon: There are several different ways of characterizing finiteness, and many of them are not equivalent without (some of) the axiom of choice $\endgroup$ – Asaf Karagila Mar 27 '13 at 18:49
  • $\begingroup$ @AsafKaragila HenningMakholm This means that their are models of ZF such that their are sets that are Dedekind finite but fail to be finite in some other (obvious) way? $\endgroup$ – Baby Dragon Mar 27 '13 at 18:56
3
$\begingroup$

define a new function

$$ g: \operatorname{Im}{f} \rightarrow \{1, \cdots, n\} $$

by setting $g(y)$ as that $x$ such that $f(x)=y$ (well-defined because each $y$ is an image and $f$ is injective). note that $f\circ g$ is the identity on $\operatorname{Im}{f}$, hence g must be injective; likewise, $g\circ f$ is the identity on $\{1, \cdots, n\}$, hence g must be surjective. we have just proved that g is a bijection, i.e. a permutation of $1, \cdots, n$.

the concept of cardinality is just shorthand for 'there exists a bijection'...

$\endgroup$
2
$\begingroup$

Another hint: Prove it by induction. It’s clear for $n=1$. Otherwise if the statement holds for some $n$, take an injective map $σ \colon \{1, …, n+1\} → \{1, …, n+1\}$. Assume $σ(n+1) = n+1$ – why can you do this? What follows?

$\endgroup$
1
$\begingroup$

Hint: Let $f : [n] \to [n]$ be injective. What is the cardinality of the image of $f$?

$\endgroup$
1
$\begingroup$

Hint: If $f:[n]\rightarrow [n]$ is injective (where $[n]= \{1,2,\dots,n\}$), all that remains to be shown is that $f$ is surjective. So, suppose it's not. How does the size of the image compare to the size of the domain, and what does this say about injectivity?

$\endgroup$
1
$\begingroup$

What if $f$ would not be bijective? Then one number would not be in the image of $f$. How can that be?

$\endgroup$
0
$\begingroup$

Suppose $f : \{1,\ldots, n\}\to\{1,\ldots, n\}$ is injective. Then $a\neq b\implies f(a)\neq f(b)$, so $\left|\,\operatorname{Im}f\,\right| = \left|\{1,\ldots, n\}\right| = n$. As $\{1,\ldots,n\}$ is the codomain, what can we say?

Since $\{1,\ldots, n\}$ is the codomain and $\left|\{1,\ldots, n\}\right| = n$, everything in the codomain must be hit.

$\endgroup$
  • $\begingroup$ Is there a way to do this without referenece to cardinality? I ask this since here [in this section] I have not yet read/introduced the concept and the source I am using (Analysis I - Escher) has this proof before discussing cardinality. Thanks. $\endgroup$ – Michael Dykes Mar 27 '13 at 16:33
  • 1
    $\begingroup$ I think if you try to avoid it, you'll just work with it in a roundabout way. You can just use the pidgeonhole principle to show that the claims made about cardinality are true. $\endgroup$ – Stahl Mar 27 '13 at 18:18

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.