Hilbertův systém - Hilbert system

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek potřebuje pozornost odborníka na matematiku. Viz diskusní stránka pro detaily. Matematika WikiProject může pomoci s náborem odborníka. (Březen 2011) Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Říjen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematická fyzika, Hilbertův systém je zřídka používaný termín pro fyzický systém popsaný a C * -algebra.

v logika, zvláště matematická logika, a Hilbertův systém, někdy nazývané Hilbertův počet, Hilbertův deduktivní systém nebo Systém Hilbert – Ackermann, je typ systému formální odpočet přičítáno Gottlob Frege^[1] a David Hilbert. Tyto deduktivní systémy jsou nejčastěji studovány pro logika prvního řádu, ale jsou zajímavé i pro jiné logiky.

Většina variant Hilbertových systémů má charakteristický směr ve způsobu, jakým vyvažují a kompromis mezi logické axiomy a pravidla odvození.^[1] Systémy Hilbert lze charakterizovat výběrem velkého počtu schémata logických axiomů a malá sada pravidla odvození. Systémy přirozený odpočet zaujměte opačný směr, včetně mnoha pravidel pro odpočet, ale jen velmi málo nebo žádná schémata axiomu. Nejčastěji studované Hilbertovy systémy mají buď pouze jedno pravidlo závěru - modus ponens, pro výroková logika - nebo dva - s zobecnění, zvládnout predikátové logiky, stejně - a několik nekonečných schémat axiomu. Hilbertovy systémy pro výrokové modální logika, někdy nazývané Hilbert-Lewisovy systémy, jsou obecně axiomatizovány dvěma dalšími pravidly, pravidlo nezbytnosti a jednotná substituce pravidlo.

Charakteristickým rysem mnoha variant systémů Hilbert je, že kontext se nezmění v žádném z jejich pravidel odvození, zatímco v obou přirozený odpočet a následný počet obsahovat některá pravidla měnící kontext. Pokud tedy někoho zajímá pouze odvozitelnost tautologie „Žádné hypotetické soudy, pak lze Hilbertův systém formalizovat tak, že jeho pravidla odvození obsahují pouze rozsudky poměrně jednoduché formy. Totéž nelze provést s dalšími dvěma systémy odpočtů:^{[Citace je zapotřebí ]} jelikož se kontext mění v některých jejich pravidlech závěrů, nelze je formalizovat, aby bylo možné se vyhnout hypotetickým úsudkům - a to ani v případě, že je chceme použít pouze k prokázání odvoditelnosti tautologií.

Formální odpočty

V dedukčním systému ve stylu Hilberta, a formální odpočet je konečná posloupnost vzorců, ve kterých je každý vzorec buď axiomem, nebo je získán z předchozích vzorců pravidlem odvození. Tyto formální dedukce mají odrážet důkazy v přirozeném jazyce, i když jsou mnohem podrobnější.

Předpokládat ${ displaystyle Gamma}$ je sada vzorců, považovaná za hypotézy. Například, ${ displaystyle Gamma}$ může být množina axiomů pro teorie skupin nebo teorie množin. Zápis ${ displaystyle Gamma vdash phi}$ znamená, že existuje odpočet, který končí ${ displaystyle phi}$ pouze jako axiomy logické axiomy a prvky ${ displaystyle Gamma}$. Neformálně tedy ${ displaystyle Gamma vdash phi}$ znamená, že ${ displaystyle phi}$ je prokazatelné za předpokladu, že všechny vzorce v ${ displaystyle Gamma}$.

Dedukční systémy ve stylu Hilberta se vyznačují použitím mnoha schémat logické axiomy. An schéma axiomu je nekonečná sada axiomů získaná dosazením všech vzorců nějaké formy do konkrétního vzoru. Sada logických axiomů zahrnuje nejen axiomy generované z tohoto vzoru, ale také jakoukoli generalizaci jednoho z těchto axiomů. Zobecnění vzorce se získá předponou nula nebo více univerzálních kvantifikátorů ve vzorci; například ${ displaystyle forall y ( forall xPxy to Pty)}$ je zobecněním ${ displaystyle forall xPxy to Pty}$.

Logické axiomy

