Een postzegel met een logische formule

Dit najaar verscheen dankzij de inspanningen van Dirk van Dalen de eerste Nederlandse postzegel met een wiskundige en logicus erop. De media hebben veel aandacht besteed aan ons nationale genie Luitzen Egbertus Jan Brouwer (1881–1966), waarbij steeds hoger gestemde tonen niet werden geschuwd, tot en met de heiligverklaring en lancering ter hemelvaart in Kousbroeks stukje op de achterpagina van de NRC.

Maar er resteert dan toch wel een mogelijke vraag. Wat betekent dat spijkerschrift

5 A ∨ ¬A

op die postzegel nu eigenlijk? Misschien moeten we het mysterie van zo’n technische formule maar intact laten. De KNAW viert haar jubileumjaar met het motto ‘Magie van de wetenschap’: wie weet blijkt dat bij nader onderzoek wel zwarte magie…

De Wet van het Uitgesloten Derde

Maar dat zou toch jammer zijn van de logische formule op deze postzegel, die zo veel Nederlandse lippen beroert dezer dagen. Wat zij heel kort weergeeft is Brouwers beroemde ontkenning van een hoofdwet van de klassieke logica, en wel het Principe van het Uitgesloten Derde. Dit principe, bekend sinds de Klassieke Oudheid, zegt dat voor elke bewering A, hetzij A zelf, hetzij de ontkenning (‘niet-A’, of in notatie: ‘¬A’) waar is. Let wel, Uitgesloten Derde zegt niet dat wij weten welk van de twee het geval is, maar in principe moet een van de twee alternatieven gelden. Dit klinkt onschuldig en evident, en het lijkt moeilijk hierover te twisten. In dit verband nog even iets over de notatie op de postzegel. Logici gebruiken het symbool ⎥= voor geldigheid van een bewering, en het streepje erdoor staat voor een ontkenning daarvan. Waarom ook die ontkenning dan niet geschreven met het negatiehaakje ¬? Om dat uit te leggen moeten we echt veel verder de diepte in. Net als in de wiskunde, heeft in de logica simpele notatie vaak diepe achtergronden.

Klassieke propositielogica

Laten we eerst eens kijken naar de logica zoals die was toen Brouwer studeerde. We gaan even heel snel. Sinds Aristoteles en de Stoa weten we dat veel redeneren draait om een klein aantal sleutelbegrippen, zoals ‘en’ (conjunctie, ∧), ‘of’ (disjunctie, ∨) en ‘niet’ (negatie, ¬). Wie dat feit betwijfelt moet maar even met de NS reizen, en forenzen observeren. Metro en Spits zijn de meest gelezen logicatijdschriften ter wereld! Hun sudokupuzzels draaien geheel om logische patronen als ‘op dit vakje moet een cijfer x of y staan, maar x kan het niet zijn: dus is het y’, of in een notatie als op de postzegel – met ‘A’ voor de bewering ‘het vakje heeft cijfer x’ en ‘B’ voor ‘het vakje heeft cijfer y’:

A ∨ B, ¬A ⎥= B, de conclusie B volgt uit de premissen A ∨ B en ¬A.

Het wiskundig systeem van dergelijke regels, de ‘klassieke propositielogica’, is al eeuwen welbegrepen. Het werd door George Boole gecodificeerd als een elegante vorm van algebra in zijn Laws of Thought van 1847. Die algebra is niet meer dan een vorm van binair rekenen met twee waarheidswaarden 0 (‘onwaar’) en 1 (‘waar’) – een analogie die reeds was opgemerkt door Leibniz rond 1700, die dacht aan redeneermachines die met zulk binair rekenen logische geldigheid zouden testen. Dat heeft dus nog even geduurd, maar Boolese circuits beheersen sinds 1950, en nog steeds, uw computer – wat u ook in de krant mag lezen over meer futuristische quantumrekentechnieken.

De Drie Hoofdwetten

Maar nu die hoofdwetten. Drie grondprincipes van de Boolese algebra zijn moderne wiskundige weergaven van drie grondwetten van de klassieke logica. De eerste is

A = A Wet van de Identiteit

Dit lijkt niet bijster opwindend: 0 = 0 en 1 = 1, en zelfs een extreem twistziek mens als Brouwer heeft er nooit zijn pijlen op gericht. Wel zullen we straks nog een verrassende moderne herinterpretatie vinden voor dit principe. Dan komt de tweede wet:

