Logika funktoru predikátu - Predicate functor logic

v matematická logika, logika funktoru predikátu (PFL) je jedním z několika způsobů vyjádření logika prvního řádu (také známý jako predikátová logika ) čistě algebraickými prostředky, tj. bez kvantifikované proměnné. PFL zaměstnává malý počet algebraických zařízení zvaných predikátové funktory (nebo modifikátory predikátů)^[1] které fungují za podmínek, aby poskytly podmínky PFL je většinou vynálezem logik a filozof Willard Quine.

Motivace

Zdrojem pro tuto část, stejně jako pro většinu této položky, je Quine (1976). Quine navrhl PFL jako způsob algebraizace logika prvního řádu analogickým způsobem Booleova algebra algebraizuje výroková logika. Navrhl PFL, aby měl přesně expresivní sílu logika prvního řádu s identita. Proto metamatematika PFL jsou přesně ty logiky prvního řádu bez interpretovaných predikátních písmen: obě logiky jsou zvuk, kompletní, a nerozhodnutelný. Většina prací, které Quine publikoval o logice a matematice v posledních 30 letech svého života, se nějakým způsobem dotkla PFL.^{[Citace je zapotřebí ]}

Quine vzal „funktora“ ze spisů svého přítele Rudolf Carnap, první, kdo ji zaměstnal v filozofie a matematická logika a definoval jej takto:

"Slovo funktor, gramatický v importu, ale logický v biotopu ... je znak, který se váže k jednomu nebo více výrazům daného gramatického druhu (druhů), aby vytvořil výraz daného gramatického druhu. “(Quine 1982: 129)

Jiné způsoby než PFL k algebraizaci logika prvního řádu zahrnout:

• Válcová algebra podle Alfred Tarski a jeho američtí studenti. Zjednodušená cylindrická algebra navržená Bernaysem (1959) vedla Quine k napsání článku obsahujícího první použití fráze „predikátový funktor“;
• The polyadická algebra z Paul Halmos. Na základě svých ekonomických primitiv a axiomů se tato algebra nejvíce podobá PFL;
• Vztahová algebra algebraizuje fragment logika prvního řádu sestávající ze vzorců, které nemají atomový vzorec v rozsahu větším než tři kvantifikátory. Tento fragment však stačí Peano aritmetika a axiomatická teorie množin ZFC; proto relační algebra, na rozdíl od PFL, je nedokončitelný. Většinu práce o relační algebře od roku 1920 provádí Tarski a jeho američtí studenti. Síla relační algebry se projevila až v monografii Tarski a Givant (1987), která vyšla po třech důležitých dokumentech týkajících se PFL, jmenovitě Bacon (1985), Kuhn (1983) a Quine (1976);
• Kombinovaná logika staví na kombinátory, funkce vyššího řádu jehož doména je další kombinátor nebo funkce a jehož rozsah je další kombinátor. Proto kombinační logika jde nad rámec logiky prvního řádu tím, že má expresivní sílu teorie množin, což činí kombinační logiku zranitelnou vůči paradoxy. Predikátový funktor na druhé straně jednoduše mapuje predikáty (nazývané také podmínky ) do predikátů.

PFL je pravděpodobně nejjednodušší z těchto formalizmů, ale také ten, o kterém bylo napsáno nejméně.

Quine byl celoživotně fascinován kombinační logika, o čemž svědčí úvod do překladu článku ruského logika ve Van Heijenoort (1967) Mojžíš Schönfinkel zakládající kombinační logika. Když Quine začal vážně pracovat na PFL, v roce 1959 byla kombinatorická logika běžně považována za neúspěch z následujících důvodů:

• Dokud Dana Scott začal psát na teorie modelů kombinatorické logiky koncem šedesátých let téměř pouze Haskell Curry, jeho studenti a Robert Feys v Belgii pracoval na této logice;
• Uspokojivé axiomatické formulace kombinační logiky přicházely pomalu. Ve 30. letech 20. století bylo zjištěno, že některé formulace kombinatorické logiky jsou nekonzistentní. Curry také objevila Paradox kari, charakteristické pro kombinatorickou logiku;
• The lambda kalkul, se stejnou expresivní silou jako kombinační logika, byl považován za nadřazený formalismus.

