input-output-hk / input-output-hk/Lean-blaster
[soundness] Empty quantifier domains produce false Valid results
- Dominant language
- Lean
- Stars
- 57
- Forks
- 11
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 10
Description
On `beta-lambda-cache-optimization` at `bafdd4f7976037cd7bd8e443df04af096dc5b96e`, unused-quantifier elimination and SMT class-binder erasure assume nonemptiness without evidence. Blaster reports `Valid` for the following false proposition:
```lean
import Blaster
theorem counterexample : ¬ (∀ α : Type, (∀ _ : α, False) → False) := by
intro h
exact h Empty Empty.elim
-- Expected: Falsified. Actual on beta: Unexpected result (Valid).
#blaster (gen-cex: 0) (solve-result: 1) (timeout: 5)
[∀ α : Type, (∀ _ : α, False) → False]
```
The problem also affects function spaces (`α → β`) and classes (`Inhabited α`). For example, Blaster incorrectly validates `∀ α : Type, ∃ _ : Inhabited α, True`, refuted by `α := Empty`.
Only erase an unused quantifier when its domain is known to be nonempty, and retain SMT membership guards for potentially empty class domains. A local instance from an already-closed binder must not provide evidence of nonemptiness.
The already-open fix #224 will carry the numbered regression file for this issue, including kernel-checked counterexamples, optimizer tests and negative Blaster tests.
Contributor guide
No contributing guide indexed for this repository
Research direction
Review the already-open fix in #224 and reproduce the Lean counterexample from this issue. Check the numbered regression file there, including the kernel-checked counterexamples, optimizer tests, and negative Blaster tests; done means empty quantifier domains no longer produce false Valid results and membership guards are retained where needed.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100