¬(A ∧ ¬A) Wet van de (Niet-)Tegenspraak

Dit principe zegt dat geen bewering tegelijkertijd en in hetzelfde opzicht waar en onwaar is. Ondanks enige onvrede in dialectische en mystieke kring (een verhaal op zich waard) lijkt ook dit een onproblematisch principe, en weer: Brouwer heeft het nooit bestreden.

Niet-Tegenspraak komt ook voor in andere culturen waar de logica zelfstandig begon. Zo leest de Mohistische traditie in China rond 500 voor Christus dit principe als een regel van conversatie: tegenspraak tussen gesprekspartners mag niet worden geaccepteerd, maar moet altijd worden opgelost. Zo’n gedachtensprong is voor een logicus niet vreemd. Reeds Leibniz beschouwde de Chinese cultuur als serieuze intellectuele gesprekspartner, en stuurde zelfs (ongevraagde) adviezen naar Rome over religieuze contacten.

De Mohisten accepteerden ook de derde klassieke hoofdwet, de ons inmiddels al bekende

Wet van het Uitgesloten Derde A ∨ ¬A

Volgens Boole heeft deze bewering altijd waarde 1. Als A de waarde 0 heeft, dan krijgt ¬A de waarde 1, en opgeteld voor de disjunctie levert dat 1. En met A en waarde 1 gaat het evenzo. Een derde mogelijkheid is er niet. Ook hier is de Mohistische interpretatie meer gespreksgericht. Zij zegt dat deelnemers aan een conversatie eens voor een van de twee beweringen A of ¬A moeten kiezen, hoewel misschien niet meteen aan het begin.

Deze derde ‘Hoofdwet’ is al omstreden sinds de Griekse Oudheid. Aristoteles meende dat ze niet opging voor beweringen over de toekomst. Of er morgen een zeeslag zal zijn is nu nog niet waar of onwaar: anders zou de toekomst al deterministisch vastliggen.

Griekse postzegels over Aristoteles zijn er in vele soorten en maten. En ook andere culturen weten grote logici te eren. Nog veel meer postzegels circuleren in de islamitische wereld van de geleerde Avicenna (werkzaam rond het jaar 1000) – al zijn diens medische, eerder dan zijn logische vernieuwingen de voornaamste drijfveer.

Brouwers bezwaar: van waarheid naar bewijsbaarheid

Maar wat had Brouwer dan tegen A ∨ ¬A? Dat de postzegel geen geldig principe poneert, maar een bezwaar, is op zich wel in stijl. Zoals de huidige president van de KNAW Frits van Oostrom eens zei bij een ceremonie op het kerkhof van Blaricum waar Brouwer begraven ligt: ‘Deze grafsteen is pas tot stand gekomen na lange conflicten – en dat lijkt me nu geheel in de geest van de overledene’. Maar Brouwers twijfel aan het Uitgesloten Derde lag wel degelijk in zijn positieve ‘intuïtionistische’ visie op wiskundige waarheid. Hierin draait alles om de activiteit van een wiskundige die objecten construeert, en hun eigenschappen constructief bewijst. In deze visie, expliciet gemaakt door Heyting in 1929, maar ook voorkomend bij Russische tijdgenoten als Kolmogorov, zijn met name bewijzen voor complexe beweringen systematisch te construeren uit bewijzen voor eenvoudiger deelbeweringen. Voor de Boolese kernbegrippen werkt dit als volgt. Een bewijs van A∧B bestaat uit een paar van twee bewijzen, een voor A en een voor B; een bewijs voor A∨B is een bewijs van A of een bewijs van B; en een bewijs voor ¬A is een weerlegging van A. (Iets preciezer gezegd, een bewijs voor ¬A is een effectieve methode die elk bewijs voor A omzet in een bewijs voor een evident contradictoire bewering.)