Existuje několik variant axiomatizací predikátové logiky, protože pro každou logiku existuje svoboda ve výběru axiomů a pravidel, která tuto logiku charakterizují. Popíšeme zde Hilbertovu soustavu s devíti axiomy a pouze pravidlem modus ponens, kterému říkáme axiomatizace jednoho pravidla a která popisuje klasickou rovnicovou logiku. Pro tuto logiku, kde vzorce používají pouze spojovací prostředky, se zabýváme minimálním jazykem ${ displaystyle lnot}$ a ${ displaystyle to}$ a pouze kvantifikátor ${ displaystyle forall}$. Později si ukážeme, jak lze systém rozšířit tak, aby zahrnoval další logické spojky, jako například ${ displaystyle land}$ a ${ displaystyle lor}$, aniž by došlo ke zvětšení třídy odvoditelných vzorců.

První čtyři schémata logických axiomů umožňují (společně s modus ponens) manipulaci s logickými spojkami.

P1. ${ displaystyle phi to phi}$

P2. ${ Displaystyle phi to left ( psi to phi right)}$

P3. ${ Displaystyle left ( phi to left ( psi rightarrow xi right) right) to left ( left ( phi to psi right) to left ( phi do xi doprava) doprava)}$

P4. ${ Displaystyle left ( lnot phi to lnot psi right) doleva ( psi to phi right)}$

Axiom P1 je nadbytečný, jak vyplývá z P3, P2 a modus ponens (viz důkaz ). Tyto axiomy popisují klasická výroková logika; bez axiomu P4 dostaneme pozitivní implikační logika. Minimální logika je dosaženo buď přidáním axiomu P4m, nebo definováním ${ displaystyle lnot phi}$ tak jako ${ displaystyle phi to bot}$.

P4m. ${ Displaystyle left ( phi to psi right) doleva ( left ( phi to lnot psi right) to lnot phi right)}$

Intuicionistická logika je dosaženo přidáním axiomů P4i a P5i k pozitivní implikační logice nebo přidáním axiomu P5i k minimální logice. P4i i P5i jsou věty klasické výrokové logiky.

P4i. ${ Displaystyle left ( phi to lnot phi right) to lnot phi}$

P5i. ${ Displaystyle lnot phi to left ( phi to psi right)}$

Všimněte si, že se jedná o schémata axiomu, která představují nekonečně mnoho konkrétních případů axiomů. Například P1 může představovat konkrétní instanci axiomu ${ displaystyle p to p}$, nebo to může představovat ${ Displaystyle left (p to q right) to left (p to q right)}$: ${ displaystyle phi}$ je místo, kde lze umístit jakýkoli vzorec. Proměnná, jako je tato, která přesahuje vzorce, se nazývá schematická proměnná.

S druhým pravidlem jednotná substituce (USA) můžeme každé z těchto schémat axiomu změnit na jeden axiom a nahradit každou schematickou proměnnou nějakou výrokovou proměnnou, která není uvedena v žádném axiomu, abychom získali to, co nazýváme substituční axiomatizací. Obě formalizace mají proměnné, ale tam, kde má axiomatizace s jedním pravidlem schematické proměnné, které jsou mimo jazyk logiky, používá substituční axiomatizace výrokové proměnné, které dělají stejnou práci tím, že vyjadřují myšlenku proměnné v rozmezí vzorců pomocí pravidla, které používá substituci.

NÁS. Nechat ${ displaystyle phi (p)}$ být vzorec s jedním nebo více výroky proměnné ${ displaystyle p}$a nechte ${ displaystyle psi}$ být další vzorec. Pak od ${ displaystyle phi (p)}$, vyvodit ${ displaystyle phi ( psi)}$.^{[pochybný – diskutovat]}

Další tři schémata logické axiomy poskytují způsoby přidání, manipulace a odebrání univerzálních kvantifikátorů.

Q5. ${ displaystyle forall x left ( phi right) to phi [x: = t]}$ kde t může být nahrazen X v ${ displaystyle , ! phi}$

Q6. ${ Displaystyle forall x left ( phi to psi right) to left ( forall x left ( phi right) to forall x left ( psi right) right) }$

Q7. ${ Displaystyle phi to forall x left ( phi right)}$ kde X není zdarma v ${ displaystyle phi}$.

Tato tři další pravidla rozšiřují výrokový systém na axiomatizaci klasická predikátová logika. Podobně tato tři pravidla rozšiřují systém intuitivní výrokové logiky (s P1-3 a P4i a P5i) na intuicionistická predikátová logika.

Univerzální kvantifikace je často dána alternativní axiomatizaci pomocí zvláštního pravidla generalizace (viz část Metatheorems), v takovém případě jsou pravidla Q6 a Q7 nadbytečná.^{[pochybný – diskutovat]}

