Replies: 1 comment 1 reply
|
Thank you for your interest. Your comments are also very helpful. However, since the excluded middle (or, more precisely, Classical.choice) is used extensively even in the foundational parts of mathlib, it would likely not be very practical to use an intuitionistic metatheory in Lean. Nevertheless, I believe that a definition from a constructivist perspective would help make the discussion more concise. |
1 reply
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Dear developers,
First, thank you for building such a wonderful project for formal logic. I am planning to build a downstream repository on constructive mathematics based on your project. I have been working on it recently, but I have not pushed it to GitHub yet, since it is not mature enough. However, I would like to report an issue related to constructivity in the upstream repository.
If we remove the module and public keywords in FirstOrder/Kripke/Intuitionistic, we find that many theorems depend on Classical.choice. This is due to proof of LO.FirstOrder.KripkeModel.Forces.free , which simplifies the goal using Matrix.rightConcat_last and Matrix.rightConcat_castSucc. The latter, in turn, simplifies the goal using Fin.lastCases_castSucc which itself relies on Fin.reverseInduction_castSucc. If we then inspect its source code, we find that it depends on a lemma called reverseInduction_castSucc_aux, which appears to be inherently classical.
A minimal solution solution would be to add an intuitionistic version of lastCases_castSucc at the beginning of Vorspiel.Matrix. For example:
`namespace Fin
theorem reverseInduction_castSucc_aux {n : Nat} {motive : Fin (n + 1) → Sort _} {succ}
(i : Fin n) (j : Nat) (h) (h2 : i.1 < j) (zero : motive ⟨j, h⟩) :
reverseInduction.go (motive := motive) succ i.castSucc j h (Nat.le_of_lt h2) zero =
succ i (reverseInduction.go succ i.succ j h h2 zero) := by
induction j generalizing i with
| zero => grind
| succ j ih =>
rw [reverseInduction.go, dif_neg (by exact Nat.ne_of_lt h2)]
have : Decidable (i = j) := inferInstance
cases this with
| isTrue hij => subst hij; simp [reverseInduction.go]; rfl
| isFalse hij => dsimp only
rw [ih _ _ (by omega), eq_comm, reverseInduction.go, dif_neg (by change i.1 + 1 ≠ _; omega)]
@[simp, grind =] theorem reverseInduction_castSucc_i {n : Nat} {motive : Fin (n + 1) → Sort _} {zero succ}
(i : Fin n) : reverseInduction (motive := motive) zero succ (castSucc i) =
succ i (reverseInduction zero succ i.succ) := by
rw [reverseInduction, reverseInduction_castSucc_aux _ _ _ i.isLt, reverseInduction]
@[simp, grind =] theorem lastCases_castSucc_i {n : Nat} {motive : Fin (n + 1) → Sort _} {last cast}
(i : Fin n) : (Fin.lastCases last cast (Fin.castSucc i) : motive (Fin.castSucc i)) = cast i :=
reverseInduction_castSucc_i ..
end Fin`
Then rightConcat_castSucc could be proved using simp only [vecConsLast, Fin.lastCases_castSucc_i], making it constructive. Although this solution is not especially elegant, it would require no changes to Lean’s source code. Also, grind might not work in that environment; otherwise, there would be no reason for the author to use omega to prove the zero alternative. However, replacing the classical by_cases with DecidableEq should certainly work for the succ alternative.
Finally, I understand that constructivity may not be the primary concern of the upstream repository. Therefore, modifying this is not urgent. However, I believe it is still worth reporting. Anyway, thank you again for building such a wonderful project.
If you have any further thoughts, or if I have misunderstood anything here, please let me know.
Thanks.
All reactions