Hoe definieer je de norme en deling van Gaussian Integers in formele wiskunde?

We beginnen met het definiëren van twee belangrijke elementen van de Gaussian integers: de norme en de deling. Beschouwen we q = u + vi en r = (c + di)(u′ + v′i), dan krijgen we a + bi = (c + di)q + r, en moeten we de norme van r begrenzen. De norme, N(r), voldoet aan de relatie:

Het argument dat hier wordt gepresenteerd vereist dat we de Gaussian integers beschouwen als een deelverzameling van de complexe getallen. Dit kan formeel worden uitgevoerd door de Gaussian integers in de complexe getallen in te voegen, de gehele getallen in de Gaussian integers in te voegen, de afrondingsfunctie van de reële getallen naar de gehele getallen te definiëren en zorgvuldig om te gaan met de overgang tussen deze getalsystemen. Dit is precies de aanpak die wordt gevolgd in de Mathlib, waar de Gaussian integers zelf worden geconstrueerd als een speciaal geval van een ring van kwadratische getallen. In plaats van deze benadering, wordt in dit hoofdstuk echter een argument gepresenteerd dat zich beperkt tot de gehele getallen.

Dit benadrukt een keuze die vaak gemaakt moet worden bij het formaliseren van wiskunde. Wanneer een argument concepten of gereedschappen vereist die nog niet in de bibliotheek aanwezig zijn, heeft men twee keuzes: ofwel de benodigde concepten en gereedschappen formaliseren, ofwel het argument aanpassen zodat het gebruik maakt van de reeds aanwezige concepten en gereedschappen. De eerste keuze is doorgaans een goede investering van tijd, wanneer de resultaten ook in andere contexten bruikbaar zijn. Pragmatisch gezien kan het echter soms efficiënter zijn om een meer elementair bewijs te zoeken.

Het klassieke kwotient-reststelling voor de gehele getallen zegt dat voor elke a en een niet-nul b, er q en r bestaan, zodat:

In dit geval wordt echter een variant gebruikt, die stelt dat er q′ en r′ bestaan, zodat:

$a = bq′ + r′ \quad \text{en} \quad |r′| \leq \frac{b}{2}$

We definiëren de functies div' en mod' voor deling en rest bij gehele getallen. Voor elke a en b geldt dat:

Met behulp van de bovenstaande definities kunnen we het volgende bewijs uitvoeren:

Dit bewijs is afhankelijk van de eigenschap van de gehele deling en modulo-operaties en kan in de vorm van Lean als volgt worden geschreven:

Nu moeten we enkele eigenschappen van de norme definiëren en bewijzen. De norme van een Gaussian integer is de som van de kwadraten van de reële en imaginaire delen. We hebben:

Bijvoorbeeld, we kunnen bewijzen dat de norme altijd niet-negatief is en dat de norme van nul alleen nul is:

Verder kunnen we het bewijs uitvoeren dat de norme van een product van twee Gaussian integers gelijk is aan het product van hun normen:

Daarna definiëren we de complex geconjugeerde van een Gaussian integer. Als x = a + bi, dan is de geconjugeerde van x gelijk aan a − bi. De norme van de geconjugeerde van een getal is gelijk aan de norme van het oorspronkelijke getal:

Ten slotte definieert men de deling van Gaussian integers. De deling van een Gaussian integer x door een andere y wordt als volgt gedefinieerd:

Dit zorgt ervoor dat de delen van x en y op de juiste manier worden afgerond naar de dichtstbijzijnde Gaussian integers. De rest wordt vervolgens gedefinieerd als:

Deze formules kunnen eenvoudig worden omgezet in formele wiskundige beweringen, zoals:

En tenslotte, het bewijs dat de norme van de rest kleiner is dan de norme van y, geeft ons de noodzakelijke gereedschappen om de theorie van Gaussian integers verder te ontwikkelen en in wiskundige software te implementeren.

Er is echter nog iets belangrijks om in gedachten te houden bij het werken met deze getallen. Terwijl de definities en het bewijs hierboven belangrijk zijn voor het begrijpen van de eigenschappen van Gaussian integers, is het belangrijk om te beseffen dat de afstemming van formalisme met intuïtief begrip cruciaal is bij de toepassing van dergelijke theorieën in andere gebieden van de wiskunde, zoals algebraïsche getallen en analytische functies.