Aldus gelezen verandert het Uitgesloten Derde dramatisch van karakter. Het zegt in deze nieuwe interpretatie dat elke wiskundige bewering A hetzij bewijsbaar, hetzij weerlegbaar is. En dat is natuurlijk geheel onaannemelijk. Sinds Gödels Stellingen van 1931 weten we zelfs dat ‘onvolledigheid’ in de wiskunde de norm is: sommige beweringen zijn noch bewijsbaar noch weerlegbaar in de meest gangbare theo-riëen van de rekenkunde, analyse, of verzamelingenleer (aangenomen dat die theorieën consistent zijn). Gödel, niet zelden beschouwd als de grootste logicus sinds Aristoteles, heeft in zijn vaderland Oostenrijk tot nu toe slechts een postzegel in beperkte oplage voor verzamelaars mogen ontvangen.

Toch was Brouwers bezwaar niet absoluut. Hij meende dat vele wiskundige situaties wel degelijk redeneren met Uitgesloten Derde toestaan, mits ze eenvoudig genoeg zijn, zoals met name eindige structuren. Maar de extrapolatie naar oneindigheid is problematisch.

Maar spreken we dan nog wel over hetzelfde?

Nu zou men meteen kunnen zeggen dat bovenstaand bezwaar het klassieke Uitgesloten Derde helemaal niet raakt. Immers, er vindt een verschuiving plaats: van spreken over waarheid naar spreken over bewijsbaarheid. Brouwer bestreed de klassieke logica dus niet op haar eigen terrein, hij veranderde de agenda. Het maken van dit onderscheid is de ‘polderoplossing’ die door waarschijnlijk de meeste professionele logici vandaag de dag wordt aangehangen: de klassieke logica heeft gelijk inzake zuivere waarheid, maar Brouwer heeft gelijk als het gaat om bewijsbaarheid. Zoekt men dan toch nog twist tussen de twee posities, dan moeten ideologische duimschroeven worden aangedraaid. Zo stellen de verdedigers van het filosofische ‘verificationisme’ dat bewijsbaarheid of meer algemeen: ‘verifieerbaarheid’, de enige zinvolle notie van waarheid is. Zo gezien is de klassieke logica een zinledige theorie, op zijn best ‘correct in eigen kring’. Maar hoewel dit verificationisme beroemde en fervente aanhangers heeft, is het slechts een kleine wijsgerige kerk.

Intuïtionistische logica: het constructieve alternatief

Hoe dan ook, een enkel bezwaar tegen andermans theorie is geen blijvend fundament voor wetenschappelijke grootheid. Wat Brouwers logische inzichten zo opmerkelijk maakt is het positieve alternatief dat bleek te schuilen achter zijn algemene visie op wiskunde, een systeem dat thans bekendstaat als de intuïtionistische logica. De reeds genoemde bewijsinterpretatie van de logische begrippen blijkt een eigen geheel aan wetten op te leveren dat innerlijke consistentie aan schoonheid paart. De Wet van de Tegenspraak is bijvoorbeeld nog steeds van kracht: de aanname dat we zowel een bewijs voor A hebben als een weerlegging van A is bewijsbaar onjuist, en die observatie zelf is een bewijs voor ¬(A ∧ ¬A). En vele andere nuttige principes blijven correct, zij het nu met een nieuwe bewijstheoretische inhoud. Zo zijn alle redeneringen die dienen om uw sudoku op te lossen ook intuïtionistisch correct, dus dat is wellicht een geruststelling. Bij dit alles splitsen klassieke principes van redeneren vaak in meerdere varianten, sommige intuïtionistisch correct, en andere niet. Een mooi voorbeeld is de bekende methode van ‘bewijzen uit het ongerijmde’. In de klassieke logica kan men een bewering ¬A aantonen door eerst A aan te nemen en daaruit dan een tegenspraak af te leiden. Die veelgebruikte methode is intuïtionistisch geheel onproblematisch. Maar de klassieke logica heeft ook een geheimzinniger variant: het bewijzen van een bewering A door een tegenspraak af te leiden uit de negatie ¬A. Deze tweede methode is intuïtionistisch onaanvaardbaar: weerleggen dat iets weerlegbaar is, is nog niet hetzelfde als het geven van een bewijs. Hiermee samenhangend verwerpt de intuïtionist de klassiek geldige equivalentie tussen de twee beweringen ¬¬A en A. In het algemeen is de eerste zwakker dan de tweede.

Van bewijs naar informatie

