In wiskunde is het bewijs van stellingen vaak een proces van herhaalde toepassing van beweringen, wat vaak inductie vereist. Het gebruik van inductie en recursie is een krachtig hulpmiddel in het formele bewijsproces, en in Lean kunnen deze technieken worden toegepast om veel van de fundamentele eigenschappen van getallen en functies te bewijzen. De mogelijkheid om recursieve definities te gebruiken is cruciaal voor het vaststellen van de eigenschappen van natuurlijke getallen, en Lean’s structuur biedt robuuste hulpmiddelen om deze bewijzen te formaliseren.

Het bewijs van de faculteit van een natuurlijk getal is een van de eenvoudigste toepassingen van inductie in Lean. De faculteit, gedefinieerd als het product van alle natuurlijke getallen van 1 tot en met n, kan direct worden bewezen door inductie. In dit geval wordt de recursieve definitie van de faculteit gebruikt, en de bewijsvoering begint met de basisstap voor n = 0. Vervolgens wordt de inductiestap uitgevoerd met behulp van de vermenigvuldiging en de standaard regels van de algebra zoals de commutativiteit van vermenigvuldiging, wat een belangrijk hulpmiddel is om gelijkheden te vereenvoudigen zonder eindeloze lussen.

Een ander voorbeeld van het gebruik van inductie is de somformule voor de natuurlijke getallen. Het bewijs dat de som van de eerste n natuurlijke getallen gelijk is aan n(n+1)2\frac{n(n+1)}{2} wordt in Lean niet alleen met inductie, maar ook met slimme vereenvoudigingsregels uitgevoerd. De aanpak is gebaseerd op het herschrijven van de termen in de som met behulp van regels zoals de distributieve eigenschap en andere algebraïsche identiteiten. Dit stelt ons in staat om complexe sommen van getallen eenvoudiger en overzichtelijker te maken.

Naast de directe toepassingen van inductie, wordt recursie ook gebruikt om de fundamentele bewerkingen van natuurlijke getallen, zoals optellen en vermenigvuldigen, te definiëren. Deze operaties worden in Lean gedefinieerd door middel van inductie over de tweede parameter. Bij het bewijzen van eigenschappen van deze bewerkingen, zoals de associativiteit van optellen of de commutativiteit van vermenigvuldigen, moeten we zorgvuldig kiezen welke variabele we gebruiken voor de inductie. De keuze voor de inductievariabele speelt een cruciale rol in het structureren van het bewijs op een manier die de complexiteit minimaliseert.

Er is echter een ander interessant aspect van de formele wiskunde, namelijk de manier waarop soms triviale stellingen, zoals het vaststellen van de volgorde van natuurlijke getallen, moeilijk te formaliseren zijn. Bijvoorbeeld, om te bewijzen dat elke natuurlijke getal groter dan 1 ook groter dan of gelijk aan 2 is, zijn verschillende strategieën mogelijk. Een daarvan is het gebruik van de cases-tactiek, die automatisch de mogelijkheid biedt om gevallen te splitsen. Dit is vooral handig in situaties waarbij een eenvoudige tegenstelling of bewijs van het bestaan van een element in een bepaalde reeks vereist is.

Bij het onderzoeken van de eigenschappen van priemgetallen komen we een klassiek resultaat tegen: er zijn oneindig veel priemgetallen. Dit bewijs maakt gebruik van een techniek die bekend staat als de ‘factorial plus één’ methode. Als we n!+1n! + 1 beschouwen, waarbij n een willekeurig natuurlijk getal is, dan heeft dit getal altijd een priemfactor die groter is dan n. Dit volgt uit het feit dat, als een priemgetal pp een deler zou zijn van zowel n!n! als n!+1n! + 1, dit zou leiden tot een contradictie, omdat pp dan 1 zou moeten delen.