Konečná schémata axiomu jsou nutná pro práci s vzorci obsahujícími symbol rovnosti.

I8. ${ displaystyle x = x}$ pro každou proměnnou X.

I9. ${ displaystyle left (x = y right) to left ( phi [z: = x] to phi [z: = y] right)}$

Konzervativní rozšíření

Je běžné zahrnout do dedukčního systému ve stylu Hilberta pouze axiomy pro implikaci a negaci. Vzhledem k těmto axiómům je možné tvořit konzervativní rozšíření z teorém o dedukci které umožňují použití dalších spojovacích prostředků. Tato rozšíření se nazývají konzervativní, protože pokud je vzorec φ zahrnující nové spojky přepsán jako a logicky ekvivalentní vzorec θ zahrnující pouze negaci, implikaci a univerzální kvantifikaci, pak φ je derivovatelný v rozšířeném systému právě tehdy, je-li θ derivovatelný v původním systému. Po úplném prodloužení bude systém ve stylu Hilberta více připomínat systém přirozený odpočet.

Existenční kvantifikace

• Úvod

${ displaystyle forall x ( phi to existuje y ( phi [x: = y]))}$

• Odstranění

${ displaystyle forall x ( phi to psi) to existuje x ( phi) to psi}$ kde ${ displaystyle x}$ není volná proměnná z ${ displaystyle psi}$.

Spojení a disjunkce

• Úvod a eliminace spojení

úvod: ${ displaystyle alpha to beta to alpha land beta}$

eliminace zbývá: ${ displaystyle alpha klín beta na alfa}$

právo na eliminaci: ${ displaystyle alpha klín beta do beta}$

• Zavedení a vyloučení disjunkce

úvod vlevo: ${ displaystyle alpha to alpha vee beta}$

úvodní právo: ${ displaystyle beta až alfa vee beta}$

odstranění: ${ Displaystyle ( alpha to gamma) to ( beta to gamma) to alpha vee beta to gamma}$

Metatheory

Protože systémy ve stylu Hilberta mají velmi málo pravidel pro dedukci, je běžné to dokázat metateorémy které ukazují, že další pravidla pro odpočet nepřidávají žádnou deduktivní sílu v tom smyslu, že odpočet pomocí nových pravidel pro odpočet lze převést na odpočet pouze pomocí původních pravidel pro odpočet.

Některé běžné metateorémy této formy jsou:

• The teorém o dedukci: ${ displaystyle gama; phi vdash psi}$ kdyby a jen kdyby ${ Displaystyle Gamma vdash phi až psi}$.
• ${ displaystyle Gamma vdash phi leftrightarrow psi}$ kdyby a jen kdyby ${ Displaystyle Gamma vdash phi až psi}$ a ${ displaystyle Gamma vdash psi to phi}$.
• Contraposition: If ${ displaystyle gama; phi vdash psi}$ pak ${ Displaystyle Gamma; lnot psi vdash lnot phi}$.
• Zobecnění: Pokud ${ displaystyle Gamma vdash phi}$ a X nevyskytuje se zdarma v žádném vzorci ${ displaystyle Gamma}$ pak ${ displaystyle Gamma vdash pro všechny x phi}$.

Některé užitečné věty a jejich důkazy

Následuje několik vět ve výrokové logice spolu s jejich důkazy (nebo odkazy na tyto důkazy v jiných článcích). Všimněte si, že protože (P1) lze prokázat pomocí jiných axiomů, ve skutečnosti (P2), (P3) a (P4) stačí k prokázání všech těchto vět.

(HS1) ${ Displaystyle (q až r) až ((p až q) až (p až r))}$ - Hypotetický úsudek viz důkaz.

(L1) ${ Displaystyle p to ((p až q) až q)}$ - důkaz:

(1) ${ Displaystyle ((p až q) až (p až q)) až (((p až q) až p) až ((p až q) až q))}$ (instance (P3))

(2) ${ Displaystyle (p až q) až (p až q)}$ (instance (P1))

(3) ${ Displaystyle ((p až q) až p) až ((p až q) až q)}$ (z (2) a (1) o modus ponens )

(4) ${ Displaystyle (((p to q) to p) to ((p to q) to q)) to ((p to ((p to q) to p)) to (p to ((p to q) to q)))}$ (instance (HS1))

