Files

1228 lines
65 KiB
Lean4
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
/-
Released under Apache 2.0 license as described in the file LICENSE.
-/
import FormalConflictRange.Empty
/-!
# Reducing a general result to the empty boundary reads
The empty-result theory of `FormalConflictRange.Empty` characterizes a read whose
complete result is empty. This file reduces a *general* result to that theory, in
full generality of traversal and truncation.
For an untruncated result, the complete keys of a read equal a nonempty ascending
list `L` exactly when the two *boundary reads* — the read truncated to `L`'s least
reported key, and the read starting just past `L`'s greatest reported key — are both
empty, the middle interval `[k₀, keyAfter kₙ)` holds exactly `L`, and the resolved
window is bracketed by `k₀` and `kₙ`. A *reversed* read returns `L` descending; the
same bridge is stated for its ascending reading `L.reverse`.
For a *truncated* result only one end of the window is reported. A non-reversed read
returns an ascending prefix `L`: the upper boundary read is dropped, and the lower boundary
read, the middle equality, and the bracketing remain (`bridgeFwdTrunc`). A reversed
read returns a descending prefix, i.e. an ascending suffix `L.reverse`: the lower boundary
read is dropped and the upper boundary read remains (`bridgeRevTrunc`). The single
statement `compatible_iff_bridge_general` covers all four combinations via
`bridgeOf`.
## The factors
* `boundaryReadLo r k₀` keeps the full begin selector and ends at the offset-one
selector keyed at `k₀`. Its emptiness is `[resolve begin, k₀)` holding no stored
key.
* `boundaryReadHi r kₙ` begins at the offset-one selector keyed at `keyAfter kₙ` and
keeps the full end selector. Its emptiness is `[keyAfter kₙ, resolve end)`
holding no stored key.
* `midEq L db` is the interval equality `[k₀, keyAfter kₙ).keys(db) = L`.
* `bracket r L db` is the pair of inequalities `resolve begin ≤ k₀` and
`kₙ < resolve end`, which put `k₀` least and `kₙ` greatest.
-/
namespace FormalConflictRange
open RangeRead
/-! ## The offset-one selector keyed at a value -/
/-- The offset-one selector keyed at `w`: it resolves to the first stored key at
or above `w`, or to `⊤` when there is none. -/
def selAt (w : WithTop Key) : Selector := ⟨w, 1⟩
@[simp] theorem selAt_key (w : WithTop Key) : (selAt w).key = w := rfl
@[simp] theorem selAt_offset (w : WithTop Key) : (selAt w).offset = 1 := rfl
/-- The anchor of `⟨↑b, 1⟩` is the count of stored keys strictly below `b`. -/
theorem anchor_selAt_coe_toNat (db : DB) (b : Key) :
((selAt (↑b : WithTop Key)).anchor db).toNat =
db.keys.countP (fun x => decide (x < b)) := by
rw [Selector.anchor, selAt_key, selAt_offset, countP_lt_coe]
norm_num
/-- The anchor of `⟨↑b, 1⟩` is nonnegative. -/
theorem anchor_selAt_coe_nonneg (db : DB) (b : Key) :
0 ≤ (selAt (↑b : WithTop Key)).anchor db := by
rw [Selector.anchor, selAt_key, selAt_offset, countP_lt_coe]
have := Int.natCast_nonneg (db.keys.countP (fun x => decide (x < b)))
omega
/-- With room to the right, `⟨↑b, 1⟩` resolves to the stored key at the count of
keys strictly below `b`. -/
theorem resolve_selAt_coe_getElem (db : DB) (b : Key)
(h : db.keys.countP (fun x => decide (x < b)) < db.keys.length) :
resolve db (selAt (↑b : WithTop Key)) =
(↑(db.keys[db.keys.countP (fun x => decide (x < b))]) : WithTop Key) := by
rw [resolve_eq_ite, ite_eq_right (not_lt.mpr (anchor_selAt_coe_nonneg db b)),
show db.keys[((selAt (↑b : WithTop Key)).anchor db).toNat]? =
db.keys[db.keys.countP (fun x => decide (x < b))]? by rw [anchor_selAt_coe_toNat],
List.getElem?_eq_getElem h]
/-- A selector keyed at a stored key with offset one resolves to that key. -/
theorem resolve_selAt_self {db : DB} {k : Key} (hk : k ∈ db.keys) :
resolve db (selAt (↑k : WithTop Key)) = (↑k : WithTop Key) := by
obtain ⟨i, hi, hik⟩ := List.mem_iff_getElem.mp hk
have hlt : db.keys.countP (fun x => decide (x < k)) < db.keys.length := by
rw [countP_lt_eq_of_getElem db.sorted hi hik]; exact hi
rw [resolve_selAt_coe_getElem db k hlt, getElem_countP_lt db.sorted hk]
/-- The offset-one selector keyed at `b` resolves at or above `b`. -/
theorem coe_le_resolve_selAt (db : DB) (b : Key) :
(↑b : WithTop Key) ≤ resolve db (selAt (↑b : WithTop Key)) := by
by_cases h : db.keys.countP (fun x => decide (x < b)) < db.keys.length
· rw [resolve_selAt_coe_getElem db b h]
exact WithTop.coe_le_coe.mpr (le_getElem_of_countP_le db.sorted (le_refl _) h)
· rw [resolve_eq_top (db := db) (s := selAt (↑b : WithTop Key))
(anchor_selAt_coe_nonneg db b) (by rw [anchor_selAt_coe_toNat]; omega)]
exact le_top
/-- The resolution of `⟨↑b, 1⟩` is at most any stored key at or above `b`. -/
theorem resolve_selAt_le_of_mem {db : DB} {b x : Key} (hx : x ∈ db.keys) (hbx : b ≤ x) :
resolve db (selAt (↑b : WithTop Key)) ≤ (↑x : WithTop Key) := by
obtain ⟨j, hj, hjx⟩ := List.mem_iff_getElem.mp hx
have hbx' : b ≤ db.keys[j] := by rw [hjx]; exact hbx
have hci : db.keys.countP (fun y => decide (y < b)) ≤ j := by
by_contra hcon
exact absurd (getElem_lt_of_lt_countP db.sorted hj (not_le.mp hcon)) (not_lt.mpr hbx')
have hcl : db.keys.countP (fun y => decide (y < b)) < db.keys.length := by omega
rw [resolve_selAt_coe_getElem db b hcl]
refine WithTop.coe_le_coe.mpr ?_
calc (db.keys[db.keys.countP (fun y => decide (y < b))]'(by omega) : Key)
≤ db.keys[j] := (db.sorted.getElem_le_getElem_iff).mpr hci
_ = x := hjx
/-! ## The boundary reads -/
/-- The lower boundary read of the target least key `k₀`: the full begin selector, with
the end selector replaced by `⟨↑k₀, 1⟩`. -/
def boundaryReadLo (r : RangeRead) (k₀ : Key) : RangeRead :=
{ r with end_ := selAt (↑k₀ : WithTop Key) }
/-- The upper boundary read of the target greatest key `kₙ`: the begin selector replaced
by `⟨keyAfter kₙ, 1⟩`, keeping the full end selector. -/
def boundaryReadHi (r : RangeRead) (kₙ : Key) : RangeRead :=
{ r with begin := selAt (keyAfter kₙ : WithTop Key) }
/-! ## List helpers for the ascending reported keys -/
/-- Membership in `inRange` unfolded. -/
theorem inRange_mem_iff {ks : List Key} {lo hi : WithTop Key} {x : Key} :
x ∈ inRange ks lo hi ↔ x ∈ ks ∧ lo ≤ (↑x : WithTop Key) ∧ (↑x : WithTop Key) < hi := by
unfold inRange
rw [List.mem_filter, decide_eq_true_eq]
/-- Two strictly increasing key lists with the same members are equal. -/
theorem eq_of_mem_iff_pairwise {l₁ l₂ : List Key}
(h₁ : l₁.Pairwise (· < ·)) (h₂ : l₂.Pairwise (· < ·))
(h : ∀ x, x ∈ l₁ ↔ x ∈ l₂) : l₁ = l₂ :=
List.Perm.eq_of_pairwise (fun _ _ _ _ hab hba => (lt_asymm hab hba).elim) h₁ h₂
((List.subperm_of_subset h₁.nodup (fun _ ha => (h _).mp ha)).antisymm
(List.subperm_of_subset h₂.nodup (fun _ ha => (h _).mpr ha)))
/-- The least element of a nonempty ascending list is at or below every element. -/
theorem headD_le_of_pairwise {L : List Key} {x : Key} (h : L.Pairwise (· < ·)) (hx : x ∈ L) :
L.headD ([] : Key) ≤ x := by
cases L with
| nil => exact absurd hx (by simp)
| cons a t =>
rw [List.headD_cons]
rcases List.mem_cons.mp hx with hxx | hx
· rw [hxx]
· exact le_of_lt ((List.pairwise_cons.mp h).1 x hx)
/-- The greatest element of a nonempty ascending list is at or above every element. -/
theorem le_getLastD_of_pairwise {L : List Key} {x : Key} (h : L.Pairwise (· < ·)) (hx : x ∈ L) :
x ≤ L.getLastD ([] : Key) := by
have hne : L ≠ [] := by rintro rfl; exact absurd hx (by simp)
have hlast : x ≤ L.getLast hne := (h.imp (fun hab => le_of_lt hab)).rel_getLast hx
have : L.getLastD ([] : Key) = L.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne, Option.getD_some]
rw [this]; exact hlast
/-- The least element of a nonempty list is a member. -/
theorem headD_mem {L : List Key} (hne : L ≠ []) : L.headD ([] : Key) ∈ L := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne, Option.getD_some]
exact List.head_mem hne
/-- The greatest element of a nonempty list is a member. -/
theorem getLastD_mem {L : List Key} (hne : L ≠ []) : L.getLastD ([] : Key) ∈ L := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne, Option.getD_some]
exact List.getLast_mem hne
/-! ## The bridge -/
/-- The middle predicate: the stored keys in `[k₀, keyAfter kₙ)` are exactly `L`. -/
def midEq (L : List Key) (db : DB) : Prop :=
inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) = L
/-- The bracketing predicate: `k₀` is at or above `resolve begin` and `kₙ` strictly
below `resolve end`, so `k₀` is the least complete key and `kₙ` the greatest. -/
def bracket (r : RangeRead) (L : List Key) (db : DB) : Prop :=
resolve db r.begin ≤ (↑(L.headD ([] : Key)) : WithTop Key) ∧
(↑(L.getLastD ([] : Key)) : WithTop Key) < resolve db r.end_
/-- The full bridge predicate: both boundary reads are empty, the middle interval is `L`,
and `L`'s endpoints bracket the resolved window. -/
def bridge (r : RangeRead) (L : List Key) (db : DB) : Prop :=
completeKeys db (boundaryReadLo r (L.headD ([] : Key))) = [] ∧
completeKeys db (boundaryReadHi r (L.getLastD ([] : Key))) = [] ∧
midEq L db ∧ bracket r L db
/-- The bridge with its two end-emptiness conjuncts exchanged. Stating the swap once
keeps the upper-end factor-toggle arguments from re-elaborating the conjunction. -/
theorem bridge_swap {r : RangeRead} {L : List Key} {db : DB} :
bridge r L db ↔
(completeKeys db (boundaryReadHi r (L.getLastD ([] : Key))) = [] ∧
completeKeys db (boundaryReadLo r (L.headD ([] : Key))) = [] ∧
midEq L db ∧ bracket r L db) := by
unfold bridge
exact ⟨fun ⟨a, b, c, d⟩ => ⟨b, a, c, d⟩, fun ⟨a, b, c, d⟩ => ⟨b, a, c, d⟩⟩
/-- For a non-reversed read the complete keys are the in-range stored keys. -/
theorem completeKeys_of_not_reverse {db : DB} {r : RangeRead} (hrev : r.reverse = false) :
completeKeys db r = inRange db.keys (resolve db r.begin) (resolve db r.end_) := by
unfold completeKeys
rw [ite_eq_right (by simp [hrev])]
/-- The lower boundary read's complete keys are the in-range stored keys ending at
`resolve ⟨↑k, 1⟩`. -/
theorem completeKeys_boundaryReadLo {db : DB} {r : RangeRead} (hrev : r.reverse = false) (k : Key) :
completeKeys db (boundaryReadLo r k) =
inRange db.keys (resolve db r.begin) (resolve db (selAt (↑k : WithTop Key))) := by
unfold boundaryReadLo
rw [completeKeys_of_not_reverse (by simp [hrev])]
/-- The upper boundary read's complete keys are the in-range stored keys beginning at
`resolve ⟨keyAfter k, 1⟩`. -/
theorem completeKeys_boundaryReadHi {db : DB} {r : RangeRead} (hrev : r.reverse = false) (k : Key) :
completeKeys db (boundaryReadHi r k) =
inRange db.keys (resolve db (selAt (↑(keyAfter k) : WithTop Key))) (resolve db r.end_) := by
unfold boundaryReadHi
rw [completeKeys_of_not_reverse (by simp [hrev])]
/-- A read is empty exactly when its in-range stored keys are empty, regardless of
traversal: reversal preserves emptiness. -/
theorem completeKeys_eq_nil_iff_inRange {db : DB} (r : RangeRead) :
completeKeys db r = [] ↔ inRange db.keys (resolve db r.begin) (resolve db r.end_) = [] := by
unfold completeKeys
split <;> simp
/-- **The bridge equivalence for the ascending reading.** For a nonempty ascending
list `L`, the in-range stored keys equal `L` exactly when both boundary reads are empty,
the middle interval `[k₀, keyAfter kₙ)` is `L`, and the endpoints bracket the resolved
window. This is the traversal-independent core: `completeKeys` is this statement read
forward or reversed. -/
theorem inRange_eq_iff_bridge {db : DB} {r : RangeRead} {L : List Key}
(hL : L ≠ []) (hpair : L.Pairwise (· < ·)) :
inRange db.keys (resolve db r.begin) (resolve db r.end_) = L ↔ bridge r L db := by
have hlo_mem : L.headD ([] : Key) ∈ L := headD_mem hL
have hhi_mem : L.getLastD ([] : Key) ∈ L := getLastD_mem hL
have hLo_le_Hi : (↑(L.headD ([] : Key)) : WithTop Key) ≤
(↑(L.getLastD ([] : Key)) : WithTop Key) :=
WithTop.coe_le_coe.mpr (headD_le_of_pairwise hpair hhi_mem)
constructor
· intro hck
have hspec : ∀ {y : Key}, y ∈ L → y ∈ db.keys ∧
resolve db r.begin ≤ (↑y : WithTop Key) ∧
(↑y : WithTop Key) < resolve db r.end_ := by
intro y hy
have hy' : y ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) := by
rw [hck]; exact hy
exact inRange_mem_iff.mp hy'
have hbrack : bracket r L db :=
⟨(hspec hlo_mem).2.1, (hspec hhi_mem).2.2⟩
refine ⟨?_, ?_, ?_, hbrack⟩
· rw [completeKeys_eq_nil_iff_inRange, List.eq_nil_iff_forall_not_mem]
intro x hx
obtain ⟨hxdb, hlo, hhi⟩ := inRange_mem_iff.mp hx
simp only [boundaryReadLo] at hlo hhi
rw [resolve_selAt_self (hspec hlo_mem).1] at hhi
have hxL : x ∈ L := by
rw [← hck]
refine inRange_mem_iff.mpr ⟨hxdb, hlo, ?_⟩
exact lt_of_le_of_lt (le_trans (le_of_lt hhi) hLo_le_Hi) (hspec hhi_mem).2.2
exact absurd (headD_le_of_pairwise hpair hxL) (not_le.mpr (WithTop.coe_lt_coe.mp hhi))
· rw [completeKeys_eq_nil_iff_inRange, List.eq_nil_iff_forall_not_mem]
intro x hx
obtain ⟨hxdb, hlo, hhi⟩ := inRange_mem_iff.mp hx
have hxge : (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) ≤ (↑x : WithTop Key) :=
le_trans (coe_le_resolve_selAt db (keyAfter (L.getLastD ([] : Key)))) hlo
have hxgt : L.getLastD ([] : Key) < x :=
WithTop.coe_lt_coe.mp (lt_of_lt_of_le (WithTop.coe_lt_coe.mpr (keyAfter_self_lt _)) hxge)
have hlo' : resolve db r.begin ≤ (↑x : WithTop Key) :=
le_trans (hspec hlo_mem).2.1
(WithTop.coe_le_coe.mpr (le_trans (headD_le_of_pairwise hpair hhi_mem) (le_of_lt hxgt)))
have hxL : x ∈ L := by
rw [← hck]
exact inRange_mem_iff.mpr ⟨hxdb, hlo', hhi⟩
exact absurd (le_getLastD_of_pairwise hpair hxL) (not_le.mpr hxgt)
· unfold midEq
refine eq_of_mem_iff_pairwise (RangeRead.inRange_pairwise db _ _) hpair ?_
intro x
rw [inRange_mem_iff]
constructor
· rintro ⟨hxdb, hlo, hhi⟩
rw [← hck]
exact inRange_mem_iff.mpr ⟨hxdb, le_trans hbrack.1 hlo,
lt_of_lt_of_le hhi (keyAfter_le_of_lt hbrack.2)⟩
· intro hx
have hxsp := hspec hx
exact ⟨hxsp.1, WithTop.coe_le_coe.mpr (headD_le_of_pairwise hpair hx),
lt_of_le_of_lt (WithTop.coe_le_coe.mpr (le_getLastD_of_pairwise hpair hx))
(WithTop.coe_lt_coe.mpr (keyAfter_self_lt _))⟩
· rintro ⟨hlow, hhigh, hmid, hbrack⟩
rw [completeKeys_eq_nil_iff_inRange] at hlow
rw [completeKeys_eq_nil_iff_inRange] at hhigh
simp only [boundaryReadLo] at hlow
simp only [boundaryReadHi] at hhigh
have hLo_stored : L.headD ([] : Key) ∈ db.keys := by
have : L.headD ([] : Key) ∈ inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) := by rw [hmid]; exact hlo_mem
exact (inRange_mem_iff.mp this).1
have hHi_stored : L.getLastD ([] : Key) ∈ db.keys := by
have : L.getLastD ([] : Key) ∈ inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) := by rw [hmid]; exact hhi_mem
exact (inRange_mem_iff.mp this).1
refine eq_of_mem_iff_pairwise (RangeRead.inRange_pairwise db _ _) hpair ?_
intro x
rw [inRange_mem_iff]
constructor
· intro hx
obtain ⟨hxdb, hxlo, hxhi⟩ := hx
by_contra hxL
by_cases hlt : x < L.headD ([] : Key)
· have hmem : x ∈ inRange db.keys (resolve db r.begin)
(resolve db (selAt (↑(L.headD ([] : Key))))) := by
rw [inRange_mem_iff, resolve_selAt_self hLo_stored]
exact ⟨hxdb, hxlo, WithTop.coe_lt_coe.mpr hlt⟩
rw [hlow] at hmem; exact List.not_mem_nil hmem
· have hge : L.headD ([] : Key) ≤ x := le_of_not_gt hlt
by_cases hge2 : (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) ≤ (↑x : WithTop Key)
· have hmem : x ∈ inRange db.keys
(resolve db (selAt (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key)))
(resolve db r.end_) := by
rw [inRange_mem_iff]
exact ⟨hxdb, resolve_selAt_le_of_mem hxdb (WithTop.coe_le_coe.mp hge2), hxhi⟩
rw [hhigh] at hmem; exact List.not_mem_nil hmem
· have hxmid : x ∈ inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) := by
rw [inRange_mem_iff]
exact ⟨hxdb, WithTop.coe_le_coe.mpr hge, lt_of_not_ge hge2⟩
rw [hmid] at hxmid
exact hxL hxmid
· intro hx
have hxmid : x ∈ inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) := by rw [hmid]; exact hx
obtain ⟨hxdb, hxlo, hxhi⟩ := inRange_mem_iff.mp hxmid
exact ⟨hxdb, le_trans hbrack.1 hxlo,
lt_of_lt_of_le hxhi (keyAfter_le_of_lt hbrack.2)⟩
/-- **A non-reversed read's complete keys are its in-range stored keys.** -/
theorem completeKeys_eq_inRange {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = false) : completeKeys db r = L ↔
inRange db.keys (resolve db r.begin) (resolve db r.end_) = L := by
unfold completeKeys
rw [ite_eq_right (by simp [hrev])]
/-- **A reversed read's complete keys are the reverse of its in-range stored keys.**
The `↔` is reversed because `L` names the returned, descending list. -/
theorem completeKeys_eq_reverse_inRange {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = true) : completeKeys db r = L ↔
inRange db.keys (resolve db r.begin) (resolve db r.end_) = L.reverse := by
unfold completeKeys
rw [ite_eq_left (by simp [hrev]), List.reverse_eq_iff]
/-- **The bridge equivalence, non-reversed.** For a non-reversed read and a nonempty
ascending `L`, the complete keys equal `L` exactly when the bridge holds. -/
theorem completeKeys_eq_iff_bridge {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = false) (hL : L ≠ []) (hpair : L.Pairwise (· < ·)) :
completeKeys db r = L ↔ bridge r L db := by
rw [completeKeys_eq_inRange hrev]
exact inRange_eq_iff_bridge hL hpair
/-- **The bridge equivalence, reversed.** For a reversed read the returned list `L` is
descending, so the bridge is stated for `L.reverse`, the ascending reading of the same
window. -/
theorem completeKeys_eq_iff_bridge_rev {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = true) (hL : L ≠ []) (hpair : L.Pairwise (· > ·)) :
completeKeys db r = L ↔ bridge r L.reverse db := by
have hLr : L.reverse ≠ [] := by simpa using hL
have hpairr : L.reverse.Pairwise (· < ·) := by simpa using hpair.reverse
rw [completeKeys_eq_reverse_inRange hrev]
exact inRange_eq_iff_bridge hLr hpairr
/-- **Compatibility of a complete result factors as its bridge.** For a non-reversed
read, a nonempty ascending list `L` within the limit, compatibility with the
complete result `⟨L, false⟩` is equivalent to the bridge predicate. -/
theorem compatible_complete_iff_bridge {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = false) (hL : L ≠ []) (hpair : L.Pairwise (· < ·))
(hlim : withinLimit r L) :
RangeRead.Compatible db r { keys := L, more := false } ↔ bridge r L db := by
unfold RangeRead.Compatible
rw [show ({ keys := L, more := false } : Result).more = false from rfl,
show ({ keys := L, more := false } : Result).keys = L from rfl]
constructor
· rintro ⟨-, h | ⟨-, heq⟩⟩
· exact absurd h (by simp)
· exact (completeKeys_eq_iff_bridge hrev hL hpair).mp heq.symm
· intro hb
exact ⟨hlim, Or.inr ⟨rfl, ((completeKeys_eq_iff_bridge hrev hL hpair).mpr hb).symm⟩⟩
/-- **Compatibility of a reversed complete result factors as its bridge.** The
reported list `L` is descending; the bridge is stated for `L.reverse`. -/
theorem compatible_complete_iff_bridge_rev {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = true) (hL : L ≠ []) (hpair : L.Pairwise (· > ·))
(hlim : withinLimit r L) :
RangeRead.Compatible db r { keys := L, more := false } ↔ bridge r L.reverse db := by
unfold RangeRead.Compatible
rw [show ({ keys := L, more := false } : Result).more = false from rfl,
show ({ keys := L, more := false } : Result).keys = L from rfl]
constructor
· rintro ⟨-, h | ⟨-, heq⟩⟩
· exact absurd h (by simp)
· exact (completeKeys_eq_iff_bridge_rev hrev hL hpair).mp heq.symm
· intro hb
exact ⟨hlim, Or.inr ⟨rfl, ((completeKeys_eq_iff_bridge_rev hrev hL hpair).mpr hb).symm⟩⟩
/-!
## Truncated results
A truncated result reports only one end of the window: a non-reversed read reports an
ascending prefix of the in-range keys, a reversed read reports a descending prefix
(an ascending suffix read backwards). The bridge accordingly drops the boundary read on
the *unreported* side — the upper end for a non-reversed read, the lower end for a
reversed one — and keeps the middle equality and the bracketing.
-/
/-- Splitting an interval at an intermediate bound: the in-range keys of `[a, c)` are
those of `[a, b)` followed by those of `[b, c)`. -/
theorem inRange_append_range (db : DB) {a b c : WithTop Key} (hab : a ≤ b) (hbc : b ≤ c) :
inRange db.keys a c = inRange db.keys a b ++ inRange db.keys b c := by
apply eq_of_mem_iff_pairwise
· exact RangeRead.inRange_pairwise db a c
· refine (List.pairwise_append).mpr ⟨RangeRead.inRange_pairwise db a b,
RangeRead.inRange_pairwise db b c, ?_⟩
intro x hx y hy
rw [inRange_mem_iff] at hx hy
exact WithTop.coe_lt_coe.mp (lt_of_lt_of_le hx.2.2 hy.2.1)
· intro x
rw [inRange_mem_iff, List.mem_append, inRange_mem_iff, inRange_mem_iff]
constructor
· rintro ⟨hx, hax, hxc⟩
rcases lt_or_ge (x : WithTop Key) b with h | h
· exact Or.inl ⟨hx, hax, h⟩
· exact Or.inr ⟨hx, h, hxc⟩
· rintro (⟨hx, hax, hxb⟩ | ⟨hx, hbx, hxc⟩)
· exact ⟨hx, hax, lt_of_lt_of_le hxb hbc⟩
· exact ⟨hx, le_trans hab hbx, hxc⟩
/-- A list is a prefix of the reverse of `l` exactly when its reverse is a suffix of
`l`. -/
theorem prefix_reverse_iff_suffix {l₁ l₂ : List Key} :
l₁ <+: l₂.reverse ↔ l₁.reverse <:+ l₂ := by
simpa using (List.reverse_suffix (l₁ := l₁) (l₂ := l₂.reverse)).symm
/-- The forward truncated bridge: the lower boundary read is empty, the middle interval is
`L`, and `L` is bracketed in the window. The upper boundary read is dropped — the reported
keys are a prefix, so nothing above the last reported key is constrained. -/
def bridgeFwdTrunc (r : RangeRead) (L : List Key) (db : DB) : Prop :=
completeKeys db (boundaryReadLo r (L.headD ([] : Key))) = [] ∧ midEq L db ∧ bracket r L db
/-- The reverse truncated bridge: the upper boundary read is empty, the middle interval is
`L`, and `L` is bracketed in the window. The lower boundary read is dropped — the reported
keys are a suffix, so nothing below the least reported key is constrained. -/
def bridgeRevTrunc (r : RangeRead) (L : List Key) (db : DB) : Prop :=
completeKeys db (boundaryReadHi r (L.getLastD ([] : Key))) = [] ∧ midEq L db ∧ bracket r L db
/-- **Forward truncation is a prefix.** For a nonempty ascending `L`, `L` is a prefix
of the in-range keys exactly when the forward truncated bridge holds. -/
theorem prefix_inRange_iff_bridgeFwdTrunc {db : DB} {r : RangeRead} {L : List Key}
(hL : L ≠ []) (hpair : L.Pairwise (· < ·)) :
L <+: inRange db.keys (resolve db r.begin) (resolve db r.end_) ↔
bridgeFwdTrunc r L db := by
have hlo_mem : L.headD ([] : Key) ∈ L := headD_mem hL
have hhi_mem : L.getLastD ([] : Key) ∈ L := getLastD_mem hL
have hW : (inRange db.keys (resolve db r.begin) (resolve db r.end_)).Pairwise (· < ·) :=
RangeRead.inRange_pairwise db _ _
have hlo_le_hi : L.headD ([] : Key) ≤ L.getLastD ([] : Key) :=
headD_le_of_pairwise hpair hhi_mem
constructor
· intro hpre
obtain ⟨rest, hrest⟩ := hpre
have hW' : (L ++ rest).Pairwise (· < ·) := by rw [hrest]; exact hW
obtain ⟨-, -, hcross⟩ := List.pairwise_append.mp hW'
have hinL : ∀ {x : Key}, x ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) →
x ∈ L ∨ x ∈ rest := by
intro x hx; rw [← hrest] at hx; exact List.mem_append.mp hx
have hknW : L.getLastD ([] : Key) ∈
inRange db.keys (resolve db r.begin) (resolve db r.end_) := by
rw [← hrest]; exact List.mem_append.mpr (Or.inl hhi_mem)
have hkoW : L.headD ([] : Key) ∈
inRange db.keys (resolve db r.begin) (resolve db r.end_) := by
rw [← hrest]; exact List.mem_append.mpr (Or.inl hlo_mem)
have hknE : (↑(L.getLastD ([] : Key)) : WithTop Key) < resolve db r.end_ :=
(inRange_mem_iff.mp hknW).2.2
have hBko : resolve db r.begin ≤ (↑(L.headD ([] : Key)) : WithTop Key) :=
(inRange_mem_iff.mp hkoW).2.1
have hkostore : L.headD ([] : Key) ∈ db.keys := (inRange_mem_iff.mp hkoW).1
have hlow : completeKeys db (boundaryReadLo r (L.headD ([] : Key))) = [] := by
rw [completeKeys_eq_nil_iff_inRange]
simp only [boundaryReadLo, resolve_selAt_self hkostore]
rw [List.eq_nil_iff_forall_not_mem]
intro x hx
obtain ⟨hxdb, hBx, hxko⟩ := inRange_mem_iff.mp hx
have hxltE : (↑x : WithTop Key) < resolve db r.end_ :=
lt_of_lt_of_le hxko (le_trans (WithTop.coe_le_coe.mpr hlo_le_hi) (le_of_lt hknE))
have hxW : x ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) :=
inRange_mem_iff.mpr ⟨hxdb, hBx, hxltE⟩
rcases hinL hxW with hxL | hxr
· exact absurd (headD_le_of_pairwise hpair hxL) (not_le.mpr (WithTop.coe_lt_coe.mp hxko))
· exact absurd (hcross (L.headD ([] : Key)) hlo_mem x hxr)
(not_lt.mpr (le_of_lt (WithTop.coe_lt_coe.mp hxko)))
have hmid : midEq L db := by
unfold midEq
apply eq_of_mem_iff_pairwise (RangeRead.inRange_pairwise db _ _) hpair
intro x
rw [inRange_mem_iff]
constructor
· rintro ⟨hxdb, hkx, hxkA⟩
have hxle : x ≤ L.getLastD ([] : Key) :=
(lt_keyAfter_iff x (L.getLastD ([] : Key))).mp (WithTop.coe_lt_coe.mp hxkA)
have hxW : x ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) :=
inRange_mem_iff.mpr ⟨hxdb, le_trans hBko hkx,
lt_of_le_of_lt (WithTop.coe_le_coe.mpr hxle) hknE⟩
rcases hinL hxW with hxL | hxr
· exact hxL
· exact absurd (hcross (L.getLastD ([] : Key)) hhi_mem x hxr) (not_lt.mpr hxle)
· intro hx
exact ⟨(inRange_mem_iff.mp (by rw [← hrest]; exact List.mem_append.mpr (Or.inl hx))).1,
WithTop.coe_le_coe.mpr (headD_le_of_pairwise hpair hx),
WithTop.coe_lt_coe.mpr
(lt_of_le_of_lt (le_getLastD_of_pairwise hpair hx) (keyAfter_self_lt _))⟩
exact ⟨hlow, hmid, hBko, hknE⟩
· rintro ⟨hlow, hmid, hbrack⟩
rw [completeKeys_eq_nil_iff_inRange] at hlow
simp only [boundaryReadLo] at hlow
have hko_mid : L.headD ([] : Key) ∈ inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) := by
rw [hmid]; exact hlo_mem
have hkostore : L.headD ([] : Key) ∈ db.keys := (inRange_mem_iff.mp hko_mid).1
rw [resolve_selAt_self hkostore] at hlow
have hko_ka : (↑(L.headD ([] : Key)) : WithTop Key) ≤
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) :=
WithTop.coe_le_coe.mpr (le_of_lt (lt_of_le_of_lt hlo_le_hi (keyAfter_self_lt _)))
have h1 : inRange db.keys (resolve db r.begin) (resolve db r.end_) =
inRange db.keys (resolve db r.begin) (↑(L.headD ([] : Key)) : WithTop Key) ++
inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key) (resolve db r.end_) :=
inRange_append_range db hbrack.1 (le_trans hko_ka (keyAfter_le_of_lt hbrack.2))
have h2 : inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key) (resolve db r.end_) =
inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) ++
inRange db.keys (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key)
(resolve db r.end_) :=
inRange_append_range db hko_ka (keyAfter_le_of_lt hbrack.2)
rw [h1, h2, hlow, List.nil_append, hmid]
exact List.prefix_append _ _
/-- **Reverse truncation is a suffix.** For a nonempty ascending `L`, `L` is a suffix
of the in-range keys exactly when the reverse truncated bridge holds. -/
theorem suffix_inRange_iff_bridgeRevTrunc {db : DB} {r : RangeRead} {L : List Key}
(hL : L ≠ []) (hpair : L.Pairwise (· < ·)) :
L <:+ inRange db.keys (resolve db r.begin) (resolve db r.end_) ↔
bridgeRevTrunc r L db := by
have hlo_mem : L.headD ([] : Key) ∈ L := headD_mem hL
have hhi_mem : L.getLastD ([] : Key) ∈ L := getLastD_mem hL
have hW : (inRange db.keys (resolve db r.begin) (resolve db r.end_)).Pairwise (· < ·) :=
RangeRead.inRange_pairwise db _ _
have hlo_le_hi : L.headD ([] : Key) ≤ L.getLastD ([] : Key) :=
headD_le_of_pairwise hpair hhi_mem
constructor
· intro hsuf
obtain ⟨rest, hrest⟩ := hsuf
have hW' : (rest ++ L).Pairwise (· < ·) := by rw [hrest]; exact hW
obtain ⟨-, -, hcross⟩ := List.pairwise_append.mp hW'
have hinL : ∀ {x : Key}, x ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) →
x ∈ rest ∨ x ∈ L := by
intro x hx; rw [← hrest] at hx; exact List.mem_append.mp hx
have hkoW : L.headD ([] : Key) ∈
inRange db.keys (resolve db r.begin) (resolve db r.end_) := by
rw [← hrest]; exact List.mem_append.mpr (Or.inr hlo_mem)
have hknW : L.getLastD ([] : Key) ∈
inRange db.keys (resolve db r.begin) (resolve db r.end_) := by
rw [← hrest]; exact List.mem_append.mpr (Or.inr hhi_mem)
have hBko : resolve db r.begin ≤ (↑(L.headD ([] : Key)) : WithTop Key) :=
(inRange_mem_iff.mp hkoW).2.1
have hknE : (↑(L.getLastD ([] : Key)) : WithTop Key) < resolve db r.end_ :=
(inRange_mem_iff.mp hknW).2.2
have hknstore : L.getLastD ([] : Key) ∈ db.keys := (inRange_mem_iff.mp hknW).1
have hhigh : completeKeys db (boundaryReadHi r (L.getLastD ([] : Key))) = [] := by
rw [completeKeys_eq_nil_iff_inRange]
simp only [boundaryReadHi]
rw [List.eq_nil_iff_forall_not_mem]
intro x hx
obtain ⟨hxdb, hkaX, hxE⟩ := inRange_mem_iff.mp hx
have hxgt : L.getLastD ([] : Key) < x :=
WithTop.coe_lt_coe.mp (lt_of_lt_of_le (WithTop.coe_lt_coe.mpr (keyAfter_self_lt _))
(le_trans (coe_le_resolve_selAt db (keyAfter (L.getLastD ([] : Key)))) hkaX))
have hxW : x ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) :=
inRange_mem_iff.mpr ⟨hxdb, le_trans hBko
(WithTop.coe_le_coe.mpr (le_trans hlo_le_hi (le_of_lt hxgt))), hxE⟩
rcases hinL hxW with hxr | hxL
· exact absurd (hcross x hxr (L.getLastD ([] : Key)) hhi_mem) (not_lt.mpr (le_of_lt hxgt))
· exact absurd (le_getLastD_of_pairwise hpair hxL) (not_le.mpr hxgt)
have hmid : midEq L db := by
unfold midEq
apply eq_of_mem_iff_pairwise (RangeRead.inRange_pairwise db _ _) hpair
intro x
rw [inRange_mem_iff]
constructor
· rintro ⟨hxdb, hkx, hxkA⟩
have hxle : x ≤ L.getLastD ([] : Key) :=
(lt_keyAfter_iff x (L.getLastD ([] : Key))).mp (WithTop.coe_lt_coe.mp hxkA)
have hxW : x ∈ inRange db.keys (resolve db r.begin) (resolve db r.end_) :=
inRange_mem_iff.mpr ⟨hxdb, le_trans hBko hkx,
lt_of_le_of_lt (WithTop.coe_le_coe.mpr hxle) hknE⟩
rcases hinL hxW with hxr | hxL
· exact absurd (WithTop.coe_lt_coe.mpr (hcross x hxr (L.headD ([] : Key)) hlo_mem))
(not_lt.mpr hkx)
· exact hxL
· intro hx
exact ⟨(inRange_mem_iff.mp (by rw [← hrest]; exact List.mem_append.mpr (Or.inr hx))).1,
WithTop.coe_le_coe.mpr (headD_le_of_pairwise hpair hx),
WithTop.coe_lt_coe.mpr
(lt_of_le_of_lt (le_getLastD_of_pairwise hpair hx) (keyAfter_self_lt _))⟩
exact ⟨hhigh, hmid, hBko, hknE⟩
· rintro ⟨hhigh, hmid, hbrack⟩
rw [completeKeys_eq_nil_iff_inRange] at hhigh
simp only [boundaryReadHi] at hhigh
have hEmpty : inRange db.keys (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key)
(resolve db r.end_) = [] := by
rw [List.eq_nil_iff_forall_not_mem]
intro x hx
obtain ⟨hxdb, hkax, hxE⟩ := inRange_mem_iff.mp hx
have hxH : x ∈ inRange db.keys
(resolve db (selAt (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key)))
(resolve db r.end_) :=
inRange_mem_iff.mpr ⟨hxdb,
resolve_selAt_le_of_mem hxdb (WithTop.coe_le_coe.mp hkax), hxE⟩
rw [hhigh] at hxH
exact List.not_mem_nil hxH
have h1 : inRange db.keys (resolve db r.begin) (resolve db r.end_) =
inRange db.keys (resolve db r.begin) (↑(L.headD ([] : Key)) : WithTop Key) ++
inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key) (resolve db r.end_) :=
inRange_append_range db hbrack.1
(le_trans (WithTop.coe_le_coe.mpr hlo_le_hi) (le_of_lt hbrack.2))
have h2 : inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key) (resolve db r.end_) =
inRange db.keys (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) ++
inRange db.keys (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key)
(resolve db r.end_) :=
inRange_append_range db
(WithTop.coe_le_coe.mpr (le_of_lt (lt_of_le_of_lt hlo_le_hi (keyAfter_self_lt _))))
(keyAfter_le_of_lt hbrack.2)
have hR : inRange db.keys (resolve db r.begin) (resolve db r.end_) =
inRange db.keys (resolve db r.begin) (↑(L.headD ([] : Key)) : WithTop Key) ++ L := by
rw [h1, h2, hEmpty, hmid, List.append_nil]
exact ⟨_, hR.symm⟩
/-- **Compatibility of a forward truncated result factors as its bridge.** A
non-reversed result reporting `more` has an ascending prefix `L`; compatibility is the
forward truncated bridge. -/
theorem compatible_fwdTrunc_iff_bridgeFwdTrunc {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = false) (hL : L ≠ []) (hpair : L.Pairwise (· < ·))
(hlim : withinLimit r L) :
RangeRead.Compatible db r { keys := L, more := true } ↔ bridgeFwdTrunc r L db := by
unfold RangeRead.Compatible
rw [show ({ keys := L, more := true } : Result).more = true from rfl,
show ({ keys := L, more := true } : Result).keys = L from rfl,
completeKeys_of_not_reverse hrev]
constructor
· rintro ⟨-, h | ⟨hm, _⟩⟩
· exact (prefix_inRange_iff_bridgeFwdTrunc hL hpair).mp h.2.1
· exact absurd hm (by simp)
· intro hb
exact ⟨hlim, Or.inl ⟨rfl, (prefix_inRange_iff_bridgeFwdTrunc hL hpair).mpr hb, hL⟩⟩
/-- **Compatibility of a reverse truncated result factors as its bridge.** A reversed
result reporting `more` has a descending prefix `L`, i.e. `L.reverse` is an ascending
suffix; compatibility is the reverse truncated bridge for `L.reverse`. -/
theorem compatible_revTrunc_iff_bridgeRevTrunc {db : DB} {r : RangeRead} {L : List Key}
(hrev : r.reverse = true) (hL : L ≠ []) (hpair : L.Pairwise (· > ·))
(hlim : withinLimit r L) :
RangeRead.Compatible db r { keys := L, more := true } ↔
bridgeRevTrunc r L.reverse db := by
have hLr : L.reverse ≠ [] := by simpa using hL
have hpairr : L.reverse.Pairwise (· < ·) := by simpa using hpair.reverse
have hck : completeKeys db r =
(inRange db.keys (resolve db r.begin) (resolve db r.end_)).reverse := by
unfold completeKeys
rw [ite_eq_left (by simp [hrev])]
unfold RangeRead.Compatible
rw [show ({ keys := L, more := true } : Result).more = true from rfl,
show ({ keys := L, more := true } : Result).keys = L from rfl, hck]
constructor
· rintro ⟨-, h | ⟨hm, _⟩⟩
· have hM : L.reverse <:+ inRange db.keys (resolve db r.begin) (resolve db r.end_) :=
prefix_reverse_iff_suffix.mp h.2.1
exact (suffix_inRange_iff_bridgeRevTrunc hLr hpairr).mp hM
· exact absurd hm (by simp)
· intro hb
have hM : L.reverse <:+ inRange db.keys (resolve db r.begin) (resolve db r.end_) :=
(suffix_inRange_iff_bridgeRevTrunc hLr hpairr).mpr hb
have hpre : L <+: (inRange db.keys (resolve db r.begin) (resolve db r.end_)).reverse :=
prefix_reverse_iff_suffix.mpr hM
exact ⟨hlim, Or.inl ⟨rfl, hpre, hL⟩⟩
/-- The reported keys in the order the read returns them, from the ascending list `A`:
reversed when the read traverses in reverse. -/
def reportedList (r : RangeRead) (A : List Key) : List Key :=
if r.reverse then A.reverse else A
/-- The general bridge: the complete bridge for an untruncated result, and the
unreported-end bridge for a truncated one. -/
def bridgeOf (r : RangeRead) (A : List Key) (more : Bool) (db : DB) : Prop :=
match more with
| false => bridge r A db
| true => if r.reverse then bridgeRevTrunc r A db else bridgeFwdTrunc r A db
/-- **The reduction in full generality.** For a nonempty ascending list `A` (the
reported keys in ascending order), compatibility of the general result — either
truncation flag, either traversal — factors as the limit and the general bridge. The
bridge's factors name the empty boundary read on the reported side (lower for a
non-reversed read, upper for a reversed one), the middle interval equality, and the
bracketing; a truncated result drops the boundary read on the unreported side. -/
theorem compatible_iff_bridge_general {db : DB} {r : RangeRead} {A : List Key} {more : Bool}
(hA : A ≠ []) (hpair : A.Pairwise (· < ·))
(hlim : withinLimit r (reportedList r A)) :
RangeRead.Compatible db r { keys := reportedList r A, more := more } ↔
withinLimit r (reportedList r A) ∧ bridgeOf r A more db := by
have hp : A.reverse.Pairwise (· > ·) := by simpa using hpair.reverse
have hAr : A.reverse ≠ [] := by simpa using hA
unfold bridgeOf
cases more with
| false =>
cases hr : r.reverse with
| false =>
simp only [reportedList, hr, Bool.false_eq_true, ↓reduceIte] at hlim ⊢
rw [compatible_complete_iff_bridge hr hA hpair hlim]; tauto
| true =>
simp only [reportedList, hr, ↓reduceIte] at hlim ⊢
rw [compatible_complete_iff_bridge_rev hr hAr hp hlim, List.reverse_reverse]; tauto
| true =>
cases hr : r.reverse with
| false =>
simp only [reportedList, hr, Bool.false_eq_true, ↓reduceIte] at hlim ⊢
rw [compatible_fwdTrunc_iff_bridgeFwdTrunc hr hA hpair hlim]; tauto
| true =>
simp only [reportedList, hr, ↓reduceIte] at hlim ⊢
rw [compatible_revTrunc_iff_bridgeRevTrunc hr hAr hp hlim, List.reverse_reverse]; tauto
/-!
## The factor-toggle lemma
The necessity half of the reduction never cites an end theorem directly: it needs
only one full-compatible witness `db₀` and a single-key perturbation that breaks
the targeted factor. The generic statement below is the factor-toggle lemma: a sound
range can omit a key `k` only if flipping `k`'s membership in a compatible
database preserves compatibility. Since the flip is outside the range, soundness
forces compatibility on the flipped database; if that fails, `k` is necessary.
-/
/-- Flip the membership of `k` in `db`: erase it when present, insert it otherwise. -/
def toggle (db : DB) (k : Key) : DB :=
if hk : k ∈ db.keys then db.erase k else db.insert k hk
/-- Flipping a key outside a range leaves the range's stored keys unchanged. -/
theorem keys_toggle_of_not_mem (cr : ConflictRange) (db : DB) {k : Key} (hk : k ∉ cr) :
cr.keys (toggle db k) = cr.keys db := by
unfold toggle
by_cases hmem : k ∈ db.keys
· rw [dite_eq_left hmem]; exact ConflictRange.keys_erase_of_not_mem cr db hk
· rw [dite_eq_right hmem]; exact ConflictRange.keys_insert_of_not_mem cr db hmem hk
/-- Flipping a key outside a range leaves the two databases agreeing on the range. -/
theorem agreeOn_toggle_of_not_mem (cr : ConflictRange) (db : DB) {k : Key} (hk : k ∉ cr) :
AgreeOn cr db (toggle db k) :=
(keys_toggle_of_not_mem cr db hk).symm
/-- **Factor-toggle.** If some database is compatible with `(r, res)` but
flipping the membership of `k` there breaks compatibility, then `k` is necessary:
any sound range omitting `k` would see both databases as agreeing, so soundness
would transfer the compatibility, contradicting the break. -/
theorem necessary_of_toggle {r : RangeRead} {res : Result} {k : Key}
(h : ∃ db₀ : DB, RangeRead.Compatible db₀ r res ∧
¬ RangeRead.Compatible (toggle db₀ k) r res) :
Necessary r res k := by
obtain ⟨db₀, hc₀, hc₁⟩ := h
intro cr hs
by_contra hkcr
exact hc₁ ((hs db₀ (toggle db₀ k) (agreeOn_toggle_of_not_mem cr db₀ hkcr)).mp hc₀)
/-- **The factor-toggle lemma.** Suppose compatibility factors as `φ₁ ∧ φ₂` on
databases, some database `db₀` satisfies both factors, and flipping the membership
of `k` in `db₀` breaks `φ₁`. Then no range omitting `k` is sound: such a range sees
`db₀` and its flip as agreeing, so soundness would carry `φ₁`. This is the
factor-toggle lemma in factored form, and it is the form the necessity
constructions use — only the one targeted factor must break. -/
theorem not_sound_of_factor_toggle {r : RangeRead} {res : Result} {cr : ConflictRange}
{φ₁ φ₂ : DB → Prop} {db₀ : DB} {k : Key}
(hcomp : ∀ db, RangeRead.Compatible db r res ↔ (φ₁ db ∧ φ₂ db))
(h₁ : φ₁ db₀) (h₂ : φ₂ db₀) (hnot : ¬ φ₁ (toggle db₀ k)) (hk : k ∉ cr) :
¬ Sound r res cr := by
intro hs
have hc₀ : RangeRead.Compatible db₀ r res := (hcomp db₀).mpr ⟨h₁, h₂⟩
have hc₁ : RangeRead.Compatible (toggle db₀ k) r res :=
(hs db₀ (toggle db₀ k) (agreeOn_toggle_of_not_mem cr db₀ hk)).mp hc₀
exact hnot ((hcomp (toggle db₀ k)).mp hc₁).1
/-- **Factor-toggle necessity.** Under the factorization above, a single
database whose flip breaks one factor makes `k` necessary. -/
theorem necessary_of_factor_toggle {r : RangeRead} {res : Result} {k : Key}
{φ₁ φ₂ : DB → Prop} {db₀ : DB}
(hcomp : ∀ db, RangeRead.Compatible db r res ↔ (φ₁ db ∧ φ₂ db))
(h₁ : φ₁ db₀) (h₂ : φ₂ db₀) (hnot : ¬ φ₁ (toggle db₀ k)) :
Necessary r res k :=
fun cr hs => by
by_contra hkcr
exact not_sound_of_factor_toggle hcomp h₁ h₂ hnot hkcr hs
/-!
## The joint base construction
The necessity argument does not transfer soundness from the end pair; it
exhibits a single database `db₀` that is compatible with the *full* result and whose
flip at `k` breaks the targeted end factor. That object is named here: a *lower joint
base* for `k` is a full-compatible database whose flip makes the lower boundary read
nonempty, and similarly for the upper end. The transfer to `Necessary r res k` is
`necessary_of_factor_toggle`, with the bridge's four factors supplying the
factorization.
-/
/-- A **lower joint base** for `k`: a database compatible with the full complete
result `⟨L, false⟩` (via the bridge) whose flip at `k` makes the lower boundary read
nonempty, i.e. breaks the lower factor. This is the joint-base witness that turns the
empty lower certificate into `Necessary r res k`. -/
def LowerJointBase (r : RangeRead) (L : List Key) (k : Key) : Prop :=
∃ db₀ : DB, bridge r L db₀ ∧
completeKeys (toggle db₀ k) (boundaryReadLo r (L.headD ([] : Key))) ≠ []
/-- An **upper joint base** for `k`: a database compatible with the full complete
result `⟨L, false⟩` whose flip at `k` makes the upper boundary read nonempty. -/
def UpperJointBase (r : RangeRead) (L : List Key) (k : Key) : Prop :=
∃ db₀ : DB, bridge r L db₀ ∧
completeKeys (toggle db₀ k) (boundaryReadHi r (L.getLastD ([] : Key))) ≠ []
/-- **Lower joint base gives necessity.** A lower joint base for `k` makes `k`
necessary for the full pair, by factor-toggle against the full result's bridge. -/
theorem necessary_of_lowerJointBase {r : RangeRead} {res : Result} {L : List Key}
{k : Key} (hrev : r.reverse = false) (hL : L ≠ []) (hpair : L.Pairwise (· < ·))
(hlim : withinLimit r L) (hres : res = { keys := L, more := false })
(h : LowerJointBase r L k) : Necessary r res k := by
have hcomp : ∀ db, RangeRead.Compatible db r res ↔
(completeKeys db (boundaryReadLo r (L.headD ([] : Key))) = [] ∧
(completeKeys db (boundaryReadHi r (L.getLastD ([] : Key))) = [] ∧
midEq L db ∧ bracket r L db)) := by
intro db
rw [hres, compatible_complete_iff_bridge hrev hL hpair hlim]
unfold bridge
tauto
obtain ⟨db₀, hb, hflip⟩ := h
exact necessary_of_factor_toggle hcomp hb.1 hb.2 hflip
/-- **Upper joint base gives necessity.** An upper joint base for `k` makes `k`
necessary for the full pair, by factor-toggle with the upper end factor first. -/
theorem necessary_of_upperJointBase {r : RangeRead} {res : Result} {L : List Key}
{k : Key} (hrev : r.reverse = false) (hL : L ≠ []) (hpair : L.Pairwise (· < ·))
(hlim : withinLimit r L) (hres : res = { keys := L, more := false })
(h : UpperJointBase r L k) : Necessary r res k := by
have hcomp : ∀ db, RangeRead.Compatible db r res ↔
(completeKeys db (boundaryReadHi r (L.getLastD ([] : Key))) = [] ∧
(completeKeys db (boundaryReadLo r (L.headD ([] : Key))) = [] ∧
midEq L db ∧ bracket r L db)) := by
intro db
rw [hres, compatible_complete_iff_bridge hrev hL hpair hlim]
unfold bridge
tauto
obtain ⟨db₀, hb, hflip⟩ := h
exact necessary_of_factor_toggle hcomp hb.2.1 ⟨hb.1, hb.2.2⟩ hflip
/-- A lower joint base for every key of `[a, b)`. -/
def LowerJointBaseRange (r : RangeRead) (L : List Key) (a b : WithTop Key) : Prop :=
∀ k : Key, a ≤ (↑k : WithTop Key) → (↑k : WithTop Key) < b → LowerJointBase r L k
/-- An upper joint base for every key of `[a, b)`. -/
def UpperJointBaseRange (r : RangeRead) (L : List Key) (a b : WithTop Key) : Prop :=
∀ k : Key, a ≤ (↑k : WithTop Key) → (↑k : WithTop Key) < b → UpperJointBase r L k
/-- The lower joint bases on `[a, b)` make that whole interval necessary. -/
theorem necessaryRange_of_lowerJointBaseRange {r : RangeRead} {res : Result}
{L : List Key} {a b : WithTop Key} (hrev : r.reverse = false) (hL : L ≠ [])
(hpair : L.Pairwise (· < ·)) (hlim : withinLimit r L)
(hres : res = { keys := L, more := false }) (h : LowerJointBaseRange r L a b) :
NecessaryRange r res a b :=
fun k hklo hkhi => necessary_of_lowerJointBase hrev hL hpair hlim hres (h k hklo hkhi)
/-- The upper joint bases on `[a, b)` make that whole interval necessary. -/
theorem necessaryRange_of_upperJointBaseRange {r : RangeRead} {res : Result}
{L : List Key} {a b : WithTop Key} (hrev : r.reverse = false) (hL : L ≠ [])
(hpair : L.Pairwise (· < ·)) (hlim : withinLimit r L)
(hres : res = { keys := L, more := false }) (h : UpperJointBaseRange r L a b) :
NecessaryRange r res a b :=
fun k hklo hkhi => necessary_of_upperJointBase hrev hL hpair hlim hres (h k hklo hkhi)
/-!
## Joint bases for a reversed read
For a reversed read the bridge is stated on the ascending reading `L.reverse`, so the
boundary reads attach to `L`'s last and head keys rather than its head and last. These
are the reversal-symmetric twins of `LowerJointBase` / `UpperJointBase`, and they let the
reduction consume the empty theory's witnesses in either traversal order.
-/
/-- A **lower joint base for a reversed read**: a database satisfying the ascending
bridge of the reversed reading `L.reverse` whose flip at `k` makes the lower boundary
read `[resolve begin, k₀)` nonempty. The endpoint used is the bridge's own least key
`L.reverse.headD`, which is `L`'s last key. -/
def LowerJointBaseRev (r : RangeRead) (L : List Key) (k : Key) : Prop :=
∃ db₀ : DB, bridge r L.reverse db₀ ∧
completeKeys (toggle db₀ k) (boundaryReadLo r (L.reverse.headD ([] : Key))) ≠ []
/-- An **upper joint base for a reversed read**: a database satisfying the ascending
bridge of `L.reverse` whose flip at `k` makes the upper boundary read nonempty. -/
def UpperJointBaseRev (r : RangeRead) (L : List Key) (k : Key) : Prop :=
∃ db₀ : DB, bridge r L.reverse db₀ ∧
completeKeys (toggle db₀ k) (boundaryReadHi r (L.reverse.getLastD ([] : Key))) ≠ []
/-- A lower joint base for a reversed read, for every key of `[a, b)`. -/
def LowerJointBaseRangeRev (r : RangeRead) (L : List Key) (a b : WithTop Key) : Prop :=
∀ k : Key, a ≤ (↑k : WithTop Key) → (↑k : WithTop Key) < b → LowerJointBaseRev r L k
/-- An upper joint base for a reversed read, for every key of `[a, b)`. -/
def UpperJointBaseRangeRev (r : RangeRead) (L : List Key) (a b : WithTop Key) : Prop :=
∀ k : Key, a ≤ (↑k : WithTop Key) → (↑k : WithTop Key) < b → UpperJointBaseRev r L k
/-- **Lower joint base gives necessity, reversed.** A lower joint base for `k` makes `k`
necessary for the full pair, by factor-toggle against the reversed bridge. -/
theorem necessary_of_lowerJointBaseRev {r : RangeRead} {res : Result} {L : List Key}
{k : Key} (hrev : r.reverse = true) (hL : L ≠ []) (hpair : L.Pairwise (· > ·))
(hlim : withinLimit r L) (hres : res = { keys := L, more := false })
(h : LowerJointBaseRev r L k) : Necessary r res k := by
have hcomp : ∀ db, RangeRead.Compatible db r res ↔
(completeKeys db (boundaryReadLo r (L.reverse.headD ([] : Key))) = [] ∧
(completeKeys db (boundaryReadHi r (L.reverse.getLastD ([] : Key))) = [] ∧
midEq L.reverse db ∧ bracket r L.reverse db)) := by
intro db
rw [hres, compatible_complete_iff_bridge_rev hrev hL hpair hlim]
rfl
obtain ⟨db₀, hb, hflip⟩ := h
exact necessary_of_factor_toggle hcomp hb.1 hb.2 hflip
/-- **Upper joint base gives necessity, reversed.** -/
theorem necessary_of_upperJointBaseRev {r : RangeRead} {res : Result} {L : List Key}
{k : Key} (hrev : r.reverse = true) (hL : L ≠ []) (hpair : L.Pairwise (· > ·))
(hlim : withinLimit r L) (hres : res = { keys := L, more := false })
(h : UpperJointBaseRev r L k) : Necessary r res k := by
have hcomp : ∀ db, RangeRead.Compatible db r res ↔
(completeKeys db (boundaryReadHi r (L.reverse.getLastD ([] : Key))) = [] ∧
(completeKeys db (boundaryReadLo r (L.reverse.headD ([] : Key))) = [] ∧
midEq L.reverse db ∧ bracket r L.reverse db)) := by
intro db
rw [hres, compatible_complete_iff_bridge_rev hrev hL hpair hlim]
exact bridge_swap
obtain ⟨db₀, hb, hflip⟩ := h
exact necessary_of_factor_toggle hcomp hb.2.1 ⟨hb.1, hb.2.2⟩ hflip
/-- The lower joint bases on `[a, b)` make that interval necessary, reversed. -/
theorem necessaryRange_of_lowerJointBaseRangeRev {r : RangeRead} {res : Result}
{L : List Key} {a b : WithTop Key} (hrev : r.reverse = true) (hL : L ≠ [])
(hpair : L.Pairwise (· > ·)) (hlim : withinLimit r L)
(hres : res = { keys := L, more := false }) (h : LowerJointBaseRangeRev r L a b) :
NecessaryRange r res a b :=
fun k hklo hkhi => necessary_of_lowerJointBaseRev hrev hL hpair hlim hres (h k hklo hkhi)
/-- The upper joint bases on `[a, b)` make that interval necessary, reversed. -/
theorem necessaryRange_of_upperJointBaseRangeRev {r : RangeRead} {res : Result}
{L : List Key} {a b : WithTop Key} (hrev : r.reverse = true) (hL : L ≠ [])
(hpair : L.Pairwise (· > ·)) (hlim : withinLimit r L)
(hres : res = { keys := L, more := false }) (h : UpperJointBaseRangeRev r L a b) :
NecessaryRange r res a b :=
fun k hklo hkhi => necessary_of_upperJointBaseRev hrev hL hpair hlim hres (h k hklo hkhi)
/-- **Soundness factors across a compatibility equivalence.** If compatibility is a
conjunction `φ₁ ∧ φ₂` and agreement on `cr` fixes each factor separately, then `cr`
is sound. This is the soundness analogue of the factor-toggle lemma: the reduction's
soundness proof is exactly this shape, with `φ_lo`, `φ_hi`, `φ_mid`, and the
bracketing as the factors. -/
theorem Sound.of_factors {r : RangeRead} {res : Result} {cr : ConflictRange}
{φ₁ φ₂ : DB → Prop}
(hcomp : ∀ db, RangeRead.Compatible db r res ↔ (φ₁ db ∧ φ₂ db))
(h₁ : ∀ db₁ db₂, AgreeOn cr db₁ db₂ → (φ₁ db₁ ↔ φ₁ db₂))
(h₂ : ∀ db₁ db₂, AgreeOn cr db₁ db₂ → (φ₂ db₁ ↔ φ₂ db₂)) :
Sound r res cr := by
intro db₁ db₂ hagree
rw [hcomp db₁, hcomp db₂, h₁ db₁ db₂ hagree, h₂ db₁ db₂ hagree]
/-- **Soundness from four factors.** The bridge is a four-way conjunction (two end
emptinesses, the middle equality, and the bracketing); this is `Sound.of_factors`
iterated over them. -/
theorem Sound.of_four_factors {r : RangeRead} {res : Result} {cr : ConflictRange}
{φ₁ φ₂ φ₃ φ₄ : DB → Prop}
(hcomp : ∀ db, RangeRead.Compatible db r res ↔ (φ₁ db ∧ φ₂ db ∧ φ₃ db ∧ φ₄ db))
(h₁ : ∀ db₁ db₂, AgreeOn cr db₁ db₂ → (φ₁ db₁ ↔ φ₁ db₂))
(h₂ : ∀ db₁ db₂, AgreeOn cr db₁ db₂ → (φ₂ db₁ ↔ φ₂ db₂))
(h₃ : ∀ db₁ db₂, AgreeOn cr db₁ db₂ → (φ₃ db₁ ↔ φ₃ db₂))
(h₄ : ∀ db₁ db₂, AgreeOn cr db₁ db₂ → (φ₄ db₁ ↔ φ₄ db₂)) :
Sound r res cr := by
intro db₁ db₂ hagree
rw [hcomp db₁, hcomp db₂, h₁ db₁ db₂ hagree, h₂ db₁ db₂ hagree, h₃ db₁ db₂ hagree,
h₄ db₁ db₂ hagree]
/-!
## Interior necessity
-/
/-- **Interior necessity.** If every reported key of a complete result is necessary,
then so is every key between the least and the greatest reported key: a sound range
is an interval, so it contains the convex hull of the reported keys. -/
theorem necessaryRange_between_reported {r : RangeRead} {res : Result} {L : List Key}
(hL : L ≠ []) (hkeys : ∀ k ∈ L, Necessary r res k) :
NecessaryRange r res (↑(L.headD ([] : Key)) : WithTop Key)
(↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key) := by
intro k hlo hhi
refine Necessary.of_between (hkeys _ (headD_mem hL)) (hkeys _ (getLastD_mem hL))
(WithTop.coe_le_coe.mp hlo) ?_
rw [WithTop.coe_lt_coe] at hhi
exact (lt_keyAfter_iff k (L.getLastD ([] : Key))).mp hhi
/-- The reported keys of a complete result are necessary. This is the pointwise
input to the interior necessity above. -/
theorem necessary_of_mem_complete {r : RangeRead} {res : Result}
(hread : Readable r res) : ∀ k ∈ res.keys, Necessary r res k :=
fun _ hk => necessary_of_mem_result hread hk
/-!
## The hull of two end ranges
The assembled range is the hull of the two end ranges, not in general the canonical
range. Agreement on the hull restricts to each end range, and the necessary keys of
the pieces cover the hull.
-/
/-- `ConflictRange.IsEmpty` is decidable, so the hull can branch on it. -/
instance (cr : ConflictRange) : Decidable cr.IsEmpty := by
unfold ConflictRange.IsEmpty; infer_instance
/-- The hull of two conflict ranges: their interval hull `[min begin, max end_)`,
except that an empty component is dropped. An empty range denotes `∅` whatever
representative is used, so dropping it keeps the hull's *set* independent of that
representation — in particular a degenerate boundary contribution at the wrong
endpoint cannot extend the result. -/
def hull (cr₁ cr₂ : ConflictRange) : ConflictRange :=
if cr₁.IsEmpty then cr₂
else if cr₂.IsEmpty then cr₁
else ⟨min cr₁.begin cr₂.begin, max cr₁.end_ cr₂.end_⟩
/-- Each end range is a subrange of the hull. -/
theorem subrange_hull_left (cr₁ cr₂ : ConflictRange) : Subrange cr₁ (hull cr₁ cr₂) := by
unfold hull
by_cases h₁ : cr₁.IsEmpty
· rw [ite_eq_left h₁]
intro k hk
exact (ConflictRange.not_mem_of_isEmpty h₁ k hk).elim
· rw [ite_eq_right h₁]
by_cases h₂ : cr₂.IsEmpty
· rw [ite_eq_left h₂]; exact Subrange.refl _
· rw [ite_eq_right h₂]; exact subrange_of_le (min_le_left _ _) (le_max_left _ _)
/-- Each end range is a subrange of the hull. -/
theorem subrange_hull_right (cr₁ cr₂ : ConflictRange) : Subrange cr₂ (hull cr₁ cr₂) := by
unfold hull
by_cases h₁ : cr₁.IsEmpty
· rw [ite_eq_left h₁]; exact Subrange.refl _
· rw [ite_eq_right h₁]
by_cases h₂ : cr₂.IsEmpty
· rw [ite_eq_left h₂]
intro k hk
exact (ConflictRange.not_mem_of_isEmpty h₂ k hk).elim
· rw [ite_eq_right h₂]; exact subrange_of_le (min_le_right _ _) (le_max_right _ _)
/-- Agreement on a range restricts to agreement on any subrange. -/
theorem keys_eq_of_subrange_agree {cr' cr : ConflictRange} {db₁ db₂ : DB}
(hsub : Subrange cr' cr) (h : AgreeOn cr db₁ db₂) : AgreeOn cr' db₁ db₂ := by
apply eq_of_mem_iff_pairwise (ConflictRange.keys_pairwise cr' db₁)
(ConflictRange.keys_pairwise cr' db₂)
intro x
rw [ConflictRange.mem_keys_iff, ConflictRange.mem_keys_iff]
constructor
· rintro ⟨hx₁, hxcr'⟩
have : x ∈ cr.keys db₂ := by
rw [← h]
exact ConflictRange.mem_keys_iff.mpr ⟨hx₁, hsub x hxcr'⟩
exact ⟨(ConflictRange.mem_keys_iff.mp this).1, hxcr'⟩
· rintro ⟨hx₂, hxcr'⟩
have : x ∈ cr.keys db₁ := by
rw [h]
exact ConflictRange.mem_keys_iff.mpr ⟨hx₂, hsub x hxcr'⟩
exact ⟨(ConflictRange.mem_keys_iff.mp this).1, hxcr'⟩
/-- Agreement on the hull restricts to agreement on either factor. -/
theorem agreeOn_of_hull_left {cr₁ cr₂ : ConflictRange} {db₁ db₂ : DB}
(h : AgreeOn (hull cr₁ cr₂) db₁ db₂) : AgreeOn cr₁ db₁ db₂ :=
keys_eq_of_subrange_agree (subrange_hull_left cr₁ cr₂) h
/-- Agreement on the hull restricts to agreement on either factor. -/
theorem agreeOn_of_hull_right {cr₁ cr₂ : ConflictRange} {db₁ db₂ : DB}
(h : AgreeOn (hull cr₁ cr₂) db₁ db₂) : AgreeOn cr₂ db₁ db₂ :=
keys_eq_of_subrange_agree (subrange_hull_right cr₁ cr₂) h
/-- **Conditional minimality of the hull.** If the hull is sound and every key in it
is necessary, it is minimal. This is the assembly step: the reduction's remaining
obligations are exactly these two hypotheses (soundness transfers through the
bracketing/observability argument, necessity through the end theorems and the
interior convexity). -/
theorem minimal_hull_of_sound_of_necessaryRange {r : RangeRead} {res : Result}
{cr : ConflictRange} (hs : Sound r res cr)
(hnec : NecessaryRange r res cr.begin cr.end_) : Minimal r res cr :=
minimal_iff_sound_and_necessaryRange.mpr ⟨hs, hnec⟩
/-!
## Gluing necessary intervals across the hull
The reduction's necessity proof establishes a necessary range for each boundary read and
one for the middle interval; these abut, so the hull's necessary range is their
chain. `NecessaryRange.trans` is the convexity step at interval granularity. -/
/-- Necessary ranges glue at a common endpoint: `[a, b)` and `[b, c)` give `[a, c)`. -/
theorem NecessaryRange.trans {r : RangeRead} {res : Result} {a b c : WithTop Key}
(h₁ : NecessaryRange r res a b) (h₂ : NecessaryRange r res b c) :
NecessaryRange r res a c := by
intro k hak hkc
rcases lt_or_ge (k : WithTop Key) b with hlt | hge
· exact h₁ k hak hlt
· exact h₂ k hge hkc
/-- A necessary range restricts to any sub-interval. -/
theorem NecessaryRange.mono {r : RangeRead} {res : Result} {a b a' b' : WithTop Key}
(h : NecessaryRange r res a b) (ha : a ≤ a') (hb : b' ≤ b) :
NecessaryRange r res a' b' :=
fun k hklo hkhi => h k (le_trans ha hklo) (lt_of_lt_of_le hkhi hb)
/-- **Necessary range of the hull.** If the lower end range `cr₁` is necessary, the
middle interval `[cr₁.end_, cr₂.begin)` is necessary, the upper end range `cr₂` is
necessary, and the intervals are ordered (`cr₁.begin ≤ cr₂.begin` and
`cr₁.end_ ≤ cr₂.end_`), then the hull `[cr₁.begin, cr₂.end_)` is necessary. This is
exactly the hull assembly: everything below the reported keys is the lower end,
the interior is convexity, and everything above is the upper end. -/
theorem necessaryRange_hull_of_chain {r : RangeRead} {res : Result}
{cr₁ cr₂ : ConflictRange}
(h₁ : NecessaryRange r res cr₁.begin cr₁.end_)
(h₂ : NecessaryRange r res cr₁.end_ cr₂.begin)
(h₃ : NecessaryRange r res cr₂.begin cr₂.end_)
(hmin : cr₁.begin ≤ cr₂.begin) (hmax : cr₁.end_ ≤ cr₂.end_) :
NecessaryRange r res (hull cr₁ cr₂).begin (hull cr₁ cr₂).end_ := by
unfold hull
by_cases h₁e : cr₁.IsEmpty
· rw [ite_eq_left h₁e]; exact h₃
· rw [ite_eq_right h₁e]
by_cases h₂e : cr₂.IsEmpty
· rw [ite_eq_left h₂e]; exact h₁
· rw [ite_eq_right h₂e]
have h : NecessaryRange r res cr₁.begin cr₂.end_ := (h₁.trans h₂).trans h₃
have hb : min cr₁.begin cr₂.begin = cr₁.begin := min_eq_left hmin
have he : max cr₁.end_ cr₂.end_ = cr₂.end_ := max_eq_right hmax
rw [hb, he]; exact h
/-- **Minimality of the hull from the chained end ranges.** Soundness of the hull
plus the necessary chain of the previous theorem give minimality by
`minimal_iff_sound_and_necessaryRange`. -/
theorem minimal_hull_of_chain {r : RangeRead} {res : Result} {cr₁ cr₂ : ConflictRange}
(hs : Sound r res (hull cr₁ cr₂))
(h₁ : NecessaryRange r res cr₁.begin cr₁.end_)
(h₂ : NecessaryRange r res cr₁.end_ cr₂.begin)
(h₃ : NecessaryRange r res cr₂.begin cr₂.end_)
(hmin : cr₁.begin ≤ cr₂.begin) (hmax : cr₁.end_ ≤ cr₂.end_) :
Minimal r res (hull cr₁ cr₂) :=
minimal_hull_of_sound_of_necessaryRange hs (necessaryRange_hull_of_chain h₁ h₂ h₃ hmin hmax)
/-- **The reduction as a hypothesis boundary.** Minimality of the two end ranges
*for the full pair* `(r, res)`, together with a necessary middle interval and
soundness of the hull, gives minimality of the hull. The end minimalities supply
the first and third needed ranges via `minimal_iff_sound_and_necessaryRange`. This
is the precise form in which "the whole empty theory" can be assumed: what is
needed is not merely that the end pairs have minimal ranges, but that those minimal
ranges are minimal *at the full pair* — which is exactly what the factor-toggle
joint construction is for. -/
theorem minimal_hull_of_minimal_ends {r : RangeRead} {res : Result}
{cr₁ cr₂ : ConflictRange}
(hlo : Minimal r res cr₁) (hhi : Minimal r res cr₂)
(hmid : NecessaryRange r res cr₁.end_ cr₂.begin)
(hmin : cr₁.begin ≤ cr₂.begin) (hmax : cr₁.end_ ≤ cr₂.end_)
(hs : Sound r res (hull cr₁ cr₂)) :
Minimal r res (hull cr₁ cr₂) :=
minimal_hull_of_chain hs (minimal_iff_sound_and_necessaryRange.mp hlo).2 hmid
(minimal_iff_sound_and_necessaryRange.mp hhi).2 hmin hmax
/-- **Necessity of the hull from the joint bases.** With the lower joint bases below
the reported keys, the interior necessary by convexity, and the upper joint bases
above, the hull's necessary range is assembled. This is the hull necessity
assembly: the ends via factor-toggle joint witnesses, the middle free. -/
theorem necessaryRange_hull_of_jointBases {r : RangeRead} {res : Result} {L : List Key}
{cr₁ cr₂ : ConflictRange} (hrev : r.reverse = false) (hL : L ≠ [])
(hpair : L.Pairwise (· < ·)) (hlim : withinLimit r L)
(hres : res = { keys := L, more := false })
(hlo : LowerJointBaseRange r L cr₁.begin cr₁.end_)
(hmid : NecessaryRange r res cr₁.end_ cr₂.begin)
(hhi : UpperJointBaseRange r L cr₂.begin cr₂.end_)
(hmin : cr₁.begin ≤ cr₂.begin) (hmax : cr₁.end_ ≤ cr₂.end_) :
NecessaryRange r res (hull cr₁ cr₂).begin (hull cr₁ cr₂).end_ :=
necessaryRange_hull_of_chain
(necessaryRange_of_lowerJointBaseRange hrev hL hpair hlim hres hlo)
hmid (necessaryRange_of_upperJointBaseRange hrev hL hpair hlim hres hhi) hmin hmax
/-- **Minimality of the hull from the joint bases and hull soundness.** This is the
end-to-end shape of the necessity argument: the end ranges are established
by the joint bases (factor-toggle), the interior by convexity over the reported keys
(`necessaryRange_between_reported`), and the only remaining hypothesis is soundness
of the hull — the soundness half of the reduction. -/
theorem minimal_hull_of_jointBases {r : RangeRead} {res : Result} {L : List Key}
{cr₁ cr₂ : ConflictRange} (hread : Readable r res) (hrev : r.reverse = false)
(hL : L ≠ []) (hpair : L.Pairwise (· < ·)) (hlim : withinLimit r L)
(hres : res = { keys := L, more := false })
(hlo : LowerJointBaseRange r L cr₁.begin cr₁.end_)
(hhi : UpperJointBaseRange r L cr₂.begin cr₂.end_)
(hk₀ : cr₁.end_ = (↑(L.headD ([] : Key)) : WithTop Key))
(hkₙ : cr₂.begin = (↑(keyAfter (L.getLastD ([] : Key))) : WithTop Key))
(hmin : cr₁.begin ≤ cr₂.begin) (hmax : cr₁.end_ ≤ cr₂.end_)
(hs : Sound r res (hull cr₁ cr₂)) :
Minimal r res (hull cr₁ cr₂) := by
refine minimal_hull_of_chain hs
(necessaryRange_of_lowerJointBaseRange hrev hL hpair hlim hres hlo)
?_ (necessaryRange_of_upperJointBaseRange hrev hL hpair hlim hres hhi) hmin hmax
rw [hk₀, hkₙ]
have hkeys : ∀ k ∈ L, Necessary r res k := by
intro k hk
have hkres : k ∈ res.keys := by rw [hres]; exact hk
exact necessary_of_mem_result hread hkres
exact necessaryRange_between_reported hL hkeys
end FormalConflictRange