Een belangrijk aspect van dit bewijs is de keuze voor sterk inductie, een uitbreiding van de gebruikelijke inductie die ons toestaat om te bewijzen dat elke natuurlijke getal een bepaalde eigenschap bezit door te veronderstellen dat de eigenschap geldt voor alle getallen kleiner dan n, en dan de eigenschap voor n zelf te bewijzen. Dit soort inductie is onmisbaar bij het bewijs van stellingen die betrekking hebben op een oneindige reeks getallen.

Bij de formalisering van dergelijke resultaten, zoals de stelling dat elk getal groter dan 2 een priemgetal als deler heeft, moeten we zorgvuldig omgaan met de formele definitie van natuurlijk getallen en priemgetallen. Lean biedt verschillende manieren om dergelijke stellingen te bewijzen, en het is belangrijk om te begrijpen dat het werken met zulke abstracte concepten vaak betekent dat we ons moeten concentreren op de formele definities en de interactie tussen deze definities binnen de structuur van Lean’s wiskundige omgeving.

De inductie en recursie in Lean zijn niet alleen handig voor het formaliseren van eenvoudige algebraïsche identiteiten, maar ook voor het ontwikkelen van diepgaande inzichten in de structuur van getallen en de eigenschappen van fundamentele wiskundige objecten. Voor de wiskundige beoefenaar biedt deze aanpak een krachtig kader voor het systematisch bewijzen van de meest complexe stellingen, door gebruik te maken van de strikte logica en inductieve definities die inherent zijn aan de Lean-omgeving.

Hoe de telling van verzamelingen en functies werkt in combinatoriek

In de combinatoriek is het tellen van elementen een fundamenteel en essentieel onderdeel van het vakgebied. Een veelgebruikte techniek hierbij is het gebruik van finsets en fintypes, die wiskundige objecten zijn die eindige verzamelingen en de structuren daarop representeren. De wiskundige benadering van deze tellingen is complex, maar biedt krachtige gereedschappen voor het begrijpen van de onderliggende combinatorische structuren.

In veel gevallen werkt men met het type finset, wat een verzameling is van eindige objecten. De cardinaliteit (aantal elementen) van een finset kan eenvoudig worden berekend met behulp van bepaalde algebraïsche identiteiten die zijn opgenomen in bibliotheken zoals Mathlib. De basisprincipes van deze berekeningen maken gebruik van bekende combinatorische formules, zoals de telling van het product van twee verzamelingen, de unie van verzamelingen, en de afbeelding van een verzameling onder een injectieve functie.

Een eenvoudig voorbeeld is de berekening van het aantal elementen in het product van twee verzamelingen ss en tt, dat wordt gegeven door de formule:

#(s×t)=#s×#t\#(s \times t) = \#s \times \#t

Deze regel geldt wanneer de verzamelingen eindig zijn, en ze stelt ons in staat om snel het aantal elementen in het cartesisch product van twee verzamelingen te berekenen. Evenzo wordt het aantal elementen in de unie van twee verzamelingen berekend door de formule:

#(s∪t)=#s+#t−#(s∩t)\#(s \cup t) = \#s + \#t - \#(s \cap t)

Dit houdt rekening met de overlap tussen de twee verzamelingen. Als de verzamelingen disjunct zijn, zoals in het geval van de stelling:

#(s∪t)=#s+#t\#(s \cup t) = \#s + \#t

kan de berekening verder vereenvoudigd worden, omdat er geen elementen in beide verzamelingen tegelijkertijd bestaan.

De rekentechnieken worden verder geavanceerd wanneer we werken met fintypes, die eindige typen vertegenwoordigen. Dit stelt ons in staat om complexere structuren zoals direct product, directe som en afbeeldingen van typen te begrijpen. Bijvoorbeeld, de cardinaliteit van het product van twee fintypes wordt gegeven door:

#(α×β)=#α×#β\#(\alpha \times \beta) = \#\alpha \times \#\beta

waarbij α\alpha en β\beta eindige typen zijn. Dezelfde principes kunnen worden toegepast op de directe som van twee fintypes:

#(α⊕β)=#α+#β\#(\alpha \oplus \beta) = \#\alpha + \#\beta

Evenzo wordt de cardinaliteit van een afbeelding van een eindige verzameling onder een injectieve functie ff bepaald door:

#(s.imagef)=#s\#(s.image f) = \#s

waarbij ff een injectieve functie is. Dit houdt in dat de afbeelding van de verzameling ss onder ff dezelfde cardinaliteit heeft als de oorspronkelijke verzameling ss.

Een interessant voorbeeld van het gebruik van deze technieken komt voor wanneer we de cardinaliteit van de verzamelingen willen berekenen die ontstaan door de verschuiving van een reeks. Stel bijvoorbeeld dat we de verzameling nemen van de getallen 0,1,…,n0, 1, \dots, n en de verschuiving ervan met een constante mm. Als we de unie nemen van de oorspronkelijke reeks en de verschoven versie van de reeks, kunnen we de disjunctie van de twee verzamelingen gebruiken om de totale cardinaliteit te berekenen. Dit resulteert in een wiskundige uitdrukking zoals:

#(rangen∪(rangen).image(funi↦m+i))=2n\#(range n \cup (range n).image (fun i \mapsto m + i)) = 2n

In dit geval wordt gebruik gemaakt van de disjunctie van de twee verzamelingen, waarbij de eigenschap van de disjointheid wordt gebruikt om de gewenste uitkomst te verkrijgen.

De structuur van de verzameling kan ook complexer zijn, bijvoorbeeld in het geval van een driehoekige verzameling van de vorm {(i,j)∣i<j}\{ (i, j) \mid i < j \}, die de bovenste driehoek van een vierkant vormt. Het aantal elementen in deze verzameling is gelijk aan:

n(n+1)2\frac{n(n + 1)}{2}

Deze formule kan ook op een alternatieve manier worden berekend door te kijken naar de som van de eerste nn natuurlijke getallen. In beide gevallen toont de berekening het vermogen van combinatorische technieken om de complexe structuren van eindige verzamelingen te begrijpen en te analyseren.

In sommige gevallen kan men de fintypes gebruiken om deze technieken nog verder te generaliseren. Bijvoorbeeld, de equivalentie van twee verschillende benaderingen van de berekening van de driehoekige verzameling kan worden bewezen door gebruik te maken van het concept van isomorfisme van verzamelingen, waarbij een structuur wordt geconstrueerd die de gegevens naar elkaar mappt. Dit kan op elegante wijze worden gedaan met behulp van wiskundige bewijsconstructies zoals Fintype.card_coe, die de cardinaliteit van een subtype berekent.

De toepassingen van deze technieken zijn echter niet beperkt tot abstracte verzamelingen. Ze worden ook toegepast in de grafentheorie en andere vertakkingen van de combinatoriek. Bijvoorbeeld, in de context van bipartiete grafen, waarbij de graaf een set ss van knopen aan de ene kant en een set tt van knopen aan de andere kant heeft, kan de totale aantal randen in de graf worden afgeleid door het tellen van de randen die voldoen aan bepaalde voorwaarden. Als iedere knoop in ss ten minste drie randen heeft en iedere knoop in tt maximaal één rand heeft, dan blijkt uit de stelling dat:

3×#(s)≤#(t)3 \times \#(s) \leq \#(t)

Deze vorm van dubbele telling is een krachtig hulpmiddel om combinatorische beperkingen te begrijpen en te berekenen in grafen en netwerken.

In dergelijke gevallen komt het belang van goed begrijpen van de onderliggende theorie naar voren. De kracht van combinatorische technieken is niet alleen gelegen in de specifieke formules, maar ook in de manier waarop deze formules gecombineerd en aangepast kunnen worden aan een breed scala aan wiskundige en praktische problemen. Het begrijpen van de fundamenten van finsets, fintypes, en de eigenschappen van combinatorische berekeningen biedt een diepere inzicht in de structuren die in veel wiskundige en informatica-toepassingen aan de orde komen.

Hoe kan de calc-syntaxis in Lean bijdragen aan de leesbaarheid en efficiëntie van algebraïsche bewijzen?