Gaandeweg bleek het mogelijk om de intuïtionistische logica op nieuwe interessante manieren te duiden, waarbij de door Brouwer opgemerkte verschijnselen wéér aan het licht treden. Zo beschreef
E.W. Beth, Brouwers collega in de jaren vijftig aan de UvA, het intuïtionisme in termen van een model van groeiende informatiestadia, van armer naar rijker, waarbij beweringen worden geïnterpreteerd per stadium. Een wiskundige, of een rationele actor in het algemeen, verkrijgt gaandeweg steeds meer informatie, en beweegt daarmee ‘omhoog’ in deze ordening. Weer zien we nu een vreedzame coëxistentie van twee systemen. In eindstadia, waar alle informatie binnen is, geldt de klassieke logica. Maar in de voorlopige tussenstadia (waar wij ons doorgaans bevinden) kunnen klassieke wetten falen. Bijvoorbeeld, laten we een negatie niet-A in een stadium waar noemen als A op dit moment reeds is weerlegd: dat wil zeggen, A wordt door geen enkel rijker stadium alsnog waar gemaakt. Met deze interpretatie is eenvoudig in te zien dat het Uitgesloten Derde in het algemeen faalt. Neem een informatiemodel met twee stadia: een voorlopig stadium waar we A nog niet hebben, gevolgd door een eindstadium waar dat wel zo is.

In het eerste stadium 1 faalt A per veronderstelling, maar evenmin hebben we daar niet-A volgens de zojuist gegeven interpretatie, want we krijgen A later in stadium 2 alsnog. Dus is in stadium 1 de disjunctieve bewering A ∨ ¬A onwaar.

Hier is overigens een zeker gevoel voor finesse vereist. Er is in Beths semantiek, en de intuïtionistische logica, een delicaat verschil tussen zeggen dat in een zekere situatie ‘A niet opgaat’, en dat in die situatie de negatie ‘niet-A opgaat’. Maar dat zag u eigenlijk al op de postzegel. Brouwers bezwaar is geformuleerd met het streepje, de eerste zwakke negatie ‘niet’. Het is niet geformuleerd met de intuïtionistische sterke negatie ¬. En dat kan ook niet, want het principe ¬(A ∨ ¬A) is intuïtionistisch niet geldig. Sterker nog, Brouwer achtte de sterke ontkenning van het Uitgesloten Derde contradictoir, en in feite is daarmee het volgende principe intuïtionistisch geldig:

¬¬(A ∨ ¬A)

Maar ís dit niet het Uitgesloten Derde, op simpel samentrekken van een dubbele negatie na? Dat lijkt wel zo: maar zoals we reeds zagen, de klassieke logische wet ¬¬A ↔ A is intuïtionistich nu juist niet langer geldig… Het onderscheid is eenvoudig te zien in Beths modellen: ¬¬A wil zeggen dat bij elk stadium een later stadium bestaat dat A waar maakt (A is ‘onvermijdelijk’), maar dit is niet hetzelfde als zeggen dat A meteen nu al waar is. Bijvoorbeeld in stadium 1 van het voorgaande plaatje was ¬¬A waar, maar A niet.

Hier scheiden zich wellicht de wegen. Voor sommigen is dit ondraaglijke scholastiek met negaties, maar voor anderen opent zich een nieuwe denkstijl, die subtiele onderscheiden ziet die in de klassieke logica worden onderdrukt. In elk geval kan gezegd worden dat de intuïtionistische logica een coherente en subtiele beschrijving geeft van constructief redeneren in een context van bewijs, informatie en berekening. Ze heeft daarbij de klassieke logica niet verdrongen als norm, laat staan als discipline, maar ze heeft zich wel een eigen plaats verworven in de grondslagen van de wiskunde en informatica. Die plaats is niet zo groot als moderne partijgangers van Brouwer beweren, maar ook weer niet zo klein als de standaard logicaboeken willen doen geloven die voor het intuïtionisme doorgaans slechts een bescheiden nisje inruimen als ‘the revolution that failed’.

The story goes on: intuïtionisme en dialoogspelen

Intuïtionisme wordt vaak geassocieerd met grondslagen van de wiskunde, en met zuivere bewijzen van buitenaardse precisie, die geen ruimte laten voor menselijk geharrewar. Maar ideeën hebben hun eigen evolutionaire dynamiek, en we kunnen Brouwers werk even goed plaatsen in een geheel andere logische traditie die teruggaat tot de Klassieke Oudheid, en wel die van logische patronen in dialoog en debat. Eigenlijk is dat zelfs voor wiskunde een even goed gezichtspunt: een bewijs is geen ‘conversation stopper’, maar de ultieme poging tot helderheid naar anderen, en dus tot intersubjectieve communicatie. En hiermee neemt ons verhaal over logische wetten een wending naar argumentatie en spel.

