# Surjective function into Hartogs number of a set

For any set $A$, there is a surjective function $f:\mathcal{P}(A\times A)\longrightarrow\mathcal{H}(A)$. $\mathcal{H}(A)$ is the Hartogs number of $A$.

Proof attempt:

Suppose $R\subseteq A\times A$. Then either $R$ is a well-order, or it’s not. If $R$ is a well-order, then $R$ has the order type of a unique $\alpha_R$, where $\alpha_R$ is an ordinal number.

Define $f:\mathcal{P}(A\times A)\longrightarrow\mathcal{H}(A)$ by $f(R)=\alpha_R$ if $R$ is a well-order and $f(R)=0$ otherwise.

Checking that $f$ is a function is straightforward. Suppose $f(R)=\alpha$ and $f(R)=\beta$. If $R$ is not a well-order, then $f(R)=0=\alpha=\beta$. If $R$ is a well-order, then $\alpha_R$ is unique and $\alpha=\alpha_R=\beta=f(R)$.

To show $f$ is surjective, suppose $\alpha\in\mathcal{H}(A)$. We need to find an $R\in\mathcal{P}(A\times A)$ such that $f(R)=\alpha$. Here’s where I’m having trouble. I know that since $\alpha\in\mathcal{H}(A)$, it must be an ordinal. It is not difficult to construct a well-ordered set isomorphic to $\alpha$. However, I am having a hard time constructing a well-ordered $\textbf{subset of$A\times A$}$ that is isomorphic to $\alpha$.

HINT: If $\alpha\in\mathscr{H}(A)$, there is an injection $h:\alpha\to A$, and you can use $h[\alpha]\subseteq A$ to construct an $R\subseteq A\times A$ such that $f(R)=\alpha$.