Изабель доказывает коммутативность для добавления

Question

Я пытаюсь доказать коммутативность в Изабель /HOL для самоопределения add функция. Мне удалось доказать ассоциативность, но я застрял на этом.

Определение add:

fun add :: "nat ⇒ nat ⇒ nat" where
"add 0 n = n" |
"add (Suc m) n = Suc(add m n)"

Доказательство ассоциативности:

lemma add_Associative: "add(add k m) z = add k (add m z)"
apply(induction k)
apply(auto)
done

Доказательство коммутативности:

theorem add_commutativity: "add k m = add m k"
apply(induction k)
apply(induction m)
apply(auto)

Я получаю следующие цели:

goal (3 subgoals):
1. add 0 0 = add 0 0
2. ⋀m. add 0 m = add m 0 ⟹
     add 0 (Suc m) = add (Suc m) 0
3. ⋀k. add k m = add m k ⟹
     add (Suc k) m = add m (Suc k)

После применения авто у меня остается только подзадача 3:

3. ⋀k. add k m = add m k ⟹
     add (Suc k) m = add m (Suc k)

РЕДАКТИРОВАТЬ: Я не столько ищу ответ, сколько толчок в правильном направлении. Это упражнения из книги "Конкретная сементика".

Answer 1

Я бы предложил сделать доказательство как можно более модульным (то есть доказать промежуточные леммы, которые позже помогут решить доказательство коммутативности). С этой целью часто более информативно медитировать на подзадачах, представленных induct, прежде чем применять полную автоматизацию (как ваш apply (auto)).

lemma add_comm:
  "add k m = add m k"
  apply (induct k)

На данный момент подцели:

 goal (2 subgoals):
  1. add 0 m = add m 0
  2. ⋀k. add k m = add m k ⟹ add (Suc k) m = add m (Suc k)

Давайте посмотрим на них отдельно.

1. Используя определение add мы сможем только упростить левую часть, т.е. add 0 m = m, Тогда остается вопрос, как доказать add m 0 = m, Вы сделали это как часть вашего основного доказательства. Я бы сказал, что это повышает читабельность, чтобы доказать следующую отдельную лемму

   lemma add_0 [simp]:
     "add m 0 = m"
     by (induct m) simp_all
   

   и добавить его в автоматизированные инструменты (например, simp а также auto) с помощью [simp], На этом этапе первая подцель может быть решена путем simp и остается только вторая подцель.

2. После применения определения add а также гипотеза индукции (add k m = add m k) нам придется доказать Suc (add m k) = add m (Suc k), Это выглядит очень похоже на второе уравнение исходного определения addТолько с замененными аргументами. (С этой точки зрения то, что мы должны были доказать для первой подцели, соответствовало первому уравнению в определении add с заменой аргументов.) Теперь я бы предложил попробовать доказать общую лемму add m (Suc n) = Suc (add m n) чтобы продолжить.

Answer 2

Я отвечаю на вопрос RainyCats в комментарии к Крису: "Как Изабель доказывает". Я даю подробное доказательство ассоциативности add и вручную, и пошагово в Изаре.

Вручную для ассоциативности, по индукции по k:

• за k знак равно 0 мы должны доказать add (add 0 m) z = add 0 (add m z),

  Переписываем с определением add:

  • add (add 0 m) z ⇢ add m z
  • add 0 (add m z) ⇢ add m z

  Тогда цель подтверждается рефлексивностью =,

• за k знак равно Suc k'

  • мы предполагаем add (add k' m) z = add k' (add m z),
  • мы должны доказать add (add (Suc k') m) z = add (Suc k') (add m z),

  Переписываем с определением add:

  • add (add (Suc k') m) z ⇢ add (Suc (add k' m)) z ⇢ Suc (add (add k' m) z)
  • add (Suc k') (add m z) ⇢ Suc (add k' (add m z))

  По предположению индукции: Suc (add (add k' m) z) ⇢ Suc (add k' (add m z))

  И тогда цель подтверждается рефлексивностью =,

В Изаре с таким уровнем детализации это даст:

lemma add_Associative: "add(add k m) z = add k (add m z)"
proof (induction k)
  case 0
    have "add (add 0 m) z = add m z" by (subst add.simps, intro refl)
    moreover have "add 0 (add m z) = add m z" by (subst add.simps, intro refl)
    ultimately show ?case by (elim ssubst, intro refl)
next
  case (Suc k')
    have "add (add (Suc k') m) z = add (Suc (add k' m)) z" by (subst add.simps, intro refl)
    also have "… = Suc (add (add k' m) z)" by (subst add.simps, intro refl)
    also have "… = Suc (add k' (add m z))" by (subst Suc, intro refl)
    moreover have "add (Suc k') (add m z) = Suc (add k' (add m z))" by (subst add.simps, intro refl)
    ultimately show ?case by (elim ssubst, intro refl)
qed

где я сделал самые маленькие возможные шаги и где все by ... может быть заменено by simp,