Kuhnova formalizace

PFL syntax, primitiva a axiomy popsané v této části jsou do značné míry Steven Kuhn (1983). The sémantika z funktorů jsou Quine's (1982). Zbytek této položky zahrnuje určitou terminologii od Bacona (1985).

Syntax

An atomový termín je velké písmeno latinky, Já a S s výjimkou číselného horní index volal jeho stupeň, nebo zřetězenými malými proměnnými, souhrnně označovanými jako seznam argumentů. Stupeň termínu vyjadřuje stejnou informaci jako počet proměnných následujících za predikátním písmenem. Atomový člen stupně 0 označuje a Booleovská proměnná nebo a pravdivostní hodnota. Stupeň Já je vždy 2, a proto není uvedeno.

„Kombinatorické“ (slovo je Quinovo) predikátové funktory, všechny monadické a charakteristické pro PFL, jsou Inv, inv, ∃, +, a str. Termín je buď atomový termín, nebo zkonstruovaný podle následujícího rekurzivního pravidla. Pokud τ je termín, pak Invτ, invτ, ∃τ, +τ a strτ jsou termíny. Funktor s horním indexem n, n A přirozené číslo > 1, označuje n po sobě jdoucí aplikace (iterace) tohoto funktoru.

Vzorec je buď výraz, nebo je definován rekurzivním pravidlem: jsou-li α a β vzorce, pak αβ a ~ (α) jsou rovněž vzorce. Proto je „~“ dalším monadickým funktorem a zřetězení je jediným dyadickým predikátovým funktorem. Quine nazval tyto funktory „aletickými“. Přirozená interpretace „~“ je negace; zřetězení je jakékoli spojovací že v kombinaci s negací tvoří a funkčně kompletní sada spojek. Quinina přednostní funkčně kompletní sada byla spojení a negace. Takto zřetězené termíny jsou považovány za spojené. Zápis + je Bacon's (1985); všechny ostatní notace jsou Quineovy (1976; 1982). Aletická část PFL je totožná s Schémata booleovského výrazu Quine (1982).

Jak je dobře známo, dva aletické funktory by mohly být nahrazeny jediným dyadickým funktorem s následujícím syntax a sémantika: pokud α a β jsou vzorce, pak (αβ) je vzorec, jehož sémantika je „ne (α a / nebo β)“ (viz NAND a ANI ).

Axiomy a sémantika

Quine nestanovil ani axiomatizaci, ani důkazní postup pro PFL. Následující axiomatizace PFL, jedné ze dvou navržených v Kuhnovi (1983), je stručná a snadno popsatelná, ale ve velké míře využívá volné proměnné a proto plně neodpovídá duchu PFL. Kuhn dává další axiomatizaci, která se obejde bez volných proměnných, ale to je těžší popsat a to rozsáhle využívá definované funktory. Kuhn prokázal obě své axiomatizace PFL zvuk a kompletní.

Tato část je postavena na primitivních predikátových funktorech a několika definovaných. Aletické funktory lze axiomatizovat libovolnou sadou axiomů pro sentenciální logika jejichž primitivy jsou negace a jeden z ∧ nebo ∨. Ekvivalentně všechny tautologie sentential logic lze brát jako axiomy.

Quineova (1982) sémantika pro každý funktor predikátu je uvedena níže, pokud jde o abstrakce (notace set builderu), za kterou následuje buď příslušný axiom z Kuhna (1983), nebo definice z Quine (1976). Zápis ${displaystyle {x_ {1} ... x_ {n}: Fx_ {1} ... x_ {n}}}$ označuje množinu n-tice splňující atomový vzorec ${displaystyle Fx_ {1} ... x_ {n}.}$

• Identita, Já, je definován jako:

${displaystyle IFx_ {1} x_ {2} ... x_ {n} leftrightarrow Fx_ {1} x_ {1} ... x_ {n} leftrightarrow Fx_ {2} x_ {2} ... x_ {n}. }$

