Co się stanie, jeśli spróbujemy wydobyć świadka, ale tak naprawdę nie istnieje on z pojęcia typu egzystencjalnego?


12

Biorąc pod uwagę termin t : ∀x.∃y.(¬(x = 0) ⇒ x = S(y))z teorii typów Martina-Lofa, jaka jest wartość w(t(0)), gdzie wjest operator wydobywający świadka terminu typu egzystencjalnego?


Myślę, że masz na myśli . ¬(x=0)
Mark Reitblatt,

Tak, Mark, dziękuję za zwrócenie uwagi, naprawione.
dzień

Odpowiedzi:


12

Dowolna wartość. To zależy od tego, który dostaniesz. Termin typu y . ( Ź ( 0 = 0 ) 0 = S ( T ) ) jest parą int Y i funkcja wykonuje dowód Ź ( 0 = 0 ) i daje dowód 0 = S (ty.(¬(0=0)0=S.(y))y¬(0=0) . Możesz użyć terminu typu ¬ ( 0 = 0 ) i typu 0 = 00=S.(y)¬(0=0)0=0(z zwrotności), aby uzyskać termin dowolnego typu. Obejmuje to termin typu , 0 = S ( 1 ) , . Możesz więc ustawić dowolną liczbę całkowitą, jaką chcesz.0=S.(0)0=S.(1)y


10

Aby zademonstrować odpowiedź Marka, rozważ następujący dowód ttwojego oświadczenia, napisany w Coq. W dowodzie zakładamy, że podano parametr ktypu nat. Używamy kjako wartości yw przypadku x = 0:

Parameter k : nat.

Theorem t : forall x : nat, { y : nat | x <> 0 -> x = S y}.
Proof.
  induction x.
  exists k; tauto.
  induction x.
  exists 0; auto.
  destruct IHx as [z G].
  exists (S z).
  intro H.
  elim G; auto.
Defined.

Możemy udowodnić, że t 0jest to równe k:

Theorem A: projT1 (t 0) = k.
Proof.
  auto.
Qed.

protT1Jest tam, bo t 0nie jest tylko liczbą naturalną, ale w rzeczywistości liczbą naturalną z dowodem, że 0 <> 0 -> 0 = S yi projT1wyrzuca dowód.

Wyodrębniony kod Ocaml dla t, uzyskany za pomocą polecenia Extraction kto

(** val t : nat -> nat **)

let rec t = function
  | O -> k
  | S n0 -> (match n0 with
              | O -> O
              | S n1 -> S (t n0))

Ponownie możemy zobaczyć, że t 0jest równy k, który był arbtralnie przyjętym parametrem.


Dzięki za przykład w Coq, Andrej, wyjaśnia on więcej.
dzień
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.