Friedmanova překlad - Friedman translation

v matematická logika, Friedmanova překlad je určitá transformace intuitivní vzorce. Mimo jiné lze použít k prokázání, že Π02 - věty různých teorie prvního řádu klasické matematiky jsou také věty intuicionistické matematiky. Je pojmenována po svém objeviteli, Harvey Friedman.

Definice

Nechat A a B být intuitivní vzorce, kde žádná volná proměnná B je vyčísleno v A. Překlad AB je definována nahrazením každého atomového podformulu C z A podle CB. Pro účely překladu je ⊥ považován také za atomový vzorec, a proto je nahrazen ⊥ ∨ B (což odpovídá B). Všimněte si, že ¬A je definována jako zkratka pro A → ⊥, proto A)B = ABB.

aplikace

Friedmanova překladu může být použita k ukázce uzavření mnoha intuičních teorií pod Markovovo pravidlo, a získat částečná konzervativnost Výsledek. Klíčovou podmínkou je, že věty logiky mohou být rozhodnutelné, což umožňuje shodovat se nekvantifikované věty intuitivní a klasické teorie.

Například pokud A je prokazatelný v Heyting aritmetic (HA) AB je také prokazatelné v HA.[1] Navíc pokud A je Σ01-vzorec, pak AB je v HA ekvivalentní k AB. To znamená, že:

  • Heyting arithmetic is closed under the primitive recursive Markov rule (MPPR): pokud vzorec ¬¬A je prokazatelné v HA, kde A je Σ01- tedy vzorec A je také prokazatelné v HA.
  • Peano aritmetika je Π02-konzervativní nad heytingovou aritmetikou: pokud Peanoova aritmetika prokáže Π02-vzorec A, pak A je již prokazatelný v HA.

Viz také

Poznámky

  1. ^ Harvey Friedman. Klasicky a intuitivně prokazatelně rekurzivní funkce. V publikaci Scott, D. S. a Muller, G. H. Editors, Higher Set Theory, Volume 699 of Lecture Notes in Mathematics, Springer Verlag (1978), s. 21–28. doi:10.1007 / BFb0103100