(5) ${ Displaystyle (p až ((p až q) až p)) až (p až ((p až q) až q))}$ (z (3) a (4) od Modus Ponens)

(6) ${ Displaystyle p to ((p až q) až p)}$ (instance (P2))

(7) ${ Displaystyle p to ((p až q) až q)}$ (z (6) a (5) od Modus Ponens)

Následující dvě věty jsou známé společně jako Dvojitá negace:

(DN1)${ displaystyle neg neg p to p}$

(DN2) ${ Displaystyle p to neg neg p}$

Vidět důkazy.

(L2) ${ Displaystyle (p až (q až r)) až (q až (p až r))}$ - pro tento důkaz používáme metodu hypotetický úsudek metateorem jako zkratka pro několik zkušebních kroků:

(1) ${ Displaystyle (p až (q až r)) až ((p až q) až (p až r))}$ (instance (P3))

(2) ${ Displaystyle ((p až q) až (p až r)) až ((q až (p až q)) až (q až (p až r)))}$ (instance (HS1))

(3) ${ Displaystyle (p až (q až r)) až ((q až (p až q)) až (q až (p až r)))}$ (z (1) a (2) pomocí metatheorému hypotetického sylogismu)

(4) ${ Displaystyle ((p až (q až r)) až ((q až (p až q)) až (q až (p až r)))) až (((p to (q to r)) to (q to (p to q))) to ((p to (q to r)) to (q to (p to r)) ))}$ (instance (P3))

(5) ${ Displaystyle ((p až (q až r)) až (q až (p až q))) až ((p až (q až r)) (q až ( p až r)))}$ (z (3) a (4) pomocí modus ponens)

(6) ${ displaystyle q to (p až q)}$ (instance (P2))

(7) ${ Displaystyle (q až (p až q)) až ((p až (q až r)) až (q až (p až q)))}$ (instance (P2))

(8) ${ Displaystyle (p až (q až r)) až (q až (p až q))}$ (od (6) a (7) pomocí modus ponens)

(9) ${ Displaystyle (p až (q až r)) až (q až (p až r))}$ (z (8) a (5) pomocí modus ponens)

(HS2) ${ Displaystyle (p až q) až ((q až r) až (p až r))}$ - alternativní forma hypotetický úsudek. důkaz:

(1) ${ Displaystyle (q až r) až ((p až q) až (p až r))}$ (instance (HS1))

(2) ${ Displaystyle ((q až r) až ((p až q) až (p až r))) až ((p až q) až ((q až r) až ( p až r)))}$ (instance (L2))

(3) ${ Displaystyle (p až q) až ((q až r) až (p až r))}$ (z (1) a (2) od Modus Ponens)

(TR1) ${ Displaystyle (p až q) až ( neg q až neg p)}$ - Transpozice, viz důkaz (druhý směr transpozice je (P4)).

(TR2) ${ Displaystyle ( neg p až q) až ( neg q až p)}$ - jiná forma provedení; důkaz:

(1) ${ Displaystyle ( neg p až q) to ( neg q až neg neg p)}$ (instance (TR1))

(2) ${ displaystyle neg neg p to p}$ (instance (DN1))

(3) ${ Displaystyle ( neg neg p až p) až (( neg q až neg neg p) až ( neg q až p))}$ (instance (HS1))

(4) ${ Displaystyle ( neg q to neg neg p) to ( neg q to p)}$ (z (2) a (3) od Modus Ponens)

(5) ${ Displaystyle ( neg p až q) až ( neg q až p)}$ (z (1) a (4) pomocí metatheorem hypotetického úsudku)

(L3) ${ displaystyle ( neg p až p) až p}$ - důkaz:

(1) ${ Displaystyle neg p to ( neg neg (q to q) to neg p)}$ (instance (P2))

(2) ${ Displaystyle ( neg neg (q to q) to neg p) to (p to neg (q to q))}$ (instance (P4))

(3) ${ Displaystyle neg p to (p to neg (q to q))}$ (z (1) a (2) pomocí metatheorému hypotetického sylogismu)

(4) ${ Displaystyle ( neg p to (p to neg (q to q))) to (( neg p to p) to ( neg p to neg (q to q) ))}$ (instance (P3))

(5) ${ Displaystyle ( neg p až p) až ( neg p až neg (q až q))}$ (z (3) a (4) pomocí režimů ponens)

(6) ${ Displaystyle ( neg p až neg (q až q)) až ((q až q) až p)}$ (instance (P4))

