Files

4243 lines
238 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
import FormalConflictRange.Nonpos
import FormalConflictRange.Reduction
/-!
# The conflict-range algorithm
The conflict-range inference has two layers.
* A certified-region partial algorithm `conflictRangePartial`, built on the
(unconditional) empty-result theory of `FormalConflictRange.Empty` and
`FormalConflictRange.Nonpos`: a result with no keys is answered by the empty-result
value `emptyValue`, and the remaining certified offset cases are handled as in
`FormalConflictRange.Sound`. The correctness statement is
`conflictRangePartial_spec`: wherever the function returns `some cr`, that range
is minimal. The inputs on which it returns `none` are the cases this case-analysis
route did not certify. The headline theorem is proved independently in
`Proof.lean` through the closed-form development
(`FormalConflictRange.ClosedFormAll`). This module also supplies that
development's empty-result theory — `emptyValue`, `EmptyInferenceWitness`,
and `minimal_emptyValue_of_emptyInference` — so the partial-algorithm
sections below are a record of the case analysis, while the empty-result
declarations are shared with the final proof.
* The provisional totalization `conflictRangeVal`, assembled by *reduction to the
empty reads* rather than case analysis. It is the every-input wrapper used to
*state* the general reduction: it dispatches on emptiness, truncation, and
traversal and returns a `ConflictRange` on the certified regions. Off them its
value is a placeholder whose hull fallback is not sound in general (a complete
read whose reported keys are not the endpoint keys of the hull gives a
counterexample), and its `_spec` theorems are relative to the conditional
`EmptyTheoryComplete`. It is kept only as the intermediate reduction interface.
It dispatches as follows:
- an empty result is answered by the empty theory's value `emptyValue`;
- a forward truncated result is `[w, keyAfter kₙ)`: the begin selector's empty
contribution plus the reported keys, with the bare successor upper end;
- a reverse truncated result is `[kₙ, u)`: the reported keys plus the end
selector's empty contribution, the begin selector dropping out;
- a complete result in the canonical region `1 ≤ begin.offset ∧ end.offset ≤ 1` is
the canonical range `[begin.key, end.key)` (`completeValue`), which is minimal
outright by `minimal_canonicalRange_of_end_offset_le_one_general`;
- a complete result in the overshoot region `1 ≤ begin.offset` with every reported
key below `end.key` is the unbounded top range `[begin.key, ⊤)`, minimal by
`minimal_topRange_of_end_offset_ge_two_general`;
- a complete result elsewhere is the hull of the two end ranges,
`[w, k₀) ∪ [keyAfter kₙ, u)`.
Here `w = lowBound r` and `u = highBound r` are the empty theory's begin and end
endpoints (`⊥` or `begin.key`; `end.key`, or the crossed/overshoot answer).
The algorithm reduces to the single `EmptyInference` oracle: `emptyValue` is minimal
for every realizable empty result. The empty branch is discharged outright
(`minimal_emptyValue_of_emptyInference`); the reported interval is necessary
unconditionally (`necessaryRange_reportedRange`, from `necessary_of_mem_result` and
convexity), so a complete result's necessity is entirely the two boundary ranges
stretched to the complete value's endpoints (`BoundaryNecessity`), the content the
empty inference supplies as `ψ` at the two boundary reads. Hull soundness is derived
from `EmptyInference` for all bridge factors except the bracket (`BracketFactor`),
which is the bracket-observability residue. The complete branch is then
`minimal_completeRange_of_factors`/`_rev`, with the interior derived rather than
assumed; `GeneralObligation` adds only the two truncated dispatch values. Its
conditional correctness statement is `conflictRangeVal_spec` (relative to
`EmptyTheoryComplete`); the certified algorithm in this module remains
`conflictRangePartial`. In the canonical region (`begin.offset = 1`,
`end.offset ≤ 1`, canonical endpoints) the complete branch is unconditional
(`minimal_completeRange_canonical`), needing neither boundary hypothesis. There are
no `sorry`s: the uncertified content appears only as those explicit hypotheses.
The reduction identity itself is `necessaryRange_completeRange_of_reported`: the
complete value's necessary range is the lower boundary, the reported interval, and the
upper boundary, in that order, with the middle supplied by pointwise reported necessity
and convexity. Because reported necessity is unconditional
(`necessary_of_mem_result`), the general complete case is exactly "reported keys + the
two empty ends" (`minimal_completeRange_of_emptyEnds`). The boundary half is stated at
the witness level too: `LowerJointBase`/`UpperJointBase` (and their reversed twins) are
the flip witnesses the factor-toggle needs, `BoundaryJointBases` packages them by
traversal, and `minimal_completeRange_of_factors_joint`/`_rev` and
`minimal_completeRange_of_witness_joint`/`_rev` assemble the complete branch from them.
`EmptyInferenceWitness` records the empty theory in the witness-exposing form the graft
consumes and implies `EmptyInference` (`emptyInference_of_witness`). The one genuine
extraction — turning an abstract `Minimal` for a boundary read into a full-compatible
witness database — is the length-sensitive joint-base graft; it is the reason the
boundary content is a hypothesis and not a consequence of `EmptyInference` alone. It is
in fact *false*, not merely unproved: a two-key witness makes the hull endpoints differ
from the reported interval's, so `BoundaryJointBases` fails for it.
The pushed-down interface makes the confinement of offsets explicit. The complete
branch's nonempty content is `CompleteObligation`, whose fields are the generic graft
(`joint : BoundaryJointBases`) and the bracket (`bracket : BracketFactor`); correctness
is `conflictRangeVal_spec_of_witness`, taking only the witness oracle, the two
obligations, and `Readable` — no offset, no `EmptyInference`, no finished
`BoundaryNecessity`. The abstract `conflictRangeVal_spec` remains as the legacy form.
Finally, `EmptyTheoryComplete` bundles the entire residual into a single hypothesis:
the witness-exposing empty oracle, the generic graft, the bracket gap split, and the
truncated one-sided graft. From it, `conflictRangeVal_spec_complete` proves the general
algorithm correct with `Readable` the only other hypothesis, and
`exists_minimal_conflict_range_of_complete` gives existence from the same hypotheses.
The graft fields (`joint`, `truncated`) are guarded by `Readable`: a bridge database
exists only when the reported keys are the complete keys of some database, so for an
unrealizable pair `BoundaryJointBases`/`GeneralObligation` are outright false (a
duplicate reported key can never satisfy `midEq`). This conditional route is not the
headline proof: the unconditional statement is proved in `Proof.lean`, where the closed
form is established directly for the reference development. All three non-witness
fields of
`EmptyTheoryComplete` are in fact *refuted* — `bracket` and `truncated` as before, and
`joint` (`BoundaryJointBases`) by the two-key witness that also refutes the hull — so
the reduction is uninhabited rather than merely unproved.
On the empty theory itself, the witness-exposing oracle is proved at
`begin.offset = 1` (`emptyWitness_beginOne`), throughout the whole `end.offset ≤ 1`
region at any positive begin offset (`emptyWitness_underEnd_gen`, from the slice
characterization and the room bound in `FormalConflictRange.Empty`), and throughout
the overshoot region (`emptyWitness_overshoot`, `begin.offset ≥ 1`, `end.offset ≥ 2`,
any traversal). The empty-result case proofs are restated at the witness level
(`emptyWitness_underEnd`, `emptyWitness_underEnd_general`, `emptyWitness_crossFree`,
`emptyWitness_crossed_beginLe`, `emptyWitness_crossed_interval`, and the
positive-offset `emptyWitness_beginLe_of_le_general`, `emptyWitness_beginLe_general`,
`emptyWitness_mem_interval_general`), and traversal invariance transports them. The
nonpositive begin offset now has its own `emptyValue` candidate (`FormalConflictRange.Nonpos`).
An overshooting end (`end.offset ≥ 2`) is handled uniformly in the selector order: the
full range `[⊥, ⊤)` is sound and minimal (`minimal_fullRange_of_nonpos_overshoot_all`),
with every key witnessed by the singleton (`emptyWitness_nonpos_overshoot`). With
`end.offset = 1` the value is the bottom range `[⊥, end.key)` cross-free and in the short
gap, and `[⊥, begin.key)` in the crossed long gap, with flip witnesses throughout the
region (`emptyWitness_nonpos_end_one_crossFree`, `emptyWitness_nonpos_end_one_crossedShort`,
`emptyWitness_nonpos_end_one_crossedLong`). The cross-free `end.offset ≤ 0` region is also
closed (`emptyWitness_nonpos_end_nonpos_crossFree`): the value is `[⊥, end.key)`, its keys
split into the region where the criterion collapses to `cnt end.key ≤ 1 - end.offset` and
the region where the gap room `1 - end.offset - (1 - begin.offset) + 1 ≤ intervalCard
begin.key end.key` supplies it. The last nonpositive begin-and-end region with crossed
selectors -- where the end anchor can clamp as well -- is now closed too: off the trivially
empty reads `1 - begin.offset > 1 - end.offset`, and the gap splits into the short-gap case
`intervalCard end.key begin.key < end.offset - begin.offset`, whose criterion collapses to
`cnt end.key ≤ 1 - end.offset` (`emptyWitness_nonpos_crossed_short`, singleton witnesses),
and the long-gap case `emptyWitness_nonpos_crossed_long` with the coupled count witnesses
(`emptyWitness_nonpos_crossed_long_below`, `_interval`). The residual
`EmptyInferenceWitnessResidual` is therefore vacuous: the whole oracle is
`emptyInferenceWitness`, unconditionally, and `emptyInference : EmptyInference` follows.
What remains of the empty theory is only the graft and gap-split fields of
`EmptyTheoryComplete`, packaged by `emptyTheoryComplete_of_witness`. The gap-split field
`BracketFactor` is in fact *false* as stated on the hull: a compatible database can
satisfy the boundary conditions while the bracket fails. `completeValue` routes the
canonical region `1 ≤ begin.offset ∧ end.offset ≤ 1` around the hull precisely so that
this pair is answered correctly without it.
The reduction described here was the working route to the closed form; the final
argument in `Proof.lean` uses the closed-form theorems instead. The empty-result
part of this module (`emptyValue`, `EmptyInference`, and
`minimal_emptyValue_of_emptyInference`) is shared with that development.
-/
namespace FormalConflictRange
/-!
## A partial algorithm: the certified cases
The theorems above certify a region of reads. Package them into one computable
`Option`-valued function,
`conflictRangePartial`, returning `some` range exactly where a certificate exists
and `none` otherwise. This is the honest encoding of "proved only for certain
cases": it is total in type but makes absence explicit, and `none` carries no
pretense of being a range. The certificate `conflictRangePartial_spec` proves
`some cr` is minimal whenever the value is defined.
The certified region is: an empty result (any offsets and traversal, answered by the
empty-result value `emptyValue`, whose minimality is the unconditional `emptyInference`),
or else a nonempty result with begin at offset one and either the end at offset at
most one (all traversal and truncation combinations at end offset one, and — for
`end.offset ≤ 0` — the complete results, the truncated forward results, whose canonical
range is certified by `minimal_canonicalRange_of_truncated_end_offset_nonpos`, and the
truncated reversed results, whose reversed truncated range is certified by
`minimal_truncatedRangeRev_of_end_offset_nonpos`) or an
overshooting end (`end_.offset ≥ 2`) whose reported keys all lie below `end_.key` (all
traversal and truncation combinations too), or a nonempty complete result at any positive
begin offset (the canonical range at `end.offset ≤ 1`, the unbounded top at an
overshoot), or — at any positive begin offset — a truncated *forward* result with
`end.offset ≤ 0`, or the nonempty truncated *reversed* and complete cells at `begin.offset
≥ 2` (canonical, top-range, or reversed-truncated by `end.offset`), or the cross-free
nonempty complete overshoot at `begin.offset ≤ 0` (`[⊥, ⊤)`), the cross-free nonempty
complete under-end result at `begin.offset ≤ 0` (`[⊥, end_.key)`), or the cross-free nonempty
truncated forward result at `begin.offset ≤ 0` with a pinned end (`[⊥, keyAfter last
reported)`), or the crossed nonempty complete forward overshoot at `begin.offset = 0` (the
top range from the least reported key `[head, ⊤)`), or the crossed nonempty complete forward
result at `begin.offset = 0`, `end.offset = 1` with `begin.key ≤ end_.key` (the head range
`[head, end_.key)`). The
empty branch is tried first and needs no offset hypothesis; it certifies every
realizable empty result through the boundary theory rather than the offset-one cases.
-/
/-- The begin selector sits at offset one, the offset at which `resolve begin` is
threshold-defined and `key_le_resolve_of_offset_one` applies. -/
abbrev beginOne (r : RangeRead) : Prop := r.begin.offset = 1
/-- The end selector sits at offset one, the offset-one end case. -/
abbrev endOne (r : RangeRead) : Prop := r.end_.offset = 1
/-- An overshooting end: the end offset is at least two and every reported key
lies below `end_.key`. This is the region where the overshoot certificates apply,
in all four traversal/completeness combinations. -/
abbrev overshoot (r : RangeRead) (res : Result) : Prop :=
2 ≤ r.end_.offset ∧ res.keys ≠ [] ∧
(∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key)
/-- An end selector at offset at most one: the end family where `resolve end_` is
the threshold-defined case of `minimal_canonicalRange_of_end_offset_le_one`, as
opposed to the offset at least two of `overshoot`. -/
abbrev underEnd (r : RangeRead) : Prop := r.end_.offset ≤ 1
/-- The least reported key of a result, regardless of traversal: the head of an
ascending result, the last of a descending (reversed) one. -/
def leastReported (r : RangeRead) (res : Result) : Key :=
if r.reverse then res.keys.getLastD ([] : Key) else res.keys.headD ([] : Key)
/-- The greatest reported key of a result, regardless of traversal: the last of an
ascending result, the head of a descending (reversed) one. -/
def greatestReported (r : RangeRead) (res : Result) : Key :=
if r.reverse then res.keys.headD ([] : Key) else res.keys.getLastD ([] : Key)
/-- A nonempty *complete* result at a nonpositive begin offset with an overshooting
end (every reported key below `end_.key`) whose begin key lies at or below the least
reported key. On this region the unbounded full range `[⊥, ⊤)` is minimal
(`minimal_fullRange_of_nonpos_overshoot_nonempty` and its reversed twin): the empty
key is forced by `begin.key ≤ least reported`, the reported keys and everything
between them by convexity, and every key at or above the least reported key by the
overshoot necessity `necessary_of_end_offset_ge_two`. This is the cross-free half of
the nonpositive-begin nonempty region. -/
abbrev nonposOvershootComplete (r : RangeRead) (res : Result) : Prop :=
2 ≤ r.end_.offset ∧ res.more = false ∧ res.keys ≠ [] ∧
(∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key) ∧
r.begin.key ≤ ((leastReported r res : Key) : WithTop Key)
/-- A nonempty *complete* result at a nonpositive begin offset with `end_.offset ≤ 1` whose
begin key lies at or below the least reported key. On this region the bottom range
`[⊥, end_.key)` is minimal (`minimal_bottomRange_of_nonpos_underEnd_nonempty` and its
reversed twin): the empty key is forced by `begin.key ≤ least reported`, the reported keys
and everything between them by convexity, and every key from the reported last up to
`end_.key` by the end selector's reach. This is the under-end companion of
`nonposOvershootComplete` on the nonpositive-begin nonempty complete region. -/
abbrev nonposUnderEndComplete (r : RangeRead) (res : Result) : Prop :=
r.end_.offset ≤ 1 ∧ res.more = false ∧ res.keys ≠ [] ∧
r.begin.key ≤ ((leastReported r res : Key) : WithTop Key)
/-- A nonempty *truncated forward* result at a nonpositive begin offset whose begin key lies
at or below the least reported key, with the end pinned above the reported keys
(`1 ≤ end_.offset` and every reported key strictly below `end_.key`). On this region the bottom
truncated range `[⊥, keyAfter last reported)` is minimal
(`minimal_truncatedRangeBottom_of_nonpos`): the empty key is forced by `begin.key ≤ least
reported`, the reported keys and everything between them by convexity, and nothing past the
successor of the reported last because the result reports a prefix. The `1 ≤ end_.offset`
condition puts `end_.key ≤ resolve end_`, so every key at or below the reported last is below
`resolve end_`; the pinning keeps the resolved end out of the value. This is the truncated
forward companion of `nonposOvershootComplete`/`nonposUnderEndComplete` on the nonpositive-begin
nonempty region. The `1 ≤ end_.offset` and `end_.key`-overshoot conditions may hold vacuously at
`end_.offset = 1`, where realizability forces the reported keys below `end_.key`. -/
abbrev nonposFwdTruncPinned (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = false ∧
r.begin.key ≤ ((leastReported r res : Key) : WithTop Key) ∧
1 ≤ r.end_.offset ∧ ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key
/-- A nonempty *truncated reversed* result at a nonpositive begin offset whose begin key lies
at or below the least (last) reported key, with an overshooting end (`2 ≤ end_.offset` and
every reported key strictly below `end_.key`). On this region the unbounded top from the least
reported key, `[last reported, ⊤)`, is minimal
(`minimal_topOfLast_of_end_offset_ge_two_rev_nonpos`): the overshoot forces every witness
window to end at the sentinel, so compatibility depends only on the stored keys at or above the
least reported key; those keys, the reported ones, and everything convexly between them are
necessary, as is every key at or above the reported head by `necessary_of_end_offset_ge_two_rev`.
The cross-free hypothesis `begin.key ≤ least reported` replaces the `begin.offset = 1`
hypothesis of the positive-offset twin, since a nonpositive begin offset resolves at or below
`begin.key`. This is the reversed truncated overshoot companion of `nonposFwdTruncPinned` on the
nonpositive-begin nonempty region. -/
abbrev nonposRevTruncOvershoot (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = true ∧
r.begin.key ≤ ((leastReported r res : Key) : WithTop Key) ∧
2 ≤ r.end_.offset ∧ ∀ k ∈ res.keys, ((k : Key) : WithTop Key) < r.end_.key
/-- A nonempty *truncated reversed* result at a nonpositive begin offset whose begin key lies
at or below the least (last) reported key, with the end at offset one. On this region the
reversed truncated range `[last reported, end_.key)` is minimal
(`minimal_truncatedRangeRev_of_end_offset_one_nonpos`): the reported keys and everything
convexly between them are necessary, and every key at or above the reported head up to
`end_.key` by `necessary_head_to_end_key`. Soundness is that `end_.offset = 1` makes the cut
at `resolve end_` the cut at `end_.key`, so agreement on `[last, end_.key)` fixes the stored
keys the reversed prefix can observe. This is the reversed truncated under-end companion of
`nonposRevTruncOvershoot` and the nonpositive-begin companion of the offset-one reversed
truncated cell. -/
abbrev nonposRevTruncEndOne (r : RangeRead) (res : Result) : Prop :=
res.more = true ∧ r.reverse = true ∧
r.begin.key ≤ ((leastReported r res : Key) : WithTop Key) ∧
r.end_.offset = 1
/-- A nonempty *complete forward* result at `begin.offset = 0` whose `begin.key` lies
strictly above the least reported key (the crossed subcase) and whose end overshoots
(`2 ≤ end_.offset`, every reported key below `end_.key`). On this region the top range
from the least reported key, `[head, ⊤)`, is minimal
(`minimal_topOfHead_of_zero_begin_crossed_overshoot`): at offset zero the begin selector
resolves onto the greatest stored key strictly below `begin.key`; compatibility forces
that key to be the reported head, so the window is `[head, ⊤)` and agreement on
`[head, ⊤)` fixes the complete keys. Every key at or above the reported last is necessary
by `necessary_of_end_offset_ge_two`, and convexity fills the gap down to the head. This
is the crossed companion of `nonposOvershootComplete`: the cross-free hypothesis
`begin.key ≤ least reported` there is here replaced by its negation. -/
abbrev zeroCrossOvershootComplete (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧ overshoot r res ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key
/-- A nonempty *complete forward* result at `begin.offset = 0` whose `begin.key` lies strictly
above the least reported key (the crossed subcase) and whose end sits at offset one. On this
region the range from the least reported key up to `end_.key`, `[head, end_.key)`, is minimal
(`minimal_headToEnd_of_zero_begin_crossed_endOne`): the begin selector lands on the reported
head, and with `end.offset = 1` the end selector stops at the first stored key at or above
`end_.key`, so the complete keys are exactly the stored keys in `[head, end_.key)`. Unlike the
cross-free under-end region the empty key is not forced, so the value starts at the head. The
extra hypothesis `begin.key ≤ end_.key` rules out the case where a compatible database can store
keys between `end_.key` and `begin.key` that agreement on `[head, end_.key)` cannot see; there
`[head, end_.key)` is not sound. This is the `end.offset = 1` companion of
`zeroCrossOvershootComplete`. -/
abbrev zeroCrossEndOne (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧
r.end_.offset = 1 ∧ res.keys ≠ [] ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key ∧
r.begin.key ≤ r.end_.key
/-- A nonempty *complete forward* result at `begin.offset = 0` whose `begin.key` lies strictly
above both the least reported key (the crossed subcase) and `end_.key`, with the end at offset one.
On this region the range from the least reported key up to `begin.key`, `[head, begin.key)`, is
minimal (`minimal_headToBeginKey_of_zero_begin_crossed_endOne_long`): the begin selector lands on
the reported head, while a compatible database storing a key between `end_.key` and `begin.key`
would have the begin selector resolve above the head, so those keys are necessary and the value
ends at `begin.key` rather than `end_.key`. This is the `end_.key < begin.key` companion of
`zeroCrossEndOne`. -/
abbrev zeroCrossEndOneLong (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧
r.end_.offset = 1 ∧ res.keys ≠ [] ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key ∧
r.end_.key < r.begin.key
/-- A nonempty *complete forward* result at `begin.offset = 0` whose `begin.key` lies strictly
above the least reported key (the crossed subcase) and whose end offset is nonpositive. On this
region the range from the least reported key up to `end_.key`, `[head, end_.key)`, is minimal
(`minimal_headToEnd_of_zero_begin_crossed_endNonpos`): agreement on it fixes the top
`(-end_.offset)` stored keys below `end_.key`, hence the end resolution, while the extra keys
between the end resolution and `end_.key` stay out of the complete window. This is the
`end.offset ≤ 0` companion of `zeroCrossEndOne` and `zeroCrossEndOneLong`. -/
abbrev zeroCrossEndNonpos (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧
r.end_.offset ≤ 0 ∧ res.keys ≠ [] ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key
/-- A nonempty *complete forward* result at `begin.offset = 0`, crossed
(`begin.key` strictly above the reported head), with a positive end offset and
`begin.key ≤ end.key`. On this region the crossed read has the same compatible
databases as the read with its begin selector moved to offset one on the reported
head (`compatible_zero_crossed_iff_anchor`), so the offset-one closed form answers
it. This is the `end.offset ≥ 2` companion of `zeroCrossEndOne` on the crossed
begin-zero region with `begin.key ≤ end.key`. -/
abbrev zeroCrossUnderEnd (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧
2 ≤ r.end_.offset ∧ res.keys ≠ [] ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key ∧
r.begin.key ≤ r.end_.key
/-- A nonempty *complete forward* result at `begin.offset = 0` with `begin.key = ⊤`
and a positive end offset of at least two. On this region the begin selector resolves
onto the greatest stored key, compatibility forces the result to be the singleton
reported head with that head maximal, and the end selector resolves past the end. The
minimal range is the closed form `closedFormZeroCrossLong`, `[end.key, ⊤)` when
`end.key < head` and the end capacity reaches it, and `[head, ⊤)` otherwise. This is
the `begin.key = ⊤` tail of the crossed complete begin-zero long cell. -/
abbrev zeroCrossLongTop (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧
2 ≤ r.end_.offset ∧ res.keys ≠ [] ∧ r.begin.key = (⊤ : WithTop Key)
/-- A nonempty *complete forward* result at `begin.offset = 0`, crossed
(`begin.key` strictly above the reported head), in the long cell `end_.key <
begin.key`, with finite `begin.key`. The minimal range is again the closed form
`closedFormZeroCrossLong`, the anchor's range with the upper endpoint raised to
`begin.key` (`minimal_closedForm_of_zero_cross_long_finite`). This is the finite
`begin.key` companion of `zeroCrossLongTop`. -/
abbrev zeroCrossLongFinite (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = false ∧
2 ≤ r.end_.offset ∧ res.keys ≠ [] ∧ r.begin.key ≠ (⊤ : WithTop Key) ∧
r.end_.key < r.begin.key ∧
((leastReported r res : Key) : WithTop Key) < r.begin.key
/-- A nonempty *complete reversed* result at `begin.offset = 0`, crossed
(`begin.key` strictly above the least reported key). Flipping the traversal gives a
forward crossed complete result at begin offset zero, so the closed form
`closedFormZeroCrossCompleteRev` answers it (`minimal_closedForm_of_zeroCross_complete_rev`). -/
abbrev zeroCrossCompleteRev (r : RangeRead) (res : Result) : Prop :=
r.begin.offset = 0 ∧ res.more = false ∧ r.reverse = true ∧
res.keys ≠ [] ∧ ((leastReported r res : Key) : WithTop Key) < r.begin.key
/-!
## The empty-result value and its inference
The empty-result value `emptyValue` and the standing hypothesis `EmptyInference` are
declared here, before `conflictRangePartial`, because the certified algorithm consults
them directly: an empty result is answered by `emptyValue r`, and the certified branch
of the partial algorithm is exactly the empty-result inference. The witness oracle and
the unconditional proof of `EmptyInference` live later in this file, so the inference is
carried as a hypothesis here and discharged in `conflictRangePartial_spec` below.
-/
/-- The empty result's value. At a nonpositive begin offset the canonical range is
unsound (`compatible_empty_iff_clamp`), so the theory uses a different candidate. An
overshooting end offset (`2 ≤ end.offset`) is empty exactly for the empty database,
whatever the selector order, so the full range `[⊥, ⊤)` is minimal; the test precedes the
cross-free/crossed split. Otherwise (`end.offset ≤ 1`) the begin anchor may clamp to `⊥`,
so the value is the bottom range `[⊥, end.key)` cross-free, and crossed the bottom range
`[⊥, max begin.key end.key)` except when the gap is short
(`intervalCard end.key begin.key < end.offset - begin.offset`), where the begin anchor
can never be lifted and the value is `[⊥, end.key)`. At a positive begin offset it is
the canonical
range for an end at offset at most one, the top range cross-free, and the crossed candidate
otherwise. -/
def emptyValue (r : RangeRead) : ConflictRange :=
if AlwaysEmpty r then emptyRange r
else if r.begin.offset ≤ 0 then
if 2 ≤ r.end_.offset then ⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩
else if r.begin.key ≤ r.end_.key then ⟨(([] : Key) : WithTop Key), r.end_.key⟩
else if intervalCard r.end_.key r.begin.key <
(((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞) then
⟨(([] : Key) : WithTop Key), r.end_.key⟩
else ⟨(([] : Key) : WithTop Key), max r.begin.key r.end_.key⟩
else if r.end_.offset ≤ 1 then canonicalRange r
else if r.begin.key ≤ r.end_.key then topRange r
else crossedRangeGeneral r
/-- **The empty-result inference, as a standing hypothesis.** `emptyValue` returns a
minimal sound conflict range for every realizable read whose complete result is empty.
It is discharged unconditionally later in this file (`emptyInference`); it is stated
here so that `conflictRangePartial` can consult `emptyValue` directly. -/
def EmptyInference : Prop :=
∀ r' : RangeRead, Readable r' { keys := [], more := false } →
Minimal r' { keys := [], more := false } (emptyValue r')
/-- **The empty branch, from the empty inference.** A realizable result with no keys
must be `⟨[], false⟩` — a truncated (`more = true`) result cannot be empty — so the
oracle applies directly. -/
theorem minimal_emptyValue_of_emptyInference (h : EmptyInference)
{r : RangeRead} {res : Result} (hread : Readable r res) (hempty : res.keys = []) :
Minimal r res (emptyValue r) := by
obtain ⟨db, hcomp⟩ := hread
have hmore : res.more = false := by
rcases hcomp.2 with ⟨hm, _, hne⟩ | ⟨hm, _⟩
· exact absurd hempty hne
· exact hm
have hres : res = ({ keys := [], more := false } : Result) := by
cases res
simp_all
subst hres
exact h r ⟨db, hcomp⟩
/-- The partial conflict-range algorithm. It returns `some` range on the certified
region and `none` elsewhere. A result with no keys is answered by the empty-result
value `emptyValue r`, which is minimal for every realizable empty result
(`minimal_emptyValue_of_emptyInference`); this subsumes the trivially empty reads and
covers the empty result at *every* offset and traversal. For a nonempty result at begin
offset one it splits by the end selector. At end offset one the offset-one algorithm
returns the canonical range for a complete result, the truncated range for a truncated
non-reversed result, and the reversed truncated range from the last reported key for a
truncated reversed result. At an overshooting end it returns the unbounded top for a
complete result — reversed or not — the truncated range for a truncated non-reversed
result, and the top from the last reported key for a truncated reversed result. Elsewhere
(`end_.offset ≤ 0`) a complete result returns the canonical range, a truncated
*forward* result returns the canonical range
(`minimal_canonicalRange_of_truncated_end_offset_nonpos`), which is where FoundationDB's
bare successor is unsound, and a truncated *reversed* result returns the reversed
truncated range `[last reported, end.key)`
(`minimal_truncatedRangeRev_of_end_offset_nonpos`).
The guards form an exhaustive, mutually exclusive `if _h : …` chain. The top level
splits on `res.keys = []`, then `beginOne`; within begin offset one it splits on
`endOne`, then `overshoot`, then `underEnd`, leaving the uncertified region — a
non-overshooting end at an offset at least two — as a plain `none` branch. A separate
`1 ≤ begin.offset` branch
certifies every nonempty complete result there — canonical for `end.offset ≤ 1`, the
unbounded top for an overshoot — and a truncated non-reversed overshoot
(`minimal_truncatedRange_of_end_offset_ge_two_general`); for `end.offset ≤ 0` the truncated
*forward* result too, through the general positive-offset theorems, and for `end.offset = 1`
the truncated *forward* result (`minimal_truncatedRange_of_end_offset_one`). At begin offset
at least two the truncated *reversed* result is the canonical range for `end.offset ≤ 1`
(`minimal_canonicalRange_of_end_offset_le_one_rev_more`) and the unbounded top for an
overshoot (`minimal_topRange_of_end_offset_ge_two_rev_more`). Finally, at
`begin.offset ≤ 0` the cross-free nonempty complete overshoot returns the full range
`[⊥, ⊤)` (`minimal_fullRange_of_nonpos_overshoot_nonempty` and its reversed twin), the
cross-free nonempty complete under-end result returns the bottom range `[⊥, end_.key)`
(`minimal_bottomRange_of_nonpos_underEnd_nonempty` and its reversed twin), and the
cross-free nonempty *truncated forward* result with a pinned end (`1 ≤ end_.offset` and
every reported key below `end_.key`) returns the bottom truncated range
`[⊥, keyAfter last reported)` (`minimal_truncatedRangeBottom_of_nonpos`), and the
cross-free nonempty *truncated reversed* result with an overshooting end
(`2 ≤ end_.offset` and every reported key below `end_.key`) returns the unbounded top
from the least reported key, `[last reported, ⊤)`
(`minimal_topOfLast_of_end_offset_ge_two_rev_nonpos`), and the cross-free nonempty
*truncated reversed* result with `end_.offset = 1` returns the reversed truncated range
`[last reported, end_.key)` (`minimal_truncatedRangeRev_of_end_offset_one_nonpos`), and the
crossed nonempty complete forward result at `begin.offset = 0`, `end.offset = 1` with
`begin.key ≤ end_.key` returns the head range `[head, end_.key)`
(`minimal_headToEnd_of_zero_begin_crossed_endOne`), and with `end_.key < begin.key` the
head-to-`begin.key` range `[head, begin.key)`
(`minimal_headToBeginKey_of_zero_begin_crossed_endOne_long`). The
remaining `none` branches are the non-overshooting `end.offset ≥ 2` results and the
crossed nonempty results at `begin.offset ≤ 0` beyond these two certified cells.
Naming each guard, rather than sharing one catch-all, keeps
the branches disjoint and makes deleting or weakening a guard leave a hole the definition
cannot fill. -/
def conflictRangePartial (r : RangeRead) (res : Result) : Option ConflictRange :=
if _h : res.keys = [] then
some (emptyValue r)
else if _h : beginOne r then
if _h : endOne r then
some (conflictRangeOffsetOne r res)
else if _h : overshoot r res then
if _h : res.more = false then
some (topRange r)
else if _h : r.reverse = false then
some (truncatedRange r (res.keys.getLastD ([] : Key)))
else
some (topOfLast (res.keys.getLastD ([] : Key)))
else if _h : underEnd r then
-- `end_.offset ≤ 0` (the `end.offset = 1` case was taken by `endOne` above). A
-- complete result has the canonical range
-- (`minimal_canonicalRange_of_end_offset_le_one_general`). A truncated
-- (`more = true`) forward result now has it too
-- (`minimal_canonicalRange_of_truncated_end_offset_nonpos`): FoundationDB's bare
-- successor `[begin.key, keyAfter (last reported))` is *unsound* there: a
-- compatible database with a nonpositive end offset realises the failure,
-- because the resolved end clamps below `end_.key`, but the canonical upper
-- end `end_.key` is correct. A
-- truncated *reversed* result has the reversed truncated range
-- `[last reported, end_.key)` (`minimal_truncatedRangeRev_of_end_offset_nonpos`):
-- the top `(1 - end_.offset)` canonical keys are dropped, but filtering at or
-- above the last reported key selects the same suffix, so agreement on
-- `[last reported, end_.key)` still fixes compatibility.
if _h : res.more = false then
some (canonicalRange r)
else if _h : r.reverse = false then
some (canonicalRange r)
else
some (truncatedRangeRev r (res.keys.getLastD ([] : Key)))
else
-- `end_.offset ≥ 2` without overshoot. FoundationDB sends
-- `[begin.key, keyAfter (last reported))` non-reversed and
-- `[more ? last reported : begin.key, keyAfter (head reported))` reversed
-- (`getRangeFinished`, `NativeAPI.actor.cpp:4770-4785`). Left uncertified:
-- an `end_.offset ≥ 2` can run past the data even when a reported key lies at
-- or above `end_.key`, so the end anchor is not always observable and the
-- candidate need not be sound. The cell has no single shape: the
-- bare-successor value (of the greatest reported key) is minimal at
-- `end.offset = 2`
-- but fails for larger slack, where the window runs past the reported last (a
-- compatible witness realises this; the true value is the top).
none /- end offset at least two but not overshooting: no certificate -/
else if _h : 1 ≤ r.begin.offset then
-- A nonempty result at `begin.offset ≥ 1` (here `begin.offset ≠ 1`, so at least two)
-- and `end.offset ≤ 1`: a complete result has the canonical range
-- (`minimal_canonicalRange_of_end_offset_le_one_general`), and an overshooting end
-- (every reported key below `end.key`) a complete result has the unbounded top
-- (`minimal_topRange_of_end_offset_ge_two_general` and its reversed twin). The
-- truncated *forward* result additionally has the canonical range at `end.offset ≤ 0`
-- (`minimal_canonicalRange_of_truncated_end_offset_nonpos`) and the truncated range at
-- `end.offset = 1` (`minimal_truncatedRange_of_end_offset_one`). The remaining
-- truncated *reversed* cases and the non-overshooting `end.offset ≥ 2` results stay
-- uncertified.
if _h : r.end_.offset ≤ 0 then
if _h : res.more = false then
some (canonicalRange r)
else if _h : r.reverse = false then
some (canonicalRange r)
else
-- Truncated reversed at `begin.offset ≥ 2`, `end_.offset ≤ 0`: the canonical range
-- is minimal (`minimal_canonicalRange_of_end_offset_le_one_rev_more`). The begin
-- selector skips `b = begin.offset - 1` canonical keys, so the `b` keys below the
-- reported last must be tracked; convexity from the begin key through the reported
-- last, and `necessary_head_to_end_key` above it, force the whole canonical range.
some (canonicalRange r)
else if _h : underEnd r then
-- `end.offset = 1`: complete is the canonical range; the truncated *forward*
-- result is the truncated range (`minimal_truncatedRange_of_end_offset_one`), and
-- the truncated *reversed* result is the canonical range
-- (`minimal_canonicalRange_of_end_offset_le_one_rev_more`).
if _h : res.more = false then
some (canonicalRange r)
else if _h : r.reverse = false then
some (truncatedRange r (res.keys.getLastD ([] : Key)))
else
-- Truncated reversed at `begin.offset ≥ 2`, `end_.offset = 1`: same value, the
-- canonical range (`minimal_canonicalRange_of_end_offset_le_one_rev_more`).
some (canonicalRange r)
else if _h : overshoot r res then
if _h : res.more = false then
some (topRange r)
else if _h : r.reverse = false then
some (truncatedRange r (res.keys.getLastD ([] : Key)))
else
-- Truncated *reversed* at `begin.offset ≠ 1`, `end_.offset ≥ 2`, overshooting: the
-- reversed value `topOfLast` is unsound here (a compatible witness realises
-- this), because the begin selector skips keys below the reported last that
-- the candidate cannot see. The minimal value is instead the unbounded top
-- from `begin.key`,
-- `[begin.key, ⊤)` (`minimal_topRange_of_end_offset_ge_two_rev_more`): the begin
-- key is necessary, and convexity through the reported keys with
-- `necessary_of_end_offset_ge_two_rev` above the head forces the whole interval.
some (topRange r)
else
-- `begin.offset ≠ 1`, `end_.offset ≥ 2`, not overshooting. The resolved begin can
-- land above `begin.key`, so the canonical range need not be sound. Left
-- uncertified.
none /- begin offset at least two, end offset at least two, not overshooting: no
certificate -/
else
-- `begin.offset ≤ 0`, nonempty result. The empty key can be forced into every sound
-- range (`necessary_nil_of_begin_offset_nonpos`), so the canonical range is not
-- minimal, and the resolved begin can land below `begin.key`. In the cross-free
-- overshoot subcase (`begin.key ≤` the least reported key, every reported key below
-- `end_.key`) the full range `[⊥, ⊤)` is minimal
-- (`minimal_fullRange_of_nonpos_overshoot_nonempty` and its reversed twin); in the
-- cross-free non-overshooting subcase (`begin.key ≤` the least reported key,
-- `end_.offset ≤ 1`) the bottom range `[⊥, end_.key)` is minimal
-- (`minimal_bottomRange_of_nonpos_underEnd_nonempty` and its reversed twin); and in the
-- cross-free truncated forward subcase (`begin.key ≤` the least reported key, end pinned
-- above the reported keys) the bottom truncated range `[⊥, keyAfter last reported)` is
-- minimal (`minimal_truncatedRangeBottom_of_nonpos`); and in the
-- cross-free truncated reversed subcase (`begin.key ≤` the least reported key, an
-- overshooting end) the unbounded top from the least reported key `[last reported, ⊤)` is
-- minimal (`minimal_topOfLast_of_end_offset_ge_two_rev_nonpos`); and in the cross-free
-- truncated reversed subcase with `end_.offset = 1` the reversed truncated range
-- `[last reported, end_.key)` is minimal
-- (`minimal_truncatedRangeRev_of_end_offset_one_nonpos`). In the crossed complete
-- forward overshoot subcase at `begin.offset = 0` (`begin.key` strictly above the least
-- reported key) the top range from the least reported key `[head, ⊤)` is minimal
-- (`minimal_topOfHead_of_zero_begin_crossed_overshoot`). In the crossed complete forward
-- subcase at `begin.offset = 0`, `end.offset = 1` (`begin.key` strictly above the least
-- reported key, `begin.key ≤ end_.key`) the head range `[head, end_.key)` is minimal
-- (`minimal_headToEnd_of_zero_begin_crossed_endOne`); in the companion subcase with
-- `end_.key < begin.key` the keys in `(end_.key, begin.key)` are forced, so the head-to-
-- `begin.key` range `[head, begin.key)` is minimal
-- (`minimal_headToBeginKey_of_zero_begin_crossed_endOne_long`). The remaining crossed cases
-- are left uncertified.
if _h : nonposOvershootComplete r res then
some ⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩
else if _h : nonposUnderEndComplete r res then
some ⟨(([] : Key) : WithTop Key), r.end_.key⟩
else if _h : nonposFwdTruncPinned r res then
some (truncatedRangeBottom (res.keys.getLastD ([] : Key)))
else if _h : nonposRevTruncOvershoot r res then
some (topOfLast (res.keys.getLastD ([] : Key)))
else if _h : nonposRevTruncEndOne r res then
some (truncatedRangeRev r (res.keys.getLastD ([] : Key)))
else if _h : zeroCrossOvershootComplete r res then
some (topOfLast (res.keys.headD ([] : Key)))
else if _h : zeroCrossEndOne r res then
some ⟨(((res.keys.headD ([] : Key)) : Key) : WithTop Key), r.end_.key⟩
else if _h : zeroCrossEndOneLong r res then
some ⟨(((res.keys.headD ([] : Key)) : Key) : WithTop Key), r.begin.key⟩
else
none /- nonempty result at begin offset at most zero: no certificate -/
/-!
## FoundationDB's formula, and the remaining holes
`conflictRangePartial` returns `none` on several regions. FoundationDB's client
returns a range on all of them; `fdbRange` below transcribes its
`getRangeFinished` (`NativeAPI.actor.cpp:4739-4794`), including the
`readToBegin`/`readThroughEnd` side-channel flags that carry the endpoint
facts the formal development instead derives. It is recorded here as
documentation of FoundationDB's behaviour, not as a certified value. The
empty-result branch is now unconditional: `conflictRangePartial` answers any empty
result with `emptyValue r` via the proved `emptyInference`, so the empty result is
certified at every offset and traversal and the `none` regions below concern only
nonempty results. The empty-result `underEnd` case, once the sole remaining conjecture,
is also proved outright (`minimal_canonicalRange_of_underEnd_empty_conj` delegates to
`minimal_canonicalRange_of_underEnd_empty`), and the truncated reversed `underEnd`
case at begin offset one is certified by
`minimal_truncatedRangeRev_of_end_offset_nonpos`, the truncated reversed cell at begin
offset at least two with `end.offset ≤ 1` by
`minimal_canonicalRange_of_end_offset_le_one_rev_more`, and its overshooting companion by
`minimal_topRange_of_end_offset_ge_two_rev_more`. The cross-free nonempty complete
overshoot at a nonpositive begin offset is certified by
`minimal_fullRange_of_nonpos_overshoot_nonempty` (and its reversed twin), the full range
`[⊥, ⊤)`, and the cross-free nonempty complete under-end result there by
`minimal_bottomRange_of_nonpos_underEnd_nonempty` (and its reversed twin), the bottom range
`[⊥, end_.key)`. The cross-free nonempty truncated *forward* result with a pinned end there
is certified by `minimal_truncatedRangeBottom_of_nonpos` (the bottom truncated range
`[⊥, keyAfter last reported)`), and the cross-free nonempty truncated *reversed* result with
an overshooting end by `minimal_topOfLast_of_end_offset_ge_two_rev_nonpos` (the unbounded top
from the least reported key, `[last reported, ⊤)`), and the cross-free nonempty truncated
*reversed* result with `end.offset = 1` by
`minimal_truncatedRangeRev_of_end_offset_one_nonpos` (the reversed truncated range
`[last reported, end_.key)`), and the crossed nonempty complete *forward* overshoot at
`begin.offset = 0` by `minimal_topOfHead_of_zero_begin_crossed_overshoot` (the top range
from the least reported key, `[head, ⊤)`), and the crossed nonempty complete *forward* result at
`begin.offset = 0`, `end.offset = 1` with `begin.key ≤ end_.key` by
`minimal_headToEnd_of_zero_begin_crossed_endOne` (the head range `[head, end_.key)`). The
remaining branches were found
to be refutable as stated (an unobservable end anchor, or a bottom lower end that
is only forced when the empty key is necessary), so they are not posed as
conjectures.
The transcription follows FoundationDB's conventions: its `RangeResult` is
always ascending, so `result[0]` is the least reported key and
`result.end()[-1]` the greatest, while a reversed formal `Result.keys` is
descending, so `res.keys.head` is the greatest and `res.keys.getLast` the
least. The two `rangeBegin`/`rangeEnd` clamp steps mirror the
`end.getKey() < rangeBegin` and `begin.getKey() > rangeEnd` adjustments at
`NativeAPI.actor.cpp:4776` and `:4788`. -/
/-- FoundationDB's client conflict range (`getRangeFinished`,
`NativeAPI.actor.cpp:4739-4794`), parameterized by the `readToBegin` and
`readThroughEnd` flags. A `true` flag replaces the corresponding endpoint by
`⊥`/`⊤`. This records FoundationDB's choice; the formal development does not
assert it minimal on the uncertified branches (see the module docstring), except for
`minimal_canonicalRange_of_underEnd_empty_conj` on the empty `underEnd` case. -/
def fdbRange (r : RangeRead) (res : Result) (readToBegin readThroughEnd : Bool) :
ConflictRange :=
let b := r.begin.key
let e := r.end_.key
let head : WithTop Key := res.keys.headD ([] : Key)
let rangeBegin : WithTop Key :=
if readToBegin then (↑([] : Key) : WithTop Key)
else if (((r.reverse = false ∨ res.more = false ∨ 1 < r.begin.offset) ∧
0 < r.begin.offset) ∨ res.keys = []) then b
else head
let rangeBegin := if r.end_.offset > r.begin.offset ∧ e < rangeBegin then e else rangeBegin
let rangeEnd : WithTop Key :=
if readThroughEnd then ⊤
else if (((r.reverse = true ∨ res.more = false ∨ r.end_.offset ≤ 0) ∧
r.end_.offset ≤ 1) ∨ res.keys = []) then e
else (↑(keyAfter (res.keys.getLastD ([] : Key))) : WithTop Key)
let rangeEnd := if r.begin.offset < r.end_.offset ∧ rangeEnd < b then b else rangeEnd
⟨rangeBegin, rangeEnd⟩
/-- **The empty result, `begin.offset = 1`, `end_.offset ≤ 1`.** A read whose
universal window is empty (so the result is `⟨[], false⟩`) has the canonical range
`[begin.key, end.key)` as its minimal sound range, provided the read is not
trivially empty. The `hgap : ¬ AlwaysEmpty r` hypothesis is essential, not
cosmetic: under `AlwaysEmpty` the empty range is already minimal
(`minimal_emptyRange_of_alwaysEmpty`), so `Minimal.toSet_eq` forces every minimal
range to denote `∅`, and a nonempty canonical range would contradict it.
FoundationDB reaches the same range through the `result.size() == 0` arm of
`getRangeFinished` (`NativeAPI.actor.cpp:4770` and `:4782`), which takes both
endpoints from the selector keys; here it is stated as the canonical range so it
hooks directly into the `underEnd`/empty branch of `conflictRangePartial`. This is
the former conjecture, now discharged by `minimal_canonicalRange_of_underEnd_empty`. -/
theorem minimal_canonicalRange_of_underEnd_empty_conj {r : RangeRead} {res : Result}
(hread : Readable r res) (hgap : ¬ AlwaysEmpty r) (hb : beginOne r) (he : underEnd r)
(hmore : res.more = false) (hempty : res.keys = []) :
Minimal r res (canonicalRange r) :=
minimal_canonicalRange_of_underEnd_empty hread hgap hb he hmore hempty
/-- **The empty flip witness for a key.** A database compatible with the empty result
whose membership flip at `k` breaks compatibility. This is the object the factor-toggle
lemma consumes, and an abstract `Minimal` does not expose it. -/
def EmptyWitness (r : RangeRead) (k : Key) : Prop :=
∃ db₀ : DB, RangeRead.Compatible db₀ r { keys := [], more := false } ∧
¬ RangeRead.Compatible (toggle db₀ k) r { keys := [], more := false }
/-- **The witness-exposing empty inference.** The empty theory in the form the general
reduction actually consumes: `emptyValue` is sound for every realizable empty read, and
every one of its keys comes with a flip witness. This is strictly stronger than
`EmptyInference` — and it is the strength the joint-base graft needs, because the
passage from a boundary read to the full pair is a factor-toggle, which requires a
witness database that `Minimal` alone does not carry. -/
def EmptyInferenceWitness : Prop :=
∀ r' : RangeRead, Readable r' { keys := [], more := false } →
Sound r' { keys := [], more := false } (emptyValue r') ∧
∀ k : Key, k ∈ emptyValue r' → EmptyWitness r' k
/-- **The witness oracle implies the abstract oracle.** Soundness is the first component;
each key of `emptyValue` is necessary by its flip witness (`necessary_of_toggle`); the
two give `Minimal` by `minimal_iff_sound_and_necessary`. -/
theorem emptyInference_of_witness (h : EmptyInferenceWitness) : EmptyInference := by
intro r' hr
obtain ⟨hs, hwit⟩ := h r' hr
exact minimal_iff_sound_and_necessary.mpr
⟨hs, fun k hk => necessary_of_toggle (hwit k hk)⟩
/-!
### Extracting the empty flip witnesses
The empty theory's necessity proofs already build, for each key of their value, a pair
of databases differing in that key and separated by compatibility. Those pairs are
exactly `EmptyWitness`; the lemmas below expose them, which is what the general
reduction's graft consumes. The constructions are the same as the corresponding
minimality proofs, restated at the witness level.
-/
/-- **The `underEnd` empty witness.** For a realizable non-trivially-empty read with
`begin.offset = 1`, `end.offset ≤ 1`, and an empty result, every key of the canonical
range has a flip witness: a database of exactly `m = (1 - end.offset).toNat` keys of
`[begin.key, end.key)` avoiding the key, compatible with the empty result, whose flip at
the key exceeds the bound. -/
theorem emptyWitness_underEnd {r : RangeRead} (hgap : ¬ AlwaysEmpty r)
(hbegin : r.begin.offset = 1) (hend : r.end_.offset ≤ 1) {k : Key}
(hk : k ∈ canonicalRange r) : EmptyWitness r k := by
set m : ℕ := (1 - r.end_.offset).toNat with hm
have hm1 : m + 1 = (2 - r.end_.offset).toNat := by
have h1 : (0 : ℤ) ≤ 1 - r.end_.offset := by omega
have h2 : (0 : ℤ) ≤ 2 - r.end_.offset := by omega
apply Nat.cast_injective (R := ℤ)
rw [Nat.cast_add, Nat.cast_one, hm, Int.toNat_of_nonneg h1, Int.toNat_of_nonneg h2]
omega
have hroom : (m + 1 : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by
have h := two_sub_oE_le_intervalCard_canonical hbegin hend hgap
rwa [← hm1] at h
obtain ⟨db₀, hdb₀range, hkndb, hlen⟩ :=
exists_db_keysIn_avoid (B := r.begin.key) (E := r.end_.key) hroom
have hcan₀ : (canonicalRange r).keys db₀ = db₀.keys :=
canonicalRange_keys_eq_self_of_forall fun x hx => hdb₀range x hx
have hcomp₀ : RangeRead.Compatible db₀ r { keys := [], more := false } := by
rw [compatible_empty_iff_length_le_any (db := db₀) hbegin hend, hcan₀, hlen]
have hcan₁ : (canonicalRange r).keys (db₀.insert k hkndb) =
(db₀.insert k hkndb).keys := by
refine canonicalRange_keys_eq_self_of_forall fun x hx => ?_
rw [DB.mem_insert_iff hkndb] at hx
rcases hx with rfl | hx
· exact hk
· exact hdb₀range x hx
have hlen₁ : ((canonicalRange r).keys (db₀.insert k hkndb)).length = m + 1 := by
rw [hcan₁, DB.insert_keys, List.orderedInsert_length, hlen]
have hnot : ¬ RangeRead.Compatible (db₀.insert k hkndb) r
{ keys := [], more := false } := by
rw [compatible_empty_iff_length_le_any (db := db₀.insert k hkndb) hbegin hend, hlen₁]
omega
refine ⟨db₀, hcomp₀, ?_⟩
rwa [show toggle db₀ k = db₀.insert k hkndb from by
unfold toggle; rw [dite_eq_right hkndb]]
/-- **The `underEnd` empty witness at a general positive begin offset.** For a
realizable non-trivially-empty read with `1 ≤ begin.offset`, `end.offset ≤ 1`, and
`begin.key ≤ end.key`, every key of the canonical range has a flip witness: a
database of exactly `b + k` keys of `[begin.key, end.key)` avoiding the key, where
`b = (begin.offset - 1).toNat` and `k = (1 - end.offset).toNat`, compatible with the
empty result (its canonical count minus `b` is `k`), whose flip at the key exceeds
the bound. This generalizes `emptyWitness_underEnd` to positive begin offsets. -/
theorem emptyWitness_underEnd_general {r : RangeRead} (hgap : ¬ AlwaysEmpty r)
(hbegin : 1 ≤ r.begin.offset) (hend : r.end_.offset ≤ 1) (hle : r.begin.key ≤ r.end_.key)
{k : Key} (hk : k ∈ canonicalRange r) : EmptyWitness r k := by
set b : ℕ := (r.begin.offset - 1).toNat with hb
set kk : ℕ := (1 - r.end_.offset).toNat with hkk
have hroom : (b + kk + 1 : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by
rw [hb, hkk]; exact add_add_one_le_intervalCard_canonical hbegin hend hle hgap
obtain ⟨db₀, hdb₀range, hkndb, hlen⟩ :=
exists_db_keysIn_avoid (B := r.begin.key) (E := r.end_.key) (k := k) (m := b + kk) hroom
have hcan₀ : (canonicalRange r).keys db₀ = db₀.keys :=
canonicalRange_keys_eq_self_of_forall fun x hx => hdb₀range x hx
have hcomp₀ : RangeRead.Compatible db₀ r { keys := [], more := false } := by
rw [compatible_empty_iff_length_sub_le_any (db := db₀) hbegin hend, hcan₀, hlen]
omega
have hcan₁ : (canonicalRange r).keys (db₀.insert k hkndb) =
(db₀.insert k hkndb).keys := by
refine canonicalRange_keys_eq_self_of_forall fun x hx => ?_
rw [DB.mem_insert_iff hkndb] at hx
rcases hx with rfl | hx
· exact hk
· exact hdb₀range x hx
have hlen₁ : ((canonicalRange r).keys (db₀.insert k hkndb)).length = b + kk + 1 := by
rw [hcan₁, DB.insert_keys, List.orderedInsert_length, hlen]
have hnot : ¬ RangeRead.Compatible (db₀.insert k hkndb) r
{ keys := [], more := false } := by
rw [compatible_empty_iff_length_sub_le_any (db := db₀.insert k hkndb) hbegin hend, hlen₁]
omega
refine ⟨db₀, hcomp₀, ?_⟩
rwa [show toggle db₀ k = db₀.insert k hkndb from by
unfold toggle; rw [dite_eq_right hkndb]]
/-- **The `underEnd` empty witness oracle, any positive begin offset and traversal.**
With `1 ≤ begin.offset` and `end.offset ≤ 1`, `emptyValue` is the canonical range
unless the read is trivially empty. Soundness is the any-traversal bound equivalence
`compatible_empty_iff_length_sub_le_any`; if `begin.key ≤ end.key` every canonical key
has a flip witness by `emptyWitness_underEnd_general`, and if `begin.key > end.key` the
read is trivially empty (`alwaysEmpty_of_begin_gt_end`), so `emptyValue` is the empty
range and has no keys to witness. -/
theorem emptyWitness_underEnd_gen (r : RangeRead) (hbegin : 1 ≤ r.begin.offset)
(hend : r.end_.offset ≤ 1)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hle : r.begin.key ≤ r.end_.key := by
by_contra h
exact hAE (alwaysEmpty_of_begin_gt_end hbegin hend (not_le.mp h))
have hv : emptyValue r = canonicalRange r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0), ite_eq_left hend]
refine ⟨?_, ?_⟩
· rw [hv]
intro db₁ db₂ hagree
rw [compatible_empty_iff_length_sub_le_any (db := db₁) hbegin hend,
compatible_empty_iff_length_sub_le_any (db := db₂) hbegin hend,
show (canonicalRange r).keys db₁ = (canonicalRange r).keys db₂ from hagree]
· intro k hk
rw [hv] at hk
exact emptyWitness_underEnd_general hAE hbegin hend hle hk
/-- **The cross-free overshoot empty witness.** With `begin.offset = 1`,
`end.offset ≥ 2`, `begin.key ≤ end.key`, and an empty result, every key of the top range
`[begin.key, ⊤)` has a flip witness: the empty result is compatible exactly when the top
range stores nothing, so inserting the key into any compatible database makes the top
range (and hence the complete keys) nonempty. -/
theorem emptyWitness_crossFree {r : RangeRead}
(hread : Readable r { keys := [], more := false })
(hbegin : r.begin.offset = 1) (hend : 2 ≤ r.end_.offset) (hle : r.begin.key ≤ r.end_.key)
{k : Key} (hk : k ∈ topRange r) : EmptyWitness r k := by
obtain ⟨db₀, hdb₀⟩ := hread
have h0nil : (topRange r).keys db₀ = [] :=
(completeKeys_eq_nil_iff_topRange_keys_eq_nil (db := db₀) hbegin hend hle).mp
((compatible_empty_iff_complete_nil (db := db₀) (r := r)).mp hdb₀)
have hknot : k ∉ db₀.keys := by
intro hkmem
have : k ∈ (topRange r).keys db₀ := ConflictRange.mem_keys_iff.mpr ⟨hkmem, hk⟩
rw [h0nil] at this; exact List.not_mem_nil this
refine ⟨db₀, hdb₀, ?_⟩
rw [show toggle db₀ k = db₀.insert k hknot from by
unfold toggle; rw [dite_eq_right hknot]]
intro hcomp₁
have h1ne : (topRange r).keys (db₀.insert k hknot) ≠ [] := by
intro hnil
have : k ∈ (topRange r).keys (db₀.insert k hknot) :=
ConflictRange.mem_keys_iff.mpr ⟨DB.mem_insert_self _ _ _, hk⟩
rw [hnil] at this; exact List.not_mem_nil this
exact h1ne ((completeKeys_eq_nil_iff_topRange_keys_eq_nil (db := db₀.insert k hknot)
hbegin hend hle).mp ((compatible_empty_iff_complete_nil
(db := db₀.insert k hknot) (r := r)).mp hcomp₁))
/-- **The crossed empty witness at or above `B`.** At `begin.offset = 1`,
`end.offset ≥ 2`, `end.key < begin.key`, the empty database is compatible and inserting
any `k ≥ begin.key` is incompatible, so every such key of `[begin.key, ⊤)` has a flip
witness. This covers the `[begin.key, ⊤)` branch of `crossedRange`. -/
theorem emptyWitness_crossed_beginLe {r : RangeRead}
(hbegin : r.begin.offset = 1) (hoE : 2 ≤ r.end_.offset)
{k : Key} (hk : r.begin.key ≤ (k : WithTop Key)) : EmptyWitness r k := by
have hk0 : k ∉ emptyDB.keys := by simp [emptyDB]
refine ⟨emptyDB, compatible_emptyDB_emptyRes r, ?_⟩
rw [show toggle emptyDB k = emptyDB.insert k hk0 from by
unfold toggle; rw [dite_eq_right hk0]]
intro hc
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_counts hbegin (by omega)] at hc
have hkB : ¬ (k : WithTop Key) < r.begin.key := not_lt.mpr hk
have hcntB : cnt (emptyDB.insert k hk0) r.begin.key = 0 := by
rw [cnt_insert_not_lt emptyDB k hk0 hkB]
simp [cnt, emptyDB]
have hlen : (emptyDB.insert k hk0).keys.length = 1 := by
rw [DB.insert_keys]; simp [emptyDB]
have h1 : 1 ≤ (r.end_.offset - 1).toNat := by omega
rw [hcntB, hlen] at hc
omega
/-- **The crossed empty witness inside `[E, B)`.** In the long-gap branch every genuine
`k` with `end.key ≤ k < begin.key` has a flip witness: the base stores `oE - 2` keys of
`[E, B)` plus a key `j ≥ B`, so `ψ` fails, while inserting `k` makes the `[E, B)` count
reach `oE - 1` and satisfies the second disjunct. -/
theorem emptyWitness_crossed_interval {r : RangeRead}
(hbegin : r.begin.offset = 1) (hoE : 2 ≤ r.end_.offset) (hne : ¬ AlwaysEmpty r)
(hgap : ((r.end_.offset - 1).toNat : ℕ∞) ≤ intervalCard r.end_.key r.begin.key)
{k : Key} (hkE : r.end_.key ≤ (k : WithTop Key))
(hkB : (k : WithTop Key) < r.begin.key) : EmptyWitness r k := by
have hBne : r.begin.key ≠ (⊤ : WithTop Key) :=
begin_key_ne_top_of_not_alwaysEmpty (by omega) hne
obtain ⟨b, hb⟩ : ∃ b : Key, r.begin.key = (↑b : WithTop Key) := by
cases hkb : r.begin.key with
| top => exact absurd hkb hBne
| coe b => exact ⟨b, rfl⟩
have hEne : r.end_.key ≠ (⊤ : WithTop Key) := by
intro htop; rw [htop] at hkE; exact not_le.mpr (WithTop.coe_lt_top k) hkE
obtain ⟨e, he⟩ : ∃ e : Key, r.end_.key = (↑e : WithTop Key) := by
cases hke : r.end_.key with
| top => exact absurd hke hEne
| coe e => exact ⟨e, rfl⟩
have hkltb : k < b := by rw [hb] at hkB; exact WithTop.coe_lt_coe.mp hkB
have hke' : e ≤ k := by rw [he] at hkE; exact WithTop.coe_le_coe.mp hkE
have hee : e ≤ b := le_trans hke' (le_of_lt hkltb)
set m : ℕ := (r.end_.offset - 2).toNat with hm
have hm1 : m + 1 = (r.end_.offset - 1).toNat := by
rw [hm]
have h3 : (0 : ℤ) ≤ r.end_.offset - 2 := by omega
have h4 : (0 : ℤ) ≤ r.end_.offset - 1 := by omega
have : (((r.end_.offset - 2).toNat + 1 : ℕ) : ℤ) = (r.end_.offset - 1).toNat := by
rw [Nat.cast_add, Nat.cast_one, Int.toNat_of_nonneg h3, Int.toNat_of_nonneg h4]
ring
exact_mod_cast this
have hcard : (m + 1 : ℕ∞) ≤ intervalCard r.end_.key r.begin.key :=
calc (m + 1 : ℕ∞) = ((m + 1 : ℕ) : ℕ∞) := rfl
_ = ((r.end_.offset - 1).toNat : ℕ∞) := by rw [hm1]
_ ≤ intervalCard r.end_.key r.begin.key := hgap
obtain ⟨dbK, hdbKrange, hkK, hlenK⟩ :=
exists_db_keysIn_avoid (B := r.end_.key) (E := r.begin.key) (k := k) (m := m) hcard
have hdbKe : ∀ x ∈ dbK.keys, e ≤ x := by
intro x hx
have h := (hdbKrange x hx).1
rw [he] at h; exact WithTop.coe_le_coe.mp h
have hdbKb : ∀ x ∈ dbK.keys, x < b := by
intro x hx
have h := (hdbKrange x hx).2
rw [hb] at h; exact WithTop.coe_lt_coe.mp h
have hcntE : cnt dbK (↑e : WithTop Key) = 0 := by
rw [cnt_coe]; exact countP_lt_eq_zero_of_forall_ge hdbKe
have hcntB : cnt dbK (↑b : WithTop Key) = m := by
rw [cnt_coe, countP_lt_eq_length_of_forall_lt hdbKb, hlenK]
obtain ⟨j, hjb, hjK⟩ := exists_le_not_mem dbK.keys b
have hjnotin : j ∉ dbK.keys := hjK
have hcntE₂ : cnt (dbK.insert j hjnotin) (↑e : WithTop Key) = 0 := by
rw [cnt_insert_not_lt dbK j hjnotin (v := (↑e : WithTop Key)), hcntE]
rw [WithTop.coe_lt_coe]; intro hlt
exact absurd hlt (not_lt.mpr (le_trans hee hjb))
have hcntB₂ : cnt (dbK.insert j hjnotin) (↑b : WithTop Key) = m := by
rw [cnt_insert_not_lt dbK j hjnotin (v := (↑b : WithTop Key)), hcntB]
rw [WithTop.coe_lt_coe]; exact not_lt.mpr hjb
have hlen₂ : (dbK.insert j hjnotin).keys.length = m + 1 := by
rw [DB.insert_keys, List.orderedInsert_length, hlenK]
have hk_db2 : k ∉ (dbK.insert j hjnotin).keys := by
rw [DB.mem_insert_iff hjnotin]
rintro (rfl | hk)
· exact absurd hkltb (not_lt.mpr hjb)
· exact hkK hk
have hnot₂ : ¬ RangeRead.Compatible (dbK.insert j hjnotin) r
{ keys := [], more := false } := by
intro hc
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_counts hbegin (by omega)] at hc
have hcntE₂' : cnt (dbK.insert j hjnotin) r.end_.key = 0 := by rw [he]; exact hcntE₂
have hcntB₂' : cnt (dbK.insert j hjnotin) r.begin.key = m := by rw [hb]; exact hcntB₂
rcases hc with hc | hc
· rw [hcntB₂', hlen₂] at hc; omega
· rw [hcntE₂', hcntB₂'] at hc; omega
have hcntB₁ : cnt ((dbK.insert j hjnotin).insert k hk_db2)
(↑b : WithTop Key) = (r.end_.offset - 1).toNat := by
rw [cnt_insert_lt _ k hk_db2 (v := (↑b : WithTop Key)) (WithTop.coe_lt_coe.mpr hkltb),
hcntB₂]
exact hm1
have hcntE₁ : cnt ((dbK.insert j hjnotin).insert k hk_db2)
(↑e : WithTop Key) = 0 := by
rw [cnt_insert_not_lt _ k hk_db2 (v := (↑e : WithTop Key)), hcntE₂]
rw [WithTop.coe_lt_coe]; exact not_lt.mpr hke'
have hcomp₁ : RangeRead.Compatible ((dbK.insert j hjnotin).insert k hk_db2) r
{ keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_counts hbegin (by omega)).mpr (Or.inr (by
rw [hb, he, hcntE₁, hcntB₁, zero_add])))
refine ⟨(dbK.insert j hjnotin).insert k hk_db2, hcomp₁, ?_⟩
have hkeys : (toggle ((dbK.insert j hjnotin).insert k hk_db2) k).keys =
(dbK.insert j hjnotin).keys := by
rw [toggle, dite_eq_left (DB.mem_insert_self _ _ _)]
exact DB.erase_insert_keys _ k hk_db2
intro hc
exact hnot₂ ((RangeRead.compatible_congr
(RangeRead.completeKeys_congr hkeys r)).mp hc)
/-- The reported interval `[k₀, keyAfter kₙ)` of a nonempty result: from the least
reported key through just past the greatest. This is the middle component of the
complete value. -/
def reportedRange (r : RangeRead) (res : Result) : ConflictRange :=
⟨(leastReported r res : WithTop Key),
(keyAfter (greatestReported r res) : WithTop Key)⟩
/-- **Necessity of the reported interval, any traversal.** Every key of the reported
interval `[k₀, keyAfter kₙ)` is necessary for the full pair, unconditionally: the two
extremes are reported keys (`necessary_of_mem_result`) and every key between them is
convex (`Necessary.of_between`). This is the middle factor of the assembled range and
needs no empty theory. -/
theorem necessaryRange_reportedRange {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ []) :
NecessaryRange r res (reportedRange r res).begin (reportedRange r res).end_ := by
intro k hlo hhi
simp only [reportedRange] at hlo hhi
have hle : leastReported r res ≤ k := WithTop.coe_le_coe.mp hlo
have hkg : k ≤ greatestReported r res :=
(lt_keyAfter_iff k (greatestReported r res)).mp (WithTop.coe_lt_coe.mp hhi)
have hmem_lo : leastReported r res ∈ res.keys := by
unfold leastReported
split
· exact getLastD_mem hne
· exact headD_mem hne
have hmem_hi : greatestReported r res ∈ res.keys := by
unfold greatestReported
split
· exact headD_mem hne
· exact getLastD_mem hne
exact (necessary_of_mem_result hread hmem_lo).of_between
(necessary_of_mem_result hread hmem_hi) hle hkg
/-- **The begin (low) contribution: the lower boundary read's empty value.** This is
the empty-result inference applied to `boundaryReadLo r k₀`, the read that keeps the
full begin selector and ends at the least reported key `k₀`. -/
def lowBound (r : RangeRead) (res : Result) : ConflictRange :=
emptyValue (boundaryReadLo r (leastReported r res))
/-- **The end (high) contribution: the upper boundary read's empty value.** This is
the empty-result inference applied to `boundaryReadHi r kₙ`, the read that begins just
past the greatest reported key `kₙ` and keeps the full end selector. Its crossed branch
is what carries the case where a reported key is at or above `end.key`. -/
def highBound (r : RangeRead) (res : Result) : ConflictRange :=
emptyValue (boundaryReadHi r (greatestReported r res))
/-- Forward truncated value: `[w, keyAfter kₙ)`, the begin selector's empty
contribution plus the reported keys, with the bare successor upper end. -/
def forwardTruncatedRange (r : RangeRead) (res : Result) : ConflictRange :=
⟨(lowBound r res).begin, (keyAfter (greatestReported r res) : WithTop Key)⟩
/-- Reverse truncated value: `[kₙ, u)`, the reported keys plus the end selector's
empty contribution, with the bare end upper end and no begin contribution. -/
def reverseTruncatedRange (r : RangeRead) (res : Result) : ConflictRange :=
⟨(leastReported r res : WithTop Key), (highBound r res).end_⟩
/-- Complete value: the hull of the lower boundary contribution, the reported
interval, and the upper boundary contribution: `hull (hull W M) U`. The reported
interval is an explicit component, so its keys are always covered and a degenerate
boundary contribution cannot drag an endpoint past it (`hull` drops empty
components). -/
def completeRange (r : RangeRead) (res : Result) : ConflictRange :=
hull (hull (lowBound r res) (reportedRange r res)) (highBound r res)
/-- **The empty-result boundary hypothesis: `ψ` extended from the complete value's own
endpoints to the reported keys.** Everything from the complete value's lower end up to
the least reported key is necessary, and everything from just past the greatest reported
key up to the complete value's upper end is necessary. This is the empty inference's
`ψ` at the two boundary reads, transferred to the *full* pair and stretched across the
half-open gaps on either side of the reported keys (the joint-base transfer of section
7). It is a hypothesis precisely because an abstract `Minimal` statement about the
boundary pair does not expose the flip witness that transfer needs. -/
def BoundaryNecessity (r : RangeRead) (res : Result) : Prop :=
NecessaryRange r res (completeRange r res).begin (reportedRange r res).begin ∧
NecessaryRange r res (reportedRange r res).end_ (completeRange r res).end_
/-- **The bracket-observability residue.** Agreement on the complete value fixes the
bracketing predicate, i.e. whether the resolved endpoints straddle the reported span.
This is the bracket-observability equation: the one bridge factor that the emptiness
and interval equality factors do not imply. It is discharged by the empty theory's gap split at
positive offsets (the stored counts in `[begin.key, k₀)` and `[end.key, kₙ)`), which is
why the pins `resolve begin = k₀` / `resolve end_ = keyAfter kₙ` do not by themselves
remove it. -/
def BracketObservable (r : RangeRead) (res : Result) : Prop :=
∀ db₁ db₂ : DB, AgreeOn (completeRange r res) db₁ db₂ →
(bracket r res.keys db₁ ↔ bracket r res.keys db₂)
/-- The bracket-observability residue for a reversed read: the bridge is stated on the
ascending list `res.keys.reverse`, so the bracket is taken there. -/
def BracketObservableRev (r : RangeRead) (res : Result) : Prop :=
∀ db₁ db₂ : DB, AgreeOn (completeRange r res) db₁ db₂ →
(bracket r res.keys.reverse db₁ ↔ bracket r res.keys.reverse db₂)
/-- The bracket-observability residue, selected by traversal. It is the only soundness
factor not derived from `EmptyInference`; the complete branch's minimality is reduced to
it in `minimal_completeRange_of_factors`/`_rev`. -/
def BracketFactor (r : RangeRead) (res : Result) : Prop :=
if r.reverse then BracketObservableRev r res else BracketObservable r res
/-- **The complete branch's value.** In the canonical region `1 ≤ begin.offset ∧
end.offset ≤ 1` the minimal sound range is the canonical range `[begin.key, end.key)`
(`minimal_canonicalRange_of_end_offset_le_one_general`), *not* the hull: at a
nonpositive end offset the hull's empty-aware glue moves `W`'s endpoint up to the
least reported key, dropping the genuinely necessary canonical keys that lie below
it. In the overshoot region at `begin.offset ≥ 1` the resolved end is past the data
(`minimal_topRange_of_end_offset_ge_two_general`), so the value is the unbounded top
range `[begin.key, ⊤)`. Elsewhere the complete value remains the hull assembly
`completeRange`.
The remaining uncertified regions are two, both refuted as *sound* claims rather than
merely open:
* the crossed selector order with `end.key = ⊥`, positive `begin.offset`, and an end
offset between two and the begin offset (so not `overshoot`, since `⊥` is below every
nonempty key): there the hull need not be minimal;
* the `begin.offset ≠ 1` cell at an overshooting-free end, where the resolved begin may
clamp to `⊤` on one side of an agreement and to a stored key on the other, so the hull
is *unsound* (a compatible witness refutes it). That cell has no
single minimal shape either: the bare-successor value (the successor of the greatest
reported key) at `end.offset = 2` fails once the end selector's slack runs the window
past the reported last, as a compatible witness shows, with every key necessary and
the true value the unbounded top.
`conflictRangePartial` returns `none` on both, so `completeValue` is a totalization
whose hull fallback is not correct off the canonical and overshoot regions. -/
def completeValue (r : RangeRead) (res : Result) : ConflictRange :=
if 1 ≤ r.begin.offset ∧ r.end_.offset ≤ 1 then canonicalRange r
else if 1 ≤ r.begin.offset ∧ overshoot r res then topRange r
else completeRange r res
/-- **The general algorithm's value, by reduction to the empty boundary reads.** The
result is dispatched on emptiness, truncation, and traversal:
* an empty result uses the empty theory's value `emptyValue`;
* a forward truncated result is `[lowBound.begin, keyAfter kₙ)`, the begin selector's
empty contribution plus the reported keys;
* a reverse truncated result is `[kₙ, highBound.end_)`, the reported keys plus the end
selector's empty contribution, the begin selector dropping out;
* a complete result is `completeValue`, the canonical range in the canonical region and
the hull of the two boundary reads' minimal ranges `hull (lowBound r res) (highBound r res)`
elsewhere.
The low and high contributions are the empty boundary reads' minimal ranges, each the
empty range when its read is trivially empty; the definition is computable.
**This is a provisional totalization, not the headline algorithm.** The
certified algorithm is `conflictRangePartial`; `conflictRangeVal` is the
every-input `ConflictRange`-valued wrapper, and its branches off the certified
region (the truncated dispatch and the `completeValue` hull fallback) are *not*
sound in general — explicit counterexamples in the complete hull and in the
truncated branches record this. Its correctness
theorems (`conflictRangeVal_spec`, `_spec_of_witness`, `_spec_complete`) are stated
relative to the conditional `EmptyTheoryComplete` and are consequently vacuous, not
the headline claim. The unconditional statement is proved in `Proof.lean`. -/
def conflictRangeVal (r : RangeRead) (res : Result) : ConflictRange :=
if res.keys = [] then
emptyValue r
else if res.more = true then
if r.reverse = true then reverseTruncatedRange r res
else forwardTruncatedRange r res
else
completeValue r res
/-!
## The complete branch: the assembled hull
The complete branch is the reduction: the hull of the two boundary reads'
minimal ranges and the reported interval, necessary on the two boundary ranges
(`BoundaryNecessity`) and the derived interior, and sound from `EmptyInference` once the
bracket residue is supplied. -/
/-- The complete value is the hull of the lower contribution, the reported
interval, and the upper contribution, `hull (hull W M) U`. -/
theorem completeRange_eq_hull (r : RangeRead) (res : Result) :
completeRange r res =
hull (hull (lowBound r res) (reportedRange r res)) (highBound r res) := rfl
/-- The reported interval is a subrange of the complete value: the reported keys are
always covered, whichever way the boundary contributions land. -/
theorem subrange_completeRange_reported (r : RangeRead) (res : Result) :
Subrange (reportedRange r res) (completeRange r res) :=
Subrange.trans (subrange_hull_right _ _) (subrange_hull_left _ _)
/-- Each boundary contribution is a subrange of the complete value. -/
theorem subrange_completeRange_lowBound (r : RangeRead) (res : Result) :
Subrange (lowBound r res) (completeRange r res) :=
Subrange.trans (subrange_hull_left _ _) (subrange_hull_left _ _)
/-- Each boundary contribution is a subrange of the complete value. -/
theorem subrange_completeRange_highBound (r : RangeRead) (res : Result) :
Subrange (highBound r res) (completeRange r res) :=
subrange_hull_right _ _
/-- **Necessity of the complete value from the boundary `ψ`.** The first conjunct of
`BoundaryNecessity` covers `[R.begin, k₀)`, the reported interval `[k₀, keyAfter kₙ)` is
necessary unconditionally (`necessaryRange_reportedRange`), and the second conjunct
covers `[keyAfter kₙ, R.end)`. The three chain to exactly `[R.begin, R.end)`. -/
theorem necessaryRange_completeRange_of_boundaryNecessity {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ [])
(hψ : BoundaryNecessity r res) :
NecessaryRange r res (completeRange r res).begin (completeRange r res).end_ :=
(hψ.1.trans (necessaryRange_reportedRange hread hne)).trans hψ.2
/-- **Minimality of the complete value from the boundary `ψ` and soundness.** Soundness
of the hull plus the necessary range derived above give minimality by
`minimal_iff_sound_and_necessaryRange`. The interior necessity is derived
(`necessaryRange_reportedRange`), so — beyond soundness — the only content is the empty
`ψ` at the two boundaries, stretched to the complete value's endpoints. -/
theorem minimal_completeRange_of_boundaryNecessity {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ [])
(hψ : BoundaryNecessity r res)
(hs : Sound r res (completeRange r res)) :
Minimal r res (completeRange r res) :=
minimal_iff_sound_and_necessaryRange.mpr
⟨hs, necessaryRange_completeRange_of_boundaryNecessity hread hne hψ⟩
/-!
## Boundary necessity, forward complete, from the begin/end key theorems
Away from the joint-base construction, `BoundaryNecessity`'s two ranges follow directly
from the existing end-key necessity theorems plus convexity: the reported keys are
necessary (`necessary_of_mem_result`), and the selector keys fill the gaps. These supply
`BoundaryNecessity` in the non-crossed, positive-offset region without any database
graft.
-/
/-- **Lower boundary necessity, forward.** At a positive begin offset the begin key is
necessary (`necessary_begin_key`) and the least reported key is necessary; convexity
fills `[begin.key, k₀)`. -/
theorem necessaryRange_low_fwd {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hne : res.keys ≠ [])
(hoff : 1 ≤ r.begin.offset) {v : Key} (hkey : r.begin.key = (↑v : WithTop Key)) :
NecessaryRange r res r.begin.key ((leastReported r res : Key) : WithTop Key) := by
have hlen : 0 < res.keys.length := List.length_pos_of_ne_nil hne
have hv : Necessary r res v := necessary_begin_key hread hrev hlen hoff hkey
have hhead : leastReported r res = res.keys.headD ([] : Key) := by simp [leastReported, hrev]
have hk0 : Necessary r res (leastReported r res) := by
rw [hhead]; exact necessary_of_mem_result hread (headD_mem hne)
intro k hlo hhi
rw [hkey] at hlo
exact hv.of_between hk0 (WithTop.coe_le_coe.mp hlo) (le_of_lt (WithTop.coe_lt_coe.mp hhi))
/-- **Upper boundary necessity, forward.** With an end offset at most one, the keys from
`keyAfter kₙ` up to `end_.key` are necessary (`necessary_last_to_end_key`). -/
theorem necessaryRange_high_fwd {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hne : res.keys ≠ []) (hend : r.end_.offset ≤ 1) :
NecessaryRange r res ((keyAfter (greatestReported r res) : Key) : WithTop Key)
r.end_.key := by
have hgreat : greatestReported r res = res.keys.getLastD ([] : Key) := by
simp [greatestReported, hrev]
have hlastD : res.keys.getLast hne = res.keys.getLastD ([] : Key) := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
intro k hlo hhi cr hs
have hk0 : res.keys.getLastD ([] : Key) < k := by
by_contra hcon
have hle : k ≤ res.keys.getLastD ([] : Key) := le_of_not_gt hcon
have : (k : WithTop Key) < (↑(keyAfter (res.keys.getLastD ([] : Key))) : WithTop Key) :=
WithTop.coe_lt_coe.mpr ((lt_keyAfter_iff k (res.keys.getLastD ([] : Key))).mpr hle)
rw [hgreat] at hlo
exact absurd hlo (not_le.mpr this)
exact necessary_last_to_end_key hread hrev hmore hne hend cr hs
(by rw [hlastD]; exact le_of_lt hk0) hhi
/-! ### Hull endpoint identities -/
/-- The hull of two abutting intervals `[x, y)` and `[y, z)` is `[x, z)`. -/
theorem hull_abut (x y z : WithTop Key) (hxy : x ≤ y) (hyz : y ≤ z) :
hull (⟨x, y⟩ : ConflictRange) ⟨y, z⟩ = ⟨x, z⟩ := by
unfold hull
by_cases h : (⟨x, y⟩ : ConflictRange).IsEmpty
· rw [ite_eq_left h]
have : y = x := le_antisymm (by simpa [ConflictRange.IsEmpty] using h) hxy
rw [this]
· rw [ite_eq_right h]
by_cases h2 : (⟨y, z⟩ : ConflictRange).IsEmpty
· rw [ite_eq_left h2]
have : z = y := le_antisymm (by simpa [ConflictRange.IsEmpty] using h2) hyz
rw [this]
· rw [ite_eq_right h2]
rw [min_eq_left hxy, max_eq_right hyz]
/-- The hull of three abutting intervals `[B, a)`, `[a, b)`, `[b, c)` is `[B, c)`. -/
theorem hull3 (B a b c : WithTop Key) (hBa : B ≤ a) (hab : a ≤ b) (hbc : b ≤ c) :
hull (hull (⟨B, a⟩ : ConflictRange) ⟨a, b⟩) ⟨b, c⟩ = ⟨B, c⟩ := by
rw [hull_abut B a b hBa hab, hull_abut B b c (le_trans hBa hab) hbc]
/-- For a non-reversed read the least reported key is at or below the greatest. -/
theorem least_le_greatest_fwd {r : RangeRead} {res : Result} (hrev : r.reverse = false)
(hpair : res.keys.Pairwise (· < ·)) (hne : res.keys ≠ []) :
leastReported r res ≤ greatestReported r res := by
have hleast : leastReported r res = res.keys.headD ([] : Key) := by simp [leastReported, hrev]
have hgreat : greatestReported r res = res.keys.getLastD ([] : Key) := by
simp [greatestReported, hrev]
rw [hleast, hgreat]
exact headD_le_of_pairwise hpair (getLastD_mem hne)
/-!
## Hull soundness from the empty inference
The bridge is a four-way conjunction. Three of its factors transfer from `EmptyInference`
by the shape of the assembled value: the two boundary emptinesses restrict agreement on
the complete value to each boundary contribution (`subrange_completeRange_lowBound` /
`_highBound`) and read off the empty inference's soundness there; the middle interval
restricts to `reportedRange`. The fourth, `bracket`, is the observability residue: it
asks that the resolved endpoints stay outside the reported span, which the other three
factors do not force. It is isolated as a hypothesis here.
-/
/-- The empty inference applies to every read: the empty database is always compatible
with the empty result, so every read is empty-realizable. -/
theorem emptyInference_minimal (h : EmptyInference) (r : RangeRead) :
Minimal r { keys := [], more := false } (emptyValue r) :=
h r ⟨emptyDB, compatible_emptyDB_emptyRes r⟩
/-- The lower boundary read's emptiness is agreement-invariant: agreement on the
complete value restricts to the lower contribution, and the empty inference says that
contribution is sound for the boundary pair, whose compatibility is exactly boundary
emptiness (`compatible_empty_iff_complete_nil`). -/
theorem boundaryLo_empty_iff_of_agree (h : EmptyInference) (r : RangeRead) (res : Result)
{db₁ db₂ : DB} (hag : AgreeOn (completeRange r res) db₁ db₂) :
RangeRead.completeKeys db₁ (boundaryReadLo r (leastReported r res)) = [] ↔
RangeRead.completeKeys db₂ (boundaryReadLo r (leastReported r res)) = [] := by
have hsnd := (emptyInference_minimal h (boundaryReadLo r (leastReported r res))).sound
have hag' : AgreeOn (lowBound r res) db₁ db₂ :=
keys_eq_of_subrange_agree (subrange_completeRange_lowBound r res) hag
have hh := hsnd db₁ db₂ hag'
simpa only [compatible_empty_iff_complete_nil] using hh
/-- The upper boundary read's emptiness is agreement-invariant, dually. -/
theorem boundaryHi_empty_iff_of_agree (h : EmptyInference) (r : RangeRead) (res : Result)
{db₁ db₂ : DB} (hag : AgreeOn (completeRange r res) db₁ db₂) :
RangeRead.completeKeys db₁ (boundaryReadHi r (greatestReported r res)) = [] ↔
RangeRead.completeKeys db₂ (boundaryReadHi r (greatestReported r res)) = [] := by
have hsnd := (emptyInference_minimal h (boundaryReadHi r (greatestReported r res))).sound
have hag' : AgreeOn (highBound r res) db₁ db₂ :=
keys_eq_of_subrange_agree (subrange_completeRange_highBound r res) hag
have hh := hsnd db₁ db₂ hag'
simpa only [compatible_empty_iff_complete_nil] using hh
/-- The middle interval equality is agreement-invariant: it is the `reportedRange`'s
stored keys, and agreement on the complete value restricts to that subrange. -/
theorem midEq_iff_of_agree (r : RangeRead) (res : Result) (hrev : r.reverse = false)
{db₁ db₂ : DB} (hag : AgreeOn (completeRange r res) db₁ db₂) :
midEq res.keys db₁ ↔ midEq res.keys db₂ := by
have hag' : AgreeOn (reportedRange r res) db₁ db₂ :=
keys_eq_of_subrange_agree (subrange_completeRange_reported r res) hag
have hle : leastReported r res = res.keys.headD ([] : Key) := by simp [leastReported, hrev]
have hge : greatestReported r res = res.keys.getLastD ([] : Key) := by
simp [greatestReported, hrev]
have hiff : ∀ db, midEq res.keys db ↔ (reportedRange r res).keys db = res.keys := by
intro db
simp only [midEq, reportedRange, hle, hge, ConflictRange.keys_eq_inRange]
rw [hiff db₁, hiff db₂, hag']
/-- **Hull soundness, with the bracket isolated.** The three tractable bridge factors
transfer by `EmptyInference` and subrange agreement; the fourth, `bracket`, is the
observability residue, taken as `BracketObservable`. -/
theorem sound_completeRange_of_bracketTransfer {r : RangeRead} {res : Result}
(h : EmptyInference) (hrev : r.reverse = false) (hmore : res.more = false)
(hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· < ·))
(hlim : RangeRead.withinLimit r res.keys) (hbr : BracketObservable r res) :
Sound r res (completeRange r res) := by
obtain ⟨ks, m⟩ := res
simp only at hmore hL hpair hlim hbr ⊢
subst hmore
intro db₁ db₂ hag
have hle : leastReported r { keys := ks, more := false } = ks.headD ([] : Key) := by
simp [leastReported, hrev]
have hge : greatestReported r { keys := ks, more := false } = ks.getLastD ([] : Key) := by
simp [greatestReported, hrev]
rw [compatible_complete_iff_bridge hrev hL hpair hlim,
compatible_complete_iff_bridge hrev hL hpair hlim]
unfold bridge
rw [← hle, ← hge]
refine ⟨fun ⟨h1, h2, h3, h4⟩ => ⟨?_, ?_, ?_, ?_⟩,
fun ⟨h1, h2, h3, h4⟩ => ⟨?_, ?_, ?_, ?_⟩⟩
· exact (boundaryLo_empty_iff_of_agree h r _ hag).mp h1
· exact (boundaryHi_empty_iff_of_agree h r _ hag).mp h2
· exact (midEq_iff_of_agree r _ hrev hag).mp h3
· exact (hbr db₁ db₂ hag).mp h4
· exact (boundaryLo_empty_iff_of_agree h r _ hag).mpr h1
· exact (boundaryHi_empty_iff_of_agree h r _ hag).mpr h2
· exact (midEq_iff_of_agree r _ hrev hag).mpr h3
· exact (hbr db₁ db₂ hag).mpr h4
/-- The middle interval equality at the reversed reported list is agreement-invariant
(`midEq` uses the reported interval, whose stored keys are fixed by agreement). -/
theorem midEq_rev_iff_of_agree (r : RangeRead) (res : Result) (hrev : r.reverse = true)
{db₁ db₂ : DB} (hag : AgreeOn (completeRange r res) db₁ db₂) :
midEq res.keys.reverse db₁ ↔ midEq res.keys.reverse db₂ := by
have hag' : AgreeOn (reportedRange r res) db₁ db₂ :=
keys_eq_of_subrange_agree (subrange_completeRange_reported r res) hag
have hle : leastReported r res = res.keys.getLastD ([] : Key) := by simp [leastReported, hrev]
have hge : greatestReported r res = res.keys.headD ([] : Key) := by
simp [greatestReported, hrev]
have hiff : ∀ db, midEq res.keys.reverse db ↔
(reportedRange r res).keys db = res.keys.reverse := by
intro db
have h1 : res.keys.reverse.headD ([] : Key) = leastReported r res := by
rw [hle, List.headD_eq_head?, List.getLastD_eq_getLast?, List.head?_reverse]
have h2 : res.keys.reverse.getLastD ([] : Key) = greatestReported r res := by
rw [hge, List.getLastD_eq_getLast?, List.headD_eq_head?, List.getLast?_reverse]
simp only [midEq, reportedRange, h1, h2, ConflictRange.keys_eq_inRange]
rw [hiff db₁, hiff db₂, hag']
/-- **Hull soundness, with the bracket isolated, reverse traversal.** Dual to
`sound_completeRange_of_bracketTransfer`: the reported list is descending, so the bridge
is stated for `res.keys.reverse`. -/
theorem sound_completeRange_of_bracketTransfer_rev {r : RangeRead} {res : Result}
(h : EmptyInference) (hrev : r.reverse = true) (hmore : res.more = false)
(hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· > ·))
(hlim : RangeRead.withinLimit r res.keys)
(hbr : ∀ db₁ db₂ : DB, AgreeOn (completeRange r res) db₁ db₂ →
(bracket r res.keys.reverse db₁ ↔ bracket r res.keys.reverse db₂)) :
Sound r res (completeRange r res) := by
obtain ⟨ks, m⟩ := res
simp only at hmore hL hpair hlim hbr ⊢
subst hmore
have hpairr : ks.reverse.Pairwise (· < ·) := by simpa using hpair.reverse
intro db₁ db₂ hag
have hle : leastReported r { keys := ks, more := false } = ks.getLastD ([] : Key) := by
simp [leastReported, hrev]
have hge : greatestReported r { keys := ks, more := false } = ks.headD ([] : Key) := by
simp [greatestReported, hrev]
rw [compatible_complete_iff_bridge_rev hrev hL hpair hlim,
compatible_complete_iff_bridge_rev hrev hL hpair hlim]
unfold bridge
have hr1 : ks.reverse.headD ([] : Key) = ks.getLastD ([] : Key) := by
rw [List.headD_eq_head?, List.getLastD_eq_getLast?, List.head?_reverse]
have hr2 : ks.reverse.getLastD ([] : Key) = ks.headD ([] : Key) := by
rw [List.getLastD_eq_getLast?, List.headD_eq_head?, List.getLast?_reverse]
rw [hr1, hr2, ← hle, ← hge]
refine ⟨fun ⟨h1, h2, h3, h4⟩ => ⟨?_, ?_, ?_, ?_⟩,
fun ⟨h1, h2, h3, h4⟩ => ⟨?_, ?_, ?_, ?_⟩⟩
· exact (boundaryLo_empty_iff_of_agree h r _ hag).mp h1
· exact (boundaryHi_empty_iff_of_agree h r _ hag).mp h2
· exact (midEq_rev_iff_of_agree r _ hrev hag).mp h3
· exact (hbr db₁ db₂ hag).mp h4
· exact (boundaryLo_empty_iff_of_agree h r _ hag).mpr h1
· exact (boundaryHi_empty_iff_of_agree h r _ hag).mpr h2
· exact (midEq_rev_iff_of_agree r _ hrev hag).mpr h3
· exact (hbr db₁ db₂ hag).mpr h4
/-- **Hull soundness from `Readable`.** In the forward complete case `Readable` supplies
the pairwise, limit, and nonemptiness facts, so `EmptyInference` and `BracketObservable`
alone give soundness. -/
theorem sound_completeRange_of_emptyInference {r : RangeRead} {res : Result}
(h : EmptyInference) (hread : Readable r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hL : res.keys ≠ [])
(hbr : BracketObservable r res) :
Sound r res (completeRange r res) := by
obtain ⟨db₀, hcomp⟩ := hread
have heq : res.keys = RangeRead.completeKeys db₀ r := by
rcases hcomp.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
· simp [hmore] at hm
· exact heq
have hpair : res.keys.Pairwise (· < ·) := by
rw [heq]
rw [RangeRead.completeKeys, ite_eq_right (by simp [hrev])]
exact RangeRead.inRange_pairwise db₀ _ _
exact sound_completeRange_of_bracketTransfer h hrev hmore hL hpair hcomp.1 hbr
/-- **Hull soundness from `Readable`, reverse traversal.** -/
theorem sound_completeRange_of_emptyInference_rev {r : RangeRead} {res : Result}
(h : EmptyInference) (hread : Readable r res) (hrev : r.reverse = true)
(hmore : res.more = false) (hL : res.keys ≠ [])
(hbr : BracketObservableRev r res) :
Sound r res (completeRange r res) := by
obtain ⟨db₀, hcomp⟩ := hread
have heq : res.keys = RangeRead.completeKeys db₀ r := by
rcases hcomp.2 with ⟨hm, _, _⟩ | ⟨_, heq⟩
· simp [hmore] at hm
· exact heq
have hpair : res.keys.Pairwise (· > ·) := by
rw [heq]
rw [RangeRead.completeKeys, ite_eq_left (by simp [hrev])]
exact List.Pairwise.reverse (RangeRead.inRange_pairwise db₀ _ _)
exact sound_completeRange_of_bracketTransfer_rev h hrev hmore hL hpair hcomp.1 hbr
/-- **Minimality of the complete value, forward traversal, from the empty inference.**
Combines the derived hull soundness (`sound_completeRange_of_emptyInference`) with the
boundary `ψ` and the derived interior necessity. The only hypotheses beyond
`EmptyInference` are `BoundaryNecessity` and `BracketObservable`. -/
theorem minimal_completeRange_of_factors {r : RangeRead} {res : Result}
(h : EmptyInference) (hread : Readable r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hL : res.keys ≠ [])
(hψ : BoundaryNecessity r res) (hbr : BracketObservable r res) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_boundaryNecessity hread hL hψ
(sound_completeRange_of_emptyInference h hread hrev hmore hL hbr)
/-- **Minimality of the complete value, reverse traversal, from the empty inference.** -/
theorem minimal_completeRange_of_factors_rev {r : RangeRead} {res : Result}
(h : EmptyInference) (hread : Readable r res) (hrev : r.reverse = true)
(hmore : res.more = false) (hL : res.keys ≠ [])
(hψ : BoundaryNecessity r res) (hbr : BracketObservableRev r res) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_boundaryNecessity hread hL hψ
(sound_completeRange_of_emptyInference_rev h hread hrev hmore hL hbr)
/-!
## The reduction: general necessity is reported necessity plus the empty ends
`necessaryRange_completeRange_of_boundaryNecessity` derives the interior from
`Readable` and leaves only `BoundaryNecessity` as content. The point of this section is
that the general case factors *exactly* that way: the necessity of the complete value is
the necessity of the reported keys, the convex hull they span, and the two boundary empty
reads. The reported part is unconditional (`necessary_of_mem_result`), the interior is
convexity, and the only genuinely empty content is `BoundaryNecessity` — the empty theory
at the two boundary reads, stretched across the gaps to the reported keys.
-/
/-- **The reported interval is necessary from pointwise reported necessity.** This is
`necessaryRange_reportedRange` with the database witness abstracted away: any way of
knowing that each reported key is necessary — in practice `necessary_of_mem_result` —
fills the interior by convexity. -/
theorem necessaryRange_reportedRange_of_reported {r : RangeRead} {res : Result}
(hmem : ∀ k ∈ res.keys, Necessary r res k) (hne : res.keys ≠ []) :
NecessaryRange r res (reportedRange r res).begin (reportedRange r res).end_ := by
intro k hlo hhi
simp only [reportedRange] at hlo hhi
have hle : leastReported r res ≤ k := WithTop.coe_le_coe.mp hlo
have hkg : k ≤ greatestReported r res :=
(lt_keyAfter_iff k (greatestReported r res)).mp (WithTop.coe_lt_coe.mp hhi)
have hmem_lo : leastReported r res ∈ res.keys := by
unfold leastReported
split
· exact getLastD_mem hne
· exact headD_mem hne
have hmem_hi : greatestReported r res ∈ res.keys := by
unfold greatestReported
split
· exact headD_mem hne
· exact getLastD_mem hne
exact (hmem _ hmem_lo).of_between (hmem _ hmem_hi) hle hkg
/-- **The reduction identity for complete necessity.** The complete value's necessary
range is the lower boundary `ψ`, then the reported interval (from pointwise reported
necessity, by convexity), then the upper boundary `ψ`. Nothing else enters. -/
theorem necessaryRange_completeRange_of_reported {r : RangeRead} {res : Result}
(hmem : ∀ k ∈ res.keys, Necessary r res k) (hne : res.keys ≠ [])
(hψ : BoundaryNecessity r res) :
NecessaryRange r res (completeRange r res).begin (completeRange r res).end_ :=
(hψ.1.trans (necessaryRange_reportedRange_of_reported hmem hne)).trans hψ.2
/-- **The complete branch, from reported necessity and the empty ends.** Soundness of
the assembled hull plus the reduction identity above give minimality. The reported keys
are supplied by `necessary_of_mem_result` in applications; this statement keeps them as
an explicit factor so the decomposition "reported + empty" is visible. -/
theorem minimal_completeRange_of_reported {r : RangeRead} {res : Result}
(hmem : ∀ k ∈ res.keys, Necessary r res k) (hne : res.keys ≠ [])
(hψ : BoundaryNecessity r res) (hs : Sound r res (completeRange r res)) :
Minimal r res (completeRange r res) :=
minimal_iff_sound_and_necessaryRange.mpr
⟨hs, necessaryRange_completeRange_of_reported hmem hne hψ⟩
/-- **The complete branch, reduction form.** Reported necessity is now the unconditional
`necessary_of_mem_result`, so the only hypotheses beyond `Readable` are soundness of the
hull and the boundary `ψ`; the interior is derived. -/
theorem minimal_completeRange_of_emptyEnds {r : RangeRead} {res : Result}
(hread : Readable r res) (hne : res.keys ≠ [])
(hψ : BoundaryNecessity r res) (hs : Sound r res (completeRange r res)) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_reported (fun _ hk => necessary_of_mem_result hread hk) hne hψ hs
/-!
### The boundary `ψ` from the empty joint bases
`BoundaryNecessity` is the empty theory's `ψ` at the two boundary reads, transferred to
the full pair. The transfer is the factor-toggle joint-base construction; its two halves
are named here, forward and reversed, so that the boundary hypothesis can be discharged
from witnesses rather than assumed.
-/
/-- A result with `more = false` is exactly its key list paired with `false`. -/
theorem res_eq_keys_more_false {res : Result} (hmore : res.more = false) :
res = { keys := res.keys, more := false } := by
cases res; simp_all
/-- **Boundary necessity from the lower joint bases, forward.** The lower joint bases on
`[R.begin, k₀)` transfer the empty lower read's necessity to the full pair. -/
theorem boundaryNecessity_low_of_jointBases {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hmore : res.more = false) (hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· < ·)) (hlim : RangeRead.withinLimit r res.keys)
(hlo : LowerJointBaseRange r res.keys (completeRange r res).begin
(reportedRange r res).begin) :
NecessaryRange r res (completeRange r res).begin (reportedRange r res).begin :=
necessaryRange_of_lowerJointBaseRange hrev hL hpair hlim
(res_eq_keys_more_false hmore) hlo
/-- **Boundary necessity from the upper joint bases, forward.** -/
theorem boundaryNecessity_high_of_jointBases {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hmore : res.more = false) (hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· < ·)) (hlim : RangeRead.withinLimit r res.keys)
(hhi : UpperJointBaseRange r res.keys (reportedRange r res).end_
(completeRange r res).end_) :
NecessaryRange r res (reportedRange r res).end_ (completeRange r res).end_ :=
necessaryRange_of_upperJointBaseRange hrev hL hpair hlim
(res_eq_keys_more_false hmore) hhi
/-- **Boundary necessity from the lower joint bases, reversed.** -/
theorem boundaryNecessity_low_of_jointBasesRev {r : RangeRead} {res : Result}
(hrev : r.reverse = true) (hmore : res.more = false) (hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· > ·)) (hlim : RangeRead.withinLimit r res.keys)
(hlo : LowerJointBaseRangeRev r res.keys (completeRange r res).begin
(reportedRange r res).begin) :
NecessaryRange r res (completeRange r res).begin (reportedRange r res).begin :=
necessaryRange_of_lowerJointBaseRangeRev hrev hL hpair hlim
(res_eq_keys_more_false hmore) hlo
/-- **Boundary necessity from the upper joint bases, reversed.** -/
theorem boundaryNecessity_high_of_jointBasesRev {r : RangeRead} {res : Result}
(hrev : r.reverse = true) (hmore : res.more = false) (hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· > ·)) (hlim : RangeRead.withinLimit r res.keys)
(hhi : UpperJointBaseRangeRev r res.keys (reportedRange r res).end_
(completeRange r res).end_) :
NecessaryRange r res (reportedRange r res).end_ (completeRange r res).end_ :=
necessaryRange_of_upperJointBaseRangeRev hrev hL hpair hlim
(res_eq_keys_more_false hmore) hhi
/-- **The complete branch, from the empty joint bases.** This is the end-to-end
reduction statement: reported necessity is derived (`necessary_of_mem_result`), the
interior is convexity, the two boundary ranges come from the empty theory's joint-base
witnesses, and the only remaining hypothesis is hull soundness. -/
theorem minimal_completeRange_of_jointBasesEmpty {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· < ·))
(hlim : RangeRead.withinLimit r res.keys)
(hlo : LowerJointBaseRange r res.keys (completeRange r res).begin
(reportedRange r res).begin)
(hhi : UpperJointBaseRange r res.keys (reportedRange r res).end_
(completeRange r res).end_)
(hs : Sound r res (completeRange r res)) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_emptyEnds hread hL
⟨boundaryNecessity_low_of_jointBases hrev hmore hL hpair hlim hlo,
boundaryNecessity_high_of_jointBases hrev hmore hL hpair hlim hhi⟩ hs
/-- **The complete branch, from the empty joint bases, reverse traversal.** -/
theorem minimal_completeRange_of_jointBasesEmptyRev {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = true) (hmore : res.more = false)
(hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· > ·))
(hlim : RangeRead.withinLimit r res.keys)
(hlo : LowerJointBaseRangeRev r res.keys (completeRange r res).begin
(reportedRange r res).begin)
(hhi : UpperJointBaseRangeRev r res.keys (reportedRange r res).end_
(completeRange r res).end_)
(hs : Sound r res (completeRange r res)) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_emptyEnds hread hL
⟨boundaryNecessity_low_of_jointBasesRev hrev hmore hL hpair hlim hlo,
boundaryNecessity_high_of_jointBasesRev hrev hmore hL hpair hlim hhi⟩ hs
/-- **The joint-base boundary hypothesis, selected by traversal.** The two boundary
ranges of `BoundaryNecessity`, obtained from the empty theory's flip witnesses, in
whichever traversal order the read uses. This is the exact input the complete branch
extracts from the empty theory beyond `EmptyInference`; the extraction itself is the
length-sensitive graft described above. It is *false* — the endpoints are those of the
(unsound) hull, and `BoundaryNecessity` on them can demand keys that no sound range need
contain (a two-key witness refutes it). -/
def BoundaryJointBases (r : RangeRead) (res : Result) : Prop :=
if r.reverse then
LowerJointBaseRangeRev r res.keys (completeRange r res).begin
(reportedRange r res).begin ∧
UpperJointBaseRangeRev r res.keys (reportedRange r res).end_
(completeRange r res).end_
else
LowerJointBaseRange r res.keys (completeRange r res).begin
(reportedRange r res).begin ∧
UpperJointBaseRange r res.keys (reportedRange r res).end_
(completeRange r res).end_
/-- **The complete branch, from `EmptyInference` and the joint bases.** Soundness of the
hull is derived from `EmptyInference` once the bracket factor is supplied; necessity is
the derived reported interval plus the boundary ranges from the joint bases. Compared
with `minimal_completeRange_of_factors`, the boundary `BoundaryNecessity` hypothesis is
replaced by the lower-level joint bases, so the reduction exhibits the witnesses rather
than assuming the conclusion. -/
theorem minimal_completeRange_of_factors_joint {r : RangeRead} {res : Result}
(h : EmptyInference) (hread : Readable r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· < ·))
(hlim : RangeRead.withinLimit r res.keys)
(hjoint : BoundaryJointBases r res) (hbr : BracketObservable r res) :
Minimal r res (completeRange r res) := by
unfold BoundaryJointBases at hjoint
rw [ite_eq_right (by simp [hrev])] at hjoint
exact minimal_completeRange_of_jointBasesEmpty hread hrev hmore hL hpair hlim
hjoint.1 hjoint.2
(sound_completeRange_of_bracketTransfer h hrev hmore hL hpair hlim hbr)
/-- **The complete branch, from `EmptyInference` and the joint bases, reverse.** -/
theorem minimal_completeRange_of_factors_joint_rev {r : RangeRead} {res : Result}
(h : EmptyInference) (hread : Readable r res) (hrev : r.reverse = true)
(hmore : res.more = false) (hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· > ·))
(hlim : RangeRead.withinLimit r res.keys)
(hjoint : BoundaryJointBases r res) (hbr : BracketObservableRev r res) :
Minimal r res (completeRange r res) := by
unfold BoundaryJointBases at hjoint
rw [ite_eq_left (by simp [hrev])] at hjoint
exact minimal_completeRange_of_jointBasesEmptyRev hread hrev hmore hL hpair hlim
hjoint.1 hjoint.2
(sound_completeRange_of_bracketTransfer_rev h hrev hmore hL hpair hlim hbr)
/-- **The complete branch, from `EmptyInferenceWitness` and the joint bases.** The
witness-exposing oracle supplies soundness (`EmptyInference` via
`emptyInference_of_witness`); the joint bases remain the one extraction hypothesis (false in
general: a two-key witness refutes it). This
is the sharpest form of the reduction available: the reported keys and their convex hull
are derived, and the boundary necessity is stated at the witness level rather than as the
finished `BoundaryNecessity`. -/
theorem minimal_completeRange_of_witness_joint {r : RangeRead} {res : Result}
(h : EmptyInferenceWitness) (hread : Readable r res) (hrev : r.reverse = false)
(hmore : res.more = false) (hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· < ·))
(hlim : RangeRead.withinLimit r res.keys)
(hjoint : BoundaryJointBases r res) (hbr : BracketObservable r res) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_factors_joint (emptyInference_of_witness h) hread hrev hmore
hL hpair hlim hjoint hbr
/-- **The complete branch, from `EmptyInferenceWitness` and the joint bases, reverse.** -/
theorem minimal_completeRange_of_witness_joint_rev {r : RangeRead} {res : Result}
(h : EmptyInferenceWitness) (hread : Readable r res) (hrev : r.reverse = true)
(hmore : res.more = false) (hL : res.keys ≠ []) (hpair : res.keys.Pairwise (· > ·))
(hlim : RangeRead.withinLimit r res.keys)
(hjoint : BoundaryJointBases r res) (hbr : BracketObservableRev r res) :
Minimal r res (completeRange r res) :=
minimal_completeRange_of_factors_joint_rev (emptyInference_of_witness h) hread hrev hmore
hL hpair hlim hjoint hbr
/-- **The joint bases reach `BoundaryNecessity`, forward.** The witness-level boundary
content packages into the finished two-range hypothesis used by the abstract correctness
theorem. -/
theorem boundaryNecessity_of_jointBases {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hmore : res.more = false) (hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· < ·)) (hlim : RangeRead.withinLimit r res.keys)
(hjoint : BoundaryJointBases r res) : BoundaryNecessity r res := by
unfold BoundaryJointBases at hjoint
rw [ite_eq_right (by simp [hrev])] at hjoint
exact ⟨boundaryNecessity_low_of_jointBases hrev hmore hL hpair hlim hjoint.1,
boundaryNecessity_high_of_jointBases hrev hmore hL hpair hlim hjoint.2⟩
/-- **The joint bases reach `BoundaryNecessity`, reverse.** -/
theorem boundaryNecessity_of_jointBases_rev {r : RangeRead} {res : Result}
(hrev : r.reverse = true) (hmore : res.more = false) (hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· > ·)) (hlim : RangeRead.withinLimit r res.keys)
(hjoint : BoundaryJointBases r res) : BoundaryNecessity r res := by
unfold BoundaryJointBases at hjoint
rw [ite_eq_left (by simp [hrev])] at hjoint
exact ⟨boundaryNecessity_low_of_jointBasesRev hrev hmore hL hpair hlim hjoint.1,
boundaryNecessity_high_of_jointBasesRev hrev hmore hL hpair hlim hjoint.2⟩
/-!
## The truncated branches, from the existing certificates
For a forward truncated result the upper end is the bare successor of the greatest
reported key; for a reverse truncated result the lower end is the bare least
reported key and the begin selector drops out. At offset one, when the corresponding
boundary read is not trivially empty, these are exactly the certified
`minimal_truncatedRange_of_offset_one` and `minimal_truncatedRangeRev_of_offset_one`.
-/
/-- At a positive begin offset, the lower boundary read (whose end is offset one)
has `emptyValue` the canonical range `[begin.key, k₀)`: it is not trivially empty by
hypothesis, and its end offset is one, so `emptyValue` takes the canonical branch. -/
theorem lowBound_eq_canonical_of_pos {r : RangeRead} {res : Result}
(_hbegin : 1 ≤ r.begin.offset)
(hempty : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res))) :
lowBound r res =
⟨r.begin.key, (leastReported r res : WithTop Key)⟩ := by
unfold lowBound emptyValue
rw [ite_eq_right hempty,
ite_eq_right (show ¬ (boundaryReadLo r (leastReported r res)).begin.offset ≤ 0 by
simp only [boundaryReadLo]; omega),
ite_eq_left (show (boundaryReadLo r (leastReported r res)).end_.offset ≤ 1
from le_of_eq rfl)]
rfl
/-- At an end offset at most one, the upper boundary read (whose begin is offset one)
has `emptyValue` the canonical range `[keyAfter kₙ, end.key)`. -/
theorem highBound_eq_canonical_of_end_le_one {r : RangeRead} {res : Result}
(hend : r.end_.offset ≤ 1)
(hempty : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res))) :
highBound r res =
⟨(keyAfter (greatestReported r res) : WithTop Key), r.end_.key⟩ := by
unfold highBound emptyValue
rw [ite_eq_right hempty,
ite_eq_right (show ¬ (boundaryReadHi r (greatestReported r res)).begin.offset ≤ 0 by
simp only [boundaryReadHi, selAt_offset]; norm_num),
ite_eq_left (show (boundaryReadHi r (greatestReported r res)).end_.offset ≤ 1 from hend)]
rfl
/-- **`BoundaryNecessity` in the canonical region.** When the boundary contributions
have their canonical endpoints (`lowBound = [begin.key, k₀)` and
`highBound = [keyAfter kₙ, end.key)`) and they abut the reported interval, the complete
value is exactly `[begin.key, end.key)` and `BoundaryNecessity` follows from the two
end-key necessity theorems. No joint base is needed here. -/
theorem boundaryNecessity_canonical {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hne : res.keys ≠ []) (hpair : res.keys.Pairwise (· < ·))
(hbegin : 1 ≤ r.begin.offset) (hend : r.end_.offset ≤ 1)
(hWe : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res)))
(hUe : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res)))
{v : Key} (hkey : r.begin.key = (↑v : WithTop Key))
(hordB : r.begin.key ≤ (leastReported r res : WithTop Key))
(hordK : (keyAfter (greatestReported r res) : WithTop Key) ≤ r.end_.key) :
BoundaryNecessity r res := by
have hW := lowBound_eq_canonical_of_pos hbegin hWe
have hU := highBound_eq_canonical_of_end_le_one hend hUe
have hmid : (↑(leastReported r res) : WithTop Key) ≤
(↑(keyAfter (greatestReported r res)) : WithTop Key) :=
WithTop.coe_le_coe.mpr (le_of_lt (lt_of_le_of_lt
(least_le_greatest_fwd hrev hpair hne) (keyAfter_self_lt _)))
have hc : completeRange r res = ⟨r.begin.key, r.end_.key⟩ := by
unfold completeRange reportedRange
rw [hW, hU]
exact hull3 r.begin.key (leastReported r res : WithTop Key)
(keyAfter (greatestReported r res) : WithTop Key) r.end_.key hordB hmid hordK
refine ⟨?_, ?_⟩
· rw [hc]; simp only [reportedRange]
exact necessaryRange_low_fwd hread hrev hne hbegin hkey
· rw [hc]; simp only [reportedRange]
exact necessaryRange_high_fwd hread hrev hmore hne hend
/-- For a reversed read the least reported key is at or below the greatest. -/
theorem least_le_greatest_rev {r : RangeRead} {res : Result} (hrev : r.reverse = true)
(hpair : res.keys.Pairwise (· > ·)) (hne : res.keys ≠ []) :
leastReported r res ≤ greatestReported r res := by
have hleast : leastReported r res = res.keys.getLastD ([] : Key) := by simp [leastReported, hrev]
have hgreat : greatestReported r res = res.keys.headD ([] : Key) := by
simp [greatestReported, hrev]
rw [hleast, hgreat]
have hlastD : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rw [hlastD]
have hp : res.keys.Pairwise (· ≥ ·) := hpair.imp (fun hab => le_of_lt hab)
exact hp.rel_getLast (headD_mem hne)
/-- **Lower boundary necessity, reverse.** At a positive begin offset and a complete
result, the begin key is necessary (`necessary_begin_key_rev`) and the least reported
key is necessary; convexity fills `[begin.key, k₀)`. -/
theorem necessaryRange_low_rev {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = true) (hmore : res.more = false)
(hlen : 0 < res.keys.length) (hoff : 1 ≤ r.begin.offset)
{v : Key} (hkey : r.begin.key = (↑v : WithTop Key)) :
NecessaryRange r res r.begin.key ((leastReported r res : Key) : WithTop Key) := by
have hv : Necessary r res v := necessary_begin_key_rev hread hrev hmore hlen hoff hkey
have hget : leastReported r res = res.keys.getLastD ([] : Key) := by simp [leastReported, hrev]
have hle : leastReported r res ∈ res.keys := by
rw [hget]; exact getLastD_mem (List.ne_nil_of_length_pos hlen)
have hk0 : Necessary r res (leastReported r res) := necessary_of_mem_result hread hle
intro k hlo hhi
rw [hkey] at hlo
exact hv.of_between hk0 (WithTop.coe_le_coe.mp hlo) (le_of_lt (WithTop.coe_lt_coe.mp hhi))
/-- **Upper boundary necessity, reverse.** With an end offset at most one, the keys from
`keyAfter kₙ` up to `end_.key` are necessary (`necessary_head_to_end_key`). -/
theorem necessaryRange_high_rev {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = true) (_hmore : res.more = false)
(hlen : 0 < res.keys.length) (hend : r.end_.offset ≤ 1) :
NecessaryRange r res ((keyAfter (greatestReported r res) : Key) : WithTop Key) r.end_.key := by
have hhead : greatestReported r res = res.keys.headD ([] : Key) := by
simp [greatestReported, hrev]
have hne : res.keys ≠ [] := List.ne_nil_of_length_pos hlen
intro k hlo hhi cr hs
have hk0 : res.keys.head hne ≤ k := by
rw [hhead] at hlo
have h : res.keys.headD ([] : Key) ≤ k := by
by_contra hcon
have hle : k ≤ res.keys.headD ([] : Key) := le_of_not_ge hcon
have : (k : WithTop Key) < (↑(keyAfter (res.keys.headD ([] : Key))) : WithTop Key) :=
WithTop.coe_lt_coe.mpr ((lt_keyAfter_iff k (res.keys.headD ([] : Key))).mpr hle)
exact absurd hlo (not_le.mpr this)
rw [List.headD_eq_head?, List.head?_eq_some_head hne] at h
exact h
exact necessary_head_to_end_key hread hrev hne hend cr hs hk0 hhi
/-- **`BoundaryNecessity` in the canonical region, reverse traversal.** Dual to
`boundaryNecessity_canonical`. -/
theorem boundaryNecessity_canonical_rev {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = true) (hmore : res.more = false)
(hne : res.keys ≠ []) (hpair : res.keys.Pairwise (· > ·))
(hbegin : 1 ≤ r.begin.offset) (hend : r.end_.offset ≤ 1)
(hWe : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res)))
(hUe : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res)))
{v : Key} (hkey : r.begin.key = (↑v : WithTop Key))
(hordB : r.begin.key ≤ (leastReported r res : WithTop Key))
(hordK : (keyAfter (greatestReported r res) : WithTop Key) ≤ r.end_.key) :
BoundaryNecessity r res := by
have hW := lowBound_eq_canonical_of_pos hbegin hWe
have hU := highBound_eq_canonical_of_end_le_one hend hUe
have hmid : (↑(leastReported r res) : WithTop Key) ≤
(↑(keyAfter (greatestReported r res)) : WithTop Key) :=
WithTop.coe_le_coe.mpr (le_of_lt (lt_of_le_of_lt
(least_le_greatest_rev hrev hpair hne) (keyAfter_self_lt _)))
have hc : completeRange r res = ⟨r.begin.key, r.end_.key⟩ := by
unfold completeRange reportedRange
rw [hW, hU]
exact hull3 r.begin.key (leastReported r res : WithTop Key)
(keyAfter (greatestReported r res) : WithTop Key) r.end_.key hordB hmid hordK
refine ⟨?_, ?_⟩
· rw [hc]; simp only [reportedRange]
exact necessaryRange_low_rev hread hrev hmore (List.length_pos_of_ne_nil hne) hbegin hkey
· rw [hc]; simp only [reportedRange]
exact necessaryRange_high_rev hread hrev hmore (List.length_pos_of_ne_nil hne) hend
/-- **The complete value is the canonical range in the canonical region.** When both
boundary contributions have canonical endpoints and abut the reported interval, the
three-piece hull collapses to `[begin.key, end.key)`. -/
theorem completeRange_eq_canonical {r : RangeRead} {res : Result}
(hbegin : 1 ≤ r.begin.offset) (hend : r.end_.offset ≤ 1)
(hWe : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res)))
(hUe : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res)))
(hordB : r.begin.key ≤ (leastReported r res : WithTop Key))
(hmid : (leastReported r res : WithTop Key) ≤ (keyAfter (greatestReported r res) : WithTop Key))
(hordK : (keyAfter (greatestReported r res) : WithTop Key) ≤ r.end_.key) :
completeRange r res = canonicalRange r := by
have hW := lowBound_eq_canonical_of_pos hbegin hWe
have hU := highBound_eq_canonical_of_end_le_one hend hUe
unfold completeRange canonicalRange reportedRange
rw [hW, hU]
exact hull3 r.begin.key (leastReported r res : WithTop Key)
(keyAfter (greatestReported r res) : WithTop Key) r.end_.key hordB hmid hordK
/-- **The complete branch in the canonical region needs no boundary hypothesis.** At
`begin.offset = 1`, `end.offset ≤ 1`, and canonical endpoints, the complete value is the
canonical range and its minimality is the existing
`minimal_canonicalRange_of_end_offset_le_one` — neither `BoundaryNecessity` nor
`BracketFactor` is required. -/
theorem minimal_completeRange_canonical {r : RangeRead} {res : Result}
(hread : Readable r res) (hrev : r.reverse = false) (hmore : res.more = false)
(hne : res.keys ≠ []) (hpair : res.keys.Pairwise (· < ·))
(hbegin1 : r.begin.offset = 1) (hend : r.end_.offset ≤ 1)
(hWe : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res)))
(hUe : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res)))
(hordB : r.begin.key ≤ (leastReported r res : WithTop Key))
(hordK : (keyAfter (greatestReported r res) : WithTop Key) ≤ r.end_.key) :
Minimal r res (completeRange r res) := by
have hmid : (leastReported r res : WithTop Key) ≤
(keyAfter (greatestReported r res) : WithTop Key) :=
WithTop.coe_le_coe.mpr (le_of_lt (lt_of_le_of_lt
(least_le_greatest_fwd hrev hpair hne) (keyAfter_self_lt _)))
have hc := completeRange_eq_canonical (r := r) (res := res)
(by omega) hend hWe hUe hordB hmid hordK
rw [hc]
exact minimal_canonicalRange_of_end_offset_le_one hread hmore hne hbegin1 hend
/-- **Forward truncated value equals the certified truncated range.** With
`reverse = false` and the lower boundary read not trivially empty, the forward truncated
value is `[begin.key, keyAfter (greatest reported))`. -/
theorem forwardTruncatedRange_eq_truncatedRange {r : RangeRead} {res : Result}
(hrev : r.reverse = false) (hbegin : 1 ≤ r.begin.offset)
(hempty : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res))) :
forwardTruncatedRange r res =
truncatedRange r (res.keys.getLastD ([] : Key)) := by
have hleast : leastReported r res = res.keys.headD ([] : Key) := by
simp [leastReported, hrev]
have hgreat : greatestReported r res = res.keys.getLastD ([] : Key) := by
simp [greatestReported, hrev]
rw [forwardTruncatedRange, hgreat, truncatedRange, lowBound_eq_canonical_of_pos hbegin hempty]
/-- **Forward truncated, offset one.** With `begin.offset = 1` and `end.offset = 1`,
and the lower boundary read not trivially empty, the forward truncated value is minimal:
it matches `minimal_truncatedRange_of_offset_one`. -/
theorem minimal_forwardTruncatedRange_of_offset_one {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = false)
(hbegin : r.begin.offset = 1) (hend : r.end_.offset = 1)
(hempty : ¬ AlwaysEmpty (boundaryReadLo r (leastReported r res))) :
Minimal r res (forwardTruncatedRange r res) := by
rw [forwardTruncatedRange_eq_truncatedRange hrev (by omega) hempty]
exact minimal_truncatedRange_of_offset_one hread hmore hrev hbegin hend
/-- The reverse truncated value equals the certified reversed truncated range, when
the upper boundary read is not trivially empty at an end offset at most one. -/
theorem reverseTruncatedRange_eq_truncatedRangeRev {r : RangeRead} {res : Result}
(hrev : r.reverse = true) (hend : r.end_.offset ≤ 1)
(hempty : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res))) :
reverseTruncatedRange r res =
truncatedRangeRev r (res.keys.getLastD ([] : Key)) := by
have hleast : leastReported r res = res.keys.getLastD ([] : Key) := by
simp [leastReported, hrev]
rw [reverseTruncatedRange, hleast, truncatedRangeRev,
highBound_eq_canonical_of_end_le_one hend hempty]
/-- **Reverse truncated, offset one.** With `begin.offset = 1` and `end.offset = 1`,
and the upper boundary read not trivially empty, the reverse truncated value is minimal:
it matches `minimal_truncatedRangeRev_of_offset_one`. -/
theorem minimal_reverseTruncatedRange_of_offset_one {r : RangeRead} {res : Result}
(hread : Readable r res) (hmore : res.more = true) (hrev : r.reverse = true)
(hbegin : r.begin.offset = 1) (hend : r.end_.offset = 1)
(hempty : ¬ AlwaysEmpty (boundaryReadHi r (greatestReported r res))) :
Minimal r res (reverseTruncatedRange r res) := by
rw [reverseTruncatedRange_eq_truncatedRangeRev hrev (by omega) hempty]
exact minimal_truncatedRangeRev_of_offset_one hread hmore hrev hbegin hend
/-!
## The truncated branches through the empty boundary value
The forward/reverse truncated values are the lower/upper boundary contribution's
begin/end glued to the reported interval. The offset-one certificates above are the
same statement via `emptyValue`; the general statement is the same reduction as the
complete branch, with the far boundary read replaced by the reported interval. Those
reductions are the remaining obligations of the truncated branches and are stated
separately.
-/
/-!
## The empty branch
The empty result is answered by `emptyValue`, reading off the empty theory's cases.
The offset-one underEnd case is certified below; the remaining offsets are handled
by the separate empty-theory development (`FormalConflictRange.Empty`,
`FormalConflictRange.Nonpos`).
-/
/-- **The empty branch, `begin.offset = 1`, `end.offset ≤ 1`.** A non-trivially-empty
read with `begin.offset = 1` and `end.offset ≤ 1` whose result is empty has
`emptyValue r = canonicalRange r` minimal, by
`minimal_canonicalRange_of_underEnd_empty`. -/
theorem minimal_emptyValue_of_offset_one {r : RangeRead} {res : Result}
(hread : Readable r res) (hgap : ¬ AlwaysEmpty r) (hbegin : r.begin.offset = 1)
(hend : r.end_.offset ≤ 1) (hmore : res.more = false) (hempty : res.keys = []) :
Minimal r res (emptyValue r) := by
have hval : emptyValue r = canonicalRange r := by
unfold emptyValue
rw [ite_eq_right hgap, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0), ite_eq_left hend]
rw [hval]
exact minimal_canonicalRange_of_underEnd_empty hread hgap hbegin hend hmore hempty
/-- **The empty branch, `begin.offset = 1`, `end.offset ≤ 1`, any emptiness.** With no
non-triviality hypothesis at all, `emptyValue r` is minimal for the empty result at
`begin.offset = 1`, `end.offset ≤ 1`: trivially empty reads use the empty range, the
rest the canonical range. This is the `EmptyInference` instance for this region. -/
theorem minimal_emptyValue_underEnd (r : RangeRead) (hbegin : r.begin.offset = 1)
(hend : r.end_.offset ≤ 1) :
Minimal r { keys := [], more := false } (emptyValue r) := by
by_cases hAE : AlwaysEmpty r
· have : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
rw [this]; exact minimal_emptyRange_of_alwaysEmpty hAE
· have hv : emptyValue r = canonicalRange r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0), ite_eq_left hend]
rw [hv]
exact minimal_canonicalRange_of_underEnd_empty
⟨emptyDB, compatible_emptyDB_emptyRes r⟩ hAE hbegin hend rfl rfl
/-! ### The empty inference at `begin.offset = 1`: reducing to forward reads
Traversal is invisible to the empty inference, and `emptyValue` never mentions
`reverse`, so `EmptyInference` reduces to its non-reversed instance; and the
`begin.offset = 1` instance splits by the end offset into the three empty cases already
in the library. This pins the uncertified empty-theory content to `begin.offset ≠ 1`.
-/
/-- `AlwaysEmpty` is invariant under flipping the traversal. -/
theorem alwaysEmpty_reverse (r : RangeRead) :
AlwaysEmpty { r with reverse := !r.reverse } ↔ AlwaysEmpty r := by
unfold AlwaysEmpty
constructor <;> intro h db
· have hh := h db; rw [completeKeys_eq_nil_iff_inRange] at hh ⊢; exact hh
· have hh := h db; rw [completeKeys_eq_nil_iff_inRange] at hh ⊢; exact hh
/-- `emptyValue` never mentions `reverse`, so it is invariant under flipping it. -/
theorem emptyValue_reverse (r : RangeRead) :
emptyValue { r with reverse := !r.reverse } = emptyValue r := by
unfold emptyValue
by_cases h : AlwaysEmpty r
· rw [ite_eq_left ((alwaysEmpty_reverse r).mpr h), ite_eq_left h]
rfl
· rw [ite_eq_right (fun hh => h ((alwaysEmpty_reverse r).mp hh)), ite_eq_right h]
rfl
/-- Compatibility with the empty result is invariant under flipping the traversal:
reversal only reverses the complete keys, which are empty on the same databases. -/
theorem compatible_empty_flip {db : DB} {r : RangeRead} :
RangeRead.Compatible db r { keys := [], more := false } ↔
RangeRead.Compatible db { r with reverse := !r.reverse } { keys := [], more := false } := by
rw [compatible_empty_iff_complete_nil, compatible_empty_iff_complete_nil]
cases hr : r.reverse <;> simp [RangeRead.completeKeys, hr]
/-- Soundness for empty results is invariant under flipping the traversal. -/
theorem sound_empty_flip {r : RangeRead} {cr : ConflictRange} :
Sound r { keys := [], more := false } cr ↔
Sound { r with reverse := !r.reverse } { keys := [], more := false } cr := by
constructor <;> intro h d1 d2 hag
· rw [← compatible_empty_flip (db := d1), ← compatible_empty_flip (db := d2)]; exact h d1 d2 hag
· rw [compatible_empty_flip (db := d1), compatible_empty_flip (db := d2)]; exact h d1 d2 hag
/-- Necessity for empty results is invariant under flipping the traversal. -/
theorem necessary_empty_flip {r : RangeRead} {k : Key} :
Necessary r { keys := [], more := false } k ↔
Necessary { r with reverse := !r.reverse } { keys := [], more := false } k := by
unfold Necessary
exact ⟨fun h cr hs => h cr (sound_empty_flip.mpr hs),
fun h cr hs => h cr (sound_empty_flip.mp hs)⟩
/-- Minimality for empty results is invariant under flipping the traversal. -/
theorem minimal_empty_flip {r : RangeRead} {cr : ConflictRange} :
Minimal r { keys := [], more := false } cr ↔
Minimal { r with reverse := !r.reverse } { keys := [], more := false } cr := by
rw [minimal_iff_sound_and_necessary, minimal_iff_sound_and_necessary]
exact ⟨fun h => ⟨sound_empty_flip.mp h.1, fun k hk => necessary_empty_flip.mp (h.2 k hk)⟩,
fun h => ⟨sound_empty_flip.mpr h.1, fun k hk => necessary_empty_flip.mpr (h.2 k hk)⟩⟩
/-- **`EmptyInference` reduces to its non-reversed instance.** -/
theorem emptyInference_of_forward
(h : ∀ r' : RangeRead, r'.reverse = false →
Minimal r' { keys := [], more := false } (emptyValue r')) :
EmptyInference := by
intro r' _
cases hr : r'.reverse
· exact h r' hr
· have hf := h { r' with reverse := false } rfl
rw [show ({ r' with reverse := false } : RangeRead) =
{ r' with reverse := !r'.reverse } from by simp [hr]] at hf
rw [emptyValue_reverse, ← minimal_empty_flip] at hf
exact hf
/-- **The empty inference at `begin.offset = 1`, cross-free overshoot.** -/
theorem minimal_emptyValue_crossFree_fwd (r : RangeRead) (hbegin : r.begin.offset = 1)
(hend : 2 ≤ r.end_.offset) (hle : r.begin.key ≤ r.end_.key) (hrev : r.reverse = false) :
Minimal r { keys := [], more := false } (emptyValue r) := by
by_cases hAE : AlwaysEmpty r
· have : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
rw [this]; exact minimal_emptyRange_of_alwaysEmpty hAE
· have hv : emptyValue r = topRange r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0),
ite_eq_right (by omega), ite_eq_left hle]
rw [hv]
exact minimal_topRange_of_end_offset_ge_two_empty
⟨emptyDB, compatible_emptyDB_emptyRes r⟩ rfl hrev rfl hbegin hend hle
/-- **The empty inference at `begin.offset = 1`, crossed overshoot.** The crossed case
holds for either traversal. -/
theorem minimal_emptyValue_crossed (r : RangeRead) (hbegin : r.begin.offset = 1)
(hend : 2 ≤ r.end_.offset) (hcross : r.end_.key < r.begin.key) :
Minimal r { keys := [], more := false } (emptyValue r) := by
by_cases hAE : AlwaysEmpty r
· have : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
rw [this]; exact minimal_emptyRange_of_alwaysEmpty hAE
· have hv : emptyValue r = crossedRangeGeneral r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0),
ite_eq_right (by omega), ite_eq_right (not_le.mpr hcross)]
rw [hv]
exact minimal_crossedRangeGeneral_of_empty rfl rfl (by omega) hend hcross hAE
/-- **The empty inference at `begin.offset = 1`, non-reversed.** -/
theorem emptyInference_beginOne_fwd (r : RangeRead) (hbegin : r.begin.offset = 1)
(hrev : r.reverse = false) :
Minimal r { keys := [], more := false } (emptyValue r) := by
by_cases hend : r.end_.offset ≤ 1
· exact minimal_emptyValue_underEnd r hbegin hend
· have hend2 : 2 ≤ r.end_.offset := by omega
by_cases hle : r.begin.key ≤ r.end_.key
· exact minimal_emptyValue_crossFree_fwd r hbegin hend2 hle hrev
· exact minimal_emptyValue_crossed r hbegin hend2 (not_le.mp hle)
/-- **The empty witness oracle at `begin.offset = 1`, non-reversed.** At this offset the
empty theory is complete on every end offset and traversal, so every key of `emptyValue`
has a flip witness. This is the witness-level companion of
`emptyInference_beginOne_fwd`; the witnesses are the ones built by the empty-result case
proofs. -/
theorem emptyWitness_beginOne_fwd (r : RangeRead) (hbegin : r.begin.offset = 1)
(_hrev : r.reverse = false)
(hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
by_cases hend : r.end_.offset ≤ 1
· have hv : emptyValue r = canonicalRange r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0), ite_eq_left hend]
refine ⟨?_, ?_⟩
· rw [hv]
exact (minimal_canonicalRange_of_underEnd_empty hread hAE hbegin hend rfl rfl).sound
· intro k hk
rw [hv] at hk
exact emptyWitness_underEnd hAE hbegin hend hk
· have hend2 : 2 ≤ r.end_.offset := by omega
by_cases hle : r.begin.key ≤ r.end_.key
· have hv : emptyValue r = topRange r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0),
ite_eq_right (by omega), ite_eq_left hle]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_topRange_of_le_general (by omega) (by omega) hle rfl rfl
· intro k hk
rw [hv] at hk
exact emptyWitness_crossFree hread hbegin hend2 hle hk
· have hcross : r.end_.key < r.begin.key := not_le.mp hle
have hEB : r.end_.key ≤ r.begin.key := le_of_lt hcross
have hv : emptyValue r = crossedRangeGeneral r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0),
ite_eq_right (by omega), ite_eq_right (not_le.mpr hcross)]
by_cases hgap : ((r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat) ≤
intervalCard r.end_.key r.begin.key
· rw [crossedRangeGeneral, ite_eq_left hgap] at hv
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_top_end_of_crossed_general (by omega) (by omega) hEB rfl rfl
· intro k hk
rw [hv] at hk
rcases lt_or_ge (k : WithTop Key) r.begin.key with hkB | hkB
· exact emptyWitness_crossed_interval hbegin hend2 hAE (by simpa [hbegin] using hgap)
hk.1 hkB
· exact emptyWitness_crossed_beginLe hbegin hend2 hkB
· rw [crossedRangeGeneral, ite_eq_right hgap] at hv
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_top_begin_of_short_general (by omega) (by omega) hEB (not_le.mp hgap) rfl rfl
· intro k hk
rw [hv] at hk
exact emptyWitness_crossed_beginLe hbegin hend2 hk.1
/-- **The empty inference at `begin.offset = 1`, any traversal.** Combines the
non-reversed instance with traversal-invariance. -/
theorem emptyInference_beginOne (r : RangeRead) (hbegin : r.begin.offset = 1) :
Minimal r { keys := [], more := false } (emptyValue r) := by
cases hrev : r.reverse
· exact emptyInference_beginOne_fwd r hbegin hrev
· have hf := emptyInference_beginOne_fwd { r with reverse := false } hbegin rfl
rw [show ({ r with reverse := false } : RangeRead) =
{ r with reverse := !r.reverse } from by simp [hrev]] at hf
rw [emptyValue_reverse, ← minimal_empty_flip] at hf
exact hf
/-- **The empty flip witness is traversal-invariant.** Reversal only reverses the
complete keys, which are empty on the same databases (`compatible_empty_flip`), so a
flip witness for one traversal is a flip witness for the other. -/
theorem emptyWitness_flip {r : RangeRead} {k : Key} :
EmptyWitness { r with reverse := !r.reverse } k ↔ EmptyWitness r k := by
unfold EmptyWitness
constructor
· rintro ⟨db, hc, hn⟩
exact ⟨db, (compatible_empty_flip (db := db) (r := r)).mpr hc,
fun h => hn ((compatible_empty_flip (db := toggle db k) (r := r)).mp h)⟩
· rintro ⟨db, hc, hn⟩
exact ⟨db, (compatible_empty_flip (db := db) (r := r)).mp hc,
fun h => hn ((compatible_empty_flip (db := toggle db k) (r := r)).mpr h)⟩
/-- **The empty witness oracle at `begin.offset = 1`, any traversal.** The witness-level
companion of `emptyInference_beginOne`: soundness and a flip witness at every key of
`emptyValue`. This is `EmptyInferenceWitness` restricted to `begin.offset = 1`. -/
theorem emptyWitness_beginOne (r : RangeRead) (hbegin : r.begin.offset = 1)
(hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
cases hrev : r.reverse
· exact emptyWitness_beginOne_fwd r hbegin hrev hread
· have hread' : Readable { r with reverse := false } { keys := [], more := false } := by
obtain ⟨db, hc⟩ := hread
refine ⟨db, ?_⟩
have := (compatible_empty_flip (db := db) (r := r)).mp hc
rwa [show ({ r with reverse := !r.reverse } : RangeRead) = { r with reverse := false }
from by simp [hrev]] at this
have hf := emptyWitness_beginOne_fwd { r with reverse := false } hbegin rfl hread'
rw [show ({ r with reverse := false } : RangeRead) =
{ r with reverse := !r.reverse } from by simp [hrev]] at hf
refine ⟨?_, ?_⟩
· simpa [emptyValue_reverse] using (sound_empty_flip (r := r)).mpr hf.1
· intro k hk
rw [← emptyValue_reverse] at hk
exact emptyWitness_flip.mp (hf.2 k hk)
/-- **The exact residual of the empty inference.** Everything at `begin.offset = 1` is
proved; only `begin.offset ≠ 1` remains. -/
def EmptyInferenceOffOne : Prop :=
∀ r' : RangeRead, r'.begin.offset ≠ 1 → Readable r' { keys := [], more := false } →
Minimal r' { keys := [], more := false } (emptyValue r')
/-- **The exact residual of the witness oracle.** Everything at `begin.offset = 1` is
proved in `emptyWitness_beginOne`; only `begin.offset ≠ 1` remains. This is the
witness-level analogue of `EmptyInferenceOffOne`, and the form the general reduction's
empty content reduces to. -/
def EmptyInferenceWitnessOffOne : Prop :=
∀ r' : RangeRead, r'.begin.offset ≠ 1 → Readable r' { keys := [], more := false } →
Sound r' { keys := [], more := false } (emptyValue r') ∧
∀ k : Key, k ∈ emptyValue r' → EmptyWitness r' k
/-- **The genuinely open residual of the witness oracle.** At `begin.offset = 1`
(`emptyWitness_beginOne`), throughout `begin.offset ≥ 1` with `end.offset ≤ 1`
(`emptyWitness_underEnd_gen`), throughout the overshoot region (`end.offset ≥ 2`: both
`begin.offset ≥ 1` by `emptyWitness_overshoot` and `begin.offset ≤ 0` by
`emptyWitness_nonpos_overshoot`), all of `begin.offset ≤ 0`, `end.offset = 1`, and the
cross-free `begin.offset ≤ 0`, `end.offset ≤ 0` case
(`emptyWitness_nonpos_end_nonpos_crossFree`), and the crossed nonpositive-end short gap
(`emptyWitness_nonpos_crossed_short`, criterion `cnt end.key ≤ 1 - end.offset`), the oracle
is proved. What remains is the nonpositive begin offset with `end.offset ≤ 0`, crossed
selectors (`end.key < begin.key`) and a long gap
(`end.offset - begin.offset ≤ intervalCard end.key begin.key`), where `emptyValue` is the
bottom range `[⊥, begin.key)` and the gap is long enough that both disjuncts of
`compatible_empty_iff_nonpos_crossed_long` can fire. This is the residual the whole empty
theory now reduces to. -/
def EmptyInferenceWitnessResidual : Prop :=
∀ r' : RangeRead, r'.begin.offset ≤ 0 → r'.end_.offset ≤ 0 → r'.end_.key < r'.begin.key →
(((r'.end_.offset - r'.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r'.end_.key r'.begin.key →
Readable r' { keys := [], more := false } →
Sound r' { keys := [], more := false } (emptyValue r') ∧
∀ k : Key, k ∈ emptyValue r' → EmptyWitness r' k
/-- **`EmptyInferenceWitnessOffOne` from its off-one residual.** -/
theorem emptyInferenceWitness_of_offOne (h : EmptyInferenceWitnessOffOne) :
EmptyInferenceWitness := by
intro r' hr
by_cases hb : r'.begin.offset = 1
· exact emptyWitness_beginOne r' hb hr
· exact h r' hb hr
/-- **`EmptyInferenceOffOne` from its witness residual.** The witness oracle implies the
abstract oracle (`emptyInference_of_witness`), so the witness residual at off-one offsets
supplies the abstract one. -/
theorem emptyInferenceOffOne_of_witnessOffOne (h : EmptyInferenceWitnessOffOne) :
EmptyInferenceOffOne := by
intro r' hb hr
have hw := emptyInference_of_witness (emptyInferenceWitness_of_offOne h)
exact hw r' hr
/-- **`EmptyInference` from its off-`begin.offset = 1` residual.** The
`begin.offset = 1` instance is `emptyInference_beginOne`. -/
theorem emptyInference_of_offOne (h : EmptyInferenceOffOne) : EmptyInference := by
intro r' hr
by_cases hb : r'.begin.offset = 1
· exact emptyInference_beginOne r' hb
· exact h r' hb hr
/-!
## The general obligation and correctness
-/
/-- **The nonempty-branch obligation.** The empty branch is discharged by the empty
inference (`minimal_emptyValue_of_emptyInference`) and the complete branch by
`minimal_completeRange_of_factors`/`_rev`. Only the two truncated fields remain: they
are the direct minimality statements for their values, using the same boundary transfer
together with the reported interval. -/
structure GeneralObligation (r : RangeRead) (res : Result) : Prop where
/-- A forward truncated result: `[w, keyAfter kₙ)` is minimal. -/
fwdTrunc : res.more = true → r.reverse = false → res.keys ≠ [] →
Minimal r res (forwardTruncatedRange r res)
/-- A reverse truncated result: `[kₙ, u)` is minimal. -/
revTrunc : res.more = true → r.reverse = true → res.keys ≠ [] →
Minimal r res (reverseTruncatedRange r res)
/-- **The complete-branch obligation, in push-down form.** Beyond the empty theory, the
complete branch needs exactly two things, neither mentioning an offset:
* `joint`, the generic graft: the empty boundary reads' flip witnesses extend to
full-compatible databases, i.e. `BoundaryJointBases`;
* `bracket`, the observability residue, itself an instance of the empty gap split.
Everything else in the complete branch — reported-key necessity, convexity, the middle
interval, and the three derivable soundness factors — is derived. -/
structure CompleteObligation (r : RangeRead) (res : Result) : Prop where
/-- The boundary reads' empty witnesses, as full-compatible joint bases. -/
joint : BoundaryJointBases r res
/-- The bridge's fourth factor: agreement on the complete value fixes the bracket. -/
bracket : BracketFactor r res
/-- **The general algorithm's correctness, pushed down to the empty theory.** The
hypotheses are the witness-exposing empty oracle, the complete-branch obligation (a
generic graft plus the bracket factor), and the truncated obligation. No hypothesis
mentions an offset, `EmptyInference` as such, or the finished `BoundaryNecessity`: the
arbitrary offset handling lives entirely inside `EmptyInferenceWitness` and the two
obligations, while the general case is the offset-free assembly. -/
theorem conflictRangeVal_spec_of_witness {r : RangeRead} {res : Result}
(hempty : EmptyInferenceWitness) (h : GeneralObligation r res)
(hc : CompleteObligation r res) (hread : Readable r res) :
Minimal r res (conflictRangeVal r res) := by
unfold conflictRangeVal
by_cases hkeys : res.keys = []
· rw [ite_eq_left hkeys]
exact minimal_emptyValue_of_emptyInference (emptyInference_of_witness hempty) hread hkeys
· rw [ite_eq_right hkeys]
by_cases hmore : res.more = true
· rw [ite_eq_left hmore]
by_cases hrev : r.reverse = true
· rw [ite_eq_left hrev]; exact h.revTrunc hmore hrev hkeys
· rw [ite_eq_right hrev]; exact h.fwdTrunc hmore (by simpa using hrev) hkeys
· rw [ite_eq_right hmore]
have hm : res.more = false := by simpa using hmore
unfold completeValue
split
· next hcan =>
exact minimal_canonicalRange_of_end_offset_le_one_general hread hm hkeys hcan.1 hcan.2
· next _hcan =>
split
· next hover =>
cases hr : r.reverse
· exact minimal_topRange_of_end_offset_ge_two_general hread hm hr hover.2.2.1 hover.1
hover.2.1 hover.2.2.2
· exact minimal_topRange_of_end_offset_ge_two_rev_general hread hm hr hover.2.2.1 hover.1
hover.2.1 hover.2.2.2
· next _hover =>
obtain ⟨db, hcomp⟩ := hread
have hlim : RangeRead.withinLimit r res.keys := hcomp.1
cases hr : r.reverse
· have hp : res.keys.Pairwise (· < ·) := (RangeRead.compatible_sortedLT hcomp hr).pairwise
have hbr := hc.bracket
unfold BracketFactor at hbr
rw [ite_eq_right (by simp [hr])] at hbr
exact minimal_completeRange_of_witness_joint hempty ⟨db, hcomp⟩ hr hm hkeys hp hlim
hc.joint hbr
· have hp : res.keys.Pairwise (· > ·) := (RangeRead.compatible_sortedGT hcomp hr).pairwise
have hbr := hc.bracket
unfold BracketFactor at hbr
rw [ite_eq_left (by simp [hr])] at hbr
exact minimal_completeRange_of_witness_joint_rev hempty ⟨db, hcomp⟩ hr hm hkeys hp hlim
hc.joint hbr
/-- Existence follows from the witness-exposing empty oracle and the two
nonempty obligations: the value witnesses a minimal sound range, with all offset handling
confined to the empty theory. -/
theorem conjecture_exists_minimal_conflict_range_of_witness {r : RangeRead} {res : Result}
(hempty : EmptyInferenceWitness) (h : GeneralObligation r res)
(hc : CompleteObligation r res) (hread : Readable r res) :
∃ cr : ConflictRange, Minimal r res cr :=
⟨conflictRangeVal r res, conflictRangeVal_spec_of_witness hempty h hc hread⟩
/-- **The general algorithm's correctness, from the empty inference, the boundary `ψ`,
the bracket factor, and the truncated obligation.** The empty branch is the empty
inference; the complete branch is `minimal_completeRange_of_factors`/`_rev`, with soundness
derived from `EmptyInference` and `BracketFactor`; the truncated branches are `h`'s
fields. The proof is a case split mirroring the definition. -/
theorem conflictRangeVal_spec {r : RangeRead} {res : Result}
(hempty : EmptyInference) (h : GeneralObligation r res)
(hread : Readable r res) (hψ : BoundaryNecessity r res)
(hbr : BracketFactor r res) :
Minimal r res (conflictRangeVal r res) := by
unfold conflictRangeVal
by_cases hkeys : res.keys = []
· rw [ite_eq_left hkeys]; exact minimal_emptyValue_of_emptyInference hempty hread hkeys
· rw [ite_eq_right hkeys]
by_cases hmore : res.more = true
· rw [ite_eq_left hmore]
by_cases hrev : r.reverse = true
· rw [ite_eq_left hrev]; exact h.revTrunc hmore hrev hkeys
· rw [ite_eq_right hrev]; exact h.fwdTrunc hmore (by simpa using hrev) hkeys
· rw [ite_eq_right hmore]
have hm : res.more = false := by simpa using hmore
unfold completeValue
split
· next hcan =>
exact minimal_canonicalRange_of_end_offset_le_one_general hread hm hkeys hcan.1 hcan.2
· next _hcan =>
split
· next hover =>
cases hr : r.reverse
· exact minimal_topRange_of_end_offset_ge_two_general hread hm hr hover.2.2.1 hover.1
hover.2.1 hover.2.2.2
· exact minimal_topRange_of_end_offset_ge_two_rev_general hread hm hr hover.2.2.1 hover.1
hover.2.1 hover.2.2.2
· next _hover =>
unfold BracketFactor at hbr
split at hbr
· next hr =>
exact minimal_completeRange_of_factors_rev hempty hread hr hm hkeys hψ hbr
· next hr =>
exact minimal_completeRange_of_factors hempty hread (by simpa using hr) hm hkeys
hψ hbr
/-- Existence follows from the empty inference, the boundary `ψ`, the
bracket factor, and the truncated obligation: the value witnesses a minimal sound
range. -/
theorem conjecture_exists_minimal_conflict_range {r : RangeRead} {res : Result}
(hempty : EmptyInference) (h : GeneralObligation r res)
(hread : Readable r res) (hψ : BoundaryNecessity r res)
(hbr : BracketFactor r res) :
∃ cr : ConflictRange, Minimal r res cr :=
⟨conflictRangeVal r res, conflictRangeVal_spec hempty h hread hψ hbr⟩
/-!
## The complete empty theory
This section packages the entire residual of the reduction into one hypothesis,
`EmptyTheoryComplete`, and proves the general algorithm correct from it. The hypothesis
is deliberately stated at the granularity of the empty theory's outputs rather than as
the finished general theorem: `witness` is the empty-result theory in flip-witness form
(the strength the graft consumes), `joint` is the generic graft that extends those
witnesses across the reported interval, `bracket` is the observability gap split, and
`truncated` is the one-sided graft for truncated results. Each is an instance of the
empty theory's analysis at the boundary reads; none is an offset analysis of the general
read. With them the general case is the offset-free assembly.
`EmptyTheoryComplete` implies the abstract `EmptyInference` (`EmptyTheoryComplete.emptyInference`)
and the existence statement (`exists_minimal_conflict_range_of_complete`). It is the exact
form of "the empty theory is finished": there is nothing else to prove. In fact it is
*refuted*: each of `joint`, `bracket`, and `truncated` has an explicit compatible
counterexample, so the structure is uninhabited and the reduction is not a route to the
headline. -/
/-- **A complete empty theory, in reduction form.** The empty-result theory together with
the generic graft, the bracket gap split, and the truncated one-sided graft. Every field
is an output of the empty theory's analysis at a boundary read; in particular no field
mentions an offset. -/
structure EmptyTheoryComplete : Prop where
/-- The empty-result theory in flip-witness form: the strength the graft needs, which
an abstract `Minimal` does not expose. -/
witness : EmptyInferenceWitness
/-- The generic graft: each boundary read's empty flip witness extends to a
full-compatible database. Supplies both end ranges of the complete branch. The
`Readable` guard is necessary: a bridge database exists only when the reported keys
are the complete keys of some database, so an unrealizable pair makes the conclusion
false rather than merely unproved. -/
joint : ∀ (r : RangeRead) (res : Result), Readable r res → BoundaryJointBases r res
/-- The observability gap split: agreement on the complete value fixes the bracket.
The last bridge factor not derivable from the boundary emptinesses. -/
bracket : ∀ (r : RangeRead) (res : Result), BracketFactor r res
/-- The truncated one-sided graft: the used boundary read's witness extends across the
reported prefix (forward) or suffix (reverse), with the far boundary dropped. Guarded
by `Readable` for the same reason as `joint`. -/
truncated : ∀ (r : RangeRead) (res : Result), Readable r res → GeneralObligation r res
/-- **The empty branch, from a complete empty theory.** -/
theorem EmptyTheoryComplete.emptyInference (H : EmptyTheoryComplete) : EmptyInference :=
emptyInference_of_witness H.witness
/-- **The complete-branch obligation, from a complete empty theory.** The graft and the
bracket gap split of the empty theory give `CompleteObligation` for every realizable read. -/
theorem EmptyTheoryComplete.completeObligation (H : EmptyTheoryComplete) (r : RangeRead)
(res : Result) (hread : Readable r res) : CompleteObligation r res :=
⟨H.joint r res hread, H.bracket r res⟩
/-- **`BoundaryNecessity` for a complete read, from a complete empty theory.** This
recovers the legacy finished hypothesis from the witness-level graft, tying the two
forms together. -/
theorem EmptyTheoryComplete.boundaryNecessity (H : EmptyTheoryComplete) {r : RangeRead}
{res : Result} (hread : Readable r res) (hmore : res.more = false)
(hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· < ·)) (hlim : RangeRead.withinLimit r res.keys)
(hrev : r.reverse = false) : BoundaryNecessity r res :=
boundaryNecessity_of_jointBases hrev hmore hL hpair hlim (H.joint r res hread)
/-- **`BoundaryNecessity` for a complete read, from a complete empty theory, reverse.** -/
theorem EmptyTheoryComplete.boundaryNecessity_rev (H : EmptyTheoryComplete) {r : RangeRead}
{res : Result} (hread : Readable r res) (hmore : res.more = false)
(hL : res.keys ≠ [])
(hpair : res.keys.Pairwise (· > ·)) (hlim : RangeRead.withinLimit r res.keys)
(hrev : r.reverse = true) : BoundaryNecessity r res :=
boundaryNecessity_of_jointBases_rev hrev hmore hL hpair hlim (H.joint r res hread)
/-- **The general algorithm is correct from a complete empty theory.** The only
hypothesis beyond the empty theory is realizability; there is no offset, no
`EmptyInference` as a separate assumption, no `BoundaryNecessity`, and no bracket factor.
The general case is the offset-free assembly, with all offset handling confined to the
empty theory. -/
theorem conflictRangeVal_spec_complete (H : EmptyTheoryComplete) {r : RangeRead}
{res : Result} (hread : Readable r res) :
Minimal r res (conflictRangeVal r res) :=
conflictRangeVal_spec_of_witness H.witness (H.truncated r res hread)
(H.completeObligation r res hread) hread
/-- **Existence from a complete empty theory.** -/
theorem exists_minimal_conflict_range_of_complete (H : EmptyTheoryComplete) {r : RangeRead}
{res : Result} (hread : Readable r res) :
∃ cr : ConflictRange, Minimal r res cr :=
⟨conflictRangeVal r res, conflictRangeVal_spec_complete H hread⟩
/-!
### Positive-offset empty witnesses
The cross-free and crossed empty cases at all positive begin offsets are proved in
`FormalConflictRange.Empty`; these are the witness-level companions, exposing the
flip pairs those necessity proofs build.
-/
/-- **The cross-free empty witness at or above `B`, all positive begin offsets.** The
witness-level companion of `necessary_of_begin_le_of_le_general`. -/
theorem emptyWitness_beginLe_of_le_general {r : RangeRead}
(hbegin : 1 ≤ r.begin.offset) (hoE : 2 ≤ r.end_.offset) (hne : ¬ AlwaysEmpty r)
(hle : r.begin.key ≤ r.end_.key) {k : Key} (hk : r.begin.key ≤ (k : WithTop Key)) :
EmptyWitness r k := by
have hBne : r.begin.key ≠ (⊤ : WithTop Key) :=
begin_key_ne_top_of_not_alwaysEmpty hbegin hne
obtain ⟨b₀, hb₀⟩ : ∃ b₀ : Key, r.begin.key = (↑b₀ : WithTop Key) := by
cases h : r.begin.key with
| top => exact absurd h hBne
| coe b₀ => exact ⟨b₀, rfl⟩
have hbk : b₀ ≤ k := by rw [hb₀] at hk; exact WithTop.coe_le_coe.mp hk
have hkb : ¬ (k : WithTop Key) < r.begin.key := by
rw [hb₀]; exact not_lt.mpr (WithTop.coe_le_coe.mpr hbk)
set b : ℕ := (r.begin.offset - 1).toNat with hbdef
set e : ℕ := (r.end_.offset - 1).toNat with hedef
have he1 : 1 ≤ e := by omega
by_cases hEtop : r.end_.key = ⊤
· obtain ⟨dbJ, hdbJ, hkJ, hlenJ⟩ := exists_db_ge_avoid b₀ b k
let db₂ : DB := ⟨dbJ.keys, dbJ.sorted⟩
have hkeys₂ : db₂.keys = dbJ.keys := rfl
have hk₂ : k ∉ db₂.keys := by rw [hkeys₂]; exact hkJ
have hcntB₂ : cnt db₂ r.begin.key = 0 := by
rw [hb₀, cnt_coe, hkeys₂, countP_lt_eq_zero_of_forall_ge (fun x hx => hdbJ x hx)]
have hcntE₂ : cnt db₂ r.end_.key = b := by
rw [hEtop, cnt_top, hkeys₂, hlenJ]
have hlen₂ : db₂.keys.length = b := hlenJ
have hcomp₂ : RangeRead.Compatible db₂ r { keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_psi (db := db₂) (r := r) hbegin (by omega)).mpr
(Or.inl (by rw [hlen₂, hcntB₂]; omega)))
have hcntB₁ : cnt (db₂.insert k hk₂) r.begin.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.begin.key) hkb, hcntB₂]
have hnot₁ : ¬ RangeRead.Compatible (db₂.insert k hk₂) r { keys := [], more := false } := by
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_psi (db := db₂.insert k hk₂) (r := r) hbegin (by omega)]
rintro (hh | hh)
· rw [DB.insert_keys, List.orderedInsert_length, hlen₂, hcntB₁] at hh; omega
· rw [hEtop, cnt_top, DB.insert_keys, List.orderedInsert_length, hlen₂, hcntB₁] at hh
omega
refine ⟨db₂, hcomp₂, ?_⟩
rw [toggle, dite_eq_right hk₂]; exact hnot₁
· obtain ⟨e₀, he₀⟩ : ∃ e₀ : Key, r.end_.key = (↑e₀ : WithTop Key) := by
cases h : r.end_.key with
| top => exact absurd h hEtop
| coe e₀ => exact ⟨e₀, rfl⟩
have hbe₀ : b₀ ≤ e₀ := by
have hh := hle; rw [hb₀, he₀] at hh; exact WithTop.coe_le_coe.mp hh
rcases lt_or_ge b e with hlt_be | hge_be
· obtain ⟨dbJ, hdbJ, hkJ, hlenJ⟩ := exists_db_ge_avoid e₀ b k
let db₂ : DB := ⟨dbJ.keys, dbJ.sorted⟩
have hkeys₂ : db₂.keys = dbJ.keys := rfl
have hk₂ : k ∉ db₂.keys := by rw [hkeys₂]; exact hkJ
have hlen₂ : db₂.keys.length = b := by rw [hkeys₂, hlenJ]
have hcntB₂ : cnt db₂ r.begin.key = 0 := by
rw [hb₀, cnt_coe, hkeys₂, countP_lt_eq_zero_of_forall_ge]
intro x hx
exact le_trans hbe₀ (hdbJ x hx)
have hcntE₂ : cnt db₂ r.end_.key = 0 := by
rw [he₀, cnt_coe, hkeys₂, countP_lt_eq_zero_of_forall_ge (fun x hx => hdbJ x hx)]
have hlen₁ : (db₂.insert k hk₂).keys.length = b + 1 := by
rw [DB.insert_keys, List.orderedInsert_length, hlen₂]
have hcntB₁ : cnt (db₂.insert k hk₂) r.begin.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.begin.key) hkb, hcntB₂]
have hcomp₂ : RangeRead.Compatible db₂ r { keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_psi (db := db₂) (r := r) hbegin (by omega)).mpr
(Or.inl (by rw [hlen₂, hcntB₂]; omega)))
have hnot₁ : ¬ RangeRead.Compatible (db₂.insert k hk₂) r { keys := [], more := false } := by
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_psi (db := db₂.insert k hk₂) (r := r) hbegin (by omega)]
rintro (hh | hh)
· rw [hlen₁, hcntB₁] at hh; omega
· rw [hcntB₁] at hh
by_cases hkE : r.end_.key ≤ (k : WithTop Key)
· rw [cnt_insert_not_lt db₂ k hk₂ (v := r.end_.key) (by
rw [he₀]; exact not_lt.mpr (WithTop.coe_le_coe.mpr
(by rw [he₀] at hkE; exact WithTop.coe_le_coe.mp hkE))), hcntE₂] at hh
omega
· have hke₀ : k < e₀ := by
rw [he₀] at hkE; exact WithTop.coe_lt_coe.mp (lt_of_not_ge hkE)
rw [cnt_insert_lt db₂ k hk₂ (v := r.end_.key) (by
rw [he₀]; exact WithTop.coe_lt_coe.mpr hke₀), hcntE₂] at hh
omega
refine ⟨db₂, hcomp₂, ?_⟩
rw [toggle, dite_eq_right hk₂]; exact hnot₁
· have hed : e ≤ b := hge_be
have hroom := tsub_add_one_le_intervalCard_of_le_general hbegin hoE hle hne hed
by_cases hkE : r.end_.key ≤ (k : WithTop Key)
· have hke₀ : e₀ ≤ k := by rw [he₀] at hkE; exact WithTop.coe_le_coe.mp hkE
have hkEnlt : ¬ (k : WithTop Key) < r.end_.key := by
rw [he₀]; exact not_lt.mpr (WithTop.coe_le_coe.mpr hke₀)
obtain ⟨dbA, hdbA, hlenA⟩ :=
exists_db_keysIn (B := r.begin.key) (E := r.end_.key) (m := b - e + 1)
(by simpa only [← hbdef, ← hedef] using hroom)
have hAhi : ∀ x ∈ dbA.keys, x < e₀ := fun x hx => by
have h := hdbA x hx; rw [hb₀, he₀] at h; exact (mem_keysIn_coe.mp h).2
have hAlo : ∀ x ∈ dbA.keys, b₀ ≤ x := fun x hx => by
have h := hdbA x hx; rw [hb₀, he₀] at h; exact (mem_keysIn_coe.mp h).1
have hAk : k ∉ dbA.keys := fun h => absurd (hAhi k h) (not_lt.mpr hke₀)
obtain ⟨dbJ, hdbJ, hkJ, hlenJ⟩ := exists_db_ge_avoid e₀ (e - 1) k
have hcrossJ : ∀ x ∈ dbA.keys, ∀ y ∈ dbJ.keys, x < y :=
fun x hx y hy => lt_of_lt_of_le (hAhi x hx) (hdbJ y hy)
let db₂ : DB := ⟨dbA.keys ++ dbJ.keys,
List.sortedLT_append.mpr ⟨dbA.sorted, dbJ.sorted, hcrossJ⟩⟩
have hkeys₂ : db₂.keys = dbA.keys ++ dbJ.keys := rfl
have hk₂ : k ∉ db₂.keys := by
rw [hkeys₂, List.mem_append]; rintro (h | h); exacts [hAk h, hkJ h]
have hlen₂ : db₂.keys.length = b := by
rw [hkeys₂, List.length_append, hlenA, hlenJ]; simp only [hbdef, hedef]; omega
have hcntB₂ : cnt db₂ r.begin.key = 0 := by
rw [hb₀, cnt_coe, hkeys₂, countP_lt_eq_zero_of_forall_ge]
intro x hx
rw [List.mem_append] at hx
rcases hx with hx | hx
· exact hAlo x hx
· exact le_trans hbe₀ (hdbJ x hx)
have hcntE₂ : cnt db₂ r.end_.key = b - e + 1 := by
rw [he₀, cnt_coe, hkeys₂, List.countP_append,
countP_lt_eq_length_of_forall_lt hAhi, hlenA,
countP_lt_eq_zero_of_forall_ge (fun x hx => hdbJ x hx), Nat.add_zero]
have hcntB₁ : cnt (db₂.insert k hk₂) r.begin.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.begin.key) hkb, hcntB₂]
have hcntE₁ : cnt (db₂.insert k hk₂) r.end_.key = b - e + 1 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.end_.key) hkEnlt, hcntE₂]
have hlen₁ : (db₂.insert k hk₂).keys.length = b + 1 := by
rw [DB.insert_keys, List.orderedInsert_length, hlen₂]
have hcomp₂ : RangeRead.Compatible db₂ r { keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_psi (db := db₂) (r := r) hbegin (by omega)).mpr
(Or.inl (by rw [hlen₂, hcntB₂]; omega)))
have hnot₁ : ¬ RangeRead.Compatible (db₂.insert k hk₂) r { keys := [], more := false } := by
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_psi (db := db₂.insert k hk₂) (r := r) hbegin (by omega)]
rintro (hh | hh)
· rw [hlen₁, hcntB₁] at hh; omega
· rw [hcntE₁, hcntB₁, hbdef, hedef] at hh; omega
refine ⟨db₂, hcomp₂, ?_⟩
rw [toggle, dite_eq_right hk₂]; exact hnot₁
· have hke₀ : k < e₀ := by
rw [he₀] at hkE; exact WithTop.coe_lt_coe.mp (lt_of_not_ge hkE)
have hkElt : (k : WithTop Key) < r.end_.key := by
rw [he₀]; exact WithTop.coe_lt_coe.mpr hke₀
obtain ⟨dbA, hdbA, hkA, hlenA⟩ :=
exists_db_keysIn_avoid (B := r.begin.key) (E := r.end_.key) (k := k) (m := b - e)
(by simpa only [Nat.cast_add, Nat.cast_one, hbdef, hedef] using hroom)
have hAhi : ∀ x ∈ dbA.keys, x < e₀ := fun x hx => by
have h := hdbA x hx; rw [hb₀, he₀] at h; exact (mem_keysIn_coe.mp h).2
have hAlo : ∀ x ∈ dbA.keys, b₀ ≤ x := fun x hx => by
have h := hdbA x hx; rw [hb₀, he₀] at h; exact (mem_keysIn_coe.mp h).1
obtain ⟨dbJ, hdbJ, hkJ, hlenJ⟩ := exists_db_ge_avoid e₀ e k
have hcrossJ : ∀ x ∈ dbA.keys, ∀ y ∈ dbJ.keys, x < y :=
fun x hx y hy => lt_of_lt_of_le (hAhi x hx) (hdbJ y hy)
let db₂ : DB := ⟨dbA.keys ++ dbJ.keys,
List.sortedLT_append.mpr ⟨dbA.sorted, dbJ.sorted, hcrossJ⟩⟩
have hkeys₂ : db₂.keys = dbA.keys ++ dbJ.keys := rfl
have hk₂ : k ∉ db₂.keys := by
rw [hkeys₂, List.mem_append]; rintro (h | h); exacts [hkA h, hkJ h]
have hlen₂ : db₂.keys.length = b := by
rw [hkeys₂, List.length_append, hlenA, hlenJ]; simp only [hbdef, hedef]; omega
have hcntB₂ : cnt db₂ r.begin.key = 0 := by
rw [hb₀, cnt_coe, hkeys₂, countP_lt_eq_zero_of_forall_ge]
intro x hx
rw [List.mem_append] at hx
rcases hx with hx | hx
· exact hAlo x hx
· exact le_trans hbe₀ (hdbJ x hx)
have hcntE₂ : cnt db₂ r.end_.key = b - e := by
rw [he₀, cnt_coe, hkeys₂, List.countP_append,
countP_lt_eq_length_of_forall_lt hAhi, hlenA,
countP_lt_eq_zero_of_forall_ge (fun x hx => hdbJ x hx), Nat.add_zero]
have hcntB₁ : cnt (db₂.insert k hk₂) r.begin.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.begin.key) hkb, hcntB₂]
have hcntE₁ : cnt (db₂.insert k hk₂) r.end_.key = b - e + 1 := by
rw [cnt_insert_lt db₂ k hk₂ (v := r.end_.key) hkElt, hcntE₂]
have hlen₁ : (db₂.insert k hk₂).keys.length = b + 1 := by
rw [DB.insert_keys, List.orderedInsert_length, hlen₂]
have hcomp₂ : RangeRead.Compatible db₂ r { keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_psi (db := db₂) (r := r) hbegin (by omega)).mpr
(Or.inr (by rw [hcntE₂, hcntB₂, hbdef, hedef]; omega)))
have hnot₁ : ¬ RangeRead.Compatible (db₂.insert k hk₂) r { keys := [], more := false } := by
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_psi (db := db₂.insert k hk₂) (r := r) hbegin (by omega)]
rintro (hh | hh)
· rw [hlen₁, hcntB₁] at hh; omega
· rw [hcntE₁, hcntB₁, hbdef, hedef] at hh; omega
refine ⟨db₂, hcomp₂, ?_⟩
rw [toggle, dite_eq_right hk₂]; exact hnot₁
/-- **The crossed empty witness at or above `B`, all positive begin offsets.** The
witness-level companion of `necessary_of_begin_le_general`. -/
theorem emptyWitness_beginLe_general {r : RangeRead}
(hbegin : 1 ≤ r.begin.offset) (hoE : 2 ≤ r.end_.offset) (hne : ¬ AlwaysEmpty r)
(hEB : r.end_.key ≤ r.begin.key) {k : Key} (hk : r.begin.key ≤ (k : WithTop Key)) :
EmptyWitness r k := by
have hBne : r.begin.key ≠ (⊤ : WithTop Key) :=
begin_key_ne_top_of_not_alwaysEmpty hbegin hne
obtain ⟨b, hb⟩ : ∃ b : Key, r.begin.key = (↑b : WithTop Key) := by
cases hkb : r.begin.key with
| top => exact absurd hkb hBne
| coe b => exact ⟨b, rfl⟩
have hbk : b ≤ k := by rw [hb] at hk; exact WithTop.coe_le_coe.mp hk
rw [hb] at hEB
have heb : ¬ ((r.end_.offset - 1).toNat ≤ (r.begin.offset - 1).toNat) := by
intro hle
apply hne
intro db
rw [completeKeys_eq_nil_iff_psi (db := db) (r := r) hbegin (by omega)]
exact Or.inr (by
have hmono : cnt db r.end_.key ≤ cnt db r.begin.key :=
cnt_le_cnt_of_le db (by rw [hb]; exact hEB)
omega)
obtain ⟨db₂, hdb₂, hk₂, hlen₂⟩ :=
exists_db_ge_avoid b ((r.begin.offset - 1).toNat) k
have hcntB₂ : cnt db₂ r.begin.key = 0 := by
rw [hb, cnt_coe, List.countP_eq_zero]
intro x hx; simp only [decide_eq_true_eq]
exact not_lt.mpr (hdb₂ x hx)
have hcntE₂ : cnt db₂ r.end_.key = 0 := by
rw [cnt, List.countP_eq_zero]
intro x hx; simp only [decide_eq_true_eq]
exact not_lt.mpr (le_trans hEB (WithTop.coe_le_coe.mpr (hdb₂ x hx)))
have hcntB₁ : cnt (db₂.insert k hk₂) r.begin.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.begin.key), hcntB₂]
rw [hb]; exact not_lt.mpr (WithTop.coe_le_coe.mpr hbk)
have hcntE₁ : cnt (db₂.insert k hk₂) r.end_.key = 0 := by
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.end_.key), hcntE₂]
exact not_lt.mpr (le_trans hEB (WithTop.coe_le_coe.mpr hbk))
have hlen₁ : (db₂.insert k hk₂).keys.length = (r.begin.offset - 1).toNat + 1 := by
rw [DB.insert_keys, List.orderedInsert_length, hlen₂]
have hcomp₂ : RangeRead.Compatible db₂ r { keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_psi (db := db₂) (r := r) hbegin (by omega)).mpr
(Or.inl (by rw [hlen₂, hcntB₂]; omega)))
have hnot₁ : ¬ RangeRead.Compatible (db₂.insert k hk₂) r { keys := [], more := false } := by
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_psi (db := db₂.insert k hk₂) (r := r) hbegin (by omega)]
rintro (hh | hh)
· rw [hlen₁, hcntB₁] at hh; omega
· rw [hcntB₁, hcntE₁] at hh
have := Nat.lt_of_not_le heb; omega
refine ⟨db₂, hcomp₂, ?_⟩
rw [toggle, dite_eq_right hk₂]; exact hnot₁
/-- **The crossed empty witness inside `[E, B)`, all positive begin offsets.** The
witness-level companion of `necessary_of_mem_interval_general`. -/
theorem emptyWitness_mem_interval_general {r : RangeRead}
(hbegin : 1 ≤ r.begin.offset) (hoE : 2 ≤ r.end_.offset) (hne : ¬ AlwaysEmpty r)
(hEB : r.end_.key ≤ r.begin.key)
(hgap : ((r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat : ℕ∞) ≤
intervalCard r.end_.key r.begin.key)
{k : Key} (hkE : r.end_.key ≤ (k : WithTop Key))
(hkB : (k : WithTop Key) < r.begin.key) : EmptyWitness r k := by
have hBne : r.begin.key ≠ (⊤ : WithTop Key) :=
begin_key_ne_top_of_not_alwaysEmpty hbegin hne
obtain ⟨b, hb⟩ : ∃ b : Key, r.begin.key = (↑b : WithTop Key) := by
cases hkb : r.begin.key with
| top => exact absurd hkb hBne
| coe b => exact ⟨b, rfl⟩
have hkb : k < b := by rw [hb] at hkB; exact WithTop.coe_lt_coe.mp hkB
obtain ⟨e, he⟩ : ∃ e : Key, r.end_.key = (↑e : WithTop Key) := by
cases hke : r.end_.key with
| top => rw [hke] at hkE; exact absurd hkE (not_le.mpr (WithTop.coe_lt_top k))
| coe e => exact ⟨e, rfl⟩
have hke : e ≤ k := by rw [he] at hkE; exact WithTop.coe_le_coe.mp hkE
have heb : e ≤ b := le_trans hke (le_of_lt hkb)
have hEB' : r.end_.key ≤ r.begin.key := hEB
rw [hb] at hEB
obtain ⟨g, hg⟩ : ∃ g : ℕ, g = (r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat :=
⟨_, rfl⟩
have hgpos : 1 ≤ g := by
have hlt : (r.begin.offset - 1).toNat < (r.end_.offset - 1).toNat :=
Nat.lt_of_not_le (by
intro hle
apply hne
intro db
rw [completeKeys_eq_nil_iff_psi (db := db) (r := r) hbegin (by omega)]
exact Or.inr (by
have hmono : cnt db r.end_.key ≤ cnt db r.begin.key :=
cnt_le_cnt_of_le db hEB'
omega))
rw [hg]; exact Nat.sub_pos_of_lt hlt
have hcardA : (((g - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
rw [Nat.sub_add_cancel hgpos, hg]; exact hgap
obtain ⟨dbA, hdbA, hkA, hlenA⟩ :=
exists_db_keysIn_avoid (B := r.end_.key) (E := r.begin.key) (k := k) (m := g - 1) hcardA
obtain ⟨dbJ, hdbJ, hkJ, hlenJ⟩ := exists_db_ge_avoid b ((r.begin.offset - 1).toNat + 1) k
have hAe : ∀ x ∈ dbA.keys, e ≤ x := fun x hx => by
have h := (hdbA x hx).1; rw [he] at h; exact WithTop.coe_le_coe.mp h
have hAb : ∀ x ∈ dbA.keys, x < b := fun x hx => by
have h := (hdbA x hx).2; rw [hb] at h; exact WithTop.coe_lt_coe.mp h
have hcross : ∀ x ∈ dbA.keys, ∀ y ∈ dbJ.keys, x < y :=
fun x hx y hy => lt_of_lt_of_le (hAb x hx) (hdbJ y hy)
let db₂ : DB := ⟨dbA.keys ++ dbJ.keys,
List.sortedLT_append.mpr ⟨dbA.sorted, dbJ.sorted, hcross⟩⟩
have hkeys₂ : db₂.keys = dbA.keys ++ dbJ.keys := rfl
have hk₂ : k ∉ db₂.keys := by
rw [hkeys₂, List.mem_append]; rintro (h | h); exacts [hkA h, hkJ h]
have hlen₂ : db₂.keys.length = g + (r.begin.offset - 1).toNat := by
rw [hkeys₂, List.length_append, hlenA, hlenJ]
have hgg : g = (r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat := hg
omega
have hcntB₂ : cnt db₂ r.begin.key = g - 1 := by
rw [hb, cnt_coe, hkeys₂, List.countP_append]
rw [countP_lt_eq_length_of_forall_lt hAb, hlenA,
countP_lt_eq_zero_of_forall_ge (fun x hx => hdbJ x hx), Nat.add_zero]
have hcntE₂ : cnt db₂ r.end_.key = 0 := by
rw [he, cnt_coe, hkeys₂, List.countP_append]
rw [countP_lt_eq_zero_of_forall_ge (l := dbA.keys) hAe,
countP_lt_eq_zero_of_forall_ge (l := dbJ.keys)
(fun x hx => le_trans heb (hdbJ x hx)), Nat.add_zero]
have hcntB₁ : cnt (db₂.insert k hk₂) r.begin.key = g := by
rw [cnt_insert_lt db₂ k hk₂ (v := r.begin.key) (by rw [hb]; exact WithTop.coe_lt_coe.mpr hkb),
hcntB₂]
omega
have hcntE₁ : cnt (db₂.insert k hk₂) r.end_.key = 0 := by
have hke' : ¬ (k : WithTop Key) < r.end_.key := by
rw [he]; exact not_lt.mpr (WithTop.coe_le_coe.mpr hke)
rw [cnt_insert_not_lt db₂ k hk₂ (v := r.end_.key) hke', hcntE₂]
have hcomp₁ : RangeRead.Compatible (db₂.insert k hk₂) r { keys := [], more := false } :=
compatible_empty_iff_complete_nil.mpr
((completeKeys_eq_nil_iff_psi (db := db₂.insert k hk₂) (r := r) hbegin (by omega)).mpr
(Or.inr (by
rw [hcntE₁, hcntB₁]
have hgg : g = (r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat := hg
omega)))
have hnot₂ : ¬ RangeRead.Compatible db₂ r { keys := [], more := false } := by
intro hc
rw [compatible_empty_iff_complete_nil,
completeKeys_eq_nil_iff_psi (db := db₂) (r := r) hbegin (by omega)] at hc
have hgg : g = (r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat := hg
rcases hc with hc | hc
· rw [hlen₂, hcntB₂] at hc; omega
· rw [hcntE₂, hcntB₂] at hc; omega
refine ⟨db₂.insert k hk₂, hcomp₁, ?_⟩
have hkeys : (toggle (db₂.insert k hk₂) k).keys = db₂.keys := by
rw [toggle, dite_eq_left (DB.mem_insert_self _ _ _)]
exact DB.erase_insert_keys _ k hk₂
intro hc
exact hnot₂ ((RangeRead.compatible_congr
(RangeRead.completeKeys_congr hkeys r)).mp hc)
/-!
### The empty witness oracle for positive begin offsets, overshooting end
With `begin.offset ≥ 1` and `end.offset ≥ 2`, the empty value is the top range
(cross-free) or the crossed candidate; the witnesses extracted above supply every key,
so `EmptyInferenceWitnessOffOne` holds throughout this region.
-/
/-- **The empty witness oracle, `begin.offset ≥ 1`, `end.offset ≥ 2`, non-reversed.**
The two candidate branches of `emptyValue` (`topRange` and `crossedRangeGeneral`) are
covered by `emptyWitness_beginLe_of_le_general`, `emptyWitness_beginLe_general`, and
`emptyWitness_mem_interval_general`. -/
theorem emptyWitness_overshoot_fwd (r : RangeRead) (hbegin : 1 ≤ r.begin.offset)
(hend : 2 ≤ r.end_.offset) (_hrev : r.reverse = false)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
by_cases hle : r.begin.key ≤ r.end_.key
· have hv : emptyValue r = topRange r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0),
ite_eq_right (by omega), ite_eq_left hle]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_topRange_of_le_general (by omega) (by omega) hle rfl rfl
· intro k hk
rw [hv] at hk
exact emptyWitness_beginLe_of_le_general hbegin hend hAE hle hk.1
· have hcross : r.end_.key < r.begin.key := not_le.mp hle
have hEB : r.end_.key ≤ r.begin.key := le_of_lt hcross
have hv : emptyValue r = crossedRangeGeneral r := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_right (by omega : ¬ r.begin.offset ≤ 0),
ite_eq_right (by omega), ite_eq_right (not_le.mpr hcross)]
by_cases hgap : ((r.end_.offset - 1).toNat - (r.begin.offset - 1).toNat) ≤
intervalCard r.end_.key r.begin.key
· rw [crossedRangeGeneral, ite_eq_left hgap] at hv
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_top_end_of_crossed_general (by omega) (by omega) hEB rfl rfl
· intro k hk
rw [hv] at hk
rcases lt_or_ge (k : WithTop Key) r.begin.key with hkB | hkB
· exact emptyWitness_mem_interval_general hbegin hend hAE hEB
(by simpa using hgap) hk.1 hkB
· exact emptyWitness_beginLe_general hbegin hend hAE hEB hkB
· rw [crossedRangeGeneral, ite_eq_right hgap] at hv
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_top_begin_of_short_general (by omega) (by omega) hEB
(not_le.mp hgap) rfl rfl
· intro k hk
rw [hv] at hk
exact emptyWitness_beginLe_general hbegin hend hAE hEB hk.1
/-- **The empty witness oracle, `begin.offset ≥ 1`, `end.offset ≥ 2`, any traversal.**
Reversed is reduced to non-reversed by traversal invariance. -/
theorem emptyWitness_overshoot (r : RangeRead) (hbegin : 1 ≤ r.begin.offset)
(hend : 2 ≤ r.end_.offset)
(hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
cases hrev : r.reverse
· exact emptyWitness_overshoot_fwd r hbegin hend hrev hread
· have hread' : Readable { r with reverse := false } { keys := [], more := false } := by
obtain ⟨db, hc⟩ := hread
refine ⟨db, ?_⟩
have := (compatible_empty_flip (db := db) (r := r)).mp hc
rwa [show ({ r with reverse := !r.reverse } : RangeRead) = { r with reverse := false }
from by simp [hrev]] at this
have hf := emptyWitness_overshoot_fwd { r with reverse := false } hbegin hend rfl hread'
rw [show ({ r with reverse := false } : RangeRead) =
{ r with reverse := !r.reverse } from by simp [hrev]] at hf
refine ⟨?_, ?_⟩
· simpa [emptyValue_reverse] using (sound_empty_flip (r := r)).mpr hf.1
· intro k hk
rw [← emptyValue_reverse] at hk
exact emptyWitness_flip.mp (hf.2 k hk)
/-- **The empty witness oracle, nonpositive begin and overshooting end, any selector
order.** With `begin.offset ≤ 0` and `end.offset ≥ 2`, `emptyValue` is the full range
`[⊥, ⊤)` (unless the read is trivially empty). Soundness is
`sound_fullRange_of_nonpos_overshoot_all`; the flip witness at any key is the singleton
`{k}`, incompatible for every `k` by `not_compatible_singleton_overshoot_all`. This is the
crossed half of weaselbot's item 2, now discharged: `emptyValue` no longer returns the
unsound crossed bottom range here. -/
theorem emptyWitness_nonpos_overshoot (r : RangeRead) (hbegin : r.begin.offset ≤ 0)
(hend : 2 ≤ r.end_.offset)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), (⊤ : WithTop Key)⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_left hend]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_fullRange_of_nonpos_overshoot_all rfl rfl
· intro k _hk
exact ⟨emptyDB, compatible_emptyDB_emptyRes r, by
have htoggle : toggle emptyDB k = singleton k := by
unfold toggle
rw [dite_eq_right (by simp [emptyDB])]
rfl
rw [htoggle]
exact not_compatible_singleton_overshoot_all hbegin hend⟩
/-- **The empty witness oracle, nonpositive begin and `end.offset = 1`, cross-free.**
With `begin.offset ≤ 0`, `end.offset = 1` and `begin.key ≤ end.key`, `emptyValue` is the
bottom range `[⊥, end.key)`, and every key below `end.key` has the singleton flip witness:
the empty database is compatible (`compatible_emptyDB_emptyRes`) and toggling `k` gives
`{k}`, whose complete keys are nonempty (`not_compatible_singleton_self`). This is the
witness-exposing companion of `minimal_bottomRange_of_nonpos_end_one`. -/
theorem emptyWitness_nonpos_end_one_crossFree (r : RangeRead) (hbegin : r.begin.offset ≤ 0)
(hend : r.end_.offset = 1) (hle : r.begin.key ≤ r.end_.key)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), r.end_.key⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_right (by omega), ite_eq_left hle]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_bottomRange_of_nonpos_underEnd_le hbegin (le_of_eq hend) hle rfl rfl
· intro k hk
rw [hv] at hk
have htoggle : toggle emptyDB k = singleton k := by
unfold toggle
rw [dite_eq_right (by simp [emptyDB])]
rfl
exact ⟨emptyDB, compatible_emptyDB_emptyRes r, by
rw [htoggle]; exact not_compatible_singleton_self hbegin hend hk.2⟩
/-- **The empty witness oracle, nonpositive begin, `end.offset = 1`, crossed short gap.**
With `begin.offset ≤ 0`, `end.offset = 1`, crossed selectors (`end.key < begin.key`) and a
short gap, `emptyValue` is the bottom range `[⊥, end.key)`, and every key below `end.key`
has the singleton flip witness. Soundness is
`sound_bottomRange_of_nonpos_end_one_short`; necessity is the same
`necessary_of_nonpos_end_one` as the cross-free case. This closes weaselbot's second
counterexample (the always-clamping begin anchor) to the extent the short gap reaches. -/
theorem emptyWitness_nonpos_end_one_crossedShort (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset = 1)
(hcross : r.end_.key < r.begin.key)
(hgap : intervalCard r.end_.key r.begin.key <
(((1 - r.begin.offset).toNat : ℕ) : ℕ∞))
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hg : intervalCard r.end_.key r.begin.key <
(((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞) := by
rw [hend]; exact hgap
have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), r.end_.key⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_right (by omega : ¬ 2 ≤ r.end_.offset),
ite_eq_right (not_le.mpr hcross), ite_eq_left hg]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_bottomRange_of_nonpos_end_one_short hbegin hend (le_of_lt hcross) hgap rfl rfl
· intro k hk
rw [hv] at hk
have htoggle : toggle emptyDB k = singleton k := by
unfold toggle
rw [dite_eq_right (by simp [emptyDB])]
rfl
exact ⟨emptyDB, compatible_emptyDB_emptyRes r, by
rw [htoggle]; exact not_compatible_singleton_self hbegin hend hk.2⟩
theorem compat_regionP {db : DB} {r : RangeRead}
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0) (hBE : r.begin.key ≤ r.end_.key)
(hsmall : (1 - r.end_.offset).toNat < (1 - r.begin.offset).toNat ∨
intervalCard ((([] : Key)) : WithTop Key) r.begin.key <
(((1 - r.begin.offset).toNat : ℕ) : ℕ∞)) :
(RangeRead.Compatible db r { keys := [], more := false } ↔
cnt db r.end_.key ≤ (1 - r.end_.offset).toNat) := by
rw [compatible_empty_iff_nonpos_counts (db := db) hbegin hend]
set b : ℕ := (1 - r.begin.offset).toNat with hb
set e : ℕ := (1 - r.end_.offset).toNat with he
have hmono : cnt db r.begin.key ≤ cnt db r.end_.key := cnt_le_cnt_of_le db hBE
have hsmall' : e < b ∨ (cnt db r.begin.key : ℤ) < b := by
rcases hsmall with h | h
· exact Or.inl h
· refine Or.inr ?_
have h1 := cnt_le_intervalCard_nil db r.begin.key
have h2 : (cnt db r.begin.key : ℕ∞) < (b : ℕ∞) := lt_of_le_of_lt h1 h
exact_mod_cast h2
constructor
· intro h
rcases hsmall' with hs | hs
· by_cases hcb : (b : ℤ) ≤ (cnt db r.begin.key : ℤ)
· rw [max_eq_left (by omega)] at h
have : (cnt db r.begin.key : ℤ) ≤ cnt db r.end_.key := by exact_mod_cast hmono
omega
· rw [max_eq_right (by omega)] at h; omega
· rw [max_eq_right (by omega)] at h; omega
· intro h
have : (cnt db r.end_.key : ℤ) - e ≤ 0 := by omega
exact le_trans this (le_max_right _ _)
theorem compat_of_cnt {db : DB} {r : RangeRead}
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0)
{cB cE : ℕ} (hcB : cnt db r.begin.key = cB) (hcE : cnt db r.end_.key = cE) :
(RangeRead.Compatible db r { keys := [], more := false } ↔
(cE : ℤ) - ((1 - r.end_.offset).toNat : ℤ) ≤
max ((cB : ℤ) - ((1 - r.begin.offset).toNat : ℤ)) 0) := by
rw [compatible_empty_iff_nonpos_counts (db := db) hbegin hend, hcB, hcE]
theorem wI_gap {r : RangeRead}
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0) (hBE : r.begin.key ≤ r.end_.key)
(hne : ¬ AlwaysEmpty r) (hbe : (1 - r.begin.offset).toNat ≤ (1 - r.end_.offset).toNat)
(hCB : (((1 - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard ((([] : Key)) : WithTop Key) r.begin.key)
{k : Key} (hkB : r.begin.key ≤ (k : WithTop Key)) (hkE : (k : WithTop Key) < r.end_.key) :
EmptyWitness r k := by
set b : ℕ := (1 - r.begin.offset).toNat with hb
set e : ℕ := (1 - r.end_.offset).toNat with he
have hgap := tsub_add_one_le_intervalCard_of_not_alwaysEmpty_nonpos (r := r) hbegin hend
(by rw [← hb, ← he]; exact hbe) hne
obtain ⟨db, hk, hcB, hcE⟩ := exists_db_below_gap_avoid_gap hBE hkB hkE
(clo := b) (chi := e) (by rw [hb, he]; exact hbe) (by rw [hb]; exact hCB)
(by rw [he, hb]; exact hgap)
have hkBn : ¬ (k : WithTop Key) < r.begin.key := not_lt.mpr hkB
have htoggle : toggle db k = db.insert k hk := by
unfold toggle; rw [dite_eq_right hk]
have hbase : RangeRead.Compatible db r { keys := [], more := false } := by
rw [compat_of_cnt (r := r) hbegin hend hcB hcE]
rw [show ((1 - r.end_.offset).toNat : ℤ) = e from by rw [he],
show ((1 - r.begin.offset).toNat : ℤ) = b from by rw [hb]]
have : (e : ℤ) - e ≤ max ((b : ℤ) - b) 0 := by ring_nf; simp
exact this
refine ⟨db, hbase, ?_⟩
rw [htoggle]
have hcB' : cnt (db.insert k hk) r.begin.key = b := by
rw [cnt_insert_not_lt db k hk hkBn, hcB]
have hcE' : cnt (db.insert k hk) r.end_.key = e + 1 := by
rw [cnt_insert_lt db k hk hkE, hcE]
intro hcomp
rw [compat_of_cnt (r := r) hbegin hend hcB' hcE'] at hcomp
rw [show ((1 - r.end_.offset).toNat : ℤ) = e from by rw [he],
show ((1 - r.begin.offset).toNat : ℤ) = b from by rw [hb]] at hcomp
simp only [sub_self, max_eq_right le_rfl] at hcomp; omega
theorem wI_below {r : RangeRead}
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0) (hBE : r.begin.key ≤ r.end_.key)
(hne : ¬ AlwaysEmpty r) (hbe : (1 - r.begin.offset).toNat ≤ (1 - r.end_.offset).toNat)
(hCB : (((1 - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard ((([] : Key)) : WithTop Key) r.begin.key)
{k : Key} (hkB : (k : WithTop Key) < r.begin.key) :
EmptyWitness r k := by
set b : ℕ := (1 - r.begin.offset).toNat with hb
set e : ℕ := (1 - r.end_.offset).toNat with he
have hbe' : b ≤ e := hbe
have hgap := tsub_add_one_le_intervalCard_of_not_alwaysEmpty_nonpos (r := r) hbegin hend
hbe' hne
have hgap' : (((e - (b - 1) : ℕ)) : ℕ∞) ≤ intervalCard r.begin.key r.end_.key := by
have : e - (b - 1) = e - b + 1 := by omega
rw [this]; exact hgap
have hlo' : (((b - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard ((([] : Key)) : WithTop Key) r.begin.key := by
have : b - 1 + 1 = b := by omega
rw [this]; exact hCB
have hcl : b - 1 ≤ e := by omega
obtain ⟨db, hk, hcB, hcE⟩ := exists_db_below_gap_avoid_below hBE hkB
(clo := b - 1) (chi := e) hcl hlo' hgap'
have htoggle : toggle db k = db.insert k hk := by
unfold toggle; rw [dite_eq_right hk]
have hbase : RangeRead.Compatible db r { keys := [], more := false } := by
rw [compat_of_cnt (r := r) hbegin hend hcB hcE]
rw [show ((1 - r.end_.offset).toNat : ℤ) = e from by rw [he],
show ((1 - r.begin.offset).toNat : ℤ) = b from by rw [hb]]
have hbb : ((b - 1 : ℕ) : ℤ) - b = -1 := by omega
rw [hbb]
have : (e : ℤ) - e ≤ max (-1) 0 := by simp
exact this
refine ⟨db, hbase, ?_⟩
rw [htoggle]
have hcB' : cnt (db.insert k hk) r.begin.key = b := by
rw [cnt_insert_lt db k hk hkB, hcB]; omega
have hcE' : cnt (db.insert k hk) r.end_.key = e + 1 := by
rw [cnt_insert_lt db k hk (lt_of_lt_of_le hkB hBE), hcE]
intro hcomp
rw [compat_of_cnt (r := r) hbegin hend hcB' hcE'] at hcomp
rw [show ((1 - r.end_.offset).toNat : ℤ) = e from by rw [he],
show ((1 - r.begin.offset).toNat : ℤ) = b from by rw [hb]] at hcomp
simp only [sub_self, max_eq_right le_rfl] at hcomp; omega
/-- Region P witness. -/
theorem wP {r : RangeRead}
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0) (hBE : r.begin.key ≤ r.end_.key)
(hne : ¬ AlwaysEmpty r)
(hsmall : (1 - r.end_.offset).toNat < (1 - r.begin.offset).toNat ∨
intervalCard ((([] : Key)) : WithTop Key) r.begin.key <
(((1 - r.begin.offset).toNat : ℕ) : ℕ∞))
{k : Key} (hkE : (k : WithTop Key) < r.end_.key) :
EmptyWitness r k := by
set e : ℕ := (1 - r.end_.offset).toNat with he
have hroom := not_alwaysEmpty_intervalCard_bot (r := r) hbegin hend hne
have hroom' : (((e + 1 : ℕ)) : ℕ∞) ≤ intervalCard ((([] : Key)) : WithTop Key) r.end_.key := by
rw [← he] at hroom; exact hroom
obtain ⟨db, hdb, hk, hlen⟩ :=
exists_db_keysIn_avoid (B := ((([] : Key)) : WithTop Key)) (E := r.end_.key) (k := k)
(m := e) hroom'
have hcE : cnt db r.end_.key = e := by
rw [cnt_eq_length_of_forall_lt db (fun x hx => (hdb x hx).2), hlen]
have htoggle : toggle db k = db.insert k hk := by
unfold toggle; rw [dite_eq_right hk]
have hbase : RangeRead.Compatible db r { keys := [], more := false } := by
rw [compat_regionP (r := r) hbegin hend hBE hsmall]
rw [hcE]
refine ⟨db, hbase, ?_⟩
rw [htoggle]
have hcE' : cnt (db.insert k hk) r.end_.key = e + 1 := by
rw [cnt_insert_lt db k hk hkE, hcE]
intro hcomp
rw [compat_regionP (r := r) hbegin hend hBE hsmall, hcE'] at hcomp
omega
/-- **The crossed long-gap empty witness, `end.key ≤ k < begin.key`.** The flip pair is
the coupled-count construction: `db₀` stores one key below `end.key` together with
`1 - begin.offset - 1` keys of `[end.key, begin.key)` avoiding `k`, and finally `k`. Its
counts are `cnt end.key = 1` and `cnt begin.key = 1 - begin.offset`, so the empty result
is compatible on the first disjunct; erasing `k` drops the begin count by one, leaving
`1 - begin.offset - 1` in the gap and `cnt end.key = 1`, so both disjuncts fail. -/
theorem emptyWitness_nonpos_end_one_crossedLong_interval (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset = 1)
(hcross : r.end_.key < r.begin.key)
(hgap : (((1 - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r.end_.key r.begin.key)
(hne : ¬ AlwaysEmpty r)
{k : Key} (hkE : r.end_.key ≤ (k : WithTop Key))
(hkB : (k : WithTop Key) < r.begin.key) :
EmptyWitness r k := by
set N : ℕ := (1 - r.begin.offset).toNat with hN
have hNpos : 1 ≤ N := by omega
have hEbot : r.end_.key ≠ ((([] : Key)) : WithTop Key) :=
fun hbot => hne (alwaysEmpty_of_end_key_eq_bot hbegin hend (le_of_lt hcross) hbot)
have hpE : ((([] : Key)) : WithTop Key) < r.end_.key := by
have hle : ((([] : Key)) : WithTop Key) ≤ r.end_.key := by
cases r.end_.key with
| top => exact le_top
| coe e => exact WithTop.coe_le_coe.mpr (nil_le_key e)
exact lt_of_le_of_ne hle (Ne.symm hEbot)
have hcard : (((N - 1) + 1 : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
rw [Nat.sub_add_cancel hNpos]; rw [hN]; exact hgap
obtain ⟨dbA, hdbA, hkA, hlenA⟩ :=
exists_db_keysIn_avoid (B := r.end_.key) (E := r.begin.key) (k := k) (m := N - 1) hcard
have hdbAge : ∀ x ∈ dbA.keys, r.end_.key ≤ (x : WithTop Key) := by
intro x hx
have h := hdbA x hx
exact h.1
have hdbAlt : ∀ x ∈ dbA.keys, (x : WithTop Key) < r.begin.key := by
intro x hx
have h := hdbA x hx
exact h.2
have hcntA_E : cnt dbA r.end_.key = 0 :=
cnt_eq_zero_of_forall_ge dbA hdbAge
have hcntA_B : cnt dbA r.begin.key = N - 1 := by
rw [cnt_eq_length_of_forall_lt dbA hdbAlt, hlenA]
have hp_notin : ([] : Key) ∉ dbA.keys := by
intro hp_mem
exact absurd hpE (not_lt.mpr (hdbAge ([] : Key) hp_mem))
have hk_notin_insert : k ∉ (dbA.insert ([] : Key) hp_notin).keys := by
rw [DB.mem_insert_iff hp_notin]
rintro (rfl | hk_A)
· exact absurd hpE (not_lt.mpr hkE)
· exact hkA hk_A
let db₀ : DB := (dbA.insert ([] : Key) hp_notin).insert k hk_notin_insert
have hcntE₁ : cnt (dbA.insert ([] : Key) hp_notin) r.end_.key = 1 := by
rw [cnt_insert_lt dbA ([] : Key) hp_notin hpE, hcntA_E, Nat.zero_add]
have hcntB₁ : cnt (dbA.insert ([] : Key) hp_notin) r.begin.key = N := by
rw [cnt_insert_lt dbA ([] : Key) hp_notin (lt_of_lt_of_le hpE (le_of_lt hcross)),
hcntA_B, Nat.sub_add_cancel hNpos]
have hcntE₀ : cnt db₀ r.end_.key = 1 := by
dsimp only [db₀]
rw [cnt_insert_not_lt _ k hk_notin_insert (v := r.end_.key) (not_lt.mpr hkE), hcntE₁]
have hcntB₀ : cnt db₀ r.begin.key = N + 1 := by
dsimp only [db₀]
rw [cnt_insert_lt _ k hk_notin_insert hkB, hcntB₁]
have hcomp₀ : RangeRead.Compatible db₀ r { keys := [], more := false } :=
(compatible_empty_iff_nonpos_end_one_crossed' (db := db₀) hbegin hend
(le_of_lt hcross)).mpr (Or.inl (by rw [hcntB₀, hcntE₀]; omega))
refine ⟨db₀, hcomp₀, ?_⟩
have htoggle : toggle db₀ k = db₀.erase k := by
unfold toggle
rw [dite_eq_left (DB.mem_insert_self _ _ _)]
rw [htoggle]
intro hc
have hmemk : k ∈ db₀.keys := DB.mem_insert_self _ _ _
have hcntE₂ : cnt (db₀.erase k) r.end_.key = 1 := by
rw [cnt_erase_not_lt db₀ hmemk (not_lt.mpr hkE), hcntE₀]
have hcntB₂ : cnt (db₀.erase k) r.begin.key = N := by
rw [cnt_erase_lt db₀ hmemk hkB, hcntB₀]
omega
rw [compatible_empty_iff_nonpos_end_one_crossed' (db := db₀.erase k) hbegin hend
(le_of_lt hcross)] at hc
rcases hc with hc | hc
· rw [hcntB₂, hcntE₂] at hc; omega
· rw [hcntE₂] at hc; omega
/-- **The crossed long-gap empty witness, `k < end.key`.** Here the flip pair is even
simpler: `db₀` stores `1 - begin.offset - 1` keys of `[end.key, begin.key)` and no key
below `end.key`, so its begin count is `1 - begin.offset - 1` and its end count is `0`.
The empty result is compatible on the second disjunct (`cnt end.key = 0`); inserting `k`
below `end.key` lifts `cnt end.key` to `1` and `cnt begin.key` to `1 - begin.offset`,
leaving the first disjunct too short, so the result becomes incompatible. -/
theorem emptyWitness_nonpos_end_one_crossedLong_below (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset = 1)
(hcross : r.end_.key < r.begin.key)
(hgap : (((1 - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r.end_.key r.begin.key)
{k : Key} (hkE : (k : WithTop Key) < r.end_.key) :
EmptyWitness r k := by
set N : ℕ := (1 - r.begin.offset).toNat with hN
have hNpos : 1 ≤ N := by omega
have hcard : (((N - 1 : ℕ)) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key :=
le_trans (by exact_mod_cast Nat.sub_le N 1) hgap
obtain ⟨dbA, hdbA, hlenA⟩ :=
exists_db_keysIn (B := r.end_.key) (E := r.begin.key) (m := N - 1) hcard
have hdbAge : ∀ x ∈ dbA.keys, r.end_.key ≤ (x : WithTop Key) := by
intro x hx
have h := hdbA x hx
exact h.1
have hdbAlt : ∀ x ∈ dbA.keys, (x : WithTop Key) < r.begin.key := by
intro x hx
have h := hdbA x hx
exact h.2
have hcntA_E : cnt dbA r.end_.key = 0 :=
cnt_eq_zero_of_forall_ge dbA hdbAge
have hcntA_B : cnt dbA r.begin.key = N - 1 := by
rw [cnt_eq_length_of_forall_lt dbA hdbAlt, hlenA]
have hk_notin : k ∉ dbA.keys := by
intro hk
exact absurd hkE (not_lt.mpr (hdbAge k hk))
refine ⟨dbA, ?_, ?_⟩
· rw [compatible_empty_iff_nonpos_end_one_crossed' (db := dbA) hbegin hend
(le_of_lt hcross)]
exact Or.inr hcntA_E
· have htoggle : toggle dbA k = dbA.insert k hk_notin := by
unfold toggle
rw [dite_eq_right hk_notin]
rw [htoggle]
intro hc
rw [compatible_empty_iff_nonpos_end_one_crossed' (db := dbA.insert k hk_notin) hbegin
hend (le_of_lt hcross)] at hc
have hcntE₁ : cnt (dbA.insert k hk_notin) r.end_.key = 1 := by
rw [cnt_insert_lt dbA k hk_notin hkE, hcntA_E, Nat.zero_add]
have hcntB₁ : cnt (dbA.insert k hk_notin) r.begin.key = N := by
rw [cnt_insert_lt dbA k hk_notin (lt_of_lt_of_le hkE (le_of_lt hcross)), hcntA_B,
Nat.sub_add_cancel hNpos]
rcases hc with hc | hc
· rw [hcntB₁, hcntE₁] at hc; omega
· rw [hcntE₁] at hc; omega
/-- **The empty witness oracle, nonpositive begin, `end.offset = 1`, crossed long gap.**
With `begin.offset ≤ 0`, `end.offset = 1`, crossed selectors (`end.key < begin.key`) and a
gap long enough to lift the begin anchor (`1 - begin.offset ≤ intervalCard end.key
begin.key`), `emptyValue` is the bottom range `[⊥, begin.key)`. Soundness is
`sound_bottomRange_of_nonpos_end_one_crossed`; every key below `begin.key` has a flip
witness, split on whether it lies at or above `end.key` (the coupled two-key construction)
or below it (the empty-second-disjunct construction). This closes the crossed long gap,
the last `end.offset = 1` corner. -/
theorem emptyWitness_nonpos_end_nonpos_crossFree (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0) (hBE : r.begin.key ≤ r.end_.key)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), r.end_.key⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_right (by omega : ¬ 2 ≤ r.end_.offset),
ite_eq_left hBE]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_bottomRange_of_nonpos_underEnd_le (r := r) hbegin (by omega) hBE rfl rfl
· intro k hk
rw [hv] at hk
-- region split
by_cases hreg : (1 - r.end_.offset).toNat < (1 - r.begin.offset).toNat ∨
intervalCard ((([] : Key)) : WithTop Key) r.begin.key <
(((1 - r.begin.offset).toNat : ℕ) : ℕ∞)
· exact wP (r := r) hbegin hend hBE hAE hreg hk.2
· have hbe : (1 - r.begin.offset).toNat ≤ (1 - r.end_.offset).toNat :=
le_of_not_gt (fun hh => hreg (Or.inl hh))
have hCB : (((1 - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard ((([] : Key)) : WithTop Key) r.begin.key :=
le_of_not_gt (fun hh => hreg (Or.inr hh))
rcases lt_or_ge (k : WithTop Key) r.begin.key with hkB | hkB
· exact wI_below (r := r) hbegin hend hBE hAE hbe hCB hkB
· exact wI_gap (r := r) hbegin hend hBE hAE hbe hCB hkB hk.2
theorem emptyWitness_nonpos_end_one_crossedLong (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset = 1)
(hcross : r.end_.key < r.begin.key)
(hgap : (((1 - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r.end_.key r.begin.key)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hg : ¬ intervalCard r.end_.key r.begin.key <
(((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞) := by
rw [hend]; exact not_lt.mpr hgap
have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), r.begin.key⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_right (by omega : ¬ 2 ≤ r.end_.offset),
ite_eq_right (not_le.mpr hcross), ite_eq_right hg, max_eq_left (le_of_lt hcross)]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_bottomRange_of_nonpos_end_one_crossed hbegin hend (le_of_lt hcross) rfl rfl
· intro k hk
rw [hv] at hk
rcases lt_or_ge (k : WithTop Key) r.end_.key with hkE | hkE
· exact emptyWitness_nonpos_end_one_crossedLong_below r hbegin hend hcross hgap hkE
· exact emptyWitness_nonpos_end_one_crossedLong_interval r hbegin hend hcross hgap hAE
hkE hk.2
/-- **The crossed short-gap room, key at or above `end.key`.** The short-gap criterion is
`cnt end.key ≤ e`, so no `AlwaysEmpty` read can have fewer than `e + 1` keys below
`end.key`: the `[⊥, end.key)` room the short-gap witness spends. -/
theorem not_alwaysEmpty_intervalCard_bot_end {r : RangeRead}
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0) (hne : ¬ AlwaysEmpty r) :
(((1 - r.end_.offset).toNat + 1 : ℕ) : ℕ∞) ≤
intervalCard ((([] : Key)) : WithTop Key) r.end_.key := by
have hnot : ¬ intervalCard ((([] : Key)) : WithTop Key) r.end_.key ≤
(((1 - r.end_.offset).toNat : ℕ) : ℕ∞) := by
intro h
apply hne
intro db
rw [← compatible_empty_iff_complete_nil]
rw [compatible_empty_iff_nonpos_endle (db := db) hbegin (by omega)]
have hcE : cnt db r.end_.key ≤ (1 - r.end_.offset).toNat := by
have hle := cnt_le_intervalCard_nil db r.end_.key
exact Nat.cast_le.mp (le_trans hle h)
have : (cnt db r.end_.key : ℤ) + r.end_.offset - 1 ≤ 0 := by omega
exact le_trans this (le_max_right _ _)
rw [not_le] at hnot
rw [show (((1 - r.end_.offset).toNat + 1 : ℕ) : ℕ∞) =
(((1 - r.end_.offset).toNat : ℕ) : ℕ∞) + 1 by push_cast; ring]
exact ENat.add_one_le_iff (by simp) |>.mpr hnot
/-- **The crossed nonpositive-end short-gap empty witness.** With `begin.offset ≤ 0`,
`end.offset ≤ 0`, crossed selectors and a short gap, `emptyValue` is `[⊥, end.key)`
(unless trivially empty). Soundness is `sound_bottomRange_of_nonpos_crossed_short`;
every key below `end.key` has the singleton flip witness: the empty database is
compatible, and toggling `k` gives the singleton `{k}`, incompatible by
`not_compatible_singleton_self`. -/
theorem emptyWitness_nonpos_crossed_short (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0)
(hcross : r.end_.key < r.begin.key)
(hgap : intervalCard r.end_.key r.begin.key <
(((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞))
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), r.end_.key⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_right (by omega : ¬ 2 ≤ r.end_.offset),
ite_eq_right (not_le.mpr hcross), ite_eq_left hgap]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_bottomRange_of_nonpos_crossed_short hbegin hend (le_of_lt hcross) hgap rfl rfl
· intro k hk
rw [hv] at hk
set e : ℕ := (1 - r.end_.offset).toNat with he
have hroom := not_alwaysEmpty_intervalCard_bot_end (r := r) hbegin hend hAE
obtain ⟨db, hdb, hknot, hlen⟩ :=
exists_db_keysIn_avoid (B := ((([] : Key)) : WithTop Key)) (E := r.end_.key)
(k := k) (m := e) (by rw [← he] at hroom; exact hroom)
have hcE : cnt db r.end_.key = e := by
rw [cnt_eq_length_of_forall_lt db (fun x hx => (hdb x hx).2), hlen]
have htoggle : toggle db k = db.insert k hknot := by
unfold toggle; rw [dite_eq_right hknot]
refine ⟨db, ?_, ?_⟩
· rw [compatible_empty_iff_nonpos_crossed_short (db := db) hbegin hend
(le_of_lt hcross) hgap, hcE]
· rw [htoggle]
have hcE' : cnt (db.insert k hknot) r.end_.key = e + 1 := by
rw [cnt_insert_lt db k hknot hk.2, hcE]
intro hcomp
rw [compatible_empty_iff_nonpos_crossed_short (db := db.insert k hknot) hbegin hend
(le_of_lt hcross) hgap, hcE'] at hcomp
omega
/-- **The crossed nonpositive-end long-gap empty witness, `k < end.key`.** The flip pair
stores `1 - end.offset` keys below `end.key` avoiding `k`; the empty result is compatible
on the short disjunct `cnt end.key ≤ 1 - end.offset`, and inserting `k` lifts the end count
to `1 - end.offset + 1`, killing the short disjunct while the gap (unchanged) stays below
`1 - begin.offset - (1 - end.offset)`, which is positive off the trivially empty region. -/
theorem emptyWitness_nonpos_crossed_long_below (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0)
(hcross : r.end_.key ≤ r.begin.key) (hne : ¬ AlwaysEmpty r)
{k : Key} (hkE : (k : WithTop Key) < r.end_.key) :
EmptyWitness r k := by
set e : ℕ := (1 - r.end_.offset).toNat with he
set b : ℕ := (1 - r.begin.offset).toNat with hb
have hbgt : 1 ≤ b - e := by
have : e < b := by
by_contra hle
exact hne (alwaysEmpty_of_slack_le_slack hbegin hend hcross (le_of_not_gt hle))
omega
have hroom := not_alwaysEmpty_intervalCard_bot_end (r := r) hbegin hend hne
obtain ⟨db, hdb, hknot, hlen⟩ :=
exists_db_keysIn_avoid (B := ((([] : Key)) : WithTop Key)) (E := r.end_.key)
(k := k) (m := e) (by rw [← he] at hroom; exact hroom)
have hlt : ∀ x ∈ db.keys, (x : WithTop Key) < r.end_.key := fun x hx => (hdb x hx).2
have hcE : cnt db r.end_.key = e := by
rw [cnt_eq_length_of_forall_lt db hlt, hlen]
have hcB : cnt db r.begin.key = e := by
rw [cnt_eq_length_of_forall_lt db (fun x hx => lt_of_lt_of_le (hlt x hx) hcross), hlen]
refine ⟨db, ?_, ?_⟩
· rw [compatible_empty_iff_nonpos_crossed_long (db := db) hbegin hend hcross]
exact Or.inl (by rw [hcE, he])
· have htoggle : toggle db k = db.insert k hknot := by
unfold toggle; rw [dite_eq_right hknot]
rw [htoggle]
intro hcomp
rw [compatible_empty_iff_nonpos_crossed_long (db := db.insert k hknot) hbegin hend
hcross] at hcomp
have hcE' : cnt (db.insert k hknot) r.end_.key = e + 1 := by
rw [cnt_insert_lt db k hknot hkE, hcE]
have hcB' : cnt (db.insert k hknot) r.begin.key = e + 1 := by
rw [cnt_insert_lt db k hknot (lt_of_lt_of_le hkE hcross), hcB]
rcases hcomp with h | ⟨-, hg'⟩
· rw [hcE', he] at h; omega
· have hlen2 : (between (db.insert k hknot) r.end_.key r.begin.key).length =
e + 1 - (e + 1) := by
rw [← cnt_sub_eq_between_length hcross, hcB', hcE']
rw [hlen2, ← hb, ← he] at hg'
omega
/-- **The crossed nonpositive-end long-gap empty witness, `end.key ≤ k < begin.key`.**
The flip pair is the coupled construction: `db₀` stores `1 - end.offset + 1` keys below
`end.key` and `1 - begin.offset - (1 - end.offset) - 1` keys of `[end.key, begin.key)`
avoiding `k`, and finally `k`. Its counts are `cnt begin.key = 1 - begin.offset + 1` and
`cnt end.key = 1 - end.offset + 1`, so the empty result is compatible on the long disjunct;
erasing `k` drops the begin count by one, leaving the gap one short of
`1 - begin.offset - (1 - end.offset)`, so both disjuncts fail. -/
theorem emptyWitness_nonpos_crossed_long_interval (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0)
(hcross : r.end_.key < r.begin.key)
(hgap : (((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r.end_.key r.begin.key)
(hne : ¬ AlwaysEmpty r)
{k : Key} (hkE : r.end_.key ≤ (k : WithTop Key)) (hkB : (k : WithTop Key) < r.begin.key) :
EmptyWitness r k := by
set e : ℕ := (1 - r.end_.offset).toNat with he
set b : ℕ := (1 - r.begin.offset).toNat with hb
have hbgt : 1 ≤ b - e := by
have : e < b := by
by_contra hle
exact hne (alwaysEmpty_of_slack_le_slack hbegin hend (le_of_lt hcross) (le_of_not_gt hle))
omega
have hgap' : ((b - e : ℕ) : ℕ∞) ≤ intervalCard r.end_.key r.begin.key := by
have h := offset_sub_toNat r.begin.offset r.end_.offset hbegin hend
rw [← hb, ← he] at h
rw [← h]; exact hgap
have hroom := not_alwaysEmpty_intervalCard_bot_end (r := r) hbegin hend hne
have hroom' : (((e + 1 : ℕ)) : ℕ∞) ≤ intervalCard ((([] : Key)) : WithTop Key) r.end_.key := by
rw [← he] at hroom; exact hroom
obtain ⟨dbLo, hLo, hlenLo⟩ :=
exists_db_keysIn (B := ((([] : Key)) : WithTop Key)) (E := r.end_.key) (m := e + 1) hroom'
obtain ⟨dbHi, hHi, hkHi, hlenHi⟩ :=
exists_db_keysIn_avoid (B := r.end_.key) (E := r.begin.key) (k := k)
(m := b - e - 1) (by
have hbeq : b - e = (b - e - 1) + 1 := by omega
rw [hbeq] at hgap'
rwa [Nat.cast_add, Nat.cast_one] at hgap')
have hkLo : k ∉ dbLo.keys := fun hk => absurd hkE (not_le.mpr (hLo k hk).2)
have hcross' : ∀ x ∈ dbLo.keys, ∀ y ∈ dbHi.keys, x < y := fun x hx y hy =>
WithTop.coe_lt_coe.mp (lt_of_lt_of_le (hLo x hx).2 (hHi y hy).1)
let dbPre : DB := ⟨dbLo.keys ++ dbHi.keys,
List.sortedLT_append.mpr ⟨dbLo.sorted, dbHi.sorted, hcross'⟩⟩
have hkeys : dbPre.keys = dbLo.keys ++ dbHi.keys := rfl
have hkPre : k ∉ dbPre.keys := by
rw [hkeys, List.mem_append]; rintro (h | h)
exacts [hkLo h, hkHi h]
let db₀ : DB := dbPre.insert k hkPre
have hcntPre_E : cnt dbPre r.end_.key = e + 1 := by
have hsplit : cnt dbPre r.end_.key = cnt dbLo r.end_.key + cnt dbHi r.end_.key := by
unfold cnt; rw [hkeys, List.countP_append]
rw [hsplit, cnt_eq_length_of_forall_lt dbLo (fun x hx => (hLo x hx).2),
cnt_eq_zero_of_forall_ge dbHi (fun x hx => (hHi x hx).1), Nat.add_zero, hlenLo]
have hcntPre_B : cnt dbPre r.begin.key = e + 1 + (b - e - 1) := by
have hsplit : cnt dbPre r.begin.key = cnt dbLo r.begin.key + cnt dbHi r.begin.key := by
unfold cnt; rw [hkeys, List.countP_append]
rw [hsplit,
cnt_eq_length_of_forall_lt dbLo (fun x hx => lt_of_lt_of_le (hLo x hx).2 (le_of_lt hcross)),
cnt_eq_length_of_forall_lt dbHi (fun x hx => (hHi x hx).2), hlenLo, hlenHi]
have hcntE : cnt db₀ r.end_.key = e + 1 := by
dsimp only [db₀]
rw [cnt_insert_not_lt dbPre k hkPre (not_lt.mpr hkE), hcntPre_E]
have hcntB : cnt db₀ r.begin.key = b + 1 := by
dsimp only [db₀]
rw [cnt_insert_lt dbPre k hkPre hkB, hcntPre_B]; omega
have hcomp₀ : RangeRead.Compatible db₀ r { keys := [], more := false } := by
rw [compatible_empty_iff_nonpos_crossed_long (db := db₀) hbegin hend (le_of_lt hcross)]
refine Or.inr ⟨by rw [hcntB, hb]; exact Nat.le_succ b, ?_⟩
have hlen : (between db₀ r.end_.key r.begin.key).length =
cnt db₀ r.begin.key - cnt db₀ r.end_.key := by
have := cnt_eq_add_between db₀ (le_of_lt hcross); omega
rw [hlen, hcntB, hcntE, hb, he]; omega
refine ⟨db₀, hcomp₀, ?_⟩
have htoggle : toggle db₀ k = db₀.erase k := by
unfold toggle; rw [dite_eq_left (DB.mem_insert_self dbPre k hkPre)]
rw [htoggle]
intro hc
have hmemk : k ∈ db₀.keys := DB.mem_insert_self dbPre k hkPre
have hE2 : cnt (db₀.erase k) r.end_.key = e + 1 := by
rw [cnt_erase_not_lt db₀ hmemk (not_lt.mpr hkE), hcntE]
have hB2 : cnt (db₀.erase k) r.begin.key = b := by
rw [cnt_erase_lt db₀ hmemk hkB, hcntB]; omega
rw [compatible_empty_iff_nonpos_crossed_long (db := db₀.erase k) hbegin hend
(le_of_lt hcross)] at hc
rcases hc with hce | ⟨-, hgap2⟩
· rw [hE2] at hce; omega
· have hlen2 : (between (db₀.erase k) r.end_.key r.begin.key).length =
b - (e + 1) := by
rw [← cnt_sub_eq_between_length (le_of_lt hcross), hB2, hE2]
rw [hlen2, hb, he] at hgap2
omega
/-- **The crossed nonpositive-end long-gap empty witness.** With `begin.offset ≤ 0`,
`end.offset ≤ 0`, crossed selectors (`end.key < begin.key`) and a long gap, `emptyValue`
is the bottom range `[⊥, begin.key)` (unless trivially empty). Soundness is
`sound_bottomRange_of_nonpos_end_one_crossed`; every key below `begin.key` has a flip
witness, split on whether it lies below `end.key` (`emptyWitness_nonpos_crossed_long_below`)
or in `[end.key, begin.key)` (`emptyWitness_nonpos_crossed_long_interval`). This is the
exact residual case `EmptyInferenceWitnessResidual`. -/
theorem emptyWitness_nonpos_crossed_long (r : RangeRead)
(hbegin : r.begin.offset ≤ 0) (hend : r.end_.offset ≤ 0)
(hcross : r.end_.key < r.begin.key)
(hgap : (((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r.end_.key r.begin.key)
(_hread : Readable r { keys := [], more := false }) :
Sound r { keys := [], more := false } (emptyValue r) ∧
∀ k : Key, k ∈ emptyValue r → EmptyWitness r k := by
by_cases hAE : AlwaysEmpty r
· have hv : emptyValue r = emptyRange r := by simp [emptyValue, hAE]
refine ⟨?_, ?_⟩
· rw [hv]; exact sound_emptyRange_of_alwaysEmpty hAE
· intro k hk
rw [hv] at hk
exact absurd hk (ConflictRange.not_mem_of_isEmpty (by
simp [ConflictRange.IsEmpty, emptyRange]) k)
· have hg : ¬ intervalCard r.end_.key r.begin.key <
(((r.end_.offset - r.begin.offset).toNat : ℕ) : ℕ∞) := not_lt.mpr hgap
have hv : emptyValue r = ⟨(([] : Key) : WithTop Key), r.begin.key⟩ := by
unfold emptyValue
rw [ite_eq_right hAE, ite_eq_left hbegin, ite_eq_right (by omega : ¬ 2 ≤ r.end_.offset),
ite_eq_right (not_le.mpr hcross), ite_eq_right hg, max_eq_left (le_of_lt hcross)]
refine ⟨?_, ?_⟩
· rw [hv]
exact sound_bottomRange_of_nonpos_crossed_long hbegin hend (le_of_lt hcross) rfl rfl
· intro k hk
rw [hv] at hk
rcases lt_or_ge (k : WithTop Key) r.end_.key with hkE | hkE
· exact emptyWitness_nonpos_crossed_long_below r hbegin hend (le_of_lt hcross) hAE hkE
· exact emptyWitness_nonpos_crossed_long_interval r hbegin hend hcross hgap hAE hkE hk.2
/-- **`EmptyInferenceWitnessOffOne` from the nonpositive-begin residual.** The
off-one region splits into the nonpositive begin offsets: the overshooting end
(`end.offset ≥ 2`, `emptyWitness_nonpos_overshoot`); then with `end.offset ≤ 1` the
cross-free `end.offset = 1` case (`emptyWitness_nonpos_end_one_crossFree`), the crossed
`end.offset = 1` short gap (`emptyWitness_nonpos_end_one_crossedShort`), the crossed
`end.offset = 1` long gap (`emptyWitness_nonpos_end_one_crossedLong`), the cross-free
`end.offset ≤ 0` case (`emptyWitness_nonpos_end_nonpos_crossFree`), or the crossed
`end.offset ≤ 0` residual; and the `1 ≤ begin.offset` region splits into `end.offset ≤ 1`
(`emptyWitness_underEnd_gen`) and `end.offset ≥ 2` (`emptyWitness_overshoot`). -/
theorem emptyInferenceWitnessOffOne_of_residual (h : EmptyInferenceWitnessResidual) :
EmptyInferenceWitnessOffOne := by
intro r' hb hr
rcases le_or_gt r'.begin.offset 0 with hb0 | hbpos
· rcases lt_or_ge r'.end_.offset 2 with he | he
· -- `end.offset ≤ 1`
by_cases h1 : r'.end_.offset = 1
· rcases lt_or_ge r'.end_.key r'.begin.key with hcross | hle
· by_cases hg : intervalCard r'.end_.key r'.begin.key <
(((1 - r'.begin.offset).toNat : ℕ) : ℕ∞)
· exact emptyWitness_nonpos_end_one_crossedShort r' hb0 h1 hcross hg hr
· exact emptyWitness_nonpos_end_one_crossedLong r' hb0 h1 hcross (not_lt.mp hg) hr
· exact emptyWitness_nonpos_end_one_crossFree r' hb0 h1 hle hr
· -- `end.offset ≤ 0`
rcases lt_or_ge r'.end_.key r'.begin.key with hcross | hle
· by_cases hg : (((r'.end_.offset - r'.begin.offset).toNat : ℕ) : ℕ∞) ≤
intervalCard r'.end_.key r'.begin.key
· exact h r' hb0 (by omega) hcross hg hr
· exact emptyWitness_nonpos_crossed_short r' hb0 (by omega) hcross (not_le.mp hg) hr
· exact emptyWitness_nonpos_end_nonpos_crossFree r' hb0 (by omega) hle hr
· exact emptyWitness_nonpos_overshoot r' hb0 he hr
· have hb1 : 1 ≤ r'.begin.offset := by omega
rcases lt_or_ge r'.end_.offset 2 with he | he
· exact emptyWitness_underEnd_gen r' hb1 (by omega) hr
· exact emptyWitness_overshoot r' hb1 he hr
/-- **`EmptyInferenceWitness` from the residual.** The whole empty theory reduces to
`EmptyInferenceWitnessResidual`: the crossed nonpositive-begin, nonpositive-end long gap. -/
theorem emptyInferenceWitness_of_residual (h : EmptyInferenceWitnessResidual) :
EmptyInferenceWitness :=
emptyInferenceWitness_of_offOne (emptyInferenceWitnessOffOne_of_residual h)
/-- **The witness oracle, unconditionally.** The last residual
`EmptyInferenceWitnessResidual` is discharged by the nonpositive-end crossed case analysis:
short gaps by `emptyWitness_nonpos_crossed_short`, long gaps by
`emptyWitness_nonpos_crossed_long`. -/
theorem emptyInferenceWitness : EmptyInferenceWitness :=
emptyInferenceWitness_of_residual fun r' hb he hcross hgap hr =>
emptyWitness_nonpos_crossed_long r' hb he hcross hgap hr
/-- **The abstract empty inference, unconditionally.** -/
theorem emptyInference : EmptyInference :=
emptyInference_of_witness emptyInferenceWitness
/-- **The partial algorithm is minimal wherever it is defined.** `conflictRangePartial`
returns `some` only on certified cases, each discharged by a named theorem: an empty
result by the (unconditional) empty inference `emptyInference`; the offset-one
complete/truncated cases by the offset-one certificates; an overshooting end by the
unbounded-top theorems for a complete result and the truncated/top-of-last theorems
otherwise; and every nonempty complete result at `begin.offset ≥ 1` by
`minimal_canonicalRange_of_end_offset_le_one_general` for `underEnd` and the
`minimal_topRange_of_end_offset_ge_two_general` pair for an overshoot, with the truncated
*non-reversed* result by `minimal_truncatedRange_of_end_offset_ge_two_general` at an
overshoot and `minimal_truncatedRange_of_end_offset_one` at `end.offset = 1`. The
`none` branches are unreachable from a `some` value, so only their guards matter. This
statement lives after `emptyInference` because its empty branch consumes that theorem;
nothing in the definition depends on the ordering. -/
theorem conflictRangePartial_spec {r : RangeRead} {res : Result} {cr : ConflictRange}
(hread : Readable r res) (h : conflictRangePartial r res = some cr) :
Minimal r res cr := by
unfold conflictRangePartial at h
by_cases hkeys : res.keys = []
· rw [dite_eq_left hkeys, Option.some.injEq] at h
subst h
exact minimal_emptyValue_of_emptyInference emptyInference hread hkeys
· rw [dite_eq_right hkeys] at h
by_cases hb : beginOne r
· rw [dite_eq_left hb] at h
by_cases he : endOne r
· rw [dite_eq_left he, Option.some.injEq] at h
subst h
by_cases hmore : res.more = true
· by_cases hrev : r.reverse = true
· exact conflictRangeOffsetOne_spec_truncated_rev hread hmore hrev hb he
· exact conflictRangeOffsetOne_spec_truncated hread hmore (by simpa using hrev) hb he
· exact conflictRangeOffsetOne_spec hread (by simpa using hmore) hb he
· rw [dite_eq_right he] at h
by_cases hover : overshoot r res
· rw [dite_eq_left hover] at h
obtain ⟨hend2, hne, hhi⟩ := hover
by_cases hmore : res.more = false
· rw [dite_eq_left hmore, Option.some.injEq] at h
subst h
cases hrev : r.reverse with
| false =>
exact minimal_topRange_of_end_offset_ge_two hread hmore hrev hne hb hend2 hhi
| true =>
exact minimal_topRange_of_end_offset_ge_two_rev hread hmore hrev hne hb hend2 hhi
· rw [dite_eq_right hmore] at h
by_cases hrev : r.reverse = false
· rw [dite_eq_left hrev, Option.some.injEq] at h
subst h
exact minimal_truncatedRange_of_end_offset_ge_two hread (by simpa using hmore)
hrev hb hend2 hhi
· rw [dite_eq_right hrev, Option.some.injEq] at h
subst h
exact minimal_topOfLast_of_end_offset_ge_two_rev hread (by simpa using hmore)
(by simpa using hrev) hb hend2 hhi
· rw [dite_eq_right hover] at h
by_cases hunder : underEnd r
· rw [dite_eq_left hunder] at h
by_cases hm : res.more = false
· rw [dite_eq_left hm, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_end_offset_le_one_general hread hm hkeys hb.ge hunder
· rw [dite_eq_right hm] at h
by_cases hrev : r.reverse = false
· rw [dite_eq_left hrev, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_truncated_end_offset_nonpos hread
(by simpa using hm) hrev hb.ge (by
have hne1 : r.end_.offset ≠ 1 := fun hcon => he hcon
omega)
· rw [dite_eq_right hrev, Option.some.injEq] at h
subst h
exact minimal_truncatedRangeRev_of_end_offset_nonpos hread (by simpa using hm)
(by simpa using hrev) hb (by
have hne1 : r.end_.offset ≠ 1 := fun hcon => he hcon
omega)
· rw [dite_eq_right hunder] at h
exact absurd h (by simp)
· rw [dite_eq_right hb] at h
by_cases hge : 1 ≤ r.begin.offset
· rw [dite_eq_left hge] at h
by_cases he0 : r.end_.offset ≤ 0
· rw [dite_eq_left he0] at h
by_cases hm : res.more = false
· rw [dite_eq_left hm, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_end_offset_le_one_general hread hm hkeys hge
(by omega)
· rw [dite_eq_right hm] at h
by_cases hrev : r.reverse = false
· rw [dite_eq_left hrev, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_truncated_end_offset_nonpos hread
(by simpa using hm) hrev hge he0
· rw [dite_eq_right hrev, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_end_offset_le_one_rev_more hread (by simpa using hm)
(by simpa using hrev) hkeys
(by have hne1 : r.begin.offset ≠ 1 :=
fun hcon => hb (by simpa [beginOne] using hcon)
omega)
(by omega)
· rw [dite_eq_right he0] at h
by_cases hunder : underEnd r
· rw [dite_eq_left hunder] at h
by_cases hm : res.more = false
· rw [dite_eq_left hm, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_end_offset_le_one_general hread hm hkeys hge hunder
· rw [dite_eq_right hm] at h
by_cases hrev : r.reverse = false
· rw [dite_eq_left hrev, Option.some.injEq] at h
subst h
exact minimal_truncatedRange_of_end_offset_one hread (by simpa using hm) hrev hge
(by omega)
· rw [dite_eq_right hrev, Option.some.injEq] at h
subst h
exact minimal_canonicalRange_of_end_offset_le_one_rev_more hread (by simpa using hm)
(by simpa using hrev) hkeys
(by have hne1 : r.begin.offset ≠ 1 :=
fun hcon => hb (by simpa [beginOne] using hcon)
omega)
hunder
· rw [dite_eq_right hunder] at h
by_cases hover : overshoot r res
· rw [dite_eq_left hover] at h
obtain ⟨hend2, hne, hhi⟩ := hover
by_cases hm : res.more = false
· rw [dite_eq_left hm, Option.some.injEq] at h
subst h
cases hrev : r.reverse with
| false =>
exact minimal_topRange_of_end_offset_ge_two_general hread hm hrev hne
hge hend2 hhi
| true =>
exact minimal_topRange_of_end_offset_ge_two_rev_general hread hm hrev hne
hge hend2 hhi
· rw [dite_eq_right hm] at h
by_cases hrev : r.reverse = false
· rw [dite_eq_left hrev, Option.some.injEq] at h
subst h
exact minimal_truncatedRange_of_end_offset_ge_two_general hread
(by simpa using hm) hrev hge hend2 hhi
· rw [dite_eq_right hrev, Option.some.injEq] at h
subst h
exact minimal_topRange_of_end_offset_ge_two_rev_more hread (by simpa using hm)
(by simpa using hrev)
(by have hne1 : r.begin.offset ≠ 1 :=
fun hcon => hb (by simpa [beginOne] using hcon)
omega)
hend2 hhi
· rw [dite_eq_right hover] at h
exact absurd h (by simp)
· rw [dite_eq_right hge] at h
by_cases hnp : nonposOvershootComplete r res
· rw [dite_eq_left hnp, Option.some.injEq] at h
subst h
obtain ⟨hend2, hm, hne, hhi, hloD⟩ := hnp
cases hrev : r.reverse with
| false =>
exact minimal_fullRange_of_nonpos_overshoot_nonempty hread hrev hm hne
(by omega) hend2 hhi (by
have hloD' : r.begin.key ≤ ((res.keys.headD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrev] using hloD
have hhead : res.keys.headD ([] : Key) = res.keys.head hne := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
rwa [← hhead])
| true =>
exact minimal_fullRange_of_nonpos_overshoot_nonempty_rev hread hrev hm hne
(by omega) hend2 hhi (by
have hloD' : r.begin.key ≤
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrev] using hloD
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rwa [← hlast])
· rw [dite_eq_right hnp] at h
by_cases hnu : nonposUnderEndComplete r res
· rw [dite_eq_left hnu, Option.some.injEq] at h
subst h
obtain ⟨hend1, hm, hne, hloD⟩ := hnu
cases hrev : r.reverse with
| false =>
exact minimal_bottomRange_of_nonpos_underEnd_nonempty hread hrev hm hne
(by omega) hend1 (by
have hloD' : r.begin.key ≤ ((res.keys.headD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrev] using hloD
have hhead : res.keys.headD ([] : Key) = res.keys.head hne := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne]; rfl
rwa [← hhead])
| true =>
exact minimal_bottomRange_of_nonpos_underEnd_nonempty_rev hread hrev hm hne
(by omega) hend1 (by
have hloD' : r.begin.key ≤
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrev] using hloD
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hne := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hne]; rfl
rwa [← hlast])
· rw [dite_eq_right hnu] at h
by_cases hft : nonposFwdTruncPinned r res
· rw [dite_eq_left hft, Option.some.injEq] at h
subst h
obtain ⟨hm, hrev, hloD, hend, hhi⟩ := hft
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hkeys := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hkeys]; rfl
rw [hlast]
exact minimal_truncatedRangeBottom_of_nonpos hread hrev hm hkeys (by omega) (by
have hloD' : r.begin.key ≤ ((res.keys.headD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrev] using hloD
have hhead : res.keys.headD ([] : Key) = res.keys.head hkeys := by
rw [List.headD_eq_head?, List.head?_eq_some_head hkeys]; rfl
rwa [← hhead]) hend hhi
· rw [dite_eq_right hft] at h
by_cases hrt : nonposRevTruncOvershoot r res
· rw [dite_eq_left hrt, Option.some.injEq] at h
subst h
obtain ⟨hm, hrevr, hloD, hend2, hhi⟩ := hrt
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hkeys := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hkeys]; rfl
rw [hlast]
exact minimal_topOfLast_of_end_offset_ge_two_rev_nonpos hread hm hrevr hkeys
(by omega) hend2 (by
have hloD' : r.begin.key ≤
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrevr] using hloD
rwa [← hlast]) hhi
· rw [dite_eq_right hrt] at h
by_cases hrt1 : nonposRevTruncEndOne r res
· rw [dite_eq_left hrt1, Option.some.injEq] at h
subst h
obtain ⟨hm, hrevr, hloD, hend1⟩ := hrt1
have hlast : res.keys.getLastD ([] : Key) = res.keys.getLast hkeys := by
rw [List.getLastD_eq_getLast?, List.getLast?_eq_some_getLast hkeys]; rfl
rw [hlast]
exact minimal_truncatedRangeRev_of_end_offset_one_nonpos hread hm hrevr hkeys
(by omega) hend1 (by
have hloD' : r.begin.key ≤
((res.keys.getLastD ([] : Key) : Key) : WithTop Key) := by
simpa [leastReported, hrevr] using hloD
rwa [← hlast])
· rw [dite_eq_right hrt1] at h
by_cases hzc : zeroCrossOvershootComplete r res
· rw [dite_eq_left hzc, Option.some.injEq] at h
subst h
obtain ⟨hbeg0, hm, hrevf, hov, hcrossL⟩ := hzc
obtain ⟨hend2, hne, hhi⟩ := hov
have hcrossD : ((res.keys.headD ([] : Key) : Key) : WithTop Key) <
r.begin.key := by
simpa [leastReported, hrevf] using hcrossL
have hhead : res.keys.headD ([] : Key) = res.keys.head hkeys := by
rw [List.headD_eq_head?, List.head?_eq_some_head hkeys]; rfl
rw [hhead] at hcrossD
rw [hhead]
exact minimal_topOfHead_of_zero_begin_crossed_overshoot hread hrevf hm
hkeys hbeg0 hcrossD hend2 hhi
· rw [dite_eq_right hzc] at h
by_cases hze : zeroCrossEndOne r res
· rw [dite_eq_left hze, Option.some.injEq] at h
subst h
obtain ⟨hbeg0, hm, hrevf, hend1, hne', hcrossL, hkeyle⟩ := hze
have hcrossD : ((res.keys.headD ([] : Key) : Key) : WithTop Key) <
r.begin.key := by
simpa [leastReported, hrevf] using hcrossL
have hhead : res.keys.headD ([] : Key) = res.keys.head hne' := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne']; rfl
rw [hhead] at hcrossD
rw [hhead]
exact minimal_headToEnd_of_zero_begin_crossed_endOne hread hrevf hm hne'
hbeg0 hcrossD hend1 hkeyle
· rw [dite_eq_right hze] at h
by_cases hzel : zeroCrossEndOneLong r res
· rw [dite_eq_left hzel, Option.some.injEq] at h
subst h
obtain ⟨hbeg0, hm, hrevf, hend1, hne', hcrossL, hlongD⟩ := hzel
have hcrossD : ((res.keys.headD ([] : Key) : Key) : WithTop Key) <
r.begin.key := by
simpa [leastReported, hrevf] using hcrossL
have hhead : res.keys.headD ([] : Key) = res.keys.head hne' := by
rw [List.headD_eq_head?, List.head?_eq_some_head hne']; rfl
rw [hhead] at hcrossD
rw [hhead]
exact minimal_headToBeginKey_of_zero_begin_crossed_endOne_long hread
hrevf hm hne' hbeg0 hcrossD hend1 hlongD
· rw [dite_eq_right hzel] at h
exact absurd h (by simp)
/-!
## The desired outcome: a total minimal algorithm
The stated objective is a *total* conflict-range algorithm returning a *minimal* sound
range on every realizable read/result pair. This section makes the objective precise and
locates it relative to the existence headline. As a *function*, the objective is not
stronger than the headline: given the headline, `Classical.choice` turns the pointwise
existentials into a total `ConflictRange`-valued function, and `conflictRangeTotal` below
refines the certified algorithm `conflictRangePartial` — it agrees with it on every
certified `some` value, and on the uncertified `none` branches returns the chosen minimal
range. What would be strictly stronger is a *computable* total algorithm, i.e. branch
completeness of `conflictRangePartial`, which is blocked on exactly the regions where no
offset-formula candidate exists (the bare successor versus the unbounded top).
-/
/-- The desired outcome, as a proposition: a total `ConflictRange`-valued algorithm that
returns a minimal sound range on every realizable read/result pair. Non-realizable inputs
carry no requirement; being total, the algorithm still returns a range there. -/
def TotalMinimalAlgorithm : Prop :=
∃ algo : RangeRead → Result → ConflictRange,
∀ r res, Readable r res → Minimal r res (algo r res)
/-- **The desired outcome is exactly the existence headline.** A total minimal algorithm
exists iff every realizable pair admits a minimal sound range. The forward direction is
immediate; the reverse is `Classical.choice`, which needs no extra structure because the
minimal key set is unique (`Minimal.toSet_eq`). So "minimal and total" is not a stronger
obligation than existence at the level of functions. -/
theorem totalMinimalAlgorithm_iff :
TotalMinimalAlgorithm ↔
∀ r res, Readable r res → ∃ cr : ConflictRange, Minimal r res cr := by
constructor
· rintro ⟨algo, h⟩ r res hread
exact ⟨algo r res, h r res hread⟩
· intro h
classical
refine ⟨fun r res =>
if hh : ∃ cr : ConflictRange, Minimal r res cr then Classical.choose hh
else canonicalRange r, ?_⟩
intro r res hread
have hh : ∃ cr : ConflictRange, Minimal r res cr := h r res hread
dsimp only
rw [dite_eq_left hh]
exact Classical.choose_spec hh
/-- **A totalization of the certified algorithm.** Given the headline, `conflictRangePartial`
extends to a total algorithm that is minimal on every realizable pair: it keeps the certified
value where `conflictRangePartial` returns `some`, and on the uncertified `none` branches
returns the (classically chosen) minimal range. Making it *computable* — filling the `none`
branches with explicit candidates — is the remaining branch-completeness work. -/
noncomputable def conflictRangeTotal
(_h : ∀ r res, Readable r res → ∃ cr : ConflictRange, Minimal r res cr) :
RangeRead → Result → ConflictRange := by
classical
exact fun r res =>
match conflictRangePartial r res with
| some cr => cr
| none =>
if hh : ∃ cr : ConflictRange, Minimal r res cr then Classical.choose hh
else canonicalRange r
/-- `conflictRangeTotal` is minimal wherever the pair is realizable. -/
theorem conflictRangeTotal_spec
(h : ∀ r res, Readable r res → ∃ cr : ConflictRange, Minimal r res cr)
{r : RangeRead} {res : Result} (hread : Readable r res) :
Minimal r res (conflictRangeTotal h r res) := by
classical
unfold conflictRangeTotal
cases hpart : conflictRangePartial r res with
| some cr => exact conflictRangePartial_spec hread hpart
| none =>
have hh : ∃ cr : ConflictRange, Minimal r res cr := h r res hread
dsimp only
rw [dite_eq_left hh]
exact Classical.choose_spec hh
/-- `conflictRangeTotal` agrees with the certified algorithm on every certified `some`
value. -/
theorem conflictRangeTotal_eq_partial
(h : ∀ r res, Readable r res → ∃ cr : ConflictRange, Minimal r res cr)
{r : RangeRead} {res : Result} {cr : ConflictRange}
(hpart : conflictRangePartial r res = some cr) :
conflictRangeTotal h r res = cr := by
unfold conflictRangeTotal
rw [hpart]
/-- **A complete empty theory from the witness oracle.** The `witness` field is
supplied by `emptyInferenceWitness`; the other three fields remain the graft and
gap-split obligations. The graft fields are guarded by `Readable`. -/
theorem emptyTheoryComplete_of_witness
(hjoint : ∀ (r : RangeRead) (res : Result), Readable r res → BoundaryJointBases r res)
(hbracket : ∀ (r : RangeRead) (res : Result), BracketFactor r res)
(htrunc : ∀ (r : RangeRead) (res : Result), Readable r res → GeneralObligation r res) :
EmptyTheoryComplete :=
⟨emptyInferenceWitness, hjoint, hbracket, htrunc⟩
/-- **A complete empty theory from the (now vacuous) residual.** Kept for compatibility:
`EmptyInferenceWitnessResidual` is inhabited by the empty theory, so the residual may be
supplied trivially. -/
theorem emptyTheoryComplete_of_residual (h : EmptyInferenceWitnessResidual)
(hjoint : ∀ (r : RangeRead) (res : Result), Readable r res → BoundaryJointBases r res)
(hbracket : ∀ (r : RangeRead) (res : Result), BracketFactor r res)
(htrunc : ∀ (r : RangeRead) (res : Result), Readable r res → GeneralObligation r res) :
EmptyTheoryComplete :=
⟨emptyInferenceWitness_of_residual h, hjoint, hbracket, htrunc⟩
end FormalConflictRange