In Lean is het gebruik van de calc-syntaxis een manier om bewijzen op een gestructureerde en leesbare manier te formuleren, vooral bij algebraïsche identiteiten. De calc-constructie biedt een alternatief voor de gebruikelijke methode van bewijzen met behulp van de rw (rewrite) tactiek. Waar de rw-tactiek handig is voor het herschrijven van uitdrukkingen met behulp van bekende theorema’s, zoals bijvoorbeeld de distributieve eigenschap van vermenigvuldiging over optelling, maakt de calc-syntaxis het mogelijk om de stappen van een bewijs duidelijker en intuïtiever te presenteren.

Een voorbeeld hiervan is de bewering dat (a+b)×(a+b)=a2+2ab+b2(a + b) \times (a + b) = a^2 + 2ab + b^2. In plaats van het bewijs te bouwen met opeenvolgende herhalingen van de rw-tactiek, kan de calc-structuur het bewijs als volgt presenteren:

csharp
(a + b) * (a + b) = a * a + b * a + (a * b + b * b) := by rw [mul_add, add_mul, add_mul]
  = a * a + (b * a + a * b) + b * b := by rw [← add_assoc, add_assoc (a * a)]
  = a * a + 2 * (a * b) + b * b := by rw [mul_comm b a, ← two_mul]

Dit gebruik van de calc-tactiek maakt het voor de lezer gemakkelijk om de logica van het bewijs stap voor stap te volgen. Het voordeel van deze aanpak is dat het de zinnen in een bewijs niet overbelast, terwijl het nog steeds alle noodzakelijke wiskundige stappen behoudt. De structuur van de calc-tactiek maakt duidelijk hoe elke tussenstap voortbouwt op de vorige, wat helpt bij het begrijpen van de onderliggende algebraïsche transformaties.

Een ander belangrijk voordeel van de calc-syntaxis is de flexibiliteit. Hoewel het mogelijk is om een bewijs volledig te structureren met calc, kan het ook als onderdeel van een grotere bewijstactiek worden gebruikt. In dit geval wordt de calc-expressie niet meteen gebruikt om het doel op te lossen, maar fungeert het als een hulpmiddel om tussenstappen te structureren voordat de bewijsresultaten worden toegepast.

Lean maakt het ook mogelijk om de calc-tactiek te combineren met de sorry-tactiek, wat handig is tijdens de initiële fasen van het formuleren van een bewijs. Het gebruik van sorry stelt je in staat om een bewijs op te stellen zonder onmiddellijk bewijsstappen te verstrekken, wat helpt bij het opschrijven van concepten en argumenten voordat je ze formaliseren kunt.

Bovendien biedt Lean’s nth_rw-tactiek een subtiele variatie op de gebruikelijke rw-tactiek. De nth_rw-tactiek stelt de gebruiker in staat om slechts bepaalde exemplaren van een uitdrukking in een doel te vervangen, wat handig kan zijn in situaties waarin je meerdere keren dezelfde uitdrukking tegenkomt, maar je alleen één specifieke instantie wilt vervangen. Bijvoorbeeld, in een bewijs van (a+b)×(a+b)=a×c+b×c(a + b) \times (a + b) = a \times c + b \times c, kan nth_rw 2 [h] de tweede instantie van a+ba + b vervangen door cc, wat zorgt voor een efficiëntere werkwijze in complexe bewijzen.

Verder is Lean niet alleen geschikt voor bewijzen over concrete wiskundige structuren, maar ook voor abstracte structuren, zoals ringen. Door het gebruik van axioma’s en generieke notaties, kunnen bewijzen over abstracte ringen (bijvoorbeeld de verzameling van natuurlijke getallen, gehele getallen of rationale getallen) systematisch worden opgebouwd. Dit maakt Lean een krachtig hulpmiddel voor het uitvoeren van formele bewijzen binnen verschillende takken van de abstracte algebra.