Reeds in het midden van de jaren vijftig werd dit verband opgemerkt door de Duitse logicus Paul Lorenzen, die een onderbouwing zocht voor de logische wetten in de dagelijkse praktijk van argumentatie en interactie. Zijn opmerkelijke idee daarbij was dat de logische operaties ‘of’, ‘en’ en ‘niet’ fungeren als een soort ‘schakelaars’, niet alleen in een Boolese computer, maar ook in een discussie. Als ik verdedig dat A∨B, dan kunt u mij hierop aanspreken, en moet ik uiteindelijk kiezen welk van de twee ik wil verdedigen. Een disjunctie biedt dus een keuze voor de verdediger – en evenzo biedt een conjunctie A∧B een keuze voor de aanvaller: de verdediger ‘staat’ immers voor beide onderdelen. Aldus ontstaat een argumentatief spel tussen de verdediger van een bewering en de aanvaller, en is ook meteen fraai verklaard waarom conjunctie en disjunctie zich formeel zo analoog gedragen. Ze betreffen dezelfde handeling, te weten een keuze, maar alleen gedaan door verschillende spelers. Bovendien ontstaan in een dialoog nu interessante interacties tussen deze spelers door de negatie. Deze zorgt voor een rolwisseling: verdedigen van ¬A is aanvallen van A, en vice versa. (Zich te kunnen verplaatsen in de positie van een ander wordt weleens beschouwd als het meest essentiële menselijke cognitieve vermogen.) Op deze manier beschrijft de logica de structuur van een rationele wisselwerking tussen gesprekspartners. In dit perspectief noemde Lorenzen een logische gevolgtrekking nu geldig als de verdediger van de conclusie een winnende strategie heeft, dat wil zeggen, een manier die hem altijd tot winst brengt tegen elke verdediger van de premissen. Hier is een eenvoudig voorbeeldje met de sudokuregel. Als u B beweert tegen een verdediger van A∨B en ¬A, val dan eerst die disjunctie aan, zodat hij moet kiezen. Als zijn antwoord B is, dan wint u meteen al – en luidt het antwoord A, dan kunt u nu zelf veilig A aanvallen omdat hij nu in de inconsistente positie A, ¬A staat. In het algemeen zullen winnende strategieën overigens veel complexer zijn dan dit simpele gambiet: succesvolle argumentatie is dan ook een niet-triviale menselijke vaardigheid.

Wat Lorenzen nu opmerkte was dat in deze interpretatie het Uitgesloten Derde niet plausibel is. Voor de verdediger van A∨¬A is in het algemeen niet aan te geven welke keuze tot winst zou leiden. In feite bleken de met zijn winnende strategieën verdedigbare principes precies die van Brouwers intuïtionistische logica te zijn! Inmiddels zijn er ook dialoogspelen voor klassieke logica gevonden, maar die hebben andere procedurele debatregels, waar de verdediger van een disjunctie zijn keuze achteraf mag herzien. Zo beschouwd is dan de intuïtionistische logica die van een rechtstreeks gelijk, terwijl de klassieke logica ons iets menselijker behandelt. Lorenzens voorkeur was duidelijk het eerste. Hij was een intimiderend persoon, en toen ik hem eens als jeugdig medewerker moest begeleiden op een universitaire lunch, brak ik van angst mijn mes in tweeën.

Logica en het oplossen van spelen

Lorenzens werk heeft weinig invloed gehad op de grondslagen van de wiskunde, en eindigde voornamelijk als inspiratiebron voor de algemene ‘argumentatietheorie’, ook in ons eigen thuisland van het intuïtionisme. Maar het idee dat logica en spel intrinsiek bij elkaar horen bleef bestaan, en komt de laatste tijd zelfs steeds klemmender naar voren. Een belangrijke invloed hierbij is de informatica, een fundamenteel wetenschapsgebied waar de logica nog steeds de grondslagen levert voor de studie van informatie- en rekenprocessen. En modern rekenen is, u weet het van de e-mail en het internet in uw leven, al lang geen zaak meer van simpele Boolese circuits in een eenzame rekenmachine, maar van complexe interactieve informatieverwerkende processen in grote netwerken.

