Realność - Realizability

W logice matematycznej , Realność jest zbiorem metod teoria dowodu wykorzystywanych do badania konstruktywne dowody i wydobyć dodatkowe informacje od nich. Wzory z formalnej teorii są „realizowane” przez obiekty, znane jako „Realizatorzy”, w taki sposób, że wiedza o Realizer daje wiedzę na temat prawdziwości formuły. Istnieje wiele odmian realizowalności; dokładnie, jakiej klasy jest badany i formuł, które obiekty są Realizatorzy różnią się od jednego do drugiego zmienności.

Realność może być postrzegane jako formalizacji interpretacji BHK intuicjonistycznej logiki; w realizowalności pojęcie „dowód” (co jest po lewej niezdefiniowana w interpretacji BHK) otrzymuje z formalnego pojęcia „realizatorem”. Większość wariantów realizowalności rozpoczynać się twierdzeniu, że każda wypowiedź to udowodnić w systemie formalnym badane jest do zrealizowania. Realizatorem jednak zazwyczaj daje więcej informacji na temat wzoru niż formalny dowód będzie bezpośrednio dostarczyć.

Poza dając wgląd intuicjonistycznej dowodliwości, Realność mogą być stosowane do udowodnienia własności alternatywy i istnienie dla intuicjonistycznej teorii i wyodrębnić programy z dowodów, jak w lustrzanym górnictwie . Jest to również związane z Topos teorię poprzez toposu realizowalności .

Przykład: Realność numerami

Oryginalna wersja KLEENE z dnia realizowalności używa liczby naturalne jak Realizatorzy dla formuł w Heytinga arytmetyki . Poniższe klauzule są wykorzystywane do określenia związek „ n realizuje A ” między liczby naturalne n i formuł A w języku Heytinga arytmetycznych. Wymagany jest kilka kawałków oznaczenia: Po pierwsze, uporządkowane pary ( n , m ) jest traktowany jako jeden numer zastosowaniem stałego skutecznej funkcji pary ; Po drugie, dla każdej liczby naturalne n , φ n jest obliczeniowy funkcja o indeksie n .

  • Liczba n realizuje formułę atomowej s = T tylko wtedy, gdy s = t jest prawdziwe. Zatem każda liczba realizuje prawdziwe równanie, a nie liczba realizuje fałszywe równanie.
  • Para ( n , m ) realizuje wzór ∧ B , wtedy i tylko wtedy, gdy n realizuje i m realizuje B . Zatem Realizer dla związku jest para Realizatorzy dla conjuncts.
  • Para ( n , m ) realizuje wzór ∨ B , wtedy i tylko wtedy, gdy w poniższym zawieszone: n oznacza 0 lub 1; jeśli n wynosi 0, to wówczas m realizuje ; jeśli n wynosi 1, to m realizuje B . Zatem Realizer do alternatywy wyraźnie wybiera jeden z disjuncts z ( n ), i podaje Realizer na nim (z m ).
  • Liczba n realizuje wzorze A → B , wtedy i tylko wtedy, gdy dla każdego m realizującego , φ n ( m ) realizuje B . Zatem realizatorem dla implikacji jest obliczalna funkcja, która zajmuje Realizer dla hipotezy i tworzy Realizer do zawarcia.
  • Para ( n , m ) realizuje wzorze (∃ x ) ( x ), wtedy i tylko wtedy, gdy m jest Realizer do A ( n ). Zatem realizatorem dla egzystencjalnego wzoru daje wyraźne świadectwo dla kwantyfikatora wraz z realizatorem dla wzoru tworzony z tego świadka.
  • Liczba n realizuje wzorze (∀ x ) ( x ) wtedy i tylko wtedy, gdy dla wszystkich m , φ n ( m ) określa się i realizuje A ( m ). Zatem realizatorem uniwersalnego rachunku jest obliczalna funkcja, która produkuje dla każdego m , świadka, o wzorze tworzony z m .

Z tej definicji, następujące twierdzenie uzyskuje się:

Niech być zdanie Heytinga arytmetyki (HA). Jeśli okaże się HA wówczas istnieje n takie, że n realizuje .

Z drugiej strony, istnieją wzory, które są realizowane, ale które nie są możliwe do udowodnienia w HA, w rzeczywistości po raz pierwszy ustanowionego przez Rose.

Dalsza analiza metody mogą być stosowane do wykazania, że HA ma „ alternatywy i istnienie właściwości ”:

  • Jeśli okaże się karę HA (∃ x ) ( x ), a następnie występuje brak takich, że HA okazuje ( n )
  • Jeśli HA dowodzi zdanie ∨ B , następnie HA dowodzi A lub HA dowodzi B .

późniejsze wydarzenia

Kreisel wprowadził zmodyfikowaną realizowalności , który korzysta wpisane rachunek lambda jako język Realizatorzy. Zmodyfikowany Realność jest jeden sposób, aby pokazać, że zasada Markowa nie derivable w intuicjonistycznej logiki. Wręcz przeciwnie, pozwala konstruktywnie uzasadnić zasadę niezależności założeniu:

,

Względna Realność jest analiza intuicjonisty z cyklicznych lub rekurencyjnie przeliczalnych elementów struktur danych, które niekoniecznie są obliczalne, takich jak obliczalnych operacji na wszystkich liczb rzeczywistych, gdy Real może być przybliżona tylko na cyfrowych systemów komputerowych.

Aplikacje

Realność jest jedną z metod stosowanych w lustrzanym górnictwie wyodrębnić konkretne „Programy” z pozoru nonconstructive dowodu matematycznego. Ekstrakcja za pomocą realizowalności Program realizowany jest w niektórych odpornych asystentów , takich jak Coq .

Zobacz też

Uwagi

  1. ^ Van Oosten 2000
  2. ^ Van Oosten 2000, s. 7
  3. ^ Rose 1953
  4. ^ Van Oosten 2000, s. 6
  5. ^ Birkedal 2000

Referencje

  • Birkedal Lars; Jaap van Oosten (2000). Względna i modyfikowane względem Realność .
  • Kreisel G. (1959). „Interpretacja Analiza w drodze konstruktywnego funkcjonałów skończonych Types”, w:. Constructivity z matematyki, pod redakcją A. Heytinga, North-Holland, pp 101-128.
  • Kleene, SC (1945). „W interpretacji intuicjonistycznej teorii liczb”. Journal of Symbolic Logic . 10 (4): 109-124. doi : 10,2307 / 2269016 . JSTOR  2269016 .
  • Kleene, SC (1973). „Realność: Badanie retrospektywne” od Mathias, ARD; Hartley Rogers (1973). Letnia Szkoła w Cambridge Mathematical Logic: utrzymywane w Cambridge / Anglia, 1-21 sierpnia 1971 r . Berlin: Springer. ISBN  3-540-05569-X ., S. 95-112.
  • van Oosten Jaap (2000). Realność: Esej historyczny .
  • Rose, GF (1953). „Rachunek zdań i Realność”. Transactions of the American Mathematical Society . 75 (1): 1-19. doi : 10,2307 / 1990776 . JSTOR  1990776 .

Linki zewnętrzne

  • Realność zbiór linków do najnowszych opracowań poświęconych realizowalności i tematów pokrewnych.