input-output-hk / input-output-hk/Lean-blaster

[soundness] Empty quantifier domains produce false Valid results

Open
#226 0 comments 0 reactions 0 assignees View on GitHub
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.