Nu heeft dit contact met de informatica vele aspecten, waarvan de meeste zelfs lopen via de klassieke logica. Sterker nog, in de spelarena lijkt het Uitgesloten Derde juist triomfen te vieren! Om dat te zien gaan we terug naar een tijdgenoot van Brouwer, de Duitse wiskundige Ernst Zermelo, een grondlegger van de moderne verzamelingenleer. Zermelo was geïnteresseerd in de volgende vraag: ‘Wie heeft de beste positie in het schaakspel?’ (Grote wiskundigen hebben een breed bereik aan interessen.) Wat hij in 1913 bewees is het volgende. In een eindig spel voor twee spelers met slechts twee mogelijke uitkomsten, ‘winst’ en ‘verlies’, waar elk spelverloop een keer moet aflopen, heeft een van de twee spelers een winnende strategie. We geven het aardige wiskundige bewijs:

Stel dat het spel maar 1 zet duurt, en Speler i begint. Dan heeft i óf een zet die tot winst leidt (en i’s winnende strategie is: ‘kies zo’n winnende zet’), óf alle zetten leiden tot verlies voor i, en in dat geval geval heeft juist Speler ii een winnende strategie (‘wacht af, en win’). Als het spel 2 zetten duurt, dan herhalen we de zojuist gegeven redenering. Of de beginspeler kan een zet kiezen die hem brengt naar een positie met een winnende strategie, en dan heeft die speler ook in totaal een winnende strategie, of alle zetten van de beginspeler leiden naar een positie met een winnende strategie voor de andere speler, en dan heeft die laatste dus een winnende strategie. En evenzo voor langere spelen.

Deze redenering kan zelfs worden gebruikt om een mechanisch algoritme te schrijven dat de boom van alle mogelijke zetten van een eindig spel doorloopt, en van knoop tot knoop bepaalt wie daar de winnende strategie heeft. Dit algoritme is de basis voor alle verdere methoden die met behulp van computers spelen oplossen, een vorm van meta-topsport waar onze Nederlandse IKAT/MICC-groep in Maastricht internationaal aan de top staat.

Natuurlijk kent schaken ook een derde mogelijkheid van remise. Zermelo’s stelling zegt in dat geval dat hetzij een van de spelers in het schaakspel een winnende strategie heeft, of de ander heeft een ‘niet-verliezende’ strategie, die voor hem altijd eindigt in winst of remise. Dit resultaat werd door de Nederlandse wereldkampioen Max Euwe in 1929 herontdekt. Overigens weten we bijna een eeuw na Zermelo’s resultaat nog steeds niet welk van de genoemde twee gevallen voor het schaakspel opgaat: de volledige spelboom is gewoon te groot om uit te zoeken. In die zin is zelfs het ‘eindige’ Uitgesloten Derde een idealisering, die niet meteen tot expliciete kennis hoeft te leiden. Maar de klok tikt voor het schaken. Voor het bordspel ‘Checkers’ (een in Amerika gangbare variant van dammen) is onlangs, na vijftien jaar continu computerrekenwerk door de spelboom heen, het Zermelo-antwoord gevonden: de beginspeler heeft een niet-verliezende strategie.

Wie even nadenkt over Zermelo’s bewijs zoals boven geschetst ziet dat het draait om het Uitgesloten Derde, en we zien concreet hoe krachtig en elegant dit logische principe is. Overigens zou een intuïtionist hier ook geen bezwaar aantekenen: het ging immers om eindige spelen. Voor oneindige spelen ligt de situatie subtieler, en we volgen die draad nu iets verder tot in enkele andere disciplines. Logische thema’s ‘steken’ vaak ‘over’ van één academisch domein naar een ander, en dat maakt ze juist zo fascinerend.

Niet-gedetermineerde spelen, verzamelingenleer en speltheorie