Het gebruik van de ring-tactiek in Lean is een ander voorbeeld van hoe Lean wiskundige bewijzen kan vereenvoudigen. Deze tactiek is specifiek ontworpen om algebraïsche identiteiten te bewijzen die voortkomen uit de axioma’s van commutatieve ringen. Door simpelweg ring te gebruiken, kan een gebruiker snel bewijsleveren voor identiteiten zoals (a+b)×(a+b)=a2+2ab+b2(a + b) \times (a + b) = a^2 + 2ab + b^2 of (a+b)×(a−b)=a2−b2(a + b) \times (a - b) = a^2 - b^2, zonder de noodzaak om elke stap handmatig te verifiëren. Dit kan bijzonder nuttig zijn bij het werken met meer gecompliceerde algebraïsche structuren, waar de regels en eigenschappen van de ringen automatisch worden toegepast door de ring-tactiek.

Daarnaast is het belangrijk te beseffen dat niet alle eigenschappen die we van de reële getallen kennen, altijd gelden in een willekeurige ring. Bijvoorbeeld, de commutativiteit van vermenigvuldiging die geldt voor de reële getallen, geldt niet noodzakelijk voor alle ringen. Dit betekent dat, hoewel Lean kan helpen bij het bewijzen van feiten over verschillende algebraïsche structuren, de gebruiker goed moet begrijpen welke eigenschappen specifiek zijn voor de ring waarmee wordt gewerkt. In een commutatieve ring, zoals de gehele getallen of de rationale getallen, zullen de meeste klassieke algebraïsche identiteiten wel van toepassing zijn, maar in een niet-commutatieve ring (zoals matrices) kan dit niet altijd het geval zijn.

Lean’s flexibiliteit in het hanteren van zowel concrete als abstracte algebraïsche structuren, samen met de robuuste set van bewijstactieken zoals calc, rw en ring, maakt het tot een krachtig hulpmiddel voor iedereen die diepgaande wiskundige analyses en formele bewijzen wil uitvoeren. Voor de gebruiker is het van essentieel belang om de verschillende tactieken goed te begrijpen en te weten wanneer ze het beste toegepast kunnen worden om efficiënte en leesbare bewijzen te creëren.

Hoe kunnen we het begrip rang en universumhiërarchie in wiskundige structuren formaliseren?

Bij het definiëren van de rang als een kardinaal, begrijpen we dit als een element van de "quotient van de verzameling van types onder de aanwezigheid van een bijectieve equivalentierelatie". Dit lijkt misschien een abstracte definitie, maar het biedt een belangrijke basis voor verdere wiskundige formalismen. In de context van kardinaliteit komen er echter fundamentele problemen naar voren die we elders in dit boek proberen te vermijden, zoals de paradox van Russell. Het idee van een type van alle types leidt namelijk tot logische inconsistenties, en dit probleem kan niet genegeerd worden wanneer we kardinalen bespreken. Dit impliceert dat we, in plaats van een universeel type van alle types te postuleren, moeten werken met een hiërarchie van universa.

Elke verzameling van types heeft een bepaald universeum-niveau, dat zich gedraagt als natuurlijke getallen. Er bestaat bijvoorbeeld een nul-niveau, het universum Type 0, dat simpelweg wordt aangeduid als Type. Dit universum is voldoende om het merendeel van de klassieke wiskunde te bevatten, waarbij bijvoorbeeld de natuurlijke getallen en de reële getallen in Type vallen. Elk niveau uu heeft een opvolger, aangeduid met u+1u + 1, en het universum Type uu heeft type Type (u+1)(u+1). Het is belangrijk te begrijpen dat universeum-niveaus geen natuurlijke getallen zijn; hun aard verschilt wezenlijk. Dit betekent bijvoorbeeld dat we in een formeel systeem zoals Lean niet iets als u≠u+1u \neq u + 1 kunnen stellen, omdat er geen type is waarin deze bewering zinvol zou zijn. In feite is het zelfs onmogelijk om te zeggen dat Type(u)≠Type(u+1)Type(u) \neq Type(u + 1), aangezien Type(u)Type(u) en Type(u+1)Type(u + 1) verschillende types hebben.