Identita je reflexní (Ixx), symetrický (Ixy→Iyx), tranzitivní ( (Ixy∧Iyz) → Ixz), a řídí se vlastností substituce:

${displaystyle (Fx_ {1} ... x_ {n} země Ix_ {1} y) ightarrow Fyx_ {2} ... x_ {n}.}$

• Polstrování, +, přidá proměnnou nalevo od libovolného seznamu argumentů.

${displaystyle + F ^ {n} = _ {def} {x_ {0} x_ {1} ... x_ {n}: F ^ {n} x_ {1} ... x_ {n}}.}$

${displaystyle + Fx_ {1} ... x_ {n} šipka vlevo Fx_ {2} ... x_ {n}.}$

• Oříznutí, ∃, vymaže proměnnou úplně vlevo v libovolném seznamu argumentů.

${displaystyle existuje F ^ {n} = _ {def} {x_ {2} ... x_ {n}: existuje x_ {1} F ^ {n} x_ {1} ... x_ {n}}.}$

${displaystyle Fx_ {1} ... x_ {n} ightarrow existuje Fx_ {2} ... x_ {n}.}$

Oříznutí umožňuje dva užitečné definované funktory:

• Odraz, S:

${displaystyle SF ^ {n} = _ {def} {x_ {2} ... x_ {n}: F ^ {n} x_ {2} x_ {2} ... x_ {n}}.}$

${displaystyle SF ^ {n} leftrightarrow existuje IF ^ {n}.}$

S zobecňuje pojem reflexivity na všechny termíny jakéhokoli konečného stupně většího než 2. Pozn .: S by neměla být zaměňována s primitivní kombinátor S kombinační logiky.

• kartézský součin, ${displaystyle imes}$;

${displaystyle F ^ {m} imes G ^ {n} leftrightarrow F ^ {m} existuje ^ {m} G ^ {n}.}$

Pouze zde Quine přijala infixovou notaci, protože tato infixová notace pro kartézský součin je v matematice velmi dobře zavedená. Kartézský součin umožňuje opakující se spojku takto:

${displaystyle F ^ {m} x_ {1} ... x_ {m} G ^ {n} x_ {1} ... x_ {n} levá šipka (F ^ {m} je G ^ {n}) x_ { 1} ... x_ {m} x_ {1} ... x_ {n}.}$

Uspořádejte seznam zřetězených argumentů tak, aby se dvojice duplicitních proměnných posunula úplně vlevo, a poté vyvolajte S eliminovat duplikaci. Opakováním tolikrát, kolikrát je potřeba, se zobrazí seznam argumentů o maximální délce (m,n).

Další tři funktory aktivují libovolné pořadí seznamů argumentů.

• Hlavní inverze, Inv, otočí proměnné v seznamu argumentů doprava, takže poslední proměnná se stane první.

${displaystyle InvF ^ {n} = _ {def} {x_ {1} ... x_ {n}: F ^ {n} x_ {n} x_ {1} ... x_ {n-1}}.}$

${displaystyle InvFx_ {1} ... x_ {n} leftrightarrow Fx_ {n} x_ {1} ... x_ {n-1}.}$

• Menší inverze, inv, zamění první dvě proměnné v seznamu argumentů.

${displaystyle invF ^ {n} = _ {def} {x_ {1} ... x_ {n}: F ^ {n} x_ {2} x_ {1} ... x_ {n}}.}$

${displaystyle invFx_ {1} ... x_ {n} leftrightarrow Fx_ {2} x_ {1} ... x_ {n}.}$

• Permutace, str, otočí druhé až poslední proměnné v seznamu argumentů doleva, takže druhá proměnná se stane poslední.

${displaystyle pF ^ {n} = _ {def} {x_ {1} ... x_ {n}: F ^ {n} x_ {1} x_ {3} ... x_ {n} x_ {2}} .}$

${displaystyle pFx_ {1} ... x_ {n} leftrightarrow InvinvFx_ {1} x_ {3} ... x_ {n} x_ {2}.}$