Een spel waarin een van beide spelers een winnende strategie heeft heet gedetermineerd. Zijn alle spelen gedetermineerd? Met deze eenvoudige vraag bevinden we ons meteen in de grondslagen van de verzamelingenleer. Er zijn voorbeelden gevonden van oneindige niet-gedetermineerde spelen, maar deze bleken sterk af te hangen van de wiskundige principes die men aanneemt voor het redeneren met verzamelingen: met name het ‘KeuzeAxioma’. Er is daarom in de jaren zestig zelfs voorgesteld om als alternatief axioma gewoon te postuleren dat alle spelen gedetermineerd zijn. Dit Axioma van Gedetermineerdheid zou men kunnen beschouwen als een op hol geslagen Uitgesloten Derde, maar dan wel een met vele mooie wiskundige consequenties. Er bestaat een brede consensus dat de verzamelingenleer nieuwe axioma’s behoeft, maar veel minder over precies welke. In elk geval blijken spelen hier een belangrijke bron van intuïties te zijn.

Nu is dit alles nog steeds geen speltheorie in de gangbare economische zin. Dat laatste vakgebied beschrijft meer verfijnde voorkeuren van spelers inzake de uitkomsten van een spel dan alleen winnen en verliezen. Daarmee samenhangend benadrukt de wiskundige speltheorie ‘Nash-evenwichten’ tussen door spelers gekozen strategieën, waarin niemand zijn uitkomst kan verbeteren door eenzijdig af te wijken als alle anderen bij hun keuze blijven. De recente speelfilm A Beautiful Mind brengt iets van deze evenwichtstheorie, en veel van het tragische leven van zijn voornaamste grondlegger in beeld. Zulke Nash-evenwichten beschrijven interacties tussen spelers die Zermelo’s kader ver overstijgen, en zijn daarmee essentieel voor de studie van realistisch economisch en sociaal gedrag. Ook op dit rijkere onderzoeksgebied liggen de laatste tijd niettemin levendige contacten tussen logica en speltheorie, soms samengevat onder de noemer van ‘intelligente interactie’.

Maar zelfs hier ontmoeten we Brouwer. Dat is dan wel in zijn andere persona, als baanbreker in de topologie, ontstaan in de twintigste eeuw als abstracte studie van ruimtelijke structuren. Brouwers faam bij wiskundigen berust met name op zijn Dekpuntsstelling, een fundamenteel resultaat met verrassende toepassingen. Het zegt ruwweg dat alle continue functies op geschikte topologische ruimtes ‘dekpunten’ hebben: punten x waar de functiewaarde f(x) gelijk is aan x zelf. Nu blijken speltheoretische evenwichten en topologische dekpunten wiskundig sterk verwant, en, zoals reeds opgemerkt door Von Neumann, belangrijke resultaten uit de speltheorie volgen uit Brouwers stelling. In zijn bewijs legde Brouwer zichzelf overigens bepaald geen intuïtionistische restricties op, en de Dekpuntsstelling is strikt genomen zelfs constructief-wiskundig onbewijsbaar. (Dit sluit niet uit dat constructieve ‘herformuleringen’ bestaan, en de discussie duurt voort.) Brouwer predikte dus tegen het Uitgesloten Derde, maar zondigen was hem niet vreemd.

Logica, interactief rekenen en lineaire spelalgebra

Ons reeds lange verhaal van Brouwers intuïtionisme, klassieke logica, informatica, verzamelingenleer en speltheorie kent toch nog een laatste verrassende wending. Het Uitgesloten Derde blijft steeds weer actief als bron van nieuwe inzichten. Daartoe gaan we terug naar de grondbegrippen van de logica zelf, die ook in het huidige onderzoek nog steeds ter discussie staan. In spel, dialoog en argumentatie staat interactie tussen meerdere personen centraal: een proces met tijdsverloop. Maar dan is onze eerdere interpretatie van het logische ‘A of B’ als keuze voor een der deelspelen A, B toch wel erg drastisch. Immers, die keuze moet reeds aan het begin worden gemaakt, terwijl we nog niets weten over hoe het in die deelspelen toegaat. Om deze reden is voorgesteld om ook nog een tweede logische vorm van keuze in te voeren. Hierbij worden A, B beide parallel gespeeld, terwijl de speler die de keuze moet maken, ‘lokaal’ bij elk van zijn beurten mag beslissen in welk van de twee spelen de volgende zet plaatsvindt. Dit uitgesteld kiezen lijkt meer op wat we al zagen voor klassieke Lorenzen-dialogen, en met enige historische goede wil ook bij de Mohisten. Een veel geciteerd, en vaak herontdekt voorbeeld komt weer uit de sfeer van het al eerder besproken schaakspel. Hier is een methode die u kunt gebruiken om Bobby Fischer te slim af te zijn, bekend als de ‘Copy Cat’-strategie:

