Andra ordningens logik

Andra ordningens logik i matematisk logik är ett formellt system som utökar första ordningens logik [1] med möjligheten att kvantifiera generalitet och existens inte bara över variabler, utan också över predikat och funktionella symboler. Andra ordningens logik är irreducerbar till första ordningens logik. I sin tur utökas den med logik och typteori av högre ordning .

Språk och syntax

Formella språk av andra ordningens logik är uppbyggda kring en uppsättning funktionssymboler och en uppsättning predikatsymboler . Varje funktion och predikatsymbol har en tillhörande aritet (antal argument). Ytterligare tecken används också ${\mathcal {F}}$ ${\mathcal {P}}$

Symboler för enskilda variabler, vanligtvis osv. ${\displaystyle \ x,y,z,x_{1},y_{1},z_{1},x_{2},y_{2},z_{2))$
Symboler för funktionella variabler etc. Varje funktionell variabel motsvarar något positivt tal - funktionens aritet. ${\displaystyle \ F,G,H,F_{1},G_{1},H_{1},F_{2},G_{2},H_{2))$
Symboler för predikatvariabler etc. Varje predikatvariabel motsvarar något positivt tal - predikatets aritet. ${\displaystyle \ P,R,S,P_{1},R_{1},S_{1},P_{2},R_{2},S_{2))$
Propositionskopplingar: , $\lor ,\land ,\neg ,\to$
Allmänhet och existenskvantifierare , $\för alla$ $\existerar$
Servicesymboler: parenteser och kommatecken.

De listade symbolerna, tillsammans med symbolerna , bildar alfabetet för första ordningens logik. Mer komplexa konstruktioner definieras induktivt . ${\mathcal {P}}$ ${\mathcal {F}}$

En term är en symbol för en individuell variabel, eller ett uttryck som har formen , där är en funktionell symbol för arity , och är termer, eller ett uttryck för formen , där är en funktionell variabel för arity , och är termer. $\f(t_{1},\ldots ,t_{n})$ $\f$ $\n$ $\ t_{1},\ldots ,t_{n}$ $\ F(t_{1},\ldots ,t_{n})$ $\F$ $\n$ $\ t_{1},\ldots ,t_{n}$
En atom har formen , där är predikatsymbolen för arity , och är termer eller , där är predikatvariabeln för arity , och är termer. $\p(t_{1},\ldots ,t_{n})$ $sid$ $\n$ $\ t_{1},\ldots ,t_{n}$ $\P(t_{1},\ldots ,t_{n})$ $P$ $\n$ $\ t_{1},\ldots ,t_{n}$
En formel är antingen en atom eller en av följande konstruktioner: , där är formler och är individuella, funktionella och predikatvariabler. (Konstruktioner är formler av andra och inte första ordningen ). $\neg A,(A_{1}\eller A_{2}),(A_{1}\land A_{2}),(A_{1}\till A_{2}),\forall xA,\exists xA ,\förall FA,\exists FA,\forall PA,\exists PA$ $\A,A_{1},A_{2}$ $\x,F,P$ $\forall FA,\exists FA,\forall PA,\exists PA$

Axiomatik och bevis för formler

Semantik

I klassisk logik ges tolkningen av andra ordningens logiska formler på en andra ordningens modell, som bestäms av följande data.

bas set , $\mathcal{D}$
Semantisk funktion som visas $\sigma$
- varje -är funktionssymbol från till -är funktion , $n$ $f$ ${\mathcal {F}}$ $n$ $\sigma (f):{\mathcal {D}}\times \ldots \times {\mathcal {D}}\högerpil {\mathcal {D}}$
- varje -är predikatsymbol från till -är relation . $n$ $sid$ ${\mathcal {P}}$ $n$ $\sigma (p)\subseteq {\mathcal {D}}\times \ldots \times {\mathcal {D}}$

Egenskaper

Till skillnad från första ordningens logik har andra ordningens logik inte egenskaperna fullständighet och kompakthet . Även i denna logik är påståendet om Löwenheim-Skolem-satsen felaktigt .

Anteckningar

↑ Shapiro (1991) och Hinman (2005) ger fullständiga introduktioner till ämnet, med fullständiga definitioner.

Litteratur

Henkin, L. (1950). "Fullständighet i teorin om typer". Journal of Symbolic Logic 15(2): 81-91.
Hinman, P. (2005). Grunderna i matematisk logik. A.K. Peters. ISBN 1-56881-262-0 .
Shapiro, S. (2000). Foundations without Foundationalism: A Case for Second-order Logic. Oxford University Press . ISBN 0-19-825029-0 .
Rossberg, M. (2004). "Första ordningens logik, andra ordningens logik och fullständighet". i V. Hendricks et al., eds.. Första ordningens logik revisited. Berlin: Logos Verlag.
Vaananen, J. (2001). "Andra ordningens logik och matematikens grunder". Bulletin of Symbolic Logic 7(4): 504-520.

Ordböcker och uppslagsverk	Britannica (online)

Logik

Filosofi • Semantik • Syntax • Historia

Logiska grupper

klassisk logik	Aristotelisk logik propositionell logik Första beställningslogik Andra ordningens logik högre ordningslogik
matematisk logik	mängdteori Modellteori Beräkningsbarhetsteori Bevisteori och konstruktiv matematik Linjär logik formellt system naturlig slutsats Sekvenskalkyl Algebra av logik Relevant logik Deontisk logik intuitionistisk logik Lambek kalkyl
Icke-klassisk logik	intuitionism rolig logik Substrukturell logik logik Beskrivningslogik Flervärdig logik Logisk syntes Bindande logik Temporal logik Modal logik ( Hybrid logik ) epistemisk logik
Filosofisk logik	Kritiskt tänkande informell logik deduktiva resonemang

Komponenter

Bortförande (logik)
Sannolikhet
påstående
Avdrag / Induktion / Traduktion
Verklighet
induktivt resonemang
slutledning
boolesk konstant
Sann
logiskt följa
Logisk form
Nödvändiga och tillräckliga förutsättningar
Beskrivning
Definition
Utbyte
Paket
Kontrovers ( Antinomy )
Syntetisk bedömning / Analytisk bedömning
Länk

Lista över booleska symboler