Andra ordningens logik

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2017-12) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Andra ordningens logik är en utvidgning av första ordningens logik inom den matematiska logiken. Där första ordningens logik bara tillåter "diskreta" individvariabler och egenskapsvariabler kan andra ordningens logik även använda variabler för hela uppsättningar av individuella företeelser. Första ordningens logik är själv en utvidgning av satslogiken och andra ordningens logik utvidgas i sin tur av högre ordningens logik och av mängdläran.

Skillnaden mellan första och andra ordningens logik (h.e. FOL respektive AOL) kan illustreras på följande sätt. FOL och AOL hör till predikatlogiken och skall skiljas ifrån satslogiken. Satslogiken talar bara om satser och kan till exempel uttrycka bivalensprincipen: ${\displaystyle x\lor \lnot x}$ d.v.s. "antingen gäller x, eller så gör den det inte", där "x" representerar en valfri sats. FOL däremot pratar inte speciellt om satser utan om alla slags enskilda företeelser och deras predikat och kan därför till exempel säga: ${\displaystyle \forall x(P(x)\lor \lnot P(x))}$ d.v.s. "för varje individuell företeelse "x", gäller att antingen har x egenskapen "P" eller så har den det inte. Som synes förutsätts inte generalitet i predikatslogiken, i stället har man infört de så kallade kvantifikatorerna ${\displaystyle \forall }$ och ${\displaystyle \exists }$, d.v.s. "för alla" respektive "för minst en". Inom AOL kan man dessutom prata om mängder och deras element. För detta ändamål inför man ett nytt konnektiv: ${\displaystyle \in }$ som utläses "ingår i" eller "är ett element av". till exempel kan man säga: ${\displaystyle \forall P\land \forall x(x\in P\lor x\not \in P)}$ d.v.s. "för varje uppsättning företeelser "P" och varje individuell företeelse "x", gäller att antingen ingår x i P eller så gör den det inte.

Tillämpning och kritik

Ett ytterligare steg av logisk komplexitet är mängdläran, ett område inom matematiken där AOL har haft en avgörande tillämpning. Mängdläran studerar enbart mängder, d.v.s. utgår ifrån att alla element av en mängd själva är mängder. Inom mängdläran vill man formulera hela matematiken som AOL. Den spontana versionen av detta gav upphov till Russells paradox eftersom den tillät existensen av en mängd som utgör mängden av alla mängder som inte är element av sig själva, vilket är omöjligt. När AOL idag appliceras på matematiken (främst i form av ZFC-teorin) görs det utifrån en rad axiom som bl.a. inskränker möjligheterna för vilka mängder som får bildas.

Den starka uttrycksfullheten hos olika former av AOL när den appliceras på ändliga strukturer har gjort att den är nära förknippad med komplexitetsteori inom datavetenskapen. Komplexitetsteori går ut på att klassificera typer av beräkningsproblem utifrån hur bra olika algoritmer är på att behandla dem. Problemen delas upp efter hur avancerad form av andra ordningens logik man behöver för att uttrycka och lösa dem.

Flera logiker har varit kritiska till AOL och bland dem har W. V. Quine varit särskilt utmärkande. Quine pekade på att i predikatlogiska satser som P(x), används "x" som en variabel eller ett namn som pekar ut ett föremål och därmed kan kvantifieras, som i "för alla saker gäller att...", men P:t används som en förkortning för en ofullständig sats, inte som ett namn för något (varken ett konkret föremål eller en abstrakt egenskap). Exempelvis kan vi låta P:et betyda "...är rött". Det är enligt Quine meningslöst att försöka tänka sig en kvantifikation av någonting sådant, i stil med "för alla är röd gäller att".

Quine sa med en känd formulering att högre ordningens logik är förklädd mängdlära, och att AOL inte är logik över huvud taget.