Brouwer-Heyting-Kolmogorovinterpretatie

In de wiskundige logica is de Brouwer-Heyting-Kolmogorovinterpretatie of BHK-interpretatie een theorie die de wiskundige stroming van het intuïtionisme onderbouwde. De BHK-interpretatie is opgesteld door L.E.J. Brouwer, Arend Heyting en Andrej Kolmogorov en wordt ook wel de realiseerbaarheidsinterpretatie genoemd, omdat de theorie sterk tegen de realiseerbaarheidstheorie van de Amerikaanse wiskundige Stephen Kleene aanleunt.

De interpretatie geeft een bewijs van een gegeven logische formule. Dit wordt gespecifieerd door de structuurinductie van die formule:

• Een bewijs van ${\displaystyle P\wedge Q}$ is een paar ${\displaystyle \langle a,b\rangle }$ met ${\displaystyle a}$ een bewijs van ${\displaystyle P}$ en ${\displaystyle b}$ een bewijs van ${\displaystyle Q}$.
• Een bewijs van ${\displaystyle P\vee Q}$ is een paar ${\displaystyle \langle a,b\rangle }$ met ${\displaystyle a}$ gelijk aan 0 en ${\displaystyle b}$ een bewijs van ${\displaystyle P}$, ofwel is ${\displaystyle a}$ gelijk aan 1 en ${\displaystyle b}$ een bewijs van ${\displaystyle Q}$.
• Een bewijs van ${\displaystyle P\to Q}$ is een functie die een bewijs van ${\displaystyle P}$ omvormt naar een bewijs van ${\displaystyle Q}$.
• Een bewijs van ${\displaystyle \exists x\in S:\phi (x)}$ is een paar ${\displaystyle \langle a,b\rangle }$ met ${\displaystyle a}$ een element van ${\displaystyle S}$, en ${\displaystyle b}$ een bewijs van ${\displaystyle \phi (a)}$.
• Een bewijs van ${\displaystyle \forall x\in S:\phi (x)}$ is een functie f die een element ${\displaystyle a}$ van ${\displaystyle S}$ omzet naar een bewijs van ${\displaystyle \phi (a)}$.
• De formule ${\displaystyle \neg P}$ is gedefinieerd als ${\displaystyle P\to \bot }$. Bijgevolg is een bewijs ervan een functie die een bewijs van ${\displaystyle P}$ omzet naar een bewijs van ${\displaystyle \bot }$.
• Er bestaat geen bewijs van ${\displaystyle \bot }$ (het absurde).

Het wordt aangenomen dat de interpretatie van de primitieve proposities door de context bekend is. In de rekenkunde is de interpretatie van de formule ${\displaystyle s=t}$ bijvoorbeeld een berekening die beide kanten tot hetzelfde getal omrekent.

Kolmogorov volgde dezelfde hoofdlijnen maar formuleerde zijn interpretatie in de vorm van problemen en oplossingen. Een formule geldig maken staat dan gelijk aan beweren dat er een oplossing voor het probleem bekend is, die de formule representeert. Zo is ${\displaystyle P\to Q}$ het probleem van het reduceren van ${\displaystyle Q}$ tot ${\displaystyle P}$. Om dit op te lossen, is een methode nodig die een probleem ${\displaystyle Q}$ kan oplossen wanneer een oplossing voor het probleem ${\displaystyle P}$ is gegeven.

De identiteitsfunctie is steeds een bewijs van de formule ${\displaystyle P\to P}$, wat ${\displaystyle P}$ ook is.

De wet van de non-contradictie ${\displaystyle \neg (P\wedge \neg P)}$ wordt uitgebreid tot ${\displaystyle (P\wedge (P\to \bot ))\to \bot }$:

• Een bewijs van ${\displaystyle (P\wedge (P\to \bot ))\to \bot }$ is een functie die een bewijs van ${\displaystyle (P\wedge (P\to \bot ))}$ omzet naar een bewijs van ${\displaystyle \bot }$.
• Een bewijs van ${\displaystyle (P\wedge (P\to \bot ))}$ is een paar van bewijzen ${\displaystyle \langle a,b\rangle }$, met ${\displaystyle a}$ een bewijs van ${\displaystyle P}$ en ${\displaystyle b}$ een bewijs van ${\displaystyle P\to \bot }$.
• Een bewijs van ${\displaystyle P\to \bot }$ is een functie die een bewijs van ${\displaystyle P}$ omzet naar een bewijs van ${\displaystyle \bot }$.

Samengevat is een bewijs van ${\displaystyle (P\wedge (P\to \bot ))\to \bot }$ een functie ${\displaystyle f}$ die een paar ${\displaystyle \langle a,b\rangle }$ (waarbij ${\displaystyle a}$ een bewijs van ${\displaystyle P}$ en ${\displaystyle b}$ een functie die een bewijs van ${\displaystyle P}$ omzet naar een bewijs van ${\displaystyle \bot }$) omzet naar een bewijs van ${\displaystyle \bot }$. De functie ${\displaystyle f(\langle a,b\rangle )=b(a)}$ past hierin en bewijst de wet van de non-contradictie, wat ${\displaystyle P}$ ook is.

Tegenover deze wet staat de wet van de uitgesloten derde die ${\displaystyle P\vee \neg P}$ uitbreidt naar ${\displaystyle P\vee (P\to \bot )}$ en geen algemeen bewijs heeft. Volgens de interpretatie is een bewijs van ${\displaystyle P\vee \neg P}$ een paar ${\displaystyle \langle a,b\rangle }$ met ${\displaystyle a}$ gelijk aan 0 en ${\displaystyle b}$ een bewijs van ${\displaystyle P}$, of ${\displaystyle a}$ gelijk aan 1 en ${\displaystyle b}$ een bewijs van ${\displaystyle P\to \bot }$. Als dus ${\displaystyle P}$ noch ${\displaystyle P\to \bot }$ bewijsbaar zijn, dan is ${\displaystyle P\vee \neg P}$ dat ook niet. Hieruit volgt dat als ${\displaystyle P}$ noch ${\displaystyle P\to \bot }$ bewijsbaar is, hetzelfde geldt voor ${\displaystyle P\vee \neg P}$.