Vzhledem k seznamu argumentů skládajícímu se z n proměnné, str implicitně zachází s posledním n−1 proměnných, jako je řetěz na kolo, přičemž každá proměnná představuje článek v řetězci. Jedna aplikace str posune řetěz o jeden článek. k po sobě jdoucí aplikace str na Fⁿ přesouvá k+1 proměnná k druhé pozici argumentu v F.

Když n=2, Inv a inv pouze výměna X₁ a X₂. Když n= 1, nemají žádný účinek. Proto str nemá žádný účinek, když n < 3.

Kuhn (1983) bere Hlavní inverze a Menší inverze jako primitivní. Zápis str v Kuhnu odpovídá inv; nemá obdobu Permutace a proto nemá žádné axiomy. Pokud po Quineovi (1976) str je bráno jako primitivní, Inv a inv lze definovat jako netriviální kombinace +, ∃a opakoval str.

Následující tabulka shrnuje, jak funktory ovlivňují stupně jejich argumentů.

Výraz	Stupeň
${displaystyle p; Inv; inv; lnot; Já}$	žádná změna
${displaystyle + F ^ {n-1}; existuje F ^ {n + 1}; SF ^ {n + 1}}$	n
${displaystyle alpha ^ {m} eta ^ {n}; F ^ {m} imes G ^ {n}}$	max (m, n)

Pravidla

Všechny instance predikátového dopisu mohou být nahrazeny jiným predikátovým písmenem stejného stupně, aniž by to ovlivnilo platnost. The pravidla jsou:

• Modus ponens;
• Nechť α a β jsou vzorce PFL, ve kterých ${displaystyle x_ {1}}$ neobjevuje se. Pak pokud ${displaystyle (alpha land Fx_ {1} ... x_ {n}) ightarrow eta}$ je tedy věta PFL ${displaystyle (alfa země existuje Fx_ {2} ... x_ {n}) ightarrow eta}$ je také PFL teorém.

Některé užitečné výsledky

Místo axiomatizace PFL navrhl Quine (1976) jako domněnkové axiomy následující domněnky.

• ${displaystyle existuje I}$

n-1 po sobě jdoucích iterací str obnovuje status quo ante:

• ${displaystyle F ^ {n} leftrightarrow p ^ {n-1} F ^ {n}}$

+ a ∃ zničit se navzájem:

Negace se distribuuje +, ∃, a str:

+ a str distribuuje přes spojení:

Identita má zajímavé důsledky:

• ${displaystyle IF ^ {n} ightarrow p ^ {n-2} existuje p + F ^ {n}}$

Quine také předpokládal pravidlo: Pokud ${displaystyle alpha}$ je teorém PFL, pak také jsou ${displaystyle palpha,}$ ${displaystyle + alpha,}$ a ${displaystyle lnot neexistuje lnot alfa}$.

Baconova práce

Bacon (1985) přebírá podmiňovací způsob, negace, Identita, Polstrování, a Hlavní, důležitý a Menší inverze jako primitivní a Oříznutí jak je definováno. Použitím terminologie a notace, která se poněkud liší od výše uvedeného, ​​Bacon (1985) uvádí dvě formulace PFL:

• A přirozený odpočet formulace ve stylu Frederick Fitch. Bacon tuto formulaci dokazuje zvuk a kompletní podrobně.
• Axiomatická formulace, kterou Bacon tvrdí, ale neprokazuje, ekvivalentní té předchozí. Některé z těchto axiomů jsou jednoduše Quinovy ​​dohady přepracované v Baconově notaci.

Bacon také:

• Diskutuje o vztahu PFL k termínová logika of Sommers (1982), a tvrdí, že přepracování PFL pomocí syntaxe navržené v Lockwoodově příloze k Sommersovi by mělo PFL usnadnit „čtení, používání a výuku“;
• Dotyky na skupinový teoretik struktura Inv a inv;
• Zmíní to sentenciální logika, monadická predikátová logika, modální logika S5 a logická logika (ne) permutovaná vztahy, jsou všechny fragmenty PFL.

Od logiky prvního řádu po PFL