U speelt twee spelen simultaan, een keer als Wit en een keer als Zwart. U laat Fischer als Wit openen, dan kopieert u zijn zet in het andere spel als Wit, en blijft daar, zodat hij nu aan de beurt is, en een antwoord op uw (= zijn eigen) eerste zet moet spelen. Dit antwoord kopieert u zelf als antwoord in het andere spel (u hebt immers het recht om van spel te wisselen), enzovoorts. Op deze manier ontstaat in beide spelen dezelfde reeks zetten – en dus moet u in een van deze twee gevallen winnen, of beide zijn remise.

Deze ‘parallelle disjunctie’ A + B werd als nieuwe logische operatie voorgesteld door de Amerikaanse wiskundige Blass rond 1970, in een studie van de dialogen van Lorenzen. Zoals we reeds zagen gaat in spelen het klassieke Uitgesloten Derde niet altijd op voor de klassieke disjunctie ∨. Om een winnende strategie te hebben, zou de beginspeler immers in

A ∨ ¬A

meteen aan het begin moeten kiezen, en dus moet hij of in A of ¬A afzonderlijk al een winnende strategie hebben. Maar dit faalde nu juist bij niet-gedetermineerde spelen A. Het bovenstaande Copy Cat-argument neemt echter helemaal niet aan dat het spel A gedetermineerd is, en het toont in feite volstrekt algemeen aan dat het logische principe

A + ¬A

wél altijd geldig is! Kort gezegd: ‘uitgestelde’, of ‘interactieve’ keuze A + B voldoet zonder meer aan het Uitgesloten Derde. De geldigheid van dit principe hangt dus ook af van welke disjunctie we beschouwen, en er zijn meerdere legitieme mogelijkheden. We ontdekken aldus een wereld van nieuwe logische operaties met eigen nieuwe wetten. Observaties als deze hebben geleid tot een veel rijkere vorm van spellogica met meer operatoren dan in de klassieke of intuïtionistische logica waren bestudeerd. Belangrijke bijdragen werden in de laatste decennia geleverd door Girard en Abramsky, en het gebied floreert nog steeds. Met andere woorden, Boolese algebra blijkt slechts een klein deel van een mooie algemene spelalgebra met operaties die complex interactief gedrag creëren.

Deze moderne interactieve visie op logica als rationele activiteit voor meerdere actoren geeft nieuwe betekenissen aan de klassieke hoofdwetten. Dat geldt voor het flamboyante Uitgesloten Derde, maar ook voor bescheiden principes als de eerdere Wet van de Identiteit. Van de gemeenplaats dat A = A verandert deze in de Copy Cat-regel ‘Maak jouw A tot mijn A’, en blijkt dan plotseling een sleutel tot interactie. Deze wijze van beschouwen maakt ook oude conflicten tussen voor- en tegenstanders van het Uitgesloten Derde enigszins achterhaald. Met het onderscheid tussen ∨ en + en andere speloperatoren is de oorspronkelijke discussie over ‘concurrerende logica’s’ een slag verfijnder geworden.

Een serie postzegels?

Het zal inmiddels duidelijk zijn dat TNT Post nog niet van de logici af is. De Brouwer-postzegel eert slechts een bezwaar tegen de klassieke logica. Het lijkt me op zijn minst redelijk om ook iets positiefs toe te voegen, en wel een geldige intuïtionistische wet:

⎥= ¬¬(A ∨ ¬A)

Maar het mooist zou toch zijn een serie van drie zegels, waarbij we het Uitgesloten Derde ook nog eens eren in zijn moderne interactieve spelgebaseerde interpretatie:

⎥= (A + ¬A

De keuze der waarden van de drie zegels laat ik graag aan onze posterijen over.

Conclusie

Dit is wel alles wat er over Brouwer en het Uitgesloten Derde valt te zeggen. Of niet.

Johan van Benthem is hoogleraar logica aan de Universiteit van Amsterdam en hoogleraar filosofie aan de Stanford University in Californië. In 1996 ontving hij de NWO Spinozaprijs voor zijn onderzoek op de grens van logica, filosofie, taalkunde en informatica. Zijn huidige interesses zijn logica en speltheorie, en logica in China.

Meer van deze auteur