Lògica de segon ordre

Una lògica de segon ordre és una extensió d'una lògica matemàtica de primer ordre en la qual s'afegeixen variables per propietats i quantificadors que operen sobre aquestes variables.^[1] Així s'expandeix el poder expressiu del llenguatge sense haver d'afegir nous símbols lògics.^[1]

Molts sistemes matemàtics no poden ser unívocament caracteritzats per un llenguatge formal de primer ordre, com ara l'aritmètica de Peano o la teoria dels grups lliures de torsió. En aquests casos els llengüatges de primer ordre formalitzen una part d'aquestes teories però hi ha propietats matemàtiques d'aquestes teories que no poden ser expressades amb el sistema d'una lògica de primer ordre.

La necessitat de les lògiques de segon ordre es reflecteixen en l'axioma d'inducció de l'aritmètica tal com Giuseppe Peano la va formalitzar:^[2]

Per qualsevol conjunt X de nombres enters, si ${\displaystyle 0\in X}$ i a més ${\displaystyle n\in X\Rightarrow n+1\in X}$, llavors es té que ${\displaystyle X=\mathbb {N} ''}$

L'expressió "Per qualsevol conjunt" requereix un llengüatge on els quantificadors puguin afectar les variables, per exemple si el predicat ${\displaystyle a\in X}$ es representa mitjançant el símbol ${\displaystyle {\tilde {X}}(a)}$ l'axioma d'inducció es pot representar en símbols com a:

${\displaystyle \forall {\tilde {X}}\ (({\tilde {X}}(0)\land \forall x({\tilde {X}}(x)\to {\tilde {X}}(x+1))\to \forall y{\tilde {X}}(y))}$

A més, una lògica de segon ordre també pot quantificar sobre propietats. Gràcies a això pot expressar, per exemple, que tot individu o té una propietat o no la té:

${\displaystyle \forall P\,\forall x\,(Px\lor \neg Px)}$

O el principi d'identitat dels indiscernibles:^[3]

${\displaystyle \forall P\,\forall x\,\forall y\,{\Big (}(Px\Leftrightarrow Py)\to (x=y){\Big )}}$

No obstant això, el que es guanya en poder expressiu es perd en metateoria. Hi ha propietats metateòriques generalment considerades desitjables que les lògiques de segon ordre no tenen i les lògiques de primer ordre sí que tenen. Per exemple, les lògiques de segon ordre (amb semàntiques estàndard) són incompletes.^[4] Vol dir que no hi pot haver cap sistema deductiu finit a partir del qual es puguin demostrar totes les veritats lògiques expressables en el llenguatge.^[4] Això és: el conjunt de les veritats del sistema és més gran que el conjunt de les veritats demostrables en el sistema. Això es deu al fet que les lògiques de segon ordre tenen el poder expressiu suficient per ser afectades pels teoremes d'incompletesa de Gödel. De fet va ser el mateix Gödel qui va demostrar que en un llenguatge de segon ordre el conjunt de veritats no és recursivament enumerable, i per tant, no hi ha cap procediment per descobrir si una proposició és vàlida en cada model possible d'aquest llenguatge de segon ordre.

La lògica de segon ordre té una expressivitat més gran de la de primer ordre, això permet axiomatitzar sistemes matemàtics més complexos. És a dir, hi ha proposicions no formalitzables exactament utilitzant el formalisme de la lògica de primer ordre però si poden ser formalitzats amb lògica de segon ordre. Això constitueix un avantatge. Tanmateix l'ús de lògiques de segon ordre ocasiona algunes dificultats:

• El teorema de compacitat, que afirma que un conjunt de proposicions lògiques d'una lògica de primer ordre és satisfactible si i només si qualsevol conjunt finit d'aquestes és satisfactible, no és vàlid per una lògica de segon ordre.
• El teorema de Löwenheim-Skolem que afirma que una lògica de primer ordre amb una quantitat finita de signes diferents admet un model numerable no és vàlid per una lògica de segon ordre.

El fet que aquests dos teoremes molt útils de la lògica de primer ordre no es puguin generalitzar a segon ordre, és a dir no admeten generalització a segon ordre, dificulten certes aplicaicons matemàtiques de la lògica de segon ordre. Per aquesta raó s'han buscat altres generalitzacions més útils de la lògica de primer ordre.

Existeixen diversos tipus de lògiques de segon ordre. Això significa que hi ha diverses maneres d'estendre una lògica de primer ordre per formar una lògica de segon ordre. Aquestes maneres d'estendre la lògica de primer ordre difereixen en el tipus de variables addicionals que introdueixen. Entre les lògiques de segon ordre més estudiades es poden trobar:

• La lògica de segon ordre monàdica (LSOM), en la que s'afegeixen només variables per subconjunts dintre d'un cert domini.
• La lògica de segon ordre completa (LSOC), en la que s'introdueixen tots els tipus possibles de variables i els quantificadors poden lligar a qualsevol tipus de variables.

Una lògica de segon ordre inclou quantificadors de diferents tipus (${\displaystyle \exists _{1},\forall _{1},\exists _{2},\forall _{2}}$), a més de quantificadors de primer ordre que requereixen variables com les de la lògica de primer ordre, existeixen quantificadors per a subconjunts i propietats, que no poden aparéixer en una lògica de primer ordre. Igualment es pot construir un llenguatge de segon ordre específic. La lògica de segon ordre conté fórmules de primer ordre i fórmules de segon ordre. Una fórmula de lògica de segon ordre s'anomena fórmula de primer ordre (i es considera un element del conjunt ${\displaystyle \Sigma _{0}^{1}}$ o del conjunt ${\displaystyle \Pi _{0}^{1}}$) si tots els quantificadors quantifiquen només variables de primer ordre (podent contenir altres variables de segon ordre lliures). Una fórmula de segon ordre existencial és una fórmula del conjunt ${\displaystyle \Sigma _{1}^{1}}$ que conté a més alguns quantificadors existencials sobre variables de segon ordre, és a dir, ${\displaystyle \exists _{2}R_{0}\ldots \exists _{2}R_{m}\phi }$, on ${\displaystyle \phi }$ designa una fórmula de primer ordre. El conjunt de fórmules existencials de segon ordre que conté només existencials ${\displaystyle \exists _{2}}$ es designa com ${\displaystyle \Sigma _{1}^{1}}$ o fins i tot ∃SO. Les fórmules de ${\displaystyle \Pi _{1}^{1}}$ es defineixen dualment, són el conjunt de fórmules de segon ordre que contenen només quantificadors ${\displaystyle \forall _{2}}$. Poden formar-se conjunts més complicats definits recursivament per qualsevol k > 0, com ${\displaystyle \Sigma _{k+1}^{1}}$ format per fórmules de la forma ${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$, on ${\displaystyle \phi }$ és una fórmula del tipus ${\displaystyle \Pi _{k}^{1}}$.

• Hilbert, David; and Ackermann, Wilhelm (1950); Principles of Mathematical Logic, Chelsea (English translation of Grundzüge der theoretischen Logik, 1928 German first edition)
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; and Thomas, Wolfgang (1994); Mathematical Logic, Undergraduate Texts in Mathematics, Berlin, DE/New York, NY: Springer-Verlag, Second Edition, ISBN 978-0-387-94258-2