chiark / gitweb /
unique tips: add condition and prove, for merge
authorIan Jackson <ijackson@chiark.greenend.org.uk>
Wed, 18 Apr 2012 20:34:13 +0000 (21:34 +0100)
committerIan Jackson <ijackson@chiark.greenend.org.uk>
Wed, 18 Apr 2012 20:34:13 +0000 (21:34 +0100)
merge.tex

index 48e7270..45b7f66 100644 (file)
--- a/merge.tex
+++ b/merge.tex
@@ -46,6 +46,13 @@ $L \in \pn$, $R \in \pry$, $M = \baseof{R}$.
     \bigforall_{E \in \pendsof{X}{\py}} E \le Y
    \right]
 }\]
+\[ \eqn{ Suitable Tip }{
+    \bigexists_T
+      \pendsof{J}{\p} = \{ T \}
+     \land
+      \forall_{E \in \pendsof{K}{\p}} T \ge E
+    , \text{where} \{J,K\} = \{L,R\}
+}\]
 \[ \eqn{ Foreign Merges }{
     \patchof{L} = \bot \implies \patchof{R} = \bot
 }\]
@@ -258,6 +265,17 @@ Therefore $D \isin C \equiv D \isin \baseof{C}$.  OK.
 
 $\qed$
 
+\subsection{Unique Tips}
+
+For $L \in \py$, trivially $\pendsof{C}{\py} = C$ so $T = C$ is
+suitable.
+
+For $L \not\in \py$, $\pancsof{C}{\py} = \pancsof{L}{\py} \cup
+\pancsof{R}{\py}$.  So $T$ from Suitable Tip is a suitable $T$ for
+Unique Tips.
+
+$\qed$
+
 \subsection{Foreign Inclusion}
 
 Consider some $D$ s.t. $\patchof{D} = \bot$.