Zulip Chat Archive
Stream: lean4
Topic: Array property using induction
Muqsit Azeem (Feb 11 2024 at 22:30):
I am using induction to prove the property that updating all the values of an array will not change the size of the array.
import Std.Data.Array
def set_elements (arr: Array Int) (index: Nat) : Array Int := Id.run do
let mut arr : Array Int := arr
let mut index : Nat := index
if index >= arr.size then
return arr
else
arr := arr.set! index 1
index := index+1
return set_elements arr index
termination_by _ => arr.size - index
decreasing_by simp_wf; sorry
def set_one (arr: Array Int) : Array Int := Id.run do
return set_elements arr 0
theorem set_elements_size (arr : Array Int) (index : Nat) : (set_elements arr index).size = arr.size := by
unfold set_elements Id.run
simp_all
induction arr.size - index
case zero =>
have h₁: arr.size = index := by sorry -- assuming case zero => arr.size - index = 0
simp_all
case succ =>
have h₂: arr.size > index := by sorry -- assuming case zero => arr.size - index > 0
simp_all
theorem size_same_set_1 (arr: Array Int) : (set_one arr).size = arr.size := by
unfold set_one Id.run
simp_all
apply set_elements_size
Applying induction on arr.size - index
splits it into two goals given below but no constraints on the induction variables.
case zero
arr: Array Int
index: Nat
⊢ Array.size (if index ≥ Array.size arr then arr else set_elements (Array.set! arr index 1) (index + 1)) = Array.size arr
and
case succ
arr: Array Int
indexn✝: Nat
n_ih✝: Array.size (if index ≥ Array.size arr then arr else set_elements (Array.set! arr index 1) (index + 1)) = Array.size arr
⊢ Array.size (if index ≥ Array.size arr then arr else set_elements (Array.set! arr index 1) (index + 1)) = Array.size arr
Therefore I added h1 and h2 in these two cases respectively.
How do I get rid of sorry
for h1 and h2?
I am using Lean version 4.5.0-rc1
Last updated: May 02 2025 at 03:31 UTC