## Stream: general

### Topic: Extra instance makes exact_dec_trivial fail

#### Seul Baek (Feb 18 2019 at 19:47):

Here's a simple proof by exact_dec_trivial :

import data.list.basic

def foo (n : nat) : Prop := n = 0

instance : decidable_pred foo :=
begin intro n, simp [foo], apply_instance end

example : ∀ n ∈ [0], foo n :=
by tactic.exact_dec_trivial


The proof succeeds because the instance decidable_forall_mem {p : α → Prop} [decidable_pred p] (l : list α) : decidable (∀ x ∈ l, p x) is available. Although not necessary, having an extra instance of this type does not affect the proof:

import data.list.basic

def foo (n : nat) : Prop := n = 0

instance : decidable_pred foo :=
begin intro n, simp [foo], apply_instance end

instance bar {α} {p : α → Prop} [decidable_pred p]
(l : list α) : decidable (∀ x ∈ l, p x) :=
decidable_of_iff _ list.all_iff_forall_prop

example : ∀ n ∈ [0], foo n :=
by tactic.exact_dec_trivial


But if you add a slightly different instance of the same type:

import data.list.basic

def foo (n : nat) : Prop := n = 0

instance : decidable_pred foo :=
begin intro n, simp [foo], apply_instance end

instance baz {α} {p : α → Prop} [decidable_pred p]
(l : list α) : decidable (∀ x ∈ l, p x) :=
begin
cases l, apply decidable.is_true, intros x h, cases h,
rw list.forall_mem_cons, apply and.decidable,
end

example : ∀ n ∈ [0], foo n :=
by tactic.exact_dec_trivial


Then exact_dec_trivial doesn't work anymore. What's the difference between bar and baz that causes this?

#### Simon Hudon (Feb 18 2019 at 19:55):

If you set the option pp.proofs to true and #print baz, you're going to see a proof term. Part of it is:

eq.mpr (baz._proof_2 l_hd l_tl) and.decidable


I'm wondering if, with baz._proof_2 being opaque, eq.mpr can't unfold it to do recursion on it.

#### Simon Hudon (Feb 18 2019 at 19:55):

@Mario Carneiro ?

#### Simon Hudon (Feb 18 2019 at 19:58):

Actually, now that I look more closely at baz._proof_2, I see that it refers to propext which is an axiom it cannot use for computation.

#### Kenny Lau (Feb 18 2019 at 20:28):

don't use tactics for definitions...

#### Kenny Lau (Feb 18 2019 at 20:29):

I think there's a similar issue with functions defined via nat.strong_rec_on that the kernel/VM cannot unfold proofs

#### Mario Carneiro (Feb 19 2019 at 00:37):

Never use rw or cast to construct decidable instances

#### Mario Carneiro (Feb 19 2019 at 00:37):

use decidable_of_iff instead (you can then prove the iff statement however you want)

#### Mario Carneiro (Feb 19 2019 at 00:38):

This is important because decidable_of_iff does not use cast to get from one type to another, it pattern matches on one and uses the iff statement to get to the other

#### Mario Carneiro (Feb 19 2019 at 00:39):

If you use rw, it will cast across propext and the resulting term will get stuck in reduction, even when it should be provable

#### Moses Schönfinkel (Feb 19 2019 at 00:40):

This should be pinned or some such, these are impossible to debug for me. The last advice I got wrt. looking into #reduce was to put a breakpoint in C++ code :-/.

#### Mario Carneiro (Feb 19 2019 at 00:42):

here's the important part of the example:

set_option pp.implicit true
#reduce @baz _ foo _ [0]
-- @eq.rec Type (decidable (0 = 0 ∧ ∀ (x : ℕ), false → x = 0)) (λ (_x : Type), _x)
--   (@is_true (0 = 0 ∧ ∀ (x : ℕ), false → x = 0) _)
--   (decidable (∀ (x : ℕ), x = 0 ∨ false → x = 0))
--   (propext _)


#### Mario Carneiro (Feb 19 2019 at 00:43):

it's stuck on a reduction of propext

#### Mario Carneiro (Feb 19 2019 at 00:43):

(example slightly unelided for clarity)

Last updated: Dec 20 2023 at 11:08 UTC