I am reading a proof of the following proposition: for a finite set $A, f: A\rightarrow A $ is a bijection if there is an inverse function $g : A\rightarrow A$ such that $\forall x \in A \ g(f(x))=x$. When showing that $f$ is onto after it has showed that $f$ is one-to-one, the proof mentions how the fact that $f$ is one-to-one means the cardinality of its range is $|A|$. I do not understand why this is the case from the mere fact that $f$ is one-to-one. Using the definition of one-to-one, I don't see anything saying that $f$ must map every single element of $A$ onto its range- only that if 2 elements of its domain are mapped to the same element in its range, these elements are equivalent. Did the proof commit a logical error here, or is there something I'm missing? Why must the cardinality of $f$'s range here be $|A|$?
If $f: A\rightarrow A $ is one-to-one, why should its range have cardinality |A|
elementary-set-theoryfunctions
Best Answer
You seem to be misunderstanding what injective means. An injective function is one in which $f(x)=f(y)\implies x=y$. Note that this is equality, not equivalence.
Consider the set $S=\{(a,f(a))\}$. The cardinality of $S$ is the same as the cardinality of $A$ because each $a\in A$ appears once as the first element in a pair in $S$. Since the range of $f$ is contained in the second elements of the pairs in $S$ we get that $\lvert f(A)\rvert\le\vert S\rvert=\lvert A\rvert$.
Since $f$ is injective, each of the elements of $A$ get mapped to a unique element of $f(A)$ so there are at least as many elements of f(A) as there are of $A$ so $\lvert f(A)\rvert\ge\lvert A\rvert$.
Therefore, $\lvert A\rvert =\lvert f(A)\rvert$