Avgränsad kvantifierare

Den här artikeln handlar om gränsad kvantifiering i matematisk logik. För avgränsad kvantifiering i typteori, se Avgränsad kvantifiering .

I studiet av formella teorier i matematisk logik ingår ofta begränsade kvantifierare (aka begränsade kvantifierare ) i ett formellt språk förutom standardkvantifierarna "∀" och "∃". Begränsade kvantifierare skiljer sig från "∀" och "∃" genom att begränsade kvantifierare begränsar intervallet för den kvantifierade variabeln. Studiet av bounded quantifiers motiveras av det faktum att avgöra om en mening med endast bounded quantifiers är sann är ofta inte lika svårt som att avgöra om en godtycklig mening är sann.

Exempel

Exempel på avgränsade kvantifierare i samband med verklig analys inkluderar:

• $\forall x>0$ - för alla x där x är större än 0
• $\exists y<0$ - det finns ett y där y är mindre än 0
• $\forall x\in \mathbb {R}$ - för alla x där x är ett reellt tal
• ${\displaystyle \forall x>0\quad \exists y<0\quad (x=y^{2})} -$ varje positivt tal är kvadraten på ett negativt tal

Begränsade kvantifierare i aritmetik

Antag att L är språket för Peano-aritmetiken (språket för andra ordningens aritmetik eller aritmetik i alla finita typer skulle också fungera). Det finns två typer av avgränsade kvantifierare: $\forall n<t$ och $\exists n<t$ . Dessa kvantifierare binder talvariabeln n och innehåller en numerisk term t som kanske inte nämner n men som kan ha andra fria variabler. ("Numeriska termer" betyder här termer som "1 + 1", "2", "2 × 3", " m + 3", etc.)

Dessa kvantifierare definieras av följande regler ( $\phi$ anger formler):

$\exists n<t\,\phi \Leftrightarrow \exists n(n<t\land \phi )$

$\forall n<t\,\phi \Leftrightarrow \forall n(n<t\rightarrow \phi )$

Det finns flera motiv för dessa kvantifierare.

• I tillämpningar av språket till rekursionsteori , såsom den aritmetiska hierarkin , tillför begränsade kvantifierare ingen komplexitet. Om $\phi$ är ett avgörbart predikat då $\exists n<t\,\phi$ och $\forall n<t\,\phi$ är också avgörbara.
• I tillämpningar för studiet av Peano-aritmetik kan det faktum att en viss mängd kan definieras med endast gränsade kvantifierare få konsekvenser för mängden beräkningsbarhet. Till exempel finns det en definition av primalitet med endast avgränsade kvantifierare: ett tal n är primtal om och endast om det inte finns två tal som är strikt mindre än n vars produkt är n . Det finns ingen kvantifieringsfri definition av primalitet i språket $\langle 0,1,+,\times ,<,=\rangle$ . Det faktum att det finns en avgränsad kvantifieringsformel som definierar primalitet visar att primaliteten för varje tal kan bestämmas beräkningsbart.

I allmänhet kan en relation på naturliga tal definieras av en begränsad formel om och endast om den är beräkningsbar i linjär-tidshierarkin, som definieras på samma sätt som polynomhierarkin , men med linjära tidsgränser istället för polynom. Följaktligen är alla predikat som kan definieras av en begränsad formel Kalmár elementära , kontextkänsliga och primitiva rekursiva .

I den aritmetiska hierarkin kallas en aritmetisk formel som endast innehåller avgränsade kvantifierare ${\displaystyle \Sigma _{0}^{0}} ,$ Δ $\displaystyle \Delta _{0}^{0}}$ och ${ \displaystyle \Pi _{0}^{0}}$ . Den övre skriften 0 utelämnas ibland.

Begränsade kvantifierare i mängdlära

Antag att L är språket $\langle \in ,\ldots ,=\rangle$ i Zermelo–Fraenkels mängdteorin , där ellipsen kan ersättas av termbildande operationer som en symbol för powerset- drift. Det finns två avgränsade kvantifierare: $\forall x\in t$ och $\exists x\in t$ . Dessa kvantifierare binder mängdvariabeln x och innehåller en term t som kanske inte nämner x men som kan ha andra fria variabler.

Semantiken för dessa kvantifierare bestäms av följande regler:

$\exists x\in t\ (\phi )\Vänsterhögerpil \exists x(x\in t\land \phi )$

$\forall x\in t\ (\phi )\Leftrightarrow \forall x(x\in t\rightarrow \phi )$

En ZF-formel som endast innehåller avgränsade kvantifierare kallas $\Sigma _{0}$ , $\Delta _{0}$ och $\Pi _{0}$ . Detta utgör grunden för Lévy-hierarkin , som definieras analogt med den aritmetiska hierarkin.

Begränsade kvantifierare är viktiga i Kripke–Platek mängdlära och konstruktiv mängdlära , där endast ₀ Δ- separation ingår. Det vill säga, det inkluderar separation för formler med endast avgränsade kvantifierare, men inte separation för andra formler. I KP är motivationen det faktum att huruvida en mängd x uppfyller en gränsad kvantifieringsformel bara beror på samlingen av mängder som är nära x i rang (eftersom powerset-operationen bara kan tillämpas ändligt många gånger för att bilda en term). I konstruktiv mängdlära motiveras det på predikativa grunder.

Se även

• Subtypning — begränsad kvantifiering i typteori
• System F _<: — en polymorf typad lambda-kalkyl med avgränsad kvantifiering

•   Hinman, P. (2005). Grunderna i matematisk logik . AK Peters. ISBN 1-56881-262-0 .
•   Kunen, K. (1980). Mängdlära: En introduktion till oberoende bevis . Elsevier. ISBN 0-444-86839-9 .