Zulip Chat Archive
Stream: lean4
Topic: Matching a conditional in a theorem
Brandon Brown (Jun 30 2021 at 19:56):
Related to the discussion in the other Lean4 topic "Alternative Int Hierarchy," I took the following custom int
type:
inductive int : Type where
| zero : int
| pos_succ : Nat → int
| neg_succ : Nat → int
And "embedded" it into the natural numbers type, or rather, I made a bijective map between this integer type and the natural number type, and defined an addition function over these integers-as-naturals such that the integers become well-ordered as 0,-1,1,-2,2,-3,3 ...
This way I do not have to deal with the 3 constructors causing case-explosion and can write functions using the two constructor natural number type and map back into my int
type representation. (This is totally not for anything practical and just for intellectual curiosity and learning lean.)
So my question is, my add function involves a conditional and I realize I don't know how to deal with these when proving theorems about a function with a conditional. The blah1
theorem should be true by definition if the number is_even
. Here's a MWE with the theorem I'd like to prove at the bottom.
open Nat
inductive int : Type where
| zero : int
| pos_succ : Nat → int
| neg_succ : Nat → int
open int
def double (n : Nat) : Nat := 2 * n
def halve (n : Nat) : Nat := n / 2
def is_even (n : Nat) : Bool := do
let y := Nat.mod n 2
return if y = 0 then true else false
def int_to_Nat' (j : int) : Nat :=
match j with
| int.zero => 0
| pos_succ j =>
match j with
| 0 => 2
| succ j =>
double (j+2)
| neg_succ j =>
match j with
| 0 => 1
| succ j => (double (j+2)) - 1
-- 0 1 2 3 4 5 6 7 8
-- 0,-1,1,-2,2,-3,3,-4,4 ...
/-
the even numbers are positive integers
the odd numbers are negative integers
-/
def Nat_to_int' (n : Nat) : int :=
match n with
| 0 => int.zero
| (n+1) => do
if is_even n then
let x := (halve n)
return neg_succ (x)
else
let x := (halve (n + 1)) - 1
return pos_succ (x)
#reduce Nat_to_int' 6
def int_as_Nat_incr (n : Nat) : Nat :=
match n with
| 0 => 2
| (n+1) =>
if is_even n then -- if negative
return n - 1
else -- if positive
return (n+3)
#reduce int_as_Nat_incr 5
def int_as_Nat_decr (n : Nat) : Nat :=
match n with
| 0 => 1
| (n + 1) =>
if is_even n then -- if negative
return (n + 3)
else -- if positive
return (n - 1)
#reduce int_as_Nat_decr 1
def add_ian (n m : Nat) : Nat :=
match n with
| 0 => m
| 1 => int_as_Nat_decr m
| succ (succ n) =>
if is_even n then -- `n` is positive
int_as_Nat_incr (add_ian n m)
else -- `n` is negative
int_as_Nat_decr (add_ian n m)
-- 0,-1,1,-2,2,-3,3
-- (1 : Nat) = (-1 : int)
#reduce add_ian 2 3 -- 1
def add'' (j k : int) : int :=
Nat_to_int' (add_ian (int_to_Nat' j) (int_to_Nat' k))
instance : Add int where
add := add''
def i1 : int := neg_succ 2 -- -3
def i2 : int := pos_succ 3 -- +4
#reduce i1 + i2 -- pos_succ 0
infixl:65 " +₁ " => add_ian
-- How do I match the `is_even n` case?
theorem blah1 : ∀ n m : Nat, is_even n → ((n+2) +₁ m) = int_as_Nat_incr (n +₁ m) := sorry
Chris B (Jun 30 2021 at 20:42):
It looks like that syntax of passing a bool elaborates to (b = true)
by default.
theorem blah1 : ∀ n m : Nat, is_even n → ((n+2) +₁ m) = int_as_Nat_incr (n +₁ m) := by
intro n m h_even
cases m
simp [h_even, Nat.add, add_ian]
simp [h_even, Nat.add, add_ian]
Brandon Brown (Jun 30 2021 at 20:52):
Oh thanks! - I definitely tried starting out with intros and cases not sure where I went wrong; I did a lot of refactoring so might've just messed up something along the way
Brandon Brown (Jun 30 2021 at 21:05):
Actually that was the wrong question, I was actually having issues proving this because I don't know how to do cases on is_even
theorem add_zero : ∀ n : Nat, n +₁ 0 = n :=
fun n =>
match n with
| 0 => rfl
| 1 => rfl
| (n+2) =>
if is_even n then -- is positive
sorry
else
sorry
I don't know how to get access to the proof is_even n
in each branch
Chris B (Jun 30 2021 at 21:30):
There might be a cool new lean4 way of doing it, but the lean3 way still works, you have to name the hypothesis in the if case, and the negated one is then available under the same name in the else case.
theorem add_zero : ∀ n : Nat, n +₁ 0 = n :=
fun n =>
match n with
| 0 => rfl
| 1 => rfl
| (n+2) =>
if h_even : is_even n then
_
else
_
Brandon Brown (Jul 01 2021 at 01:45):
Hmm I swear I tried that, but thanks again. Why doesn't this seem to work in tactic mode?
Chris B (Jul 01 2021 at 02:17):
I know very little about Lean 4's tactic mode, but I would assume just because it's not directly a tactic; you would have to preface it with exact
or something. In tactic mode it looks like byCases h_ev: is_even n
and cases h_ev: is_even n
will both get you into a similar position. Lean 4 is also whitespace sensitive in some places, so you may have run afoul of that somewhere.
Last updated: Dec 20 2023 at 11:08 UTC