m,j\geq m;\\
0,&\mbox{ if } i>m,j*1$,
essentially ``shifting" our noses and hollows to make room for those of
the newly-added point. We will then construct the remaining nose/hollow
relationships of $I^h_j$, and show that $I^h_j\in\I_n$ and
$F_n(I^h_j)=M^h_j$.\newline
Case 1: $P_j$ is a hard peak. Let $I^h_j$ have the following
properties: $p_1Hx_1$, $x_1H\beta$, $\alpha Hx_0$, $x_0Hq_k$,
$r_1Nx_1$, and $x_0Ns_l$. If our sets $\{p_i\}_{i=1}^k$ is empty, we
set $x_0Hx_1$. By this construction every element in $I^h_j$, $x_0$ and
$x_1$, has the same number and type of nose/hollow relationships as
their corresponding elements of $I$. Furthermore, with the definition
of the nose/hollow relationships of $x_0$ and $x_1$, $(x_0,x_1)$ is now
a horizontal step, with $x_0$ mapping to a positive soft peak and $x_1$
mapping to a negative soft peak. Thus we have shown that if $I\in\I_n$,
then $F_{n+1}(I^h_j)=M^h_j$.
Let $ A$ denote the incidence matrix of $I$. We will investigate the
incidence matrix of $I$, which we will denote $ A^h_j$, with the
purpose of showing that $I\in\I_n$. $ A^h_j$ is constructed as follows:
We start with the matrix $ A$, and duplicate the row and column
corresponding to $x$, placing the copy next to the original. These two
duplicate rows and columns are $x_0$ and $x_1$. The resulting matrix
implies that $\alpha Hx_1$, so we add a ``1" in the row corresponding
to $\alpha$ so that we have $\alpha Hx_0$. Now let $r_i$ correspond to
the $z_i$th row in the matrix for all $i$. We add enough 1's in rows
$z_i$ through $z_{i+1}-1$ so that the nose $r_iNs_i$ has now become
$r_iNs_{i-1}$ and $r_1Nx_1$. Note that this furthermore shifts each
hollow such that we now have $p_iHq_{i-1}$. Finally, we add enough 1's
in the row corresponding to $x_0$ so that we have $x_0Ns_k$. This
procedure is exemplified in Figures \ref{Fig:horiz_hp_incidence},
\ref{Fig:horiz_start}, and \ref{Fig:horiz_finish}.
Let $a,b\in I^h_j$ where $a$ immediately precedes $b$ in the trace of
$I^h_j$. Since $p_1Hx_1$, $x_0Hq_k$, and the pair $x_0,x_1$ have
different predecessor sets, neither $a$ nor $b$ are the elements $x_0$
or $x_1$. Suppose $\pred(a)=\pred(b)$ and $\suc(a)=\suc(b)$. Then $a$
does not nose any element, and no element hollows $a$ in $I^a$. These
statements are also true in $I$ by our construction of $I^h_j$. This
implies that $\pred(a)=\pred(b)$ and $\suc(a)=\suc(b)$ in $I$, a
contradiction. Thus, $I^h_j$ is irredundant. We must now verify the
connectedness of $I^h_j$. By our construction of $I^h_j$, no element
noses an element adjacent to it in the trace; the noses $r_1Nx_1$,
$x_0Ns_l$, and $r_iNs_{i-1}$ are all between non-adjacent elements.
Since all other nose relationships were inherited from $I$, this shows
that $I^h_j$ is connected. We conclude that $I^h_j\in\I_{n+1}$.
\begin{figure} \begin{tabular}{c}
\begin{tabular}{c|ccccccccccccccccccc}
&1&$\alpha$/$r_1$&$p_1$&$r_2$&$p_2/r_3$&$x$&$q_1/s_1$&$q_2/s_2$&$\beta/s_3$&10\\
\hline 1&0&0&0&1&1&1&1&1&1&1\\ $\alpha$/$r_1$&0&0&0&0&0&0&1&1&1&1\\
$p_1$&0&0&0&0&0&0&0&1&1&1\\ $r_2$&0&0&0&0&0&0&0&1&1&1\\
$p_2/r_3$&0&0&0&0&0&0&0&0&1&1\\ $x$&0&0&0&0&0&0&0&0&0&1\\
$q_1/s_1$&0&0&0&0&0&0&0&0&0&1\\ $q_2/s_2$&0&0&0&0&0&0&0&0&0&1\\
$\beta/s_3$&0&0&0&0&0&0&0&0&0&0\\ 10&0&0&0&0&0&0&0&0&0&0\\
\end{tabular}\\\\ The incidence matrix of a semiorder in $\I_{10}$. The
associated Riordan path is shown in\\ Figure \ref{Fig:horiz_start}.\\
\begin{tabular}{c|ccccccccccccccccccc}
&1&$\alpha$/$r_1$&$p_1$&$r_2$&$p_2/r_3$&$x_0$&$x_1$&$q_1/s_1$&$q_2/s_2$&$\beta/s_3$&10\\
\hline
1&0&0&0&1&1&1&1&1&1&1&1\\
$\alpha$/$r_1$&0&0&0&0&0&0&0&1&1&1&1\\
$p_1$&0&0&0&0&0&0&0&0&1&1&1\\
$r_2$&0&0&0&0&0&0&0&0&1&1&1\\
$p_2/r_3$&0&0&0&0&0&0&0&0&0&1&1\\
$x_0$&0&0&0&0&0&0&0&0&0&0&1\\
$x_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_1/s_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_2/s_2$&0&0&0&0&0&0&0&0&0&0&1\\
$\beta/s_3$&0&0&0&0&0&0&0&0&0&0&0\\
10&0&0&0&0&0&0&0&0&0&0&0\\
\end{tabular}\\\\
The incidence matrix after duplication.\\
\begin{tabular}{c|ccccccccccccccccccc}
&1&$\alpha$/$r_1$&$p_1$&$r_2$&$p_2/r_3$&$x_0$&$x_1$&$q_1/s_1$&$q_2/s_2$&$\beta/s_3$&10\\
\hline
1&0&0&0&1&1&1&1&1&1&1&1\\
$\alpha$/$r_1$&0&0&0&0&0&0&1&1&1&1&1\\
$p_1$&0&0&0&0&0&0&0&1&1&1&1\\
$r_2$&0&0&0&0&0&0&0&1&1&1&1\\
$p_2/r_3$&0&0&0&0&0&0&0&0&1&1&1\\
$x_0$&0&0&0&0&0&0&0&0&0&1&1\\
$x_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_1/s_1$&0&0&0&0&0&0&0&0&0&0&1\\
$q_2/s_2$&0&0&0&0&0&0&0&0&0&0&1\\
$\beta/s_3$&0&0&0&0&0&0&0&0&0&0&0\\
10&0&0&0&0&0&0&0&0&0&0&0\\
\end{tabular}\\\\
The incidence matrix after shifting rows $\alpha$ through $x_0$. The associated Riordan path is\\ shown in in Figure \ref{Fig:horiz_finish}.\\
\end{tabular}
\caption{Constructing the Incidence Matrix $ A^h_j$ from $ A$ with $j=6$}
\label{Fig:horiz_hp_incidence}
\end{figure}
Case 2: $P_j$ is a positive soft peak. Let $I^h_j$ have the following
properties: $p_1Hx_1$, $x_1H\beta$, $\alpha Hx_0$, $x_0Hq_k$,
$r_1Nx_1$, $x_1N\delta$, and $x_0Ns_k$. If $\{p_i\}_{i=1}^k$ is empty,
then set $x_0Hx_1$. Analogously to our previous case, this construction
implies that if $I^h_j\in\I_n$, then $F_{n+1}(I^h_j)=M^h_j$.
Furthermore, the construction of the incidence matrix of $I^h_j$ is
identical to that of the case of a hard peak. In duplicating the row
corresponding to $P_j$, the element $x_1$ is given the property
$x_1N\delta$, as required by our construction of $I^h_j$. Since the
procedure for constructing the incidence matrix of $I^h_j$ is the same
for both the case of the hard peak and the soft peak, we conclude that
$I^h_j$ is an interesting semiorder in the case of a soft peak as
well.\newline
Case 3: $P_j$ is a positive soft dip. Let $I^h_j$ have the following
properties: $p_1Hx_0$, $x_0Hq_k$, $x_1H\beta$, $r_1Nx_1$,
$x_1N_\delta$, $\gamma Nx_0$, and $x_0Ns_k$. Similar to the previous
cases, we have that f $I^h_j\in\I_n$, then $F_{n+1}(I^h_j)=M^h_j$.
In constructing our matrix, we proceed identically to the case of the
hard peak with one exception: rather than begin adding 1's with the row
corresponding to $\alpha$ (this element does not exist in this case),
we add a "1" to the row corresponding to $\gamma$ after duplication so
that $\gamma Nx_0$. We then proceed exactly as in the case of a hard
peak. Analogously, our resulting matrix represents an interesting
semiorder, and thus we have $F_{n+1}(I^h_j)=M^h_j$.\newline
Case 4: $P_j$ is a positive slope. Let $I^h_j$ have the following properties: $p_1Hx_0$, $x_0Hq_k$, $x_0Ns_k$, $r_1Nx_1$, $x_1N\delta$, and $x_1H\beta$. Similar to the previous cases, we have that f $I^h_j\in\I_n$, then $F_{n+1}(I^h_j)=M^h_j$.
Again, we construct our matrix in a manner identical to that of the case of the hard peak, with the following exception: Since $\alpha$ does not exist in this case, we simply ignore this element and begin adding 1's wherever necessary. This results in a matrix representing an interesting semiorder, proving that $F_{n+1}(I^h_j)=M^h_j$ for this case as well.\newline
Case 5: $P_j$ is a hard dip.
\begin{lem}\label{Lem:height}
Let $P$ be a hard dip of a Riordan path $M$ with preimage $I$ under $F_n$, let $n_i$ be the number of noses initiated prior to $P$, and let $n_t$ be the number of noses terminated prior to $P$. The height of $P$ is equal to $n_i-n_t-1$.
\end{lem}
\begin{proof}
Let $P_i$ denote the $i$th point in $M\in\R_n$, let $1 1$, each point $P_i$ that initiates a nose is preceded by an up-step, and each point that terminates a nose precedes a downstep, which follows directly from our definition of $F_n$. Thus we can associate exactly one up-step to each nose initiated after $P_1$, and exactly one down-step to each nose terminated.
Each up-step that is not part of a hard peak immediately precedes a point that initiates a nose, and each down-step that is not part of a hard peak is immediately preceded by a point that terminates a nose. A hard peak neither initiates nor terminates a nose, and contains both an up-step and a down-step. We now note that $P_1$ initiates a nose but is not preceded by an up-step.
Thus we arrive at the following two equations: $n_i=u-h+1$ (our ``+1" comes from the fact that we do not associate $P_1$ with an up-step) and $n_t=d-h$. Combining these, we get that $n_i-n_t=1+u-d$, or equivalently, $n_i-n_t-1=u-d$. We conclude that the height of $P_k$ is equal to $n_i-n_t-1$.
\end{proof}
In all previous cases, the fact that $M^h_j\in\R_{n+1}$ has been trivial. This case, however, provides the possibility of a horizontal step being added on the horizontal axis, which would result in $M^h_j$ not being a Riordan path. We will thus require that $P_j$ is of height greater than 0. Equivalently, this means that there are at least two unterminated noses initiated prior to the point $P_j$, by the previous lemma. One of these noses is initiated by the point corresponding to $\gamma$, and the rest ensure that our set $\{r_i\}^l_{i=1}$ is non-empty.
For this case, we let $I^h_j$ have the following properties: $\gamma Nx_0$, $x_0Ns_k$, $r_1Nx_1$, and $x_1N\delta$. We add 1's to our incidence matrix just as in previous cases, starting with the row corresponding to $\gamma$ and ending with that corresponding to $x_0$. Since there are no noses between adjacent points, connectedness is guaranteed, and irredundancy is guaranteed by an argument analogous to that of each previous case.
Finally, we consider the cases of a level point, a negative soft peak, and negative soft dip, and a negative slope. If $P_j$ is a negative soft peak, negative soft dip, or negative slope, we have that $M^h_j$ has a preimage under $F_{n+1}$ by Theorem \ref{Thm:mirror}. If $P_j$ is a level point, then adding a horizontal step to the point $P_j$ is equivalent to adding a horizontal step to the point $P_{j-1}$. Continuing as necessary, we find that adding a horizontal step to $P_j$ is equivalent to adding a horizontal step to $P_{j-i}$ for some $1*