Lean biedt een manier om met deze universeum-niveaus om te gaan door de toevoeging van universeum-niveau variabelen. Wanneer we iets als Type∗Type^* schrijven, voegt Lean automatisch een universeum-niveau variabele toe, aangeduid als unu_n, waarbij nn een getal is. Dit maakt het mogelijk om definities en stellingen in meerdere universa te laten bestaan. Wanneer we een universeum-niveau uu hebben, kunnen we een equivalentierelatie definiëren op Type(u)Type(u), waarbij twee types α\alpha en β\beta equivalent zijn als er een bijectie tussen hen bestaat. De quotiënt van deze relatie is de kardinaal Cardinal.{u}Cardinal.\{u\}, dat leeft in Type(u+1)Type(u+1). Het object α:Type(u)\alpha : Type(u) in deze quotiënt wordt aangeduid als Cardinal.mk(α):Cardinal.{u}Cardinal.mk(\alpha) : Cardinal.\{u\}. Dit zorgt ervoor dat we kardinalen kunnen vergelijken binnen hetzelfde universum, maar niet tussen verschillende universa.

Het concept van rang van een vectorruimte, bijvoorbeeld, kan daarom niet eenvoudig gedefinieerd worden als de kardinaliteit van alle types die een basis van de vectorruimte indexeren. In plaats daarvan wordt de rang gedefinieerd als de supremum van de kardinalen van alle lineair onafhankelijke verzamelingen binnen de vectorruimte. Als een vectorruimte VV zich in het universum-niveau uu bevindt, dan heeft zijn rang het type Cardinal.{u}Cardinal.\{u\}.

Er bestaat ook een commutatieve maximumoperatie op universeum-niveaus. Voor twee universeum-niveaus uu en vv bestaat er een operatie Cardinal.lift{u,v}:Cardinal.{v}→Cardinal.{max(v,u)}Cardinal.lift^{\{u, v\}} : Cardinal.\{v\} \to Cardinal.\{max(v, u)\} die het mogelijk maakt om kardinalen in een gemeenschappelijk universum te plaatsen. Dit vergemakkelijkt het formuleren van de dimensietheorie. Met behulp van de coercie van natuurlijke getallen naar eindige kardinalen kunnen we de eindige dimensionale gevallen aan deze discussie koppelen. Zo wordt het mogelijk om te stellen dat in eindig-dimensionale gevallen de finitaire rang gelijk is aan de rang.

Hoewel deze theorie abstract is, biedt ze krachtige methoden voor het omgaan met kardinalen en rang binnen een formeel wiskundig systeem zoals Lean. Dit voorkomt de inconsistente logica die zou voortkomen uit het idee van een universeel type en stelt ons in staat wiskundige structuren in meerdere niveaus van abstractie te begrijpen en te vergelijken.

De natuur van universeum-niveaus is cruciaal voor het begrijpen van de manier waarop wiskundige objecten op verschillende niveaus worden geformaliseerd. Dit idee van een hiërarchie van universa stelt wiskundigen in staat om de fundamenten van de verzamelingenleer, lineaire algebra en andere takken van de wiskunde te behouden zonder de logische inconsistenties die zouden optreden in een theorie die probeert te werken met een universeel type van alle types. In veel toepassingen van de moderne wiskunde, vooral in de formele systemen, wordt dit hiërarchische model gebruikt om te werken met abstracties die anders moeilijk hanteerbaar zouden zijn.

Het begrip van rang en de manier waarop kardinalen zich verhouden tot universa, vormt een essentieel onderdeel van de formele benadering van wiskundige objecten, vooral wanneer we werken met systemen zoals Lean. Dit stelt ons in staat om wiskundige structuren op een consistente en formele manier te definiëren, wat een fundamenteel verschil maakt in vergelijking met meer informele wiskundige benaderingen.

Hoe evolueerde het politiewerk en de handhaving van de wet?
Hoe voorspellen we warmteoverdrachtscoëfficiënten bij het koken van verdunde emulsies in microkanalen?
Hoe Liquid Crystals de Technologie en Materialen Beïnvloeden
Hoe Vrouwen Zichzelf Herdefiniëren in een Veranderende Wereld