Lean Kernel Arena / bugs/rec-rule-proof-irrel

Test "bugs/rec-rule-proof-irrel"

Expected: ✋ reject · Size: 25.3 KB · Lines: 466 · lean4export: 3.1.0 · Lean: 4.36.0 · 📄 Declaration · 🔗 Source

Proof of False via an ill-typed recursor rule that is compared with the derived one up to definitional equality.

J : Prop has two constructors, so it eliminates only into Prop, and the right-hand sides of the rules of J.rec are proofs. The export replaces the rule for J.j1 by an ill-typed one:

fun motive h₁ h₂ => @id (motive J.j1) (Box.mk true)   -- instead of fun motive h₁ h₂ => h₁

Here Box : Bool → Prop has the single constructor Box.mk (b : Bool) : Box b, so it eliminates into Type, and read : Box b → Bool recovers b. With the forged rule, J.rec (motive := fun _ => Box false) … J.j1 : Box false reduces to Box.mk true, and read of it is true, while read_eq says it is false.

A checker that compares the exported rule with the one it derives up to definitional equality, before type checking it, is fooled by proof irrelevance: both sides are proofs, so only their types are compared, and inferring the type of the forged rule without checking the argument of id gives motive J.j1. A checker must compare the rules structurally, or type check the exported rule before comparing it.

Checker Result ⏱️ 🧠
nano-lean ✋ 0.703 ms 24.0 MB
gruszka ✋ 1.99 ms 49.8 MB
sokonanoda ✋ 1.09 ms 29.7 MB
rpylean ✋ 1.11 ms 10.8 MB
pestka ✋ 2.38 ms 13.8 MB
kefir ✋ 1.32 ms 6.3 MB
palladium ✋ 0.901 ms 18.7 MB
con-ron ✋ 30.1 ms 39.1 MB
kefir-wasm ✋ 175 ms 96.4 MB
con-agua ✋ 20.7 ms 15.1 MB
nanobruijn ✋ 1.88 ms 13.8 MB
nanoda ✋ 1.20 ms 3.2 MB
con-leche ✋ 4.75 ms 23.6 MB
pestka-wasm ✋ 94.8 ms 106.3 MB
tenet-jvm ✋ 139 ms 66.1 MB
official-nightly ✋ 35.4 ms 109.1 MB
eink0rn ✋ 2.21 ms 13.0 MB
official ✋ 34.3 ms 93.6 MB
ind-models ✋ 102 ms 96.6 MB
tenet ✋ 143 ms 45.9 MB
tenet-hs ✋ 2.30 ms 11.0 MB
kiota ✋ 1.73 ms 11.1 MB
ocaml4lean ✋ 14.3 ms 25.0 MB
logos-kernel ✋ 0.572 ms 4.7 MB
evmlean ✋ 3.77 s 275.4 MB
mini ✋ 37.7 ms 74.6 MB
overfull ✋ 77.1 s 48.6 MB
lean4cobol ✋ 15.7 ms 13.7 MB
lean4lean ✋ 30.7 ms 89.3 MB
canonical-min 🚫 389 ms 1.1 GB
nanoclo 👍 1.03 ms 55.5 MB
vow-lean-kernel ✋ 250 ms 14.7 MB
lazylean 👍 1.50 ms 21.2 MB
metalean-slow ✋ 39.6 ms 66.1 MB
metalean-fast ✋ 32.8 ms 70.2 MB
nanoclo-fortran 👍 1.97 ms 4.5 MB
mathgraph 👍 0.927 ms 37.4 MB