Následující algoritmus je převzato z Quine (1976: 300-2). Vzhledem k tomu, uzavřený vzorec z logika prvního řádu, nejprve proveďte následující:

• Ke každému predikátnímu písmenu připojte číselný dolní index s uvedením jeho stupně;
• Přeložit vše univerzální kvantifikátory do existenční kvantifikátory a negace;
• Přeformátovat vše atomové vzorce formuláře X=y tak jako Ixy.

Na předchozí výsledek nyní použijte následující algoritmus:

1. Přeložte matice nejvíce hluboce vnořených kvantifikátorů do disjunktivní normální forma, skládající se z disjunktuje z spojky termínů, popřípadě popření atomových termínů. Výsledný podformulář obsahuje pouze negaci, konjunkci, disjunkci a existenciální kvantifikaci.

2. Distribuujte existenční kvantifikátory přes disjunkty v matici pomocí pravidlo průchodu (Quine 1982: 119):

${displaystyle existuje x [alpha (x) lor gama (x)] leftrightarrow (existuje xalpha (x) lor existuje xgamma (x)).}$

3. Nahradit spojení za kartézský součin odvoláním na skutečnost:

${displaystyle (F ^ {m} země G ^ {n}) leftrightarrow (F ^ {m} imes G ^ {n}) leftrightarrow (F ^ {m} existuje ^ {m} G ^ {n}); m < n.}$

4. Zřetězit seznamy argumentů všech atomových výrazů a přesunout zřetězený seznam zcela vpravo od podformulí.

5. Použití Inv a inv přesunout všechny instance kvantifikované proměnné (nazvat ji y) nalevo od seznamu argumentů.

6. Vyvolat S tolikrát, kolikrát je potřeba k vyloučení všech kromě poslední instance y. Odstranit y předponou podformulí jednou instancí ∃.

7. Opakujte (1) - (6), dokud nebudou odstraněny všechny kvantifikované proměnné. Eliminujte jakékoli disjunkce spadající do rozsahu kvantifikátoru vyvoláním ekvivalence:

${displaystyle (alpha lor eta lor ...) leftrightarrow lnot (lnot alfa land lnot eta land ...).}$

O reverzním překladu z PFL na logiku prvního řádu pojednává Quine (1976: 302-4).

Kanonický základ matematiky je axiomatická teorie množin, s logikou pozadí skládající se z logika prvního řádu s identita, s vesmír diskurzu skládající se výhradně ze sad. Existuje jeden predikativní dopis stupně 2, interpretováno jako stanovené členství. Překlad kanonického PFL axiomatická teorie množin ZFC není těžké, protože ne ZFC axiom vyžaduje více než 6 kvantifikovaných proměnných.^[2]

Viz také

• Algebraická logika

Poznámky pod čarou

Reference

• Bacon, John, 1985, „Úplnost logiky predikátu a funktoru,“ Journal of Symbolic Logic 50: 903–26.
• Paul Bernays 1959, „Uber eine naturliche Erweiterung des Relationenkalkuls“ v Heyting, A., ed., Konstruktivita v matematice. Severní Holandsko: 1–14.
• Kuhn, Steven T., 1983, "Axiomatizace logiky funktoru predikátu," Notre Dame Journal of Formal Logic 24: 233–41.
• Willard Quine 1976, "Algebraické logické a predikátové funktory" v Cesty paradoxu a jiné eseje, zvětšené vydání. Harvard Univ. Tisk: 283–307.
• Willard Quine, 1982. Metody logiky, 4. vyd. Harvard Univ. Lis. Chpt. 45.
• Sommers, Fred, 1982. Logika přirozeného jazyka. Oxford Univ. Lis.
• Alfred Tarski a Givant, Steven, 1987. Formalizace teorie množin bez proměnných. AMS.
• Jean Van Heijenoort, 1967. Od Frege po Gödel: Kniha zdrojů o matematické logice. Harvard Univ. Lis.

externí odkazy

• Úvod do logiky predikátu a funktoru (jedním kliknutím stáhnout, soubor PS) Mats Dahllöf (Ústav lingvistiky, Univerzita v Uppsale)