Proving a type empty in Agda -
i trying prove 2*3!=5 in agda. define function signature 2 * 3 ≡ 5 → ⊥.
making use of definition of multiplication
data _*_≡_ : ℕ → ℕ → ℕ → set base : ∀ {n} → 0 * n ≡ 0 succ : ∀ {n m k j} → m * n ≡ j → j + n ≡ k → suc m * n ≡ k
i have proven
1*3≡3 : 1 * 3 ≡ 3 1*3≡3 = (succ base) znn
and
3+3≡5 : 3 + 3 ≡ 5 → ⊥ 3+3≡5 (sns (sns (sns ())))
but when try prove:
m235 : 2 * 3 ≡ 5 → ⊥ m235 ( ( succ 1*3≡3 ) ( x ) ) = ( 3+3≡5 x )
the compiler spits out error x
.j != (suc 2) of type ℕ when checking expression x has type 3 + 3 ≡ 5
sorry if stupid question. in advance.
first of all, forgot include definition of _+_≡_
. assume it's follows:
data _+_≡_ : ℕ → ℕ → ℕ → set znn : ∀ {n} → 0 + n ≡ n sns : ∀ {n m k} → n + m ≡ k → suc n + m ≡ suc k
next, problem not finding correct syntax, have figure out how can conclude value of type 2 * 3 ≡ 5
. pattern matching have done, can ask agda values available in context, replacing right-hand-side ?, calling c-c c-l compile , using c-c c-, ask context:
m235 : 2 * 3 ≡ 5 → ⊥ m235 ( ( succ 1*3≡3 ) ( x ) ) = ?
agda say:
goal : ⊥ ----------------------------- x : .j + 3 ≡ 5 1*3≡3 : 1 * 3 ≡ .j .j : ℕ
that is: looking prove bottom (i.e. inconsistency assumptions) , have 3 values available in context. have proof of type 1 * 3 ≡ .j
, unknown number .j
proof of type .j + 3 ≡ 5
. seem assume agda can automatically notice j must 3, difficult it: conclude things here unification, not perform actual reasoning itself. solution agda understand why .j
must 3. can further pattern matching on proof of type 1 * 3 ≡ .j
:
m235 : 2 * 3 ≡ 5 → ⊥ m235 ((succ (succ base znn)) sum) = ?
now context looks follows:
goal: ⊥ ———————————————————————————————————————————————————————————— x : 3 + 3 ≡ 5
you can finish combining proof x
of type 3 + 3 ≡ 5
previous proof such proof cannot exist:
m235 : 2 * 3 ≡ 5 → ⊥ m235 (succ (succ base znn) x) = 3+3≡5 x
update: missed in first reading, there misunderstanding in question missed , failed explain. error in following code:
m235 : 2 * 3 ≡ 5 → ⊥ m235 (succ 1*3≡3 x) = 3+3≡5 x
the misunderstanding here variable name 1*3≡3 in left-hand side of clause not refer defined value same name. rather, introduces fresh new variable known agda have same type, value not known it.
what expecting can achieved using "pattern synonyms" feature introduced in agda 2.3.2: see the release notes:
pattern 1*3≡3 = (succ base) znn m235 : 2 * 3 ≡ 5 → ⊥ m235 (succ 1*3≡3 x) = 3+3≡5 x
only pattern synonyms expanded in patterns, other values aren't.
Comments
Post a Comment