Как использовать получение в экзистенциальных доказательствах?

Question

Я пытался доказать экзистенциальную теорему

lemma "∃ x. x * (t :: nat) = t"
proof
  obtain y where "y * t = t" by (auto)

но я не смог закончить доказательство. Так что у меня есть необходимые y но как я могу кормить это в первоначальной цели?

Answer 1

Правильность естественного вывода требует, чтобы вы завладели свидетелем, прежде чем открыть экзистенциальный квантификатор. Вот почему вы не можете использовать полученные переменные в show заявления. В вашем примере proof шаг неявно применяет правило exI, Это превращает экзистенциально количественную переменную x в переменную схемы ?x, который может быть создан позже, но экземпляр может ссылаться только на переменные, которые находились в области видимости, когда ?x пришел на место. В состоянии доказательства низкого уровня полученные переменные мета-количественно (!!) и экземпляры для ?x может ссылаться только на такие переменные, которые появляются в качестве параметра ?x,

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

lemma "∃ x. x * (t :: nat) = t"
proof - (* method - does not change the goal *)
  obtain y where "y * t = t" by (auto)
  then show ?thesis by(rule exI)
qed

Answer 2

Вы можете дать свидетелю (то есть элемент, который вы хотите вставить для х) в show пункт:

lemma "∃ x. x * (t :: nat) = t"
proof
  show "1*t = t" by simp
qed

Answer 3

В качестве альтернативы, если вы уже знаете свидетеля ( 1 или же Suc 0 здесь), вы можете явно создать экземпляр правила exI ввести экзистенциальный термин:

      lemma "∃ x. x * (t :: nat) = t"
  by (rule exI[where x = "Suc 0"], simp)

Здесь правило введения квантора существования thm exI является

      ?P ?x ⟹ ∃x. ?P x

с ответом вы можете постепенно его исследовать и создавать экземпляры.

thm exI[where x = "Suc 0"] является:

      ?P (Suc 0) ⟹ ∃x. ?P x

а также exI[where P = "λ x. x * t = t" and x = "Suc 0"] является

      Suc 0 * t = t ⟹ ∃x. x * t = t

А также Suc 0 * t = t это только одно упрощение ( simp) далеко. Но система может определить последний экземпляр P = "λ x. x * t = t" через унификацию, поэтому в этом нет необходимости.

Связанный:

Доказательство теорем в Изабель