(7) ${ Displaystyle ( neg p až p) až ((q až q) až p)}$ (z (5) a (6) pomocí hypotetického úsudku metatheorem)

(8) ${ displaystyle q až q}$ (instance (P1))

(9) ${ Displaystyle (q až q) až ((((q až q) až p) až p)}$ (instance (L1))

(10) ${ displaystyle ((q až q) až p) až p}$ (od (8) a (9) pomocí režimů ponens)

(11) ${ displaystyle ( neg p až p) až p}$ (z (7) a (10) s použitím hypotetického úsudku metatheorem)

Alternativní axiomatizace

Axiom 3 výše je připočítán k Łukasiewicz.^[2] Původní systém Frege měl axiomy P2 a P3, ale čtyři další axiomy místo axiomu P4 (viz Fregeův výrokový počet ).Russell a Whitehead také navrhl systém s pěti výrokovými axiomy.

Další spojení

Axiomy P1, P2 a P3, s modifikací ponens (formalizace) intuicionistická výroková logika ), odpovídají kombinační logika základní kombinátory Já, K. a S s operátorem aplikace. Důkazy v Hilbertově systému pak odpovídají kombinačním termínům v kombinační logice. Viz také Curry – Howardova korespondence.

Viz také

• Seznam Hilbertových systémů
• Přirozený odpočet

Poznámky

Reference

• Curry, Haskell B .; Robert Feys (1958). Combinatory Logic Vol. Já. 1. Amsterdam: Severní Holandsko.
• Monk, J. Donald (1976). Matematická logika. Postgraduální texty z matematiky. Berlín, New York: Springer-Verlag. ISBN  978-0-387-90170-1.
• Ruzsa, Imre; Máté, András (1997). Bevezetés a modern logikába (v maďarštině). Budapešť: Osiris Kiadó.
• Tarski, Alfred (1990). Bizonyítás és igazság (v maďarštině). Budapešť: Gondolat. Je to maďarský překlad Alfred Tarski vybrané příspěvky na sémantická teorie pravdy.
• David Hilbert (1927) „Základy matematiky“, překládali Stephan Bauer-Menglerberg a Dagfinn Føllesdal (str. 464–479). v:
  • van Heijenoort, Jean (1967). Od Frege po Gödela: Kniha pramenů v matematické logice, 1879–1931 (3. tisk 1976 ed.). Cambridge MA: Harvard University Press. ISBN  0-674-32449-8.
  • Hilbertův rok 1927, založený na dřívější přednášce „základy“ z roku 1925 (str. 367–392), představuje jeho 17 axiomů - axiomy implikace # 1-4, axiomy o & a V # 5-10, axiomy negace # 11- 12, jeho logický ε-axiom # 13, axiomy rovnosti # 14-15 a axiomy čísla # 16-17 - spolu s dalšími nezbytnými prvky jeho formalistické „teorie důkazu“ - např. indukční axiomy, rekurzní axiomy atd .; nabízí také temperamentní obranu proti L.E.J. Brouwerův intuicionismus. Viz také komentáře a vyvrácení Hermanna Weyla (1927) (str. 480–484), dodatek Paula Bernaye (1927) k Hilbertově přednášce (str. 485–489) a odpověď Luitzena Egberta Jana Brouwera (1927) (str. 490–495)
• Kleene, Stephen Cole (1952). Úvod do matematiky (10. dojem s opravami z roku 1971 vyd.). Amsterdam NY: North Holland Publishing Company. ISBN  0-7204-2103-9.
  • Viz zejména Kapitola IV Formální systém (str. 69–85), kde Kleene představuje podkapitoly §16 Formální symboly, § 17 Pravidla formování, § 18 Volné a vázané proměnné (včetně substituce), § 19 Pravidla transformace (např. Modus ponens) - a z nich představuje 21 „postulátů“ - 18 axiomů a 3 vztahy „okamžitých následků“ rozdělených takto: Postuláty pro propostionální počet # 1-8, Další postuláty pro predikátový počet # 9-12 a Další postuláty pro teorie čísel # 13-21.

externí odkazy

• Gaifman, Haim. „Dedukční systém typu Hilbert pro sentenciální logiku, úplnost a kompaktnost“ (pdf).
• Farmář, W. M. „Propoziční logika“ (pdf). Popisuje (mimo jiné) část dedukčního systému ve stylu Hilberta (omezeno na výrokový kalkul ).