Как использовать get, чтобы упростить чтение доказательств прямого исключения?

Я пытаюсь сделать базовые доказательства естественного вывода в Изабель, следуя этому документу (особенно слайд 23).

Я знаю, что могу делать такие вещи, как

theorem ‹(A ⟶ B) ⟶ A ⟶ B›
proof -
  {
    assume ‹A ⟶ B›
    {
      assume ‹A›
      with ‹A ⟶ B› have ‹B› ..
    }
    hence ‹A ⟶ B› ..
  }
  thus ‹(A ⟶ B) ⟶ A ⟶ B› ..
qed

Но также

theorem ‹(A ⟶ B) ⟶ A ⟶ B›
proof
  assume ‹A ⟶ B› and ‹A›
  then obtain ‹B› ..
qed

достигает той же цели.

Поэтому, когда я пытаюсь написать доказательство

theorem ‹(A ⟶ A ⟶ B) ⟶ A ⟶ B›
proof -
  {
    assume ‹A ⟶ A ⟶ B›
    {
      assume ‹A›
      with ‹A ⟶ A ⟶ B› have ‹A ⟶ B› ..
      hence ‹B› using ‹A› ..
    }
    hence ‹A ⟶ B› ..
  }
  thus ‹(A ⟶ A ⟶ B) ⟶ A ⟶ B› ..
qed

как

theorem ‹(A ⟶ A ⟶ B) ⟶ A ⟶ B›
proof
  assume ‹A ⟶ A ⟶ B› and ‹A›
  hence ‹A ⟶ B› ..
  then obtain ‹B› using ‹A› ..
qed

почему Изабель жалуется, что

Failed to finish proof:
goal (1 subgoal):
 1. A ⟶ A ⟶ B ⟹ A ⟶ B

Я знаю, что это очень простые вещи, которые Изабель может доказать за один шаг: цель здесь - создать краткое доказательство, удобочитаемое для человека (в той степени, в которой это возможно с помощью естественного вывода), без необходимости консультироваться с Изабель.


person Nick Hu    schedule 12.11.2018    source источник


Ответы (1)


Эта модификация вашего доказательства работает:

theorem ‹(A ⟶ A ⟶ B) ⟶ A ⟶ B›
proof(intro impI)
  assume ‹A ⟶ A ⟶ B› and ‹A›
  hence ‹A ⟶ B› ..
  then show ‹B› using ‹A› ..
qed

Проблема двоякая:

  1. При открытии блока доказательства автоматически применяется «стандартное» правило введения, основанное на форме цели, которую вы пытаетесь доказать. В вашем случае это было введение импликации, то есть теорема impI. Проблема в том, что вы применяете это только один раз, что оставляет вам предположение A -> A -> B и оставшуюся цель A -> B. В результате у вас еще нет предположения A, которое, как вы предполагаете, у вас есть, поскольку для его получения требуется второе использование impI. Вместо этого, используя proof(intros impI), я говорю Изабель воздержаться от использования своего стандартного набора правил введения и исключения в качестве первого шага в доказательстве и вместо этого применять правило введения impI как можно чаще (т. Е. Дважды). В качестве альтернативы, proof(rule impI, rule impI) также будет работать здесь с тем же эффектом.
  2. Во-вторых, ваша последняя строка then obtain и далее не завершает доказательство: вы ничего show не делаете! Используя явное show, вы сигнализируете Изабель, что хотите «уточнить» открытую цель и фактически сделать вывод о том, что вы намеревались доказать в начале блока.

Обратите внимание, что ваше использование obtain здесь для продвижения вперед на основе фактов A -> B и A не было неправильным, если ваша единственная цель - получить B. Проблема в том, что вы пытаетесь отталкиваться от фактов, чтобы вывести новые, одновременно уточняя открытую цель. Например, это тоже работает:

theorem ‹(A ⟶ A ⟶ B) ⟶ A ⟶ B›
proof(intro impI)
  assume ‹A ⟶ A ⟶ B› and ‹A›
  hence ‹A ⟶ B› ..
  then obtain ‹B› using ‹A› ..
  then show ‹B› .
qed

где факт B получен в первой строке, а вторая строка тривиально использует этот факт для уточнения открытой цели B.

person Dominic Mulligan    schedule 23.11.2018