One-to-one to prove onto

Question

I stumbled across a problem where I have to prove that a given function is one-to-one and onto. This is part (b) of problem 22 in chapter 7 of Velleman's How to Prove It, 2nd edition. It asks the reader to show that the set of all total orders on a finite set A with n elements, call this set $L$, is equinumerous with the set of all one-to-one, onto functions from $I_n$ to A ($I_n = \{ i \in \mathbb{Z}^{+} | i \le n$ }), call this set $F$. I tried to follow the hint that comes at the end of the book but hit bedrock when trying to prove that the function $g:A \rightarrow I_n$ defined as $g(a) = |\{ x \in A|xRa \}|$ is onto. Here goes the hint provided:

Define $h:F \rightarrow L$ by the formula $h(f) = \{(a, b) ∈ A × A | f^{−1}(a) \le f^{−1}(b)\}$. To see that h is one-to-one, suppose that $f \in F$, $g \in F$, and $f \neq g$. Let $i$ be the smallest element of $I_n$ for which $f(i) \neq g(i)$. Now show that $(f(i), g(i)) \in h(f)$ but $(f(i), g(i)) \notin h(g)$, so $h(f) \neq h(g)$. To see that h is onto, suppose $R$ is a total order on A. Define $g: A \rightarrow I_n$ by the formula $g(a) = |\{ x \in A|xRa \}|$. Show that $\forall a \in A \forall b \in A(aRb \iff g(a) \le g(b))$, and use this fact to show that $g^{−1} \in F$ and $h(g^{−1}) = R$.

My line of thought: I have to prove that $g^{−1} \in F$, or alternatively $g$ is a one-to-one function from $A$ onto $I_n$. Using the hint, I managed to show that $g$ is one-to-one. As for $g$ being onto, I think I could use the following facts:

1 ) From the (already proven) fact that $g$ is one-to-one, we have that $\forall a \in A \forall b \in A(a \neq b \Rightarrow g(a) \neq g(b))$.

2 ) Clearly, $1 \le g(a) \le n$, or $g(a) \in I_n$.

With these facts I think it can be shown that $\forall i \in I_n \exists a \in A (g(a) = i)$.

Curiously, this argument uses the fact that $g$ is one-to-one to prove that the $g$ is onto, and I think this is very odd! Anyway, this seems to me too cumbersome. There must be an easier way to prove that $g$ is onto...

Any advice is very much appreciated!

Answer 1

So $A$ is an $n$-element set, $R$ is a linear order on $A$, $I_n = \{1,2, \ldots, n\}$, and $g \colon A \to I_n$ is defined by $$ g(a) = |\{x \in A : xRa\}|. $$ You want to prove that $g$ is surjective.

You can prove it by induction on $n$. The case $n = 1$ is trivial, because in that case there is only one element of $A$. If we call this element $a$ then $g(a) = 1$, because $aRa$, and so $g$ surjects.

So assume the result holds for all sets $A'$ of size $n$ and all linear orders on those sets. Let $A$ be a set of size $n+1$, let $R$ be a linear order on $A$, and let $z$ be the largest element of $A$ under $R$. Let $A'$ be $A \setminus \{z\}$. Then we can define functions $g \colon A \to I_{n+1}$ and $g' \colon A' \to I_n$ as above; for $g'$ we take the restriction of $R$ to $A'$. Because we took $z$ to be the maximum element, we will not change the number of elements below any other element of $A$, and so $g$ and $g'$ agree whenever they are both defined: $g'(a) = g(a)$ for all $a \in A'$.

By induction, $g'$ is surjective from $A' = A \setminus \{z\}$ to $I_n$. Because $g'(a) = g(a)$ for all $a \in A \setminus \{z\}$, we see that every element of $I_n$ is in the range of $g$. The only other element of $I_{n+1}$ is $n+1$ itself.

So, to prove $g$ is surjective, it only remains to prove that $n+1$ is in the range of $g$. Because $z$ is the maximum of $A$ under order $R$, we have $xRz$ for every $x \in A$, so $|\{x \in A : xRz\}| = |A|= n+1$, so $g(z) = n+1$. Thus $n+1$ is also in the range of $g$, which is what we wanted to prove. Hence $g$ is surjective.

As you can see, there is no need here to prove that $g$ is injective before proving it is surjective. However, when $A$ and $B$ are $n$-element sets, there is a more general fact that a function $f\colon A \to B$ is injective if and only if it is surjective. So, if you could prove $g$ was injective, that would actually be sufficient to prove it is surjective, using the general fact.