Hoe werkt de extends-syntaxis in Lean voor algebraïsche structuren?

In de wereld van de formele wiskunde en type-theorie biedt Lean een krachtige manier om algebraïsche structuren te definiëren. De extends-syntaxis speelt hierbij een cruciale rol, door het mogelijk te maken verschillende structuren te combineren zonder herhaling van code of het verlies van symmetrie. Het idee van het uitbreiden van klassen en structuren is essentieel voor het beheren van de complexiteit van algebraïsche objecten zoals groepen, ringen en monoid-structuren.

Neem bijvoorbeeld de structuur van een semigroep, die in Lean als volgt wordt gedefinieerd:

lean
Copy code
class Semigroup2 (α : Type) extends Dia1 α where

  dia_assoc : ∀ a b c : α, a  b  c = a  (b  c)

In dit geval hebben we een Semigroup2 die de associativiteit van de bewerking  garandeert. Het gebruik van extends Dia1 α betekent dat de semigroep de eigenschappen van de Dia1-structuur overneemt, zonder dat we die expliciet opnieuw hoeven te definiëren. Dit is een van de voordelen van het gebruik van de extends-syntaxis in Lean: we kunnen bestaande structuren hergebruiken en uitbreiden, wat de efficiëntie van onze code verhoogt.

Laten we verder gaan met het combineren van een diamant-operatie met een neutraal element. In de structuur DiaOneClass1, waarin zowel de eigenschappen van de One1- als de Dia1-structuur worden gecombineerd, worden de eigenschappen van het neutrale element gedefinieerd:

lean
Copy code
class DiaOneClass1 (α : Type) extends One1 α, Dia1 α where

  one_dia : ∀ a : α, 1  a = a
  dia_one : ∀ a : α, a  1 = a

Hier wordt een element 1 geïntroduceerd, dat zowel aan de linker- als de rechterkant neutraal is voor de diamantbewerking. Het gebruik van extends One1 α, Dia1 α is weer een voorbeeld van hoe we twee verschillende structuren combineren zonder redundantie in de definitie.

lean
Copy code
class Monoid1 (α : Type) extends Semigroup1 α, DiaOneClass1 α

Er is echter een subtiele valkuil die zich voordoet wanneer we structuren zoals een monoid proberen te definiëren zonder de extends-syntaxis te gebruiken. In plaats van de samengestelde structuren automatisch te combineren, moeten we handmatig velden definiëren, wat kan leiden tot verwarring en ongewenste duplicatie van operaties. Dit wordt duidelijk als we proberen een monoid te definiëren zonder gebruik te maken van extends:

lean
Copy code
class Monoid2 (α : Type) where
  toSemigroup1 : Semigroup1 α
  toDiaOneClass1 : DiaOneClass1 α

Als we verder gaan met het definiëren van groepen, kunnen we de monoidstructuur uitbreiden door een inversie-operatie toe te voegen:

lean
Copy code
class Inv1 (α : Type) where
  inv : α → α

Vervolgens kunnen we een groep definëren door de Monoid1- en Inv1-structuren te combineren, waardoor we een groep krijgen waarin elk element een inverse heeft:

lean
Copy code
class Group1 (G : Type) extends Monoid1 G, Inv1 G where

  inv_dia : ∀ a : G, a ¹  a = 1

Een belangrijk detail is dat we hier de inversie-operatie als een apart gegeven toevoegen. Het is van belang te begrijpen dat in Lean, zoals in veel formele systemen, de noodzaak om extra structuren toe te voegen (zoals een inverse in een groep) vaak het gevolg is van de beperkingen van de formele taal en de manier waarop Lean zijn type-systeem organiseert. Dit is waarom het vaak praktischer is om deze extra gegevens als 'data' te behandelen in plaats van ze direct in de structuur op te nemen.

Als we nu de complexiteit verder willen uitbreiden naar ringen, komt er een extra uitdaging bij kijken. Een ring bevat zowel een additieve groepstructuur als een multiplicatieve monoidstructuur, en de interactie tussen deze twee structuren moet expliciet worden gedefinieerd. In plaats van één enkele bewerking, zoals we eerder hadden voor de monoid, moeten we beide bewerkingen (optelling en vermenigvuldiging) combineren, wat betekent dat we de juiste notatie en structuur voor zowel de additieve als de multiplicatieve theorieën moeten beheren.

Om deze uitdaging aan te gaan, maakt Lean gebruik van een techniek waarbij structuren worden gedupliceerd voor zowel de additieve als de multiplicatieve gevallen, met behulp van een to_additive-attribuut. Hierdoor kunnen we structuren zoals een additieve semigroep en een multiplicatieve semigroep definieëren met dezelfde onderliggende eigenschappen, wat de herbruikbaarheid van onze code vergemakkelijkt.

Het is belangrijk te begrijpen dat de extends-syntaxis en de bijbehorende methoden zoals to_additive niet alleen de leesbaarheid van de code verbeteren, maar ook bijdragen aan de modulariteit en herbruikbaarheid van algebraïsche structuren in formele systemen. Het correct gebruiken van deze technieken kan de complexiteit van de definities aanzienlijk verminderen en zorgt ervoor dat structuren flexibel en uitbreidbaar blijven zonder dat er redundant werk nodig is.

Hoe de Hiërarchie van Wiskundige Structuren en Morfismen in Lean Werkt

In wiskundige systemen, zoals de wiskundige bibliotheek Mathlib van Lean, vormen hiërarchieën van wiskundige structuren de kern van veel toepassingen. Een cruciaal onderdeel van deze structuren is de manier waarop we ze definiëren en relateren aan elkaar, bijvoorbeeld door het gebruik van modules, groepen, ringen en morfismen. Dit proces is van groot belang voor het correct modelleren van wiskundige concepten, en het begrijpen van de onderliggende principes kan leiden tot een dieper inzicht in de algebraïsche systemen.

Dit fenomeen wordt in de Lean-gemeenschap aangeduid als een 'bad diamond'. Het idee hier is dat er meerdere paden bestaan die naar dezelfde structuur leiden, maar die niet definitioneel gelijk zijn. In dit geval heeft de 'bad diamond' betrekking op het verschil in de manier waarop de scalairvermenigvuldiging (smul) wordt gedefinieerd voor de verschillende structuren. De juiste aanpak om dit probleem te verhelpen, is door een structuur te definiëren die expliciet aangeeft hoe deze operaties worden 'vergeten' wanneer men van een rijke naar een armere structuur overgaat. Dit wordt vaak aangeduid als 'forgetful inheritance', een welbekende techniek in de formele wiskundige theorieën die in Lean worden toegepast. In de praktijk betekent dit dat we gegevens kunnen 'vergeten' wanneer we een structuur vereenvoudigen, waardoor we onverwachte conflicten kunnen vermijden.

Het is belangrijk om te begrijpen dat deze techniek niet beperkt is tot de basisstructuren die we tot nu toe hebben besproken. In feite komt de techniek van forgetful inheritance op allerlei niveaus voor in Mathlib, en in grotere en complexere structuren zoals groepen, ringen en modules wordt deze benadering op vergelijkbare manieren toegepast. Het uiteindelijk doel is om ervoor te zorgen dat het systeem robuust blijft, zelfs wanneer het met steeds complexere en rijkere structuren werkt.

Bij het definiëren van deze structuren, moeten we ook morfismen in overweging nemen. Morfismen zijn de functies die structuren met elkaar verbinden, en de manier waarop ze worden gedefinieerd is van groot belang voor de opbouw van wiskundige theorieën in Lean. Er zijn verschillende manieren om morfismen te definiëren, afhankelijk van de context. De meest directe benadering is het definiëren van een predicaat voor functies, zoals in het geval van monoid-homomorfismen. Dit predicaat stelt ons in staat te zeggen wanneer een functie tussen twee monoid-structuren een geldige homomorfisme is. Het gebruik van structuren en predicaten om morfismen te definiëren, is een krachtig hulpmiddel in Lean, maar het roept ook interessante filosofische vragen op over hoe we structuren en hun relaties het beste kunnen modelleren.

In sommige gevallen is het handig om morfismen als structuren te bundelen, zoals bijvoorbeeld het bundelen van een monoid-homomorfisme in een structuur die zowel de functie als de bijbehorende voorwaarden bevat. Dit biedt een meer robuuste en flexibele manier om te werken met algebraïsche structuren. Bovendien, door de CoeFun-klasse te gebruiken, kunnen we functies die bij structuren horen, op een elegante manier behandelen, zodat de technische details van de coercie bijna onzichtbaar worden voor de gebruiker.

Bij het werken met deze structuren en morfismen in Lean, is het essentieel te begrijpen dat het proces van instance-resolutie en de keuze van de juiste definities van grote invloed zijn op de prestaties en de juistheid van de resultaten. Het is daarom belangrijk om zorgvuldig te overwegen hoe structuren en hun morfismen worden gedefinieerd en om te zorgen voor consistente en goed gedefinieerde methoden voor het overdragen van gegevens en operaties tussen verschillende niveaus van de hiërarchie.

Het begrijpen van de onderliggende mechanismen van deze systemen helpt niet alleen bij het oplossen van technische problemen in de wiskundige modellering, maar stelt de gebruiker ook in staat om wiskundige theorieën op een meer geavanceerd en georganiseerde manier te benaderen. Het is een continu proces van verfijning, waarin men steeds meer inzicht krijgt in de subtiele interacties tussen structuren, morfismen en hun onderlinge relaties. De methoden die in Lean worden gebruikt, bieden niet alleen krachtige tools voor formeel bewijs, maar ook waardevolle lessen voor het werken met wiskundige concepten in het algemeen.

Wat is het quotientsysteem van submodulen en lineaire afbeeldingen?

Een cruciaal aspect van het werken met quotientruimten is de zogenaamde universele eigenschap, die een belangrijk instrument biedt voor het begrijpen van lineaire afbeeldingen tussen verschillende ruimten. De functie $\text{Submodule.mkQ}$ is de bijbehorende lineaire afbeelding die de quotientruimte $V / E$ naar $V$ mappt, terwijl $\text{Submodule.liftQ}$ de universele eigenschap levert voor het construeren van lineaire afbeeldingen van de quotientruimte naar andere modulestructuren. Dit leidt ons naar de fundamentele stellingen over het kern- en bereikgedrag van deze operaties.

Naast de basiseigenschappen van quotientruimten, spelen de kern en het bereik van lineaire afbeeldingen een cruciale rol bij het formuleren van belangrijke theorema’s in de lineaire algebra. Bijvoorbeeld, de kernel van een lineaire afbeelding $\varphi$ is de verzameling van elementen in de vectorruimte die onder $\varphi$ naar de nulvector gaan. Voor een lineaire afbeelding van $V$ naar een andere module $W$, kunnen we werken met de comap en map functies zoals gedefinieerd in de algebraïsche theorie. Dit biedt een krachtige manier om de structuur van subruimten te analyseren door de bijbehorende quotientruimten en afbeeldingen van de oorspronkelijke ruimte naar andere ruimten te bestuderen.

In de context van eindomorfismen biedt de theorie van eigenspaces en eigenwaarden een dieper inzicht in de structurele eigenschappen van lineaire afbeeldingen. De eigenspace van een eindomorfisme $\varphi$ voor een eigenwaarde $a$ is de kernel van $\varphi - aI$, waarbij $I$ de identiteit is. Dit is een cruciaal concept omdat de eigenspace de verzameling van eigenvectoren bevat die corresponderen met een specifieke eigenwaarde. Eigenspaces zijn belangrijk voor het begrijpen van de dynamica van lineaire transformaties, omdat de eigenvectoren de invarianten van de eindomorfismen zijn.

Wanneer we verder gaan in het bestuderen van quotientruimten en eindomorfismen, moeten we niet alleen naar de abstracte theorie kijken, maar ook de praktische implicaties begrijpen voor het oplossen van lineaire systemen en het analyseren van de stabiliteit van dynamische systemen.