\section{Some lemmas}

\subsection{Alternative (overlapping) formulations of $\commitmergeof{C}{L}{M}{R}$}
$$
 D \isin C \equiv
  \begin{cases}
    D \isin L  \equiv D \isin R  : & D = C \lor D \isin L     \\
    D \isin L \nequiv D \isin R  : & D = C \lor D \not\isin M \\
    D \isin L  \equiv D \isin M  : & D = C \lor D \isin R     \\
    D \isin L \nequiv D \isin M  : & D = C \lor D \isin L     \\
    \text{as above with L and R exchanged}
  \end{cases}
$$
\proof{ ~ Truth table (ordered by original definitions): \\
  \begin{tabular}{cccc|c|cc}
     $D = C$ &
          $\isin L$ &
               $\isin M$ &
                    $\isin R$ & $\isin C$ &
                                      $L$ vs. $R$ & $L$ vs. $M$
  \\\hline
     y &  ? &  ? &  ?      &      y   & ?         & ?            \\
     n &  y &  y &  y      &      y   & $\equiv$  & $\equiv$     \\
     n &  y &  n &  y      &      y   & $\equiv$  & $\nequiv$    \\
     n &  n &  y &  n      &      n   & $\equiv$  & $\nequiv$    \\
     n &  n &  n &  n      &      n   & $\equiv$  & $\equiv$     \\
     n &  y &  y &  n      &      n   & $\nequiv$ & $\equiv$     \\
     n &  n &  y &  y      &      n   & $\nequiv$ & $\nequiv$    \\
     n &  y &  n &  n      &      y   & $\nequiv$ & $\nequiv$    \\
     n &  n &  n &  y      &      y   & $\nequiv$ & $\equiv$     \\
  \end{tabular} \\
  And original definition is symmetrical in $L$ and $R$.
}

\subsection{Exclusive Tip Contents}
Given Base Acyclic for $C$,
$$
  \bigforall_{C \in \py}
    \neg \Bigl[ D \isin \baseof{C} \land ( D \in \py \land D \le C )
      \Bigr]
$$
Ie, the two limbs of the RHS of Tip Contents are mutually exclusive.

\proof{
Let $B = \baseof{C}$ in $D \isin \baseof{C}$.  Now $B \in \pn$.
So by Base Acyclic $D \isin B \implies D \notin \py$.
}
\[ \eqntag{{\it Corollary - equivalent to Tip Contents}}{
  \bigforall_{C \in \py} D \isin C \equiv
  \begin{cases}
    D \in \py : & D \le C \\
    D \not\in \py : & D \isin \baseof{C}
  \end{cases}
}\]

\subsection{Tip Own Contents}
Given Base Acyclic for $C$,
$$
  \bigforall_{C \in \py} C \haspatch \p
$$
Ie, tip commits contain their own patch.

\proof{
Apply Exclusive Tip Contents to some $D \in \py$:
$ \bigforall_{C \in \py}\bigforall_{D \in \py}
  D \isin C \equiv D \le C $.
Thus $C \zhaspatch \p$.
And we can set $F=C$ giving $F \in \py \land F \le C$, so $C \haspatch \p$.
}

\subsection{Exact Ancestors}
$$
  \bigforall_{ C \hasparents \set{R} }
  \left[
  D \le C \equiv
    ( \mathop{\hbox{\huge{$\vee$}}}_{R \in \set R} D \le R )
    \lor D = C
  \right]
$$
\proof{ ~ Trivial.}

\subsection{Transitive Ancestors}
$$
  \left[ \bigforall_{ E \in \pendsof{C}{\set P} } E \le M \right] \equiv
  \left[ \bigforall_{ A \in \pancsof{C}{\set P} } A \le M \right]
$$

\proof{
The implication from right to left is trivial because
$ \pends() \subset \pancs() $.
For the implication from left to right:
by the definition of $\mathcal E$,
for every such $A$, either $A \in \pends()$ which implies
$A \le M$ by the LHS directly,
or $\exists_{A' \in \pancs()} \; A' \neq A \land A \le A' $
in which case we repeat for $A'$.  Since there are finitely many
commits, this terminates with $A'' \in \pends()$, ie $A'' \le M$
by the LHS.  And $A \le A''$.
}

\subsection{Calculation of Ends}
$$
  \bigforall_{C \hasparents \set A}
    \pendsof{C}{\set P} =
      \begin{cases}
       C \in \set P : & \{ C \}
      \\
       C \not\in \set P : & \displaystyle
       \left\{ E \Big|
           \Bigl[ \Largeexists_{A \in \set A}
                       E \in \pendsof{A}{\set P} \Bigr] \land
           \Bigl[ \Largenexists_{B \in \set A, F \in \pendsof{B}{\set P}}
                       E \neq F \land E \le F \Bigr]
       \right\}
      \end{cases}
$$
\proof{
Trivial for $C \in \set P$.  For $C \not\in \set P$,
$\pancsof{C}{\set P} = \bigcup_{A \in \set A} \pancsof{A}{\set P}$.
So $\pendsof{C}{\set P} \subset \bigcup_{E \in \set E} \pendsof{E}{\set P}$.
Consider some $E \in \pendsof{A}{\set P}$.  If $\exists_{B,F}$ as
specified, then either $F$ is going to be in our result and
disqualifies $E$, or there is some other $F'$ (or, eventually,
an $F''$) which disqualifies $F$ and $E$.
Otherwise, $E$ meets all the conditions for $\pends$.
}

\subsection{Single Parent Unique Tips}

Unique Tips is satisfied for single-parent commits.  Formally,
given a conformant commit $A$,
$$
 \Big[
   C \hasparents \{ A \}
 \Big] \implies \left[
   \bigforall_{P \patchisin C} \pendsof{C}{\py} = \{ T \}
 \right]
$$
\proof{
  Trivial for $C \in \py$.
  For $C \not\in \py$, $\pancsof{C}{\py} = \pancsof{A}{\py}$,
  so Unique Tips of $A$ suffices.
}

\subsection{Ingredients Prevent Replay}
Given conformant commits $A \in \set A$,
$$
  \left[
    {C \hasparents \set A} \land
   \\
    \bigforall_{D}
    \left(
       D \isin C \implies
       D = C \lor
       \Largeexists_{A \in \set A} D \isin A
    \right)
  \right] \implies \left[ \bigforall_{D}
    D \isin C \implies D \le C
  \right]
$$
\proof{
  Trivial for $D = C$.  Consider some $D \neq C$, $D \isin C$.
  By the preconditions, there is some $A$ s.t. $A \in \set A$
  and $D \isin A$.  By No Replay for $A$, $D \le A$.  And
  $A \le C$ so $D \le C$.
}

\subsection{Simple Foreign Inclusion}
Given a conformant commit $L$,
$$
  \left[
    C \hasparents \{ L \}
   \land
    \bigforall_{D} D \isin C \equiv D \isin L \lor D = C
  \right]
 \implies
  \left[
   \bigforall_{D \in \foreign}
     D \isin C \equiv D \le C
  \right]
$$
\proof{
Consider some $D \in \foreign$.
If $D = C$, trivially true.  For $D \neq C$,
by Foreign Inclusion of $D$ in $L$, $D \isin L \equiv D \le L$.
And by Exact Ancestors $D \le L \equiv D \le C$.
So $D \isin C \equiv D \le C$.
}

\subsection{Totally Foreign Ancestry}
Given conformant commits $A \in \set A$,
$$
   \left[
    C \hasparents \set A \land
    \isforeign{C} \land
      \bigforall_{A \in \set A} \isforeign{A}
   \right]
  \implies
   \left[
  \bigforall_{D}
    D \le C
   \implies
    \isforeign{D}
   \right]
$$
\proof{
Consider some $D \le C$.  If $D = C$, $\isforeign{D}$ trivially.
If $D \neq C$ then $D \le A$ where $A \in \set A$.  By Foreign
Ancestry of $A$, $\isforeign{D}$.
}

