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 Π⁰₂ - 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 A^B je definována nahrazením každého atomového podformulu C z A podle C ∨ B. 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 = A^B → B.

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 ${displaystyle Delta _ {0} ^ {0}}$ 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) A^B je také prokazatelné v HA.^[1] Navíc pokud A je Σ⁰₁-vzorec, pak A^B je v HA ekvivalentní k A ∨ B. To znamená, že:

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

Viz také

• Gödel – Gentzen negativní překlad

Poznámky