X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke-formulae.git;a=blobdiff_plain;f=lemmas.tex;h=23e22f3285bbc2ec8544714a1ed4d8a04479121d;hp=aeb656479c497363460d14de95af921d326ccd58;hb=d29c556b0ebedf4081684216f426b83ee9f04573;hpb=57f83cd8bc6bcf23e45739c00c83c9a8672ae701

diff --git a/lemmas.tex b/lemmas.tex
index aeb6564..23e22f3 100644
--- a/lemmas.tex
+++ b/lemmas.tex
@@ -1,6 +1,6 @@
 \section{Some lemmas}
 
-\subsection{Alternative (overlapping) formulations of $\mergeof{C}{L}{M}{R}$}
+\subsection{Alternative (overlapping) formulations of $\commitmergeof{C}{L}{M}{R}$}
 $$
  D \isin C \equiv
   \begin{cases}
@@ -11,7 +11,7 @@ $$
     \text{as above with L and R exchanged}
   \end{cases}
 $$
-\proof{ ~ Truth table (ordered by original definition): \\
+\proof{ ~ Truth table (ordered by original definitions): \\
   \begin{tabular}{cccc|c|cc}
      $D = C$ &
           $\isin L$ &
@@ -53,10 +53,10 @@ So by Base Acyclic $D \isin B \implies D \notin \py$.
   \end{cases}
 }\]
 
-\subsection{Tip Self Inpatch}
-Given Exclusive Tip Contents and Base Acyclic for $C$,
+\subsection{Tip Own Contents}
+Given Base Acyclic for $C$,
 $$
-  \bigforall_{C \in \py} C \haspatch \p \land \neg[ C \nothaspatch \p ]
+  \bigforall_{C \in \py} C \haspatch \p
 $$
 Ie, tip commits contain their own patch.
 
@@ -64,8 +64,8 @@ Ie, tip commits contain their own patch.
 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 \haspatch \p$.  
-And, since $C \le C$, $C \isin C$.  Therefore $\neg[ C \nothaspatch \p ]$
+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}
@@ -103,13 +103,13 @@ $$
   \bigforall_{C \hasparents \set A}
     \pendsof{C}{\set P} =
       \begin{cases}
-       C \in \p : & \{ C \}
+       C \in \set P : & \{ C \}
       \\
-       C \not\in \p : & \displaystyle
+       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}{\p}}
+           \Bigl[ \Largenexists_{B \in \set A, F \in \pendsof{B}{\set P}}
                        E \neq F \land E \le F \Bigr]
        \right\}
       \end{cases}
@@ -117,15 +117,33 @@ $$
 \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}$.
+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$.
+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
@@ -142,12 +160,13 @@ $$
 $$
 \proof{
   Trivial for $D = C$.  Consider some $D \neq C$, $D \isin C$.
-  By the preconditions, there is some $A$ s.t. $D \in \set A$
+  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 \}
@@ -156,12 +175,12 @@ $$
   \right]
  \implies
   \left[
-   \bigforall_{D \text{ s.t. } \patchof{D} = \bot}
+   \bigforall_{D \in \foreign}
      D \isin C \equiv D \le C
   \right]
 $$
 \proof{
-Consider some $D$ s.t. $\patchof{D} = \bot$.
+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$.
@@ -169,23 +188,24 @@ So $D \isin C \equiv D \le C$.
 }
 
 \subsection{Totally Foreign Contents}
+Given conformant commits $A \in \set A$,
 $$
    \left[
     C \hasparents \set A \land
-    \patchof{C} = \bot \land
-      \bigforall_{A \in \set A} \patchof{A} = \bot
+    \isforeign{C} \land
+      \bigforall_{A \in \set A} \isforeign{A}
    \right]
   \implies
    \left[
   \bigforall_{D}
     D \le C
    \implies
-    \patchof{D} = \bot
+    \isforeign{D}
    \right]
 $$
 \proof{
-Consider some $D \le C$.  If $D = C$, $\patchof{D} = \bot$ trivially.
+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
-Contents of $A$, $\patchof{D} = \bot$.
+Contents of $A$, $\isforeign{D}$.
 }