Hoe Werkt de Existentiële Kwantor in Lean?

In Lean gebruiken we de existentiële kwantor, weergegeven als $\exists$, om te zeggen: "er bestaat". De formele expressie $\exists x : \mathbb{R}, 2 < x \land x < 3$ in Lean betekent dat er een reëel getal tussen 2 en 3 bestaat. De gebruikelijke manier om een dergelijk statement te bewijzen, is door een specifiek reëel getal te tonen en aan te tonen dat het voldoet aan de gestelde eigenschap. Het getal 2.5 voldoet aan de eis, en de norm_num tactiek kan bewijzen dat het aan de beschrijving voldoet.

lean
Copy code
example : ∃ x : R, 2 < x ∧ x < 3 := by use 5 / 2 norm_num

Hier geven we met "use" het getal 5/2 op, wat voldoet aan de vereiste eigenschappen, en vervolgens wordt de bewijslast afgerond door de tactiek "norm_num", die de numerieke eigenschappen controleert.

lean
Copy code
example : ∃ x : R, 2 < x ∧ x < 3 := by have h1 : 2 < (5 : R) / 2 := by norm_num
    have h2 : (5 : R) / 2 < 3 := by norm_num
    use 5 / 2, h1, h2

Een alternatieve manier om een bestaand object te gebruiken, is via Lean’s anonieme constructeurnotatie. Dit wordt bijvoorbeeld als volgt gebruikt:

lean
Copy code
example : ∃ x : R, 2 < x ∧ x < 3 := 〈5 / 2, by norm_num〉

In deze versie van het bewijs gebruiken we geen "by", maar geven we de volledige bewijsconstructie direct aan. Dit is handig wanneer we op een beknopte manier bewijs willen leveren zonder tussenstappen.

lean
Copy code
def FnUb (f : R → R) (a : R) : Prop := ∀ x, f x ≤ a
def FnHasUb (f : R → R) := ∃ a, FnUb f a

In de praktijk kan de existentiële kwantor vaak worden gebruikt om de eigenschappen van functies of objecten in een wiskundige structuur te onderzoeken. Wanneer we weten dat er een object bestaat dat een bepaalde eigenschap heeft, kunnen we dit object een naam geven en ermee werken, zoals in het geval van de bovengrens van functies. Dit wordt vaak gedaan met de tactieken zoals "rcases", die de informatie in de existentiële kwantor "uitpakken", waardoor we toegang krijgen tot de specifieke eigenschappen van het object.

Bijvoorbeeld, stel dat we twee functies $f$ en $g$ hebben die beide een bovengrens hebben. We kunnen de eigenschap van hun som als volgt bewijzen:

lean
Copy code
example (ubf : FnHasUb f) (ubg : FnHasUb g) : FnHasUb fun x 7→ f x + g x := by rcases ubf with 〈a, ubfa〉

    rcases ubg with 〈b, ubgb〉
    use a + b
    apply fnUb_add ubfa ubgb

In dit bewijs gebruiken we de tactiek "rcases" om de bovengrenzen van $f$ en $g$ uit te pakken en deze te combineren om de bovengrens van hun som te bewijzen. Dit is een gebruikelijke methode in de wiskunde: het unpacken van informatie waarvan we weten dat het bestaat, om vervolgens verder te redeneren over de nieuwe situatie.

Het gebruik van de existentiële kwantor is van fundamenteel belang voor veel wiskundige redeneringen, en Lean biedt verschillende krachtige manieren om hiermee om te gaan. De combinatie van "rcases", "rintro", en "obtain" zijn de meest voorkomende manieren om met existentiële uitspraken in Lean te werken. Bovendien ondersteunt Lean ook pattern matching, wat overeenkomt met de technieken die in de functionele programmeertalen worden gebruikt. Dit biedt niet alleen een praktische manier van redeneren, maar helpt ook om complexe wiskundige uitspraken te structureren en te bewijzen.

Een essentieel punt bij het gebruik van de existentiële kwantor is dat het ons in staat stelt om te redeneren over het bestaan van objecten zonder deze objecten expliciet te moeten identificeren. Dit maakt het een krachtig hulpmiddel in veel verschillende wiskundige contexten.

Hoe de Keuze Axioma en Inverse Functies de Grondslagen van Wiskundige Formele Bewijzen Beïnvloeden

In de wiskundige logica en formele systemen zoals Lean, komt het idee van inverse functies vaak naar voren, vooral wanneer de betrokken functies injectief of surjectief zijn. Dit is een bijzonder gebied van studie, waarin de integratie van klassieke logica, zoals het keuze axioma, cruciaal is voor het definiëren en werken met inverse functies. In dit hoofdstuk zullen we niet alleen de technische aspecten van inverse functies verkennen, maar ook de fundamentele rol van de keuzeoperator en de noodzaak voor onberekenbaarheid in bepaalde gevallen.

Een van de fundamentele uitdagingen bij het definiëren van een inverse functie is dat we, in het geval van surjectiviteit, een element $x \in \alpha$ moeten vinden voor een gegeven $y \in \beta$ zodat $f(x) = y$. Dit vereist een beroep op het keuze axioma, een principe uit de klassieke logica dat stelt dat als er voor elke element in een verzameling een keuze kan worden gemaakt, deze keuze altijd kan worden gemaakt, zelfs als de verzameling eindig of oneindig is. In Lean wordt dit bereikt door gebruik te maken van de klassieke keuzeoperator, Classical.choose, die een element selecteert uit een niet-lege verzameling. Deze operator wordt gebruikt om de waarde van $x$ te bepalen, waarvoor geldt dat $f(x) = y$.

De formele definitie van een inverse functie binnen Lean is dan als volgt:

lean
Copy code
noncomputable section

open Classical
def inverse (f : α → β) : β → α :=
  fun y : β → 
    if h : ∃ x, f x = y then Classical.choose h else default

Hier definieert inverse f y de inverse functie voor een gegeven $y$. Als er een $x$ bestaat zodanig dat $f(x) = y$, wordt dat $x$ gekozen door Classical.choose h. Anders wordt een standaardwaarde uit $\alpha$ geretourneerd. Het gebruik van de noncomputable sectie en de klassieke logica is nodig omdat de keuzeoperator niet altijd computabel is. Dit betekent dat de keuze van $x$ kan afhangen van niet-berekenbare keuzes, die fundamenteel zijn voor dit soort formaliseringen.

De Classical.choose_spec geeft aan dat de gekozen waarde $x$ altijd voldoet aan de voorwaarden van de oorspronkelijke stelling. Dit zorgt ervoor dat de inverse functie altijd een geldig element kiest wanneer dit mogelijk is.

Wat betreft de injectiviteit en surjectiviteit van een functie, worden de eigenschappen van de inverse functie als volgt beschreven:

• Een functie heeft een linksinversie als en alleen als deze injectief is.

• Een functie heeft een rechtse inversie als en alleen als deze surjectief is.

Deze concepten kunnen gemakkelijk in Lean worden geformaliseerd, waarbij de gebruikelijke eigenschappen van injectieve en surjectieve functies worden onderzocht. De stellingen die deze relaties aantonen kunnen als volgt worden geformuleerd:

lean
Copy code
example : Injective f ↔ LeftInverse (inverse f) f := sorry

example : Surjective f ↔ RightInverse (inverse f) f := sorry

Daarnaast introduceren we in deze context de beroemde Cantor's Theorem, die stelt dat er geen surjectieve functie bestaat van een verzameling naar de machtsverzameling van die verzameling. Dit is een fundamenteel resultaat in de verzamelingenleer en wordt als volgt geformaliseerd in Lean:

lean
Copy code
theorem Cantor : ∀ f : α → Set α, ¬Surjective f := by

  intro f surjf
  let S := { i | i ∈/ f i }
  rcases surjf S with 〈j, h〉
  have h1 : j ∈/ f j := by intro h'
  have : j ∈/ f j := by rwa [h] at h' contradiction
  have h2 : j ∈ S sorry
  have h3 : j ∈/ S sorry
  contradiction

Deze stelling toont aan dat er geen surjectieve functie kan bestaan van een verzameling naar zijn machtsverzameling. Het bewijs vereist een subtiele redenering en toont aan hoe fundamentele logische principes, zoals de ontkenning van de surjectiviteit van een functie, in formele systemen kunnen worden behandeld.

De manier waarop de stelling van Schröder-Bernstein wordt geformaliseerd in Lean maakt gebruik van de techniek van het samenstellen van functies en het definieren van een bijectie door een combinatie van injectieve functies en inverse functies. De bijbehorende definitie wordt als volgt gepresenteerd:

lean
Copy code
def sbFun (x : α) : β :=

  if x ∈ sbSet f g then f x else invFun g x

Dit resultaat bouwt voort op de concepten van injectieve en surjectieve functies en illustreert de kracht van formele wiskundige systemen in Lean bij het bewijzen van zulke fundamentele theorema’s.

Belangrijk voor de lezer is te begrijpen dat de werking van inverse functies niet alleen afhankelijk is van de abstracte wiskundige principes, maar ook van de formele logica die eraan ten grondslag ligt. De keuze van een element uit een verzameling, bijvoorbeeld via de keuzeoperator, is essentieel voor de validiteit van inverse functies in formele systemen. In de praktijk wordt dit vaak over het hoofd gezien, maar het heeft grote implicaties voor de computability van wiskundige constructies. Het is ook van belang om te erkennen dat de formaliteit van de bewijsvoering ons niet alleen helpt de resultaten te begrijpen, maar ons ook in staat stelt om wiskundige concepten op een volledig rigoureuze manier te hanteren.

Hoe Bewijs je Eigenschappen van de Fibonacci-reeks met Inductie in Lean?

Een veelvoorkomende eigenschap van de Fibonacci-reeks die we willen bewijzen, is de identiteit tussen opeenvolgende Fibonacci-getallen. Het volgende bewijs toont aan dat twee opeenvolgende Fibonacci-getallen relatief priem zijn, oftewel hun grootste gemene deler is 1:

lean
Copy code
theorem fib_coprime_fib_succ (n : N) : Nat.Coprime (fib n) (fib (n + 1)) :=
by induction n with
| zero => simp
| succ n ih => simp only [fib, Nat.coprime_add_self_right] exact ih.symm

Naast het gebruik van inductie, kan Lean ook geoptimaliseerde rekenkundige definities gebruiken om de Fibonacci-getallen snel te berekenen. De directe implementatie van de Fibonacci-functie in Lean is echter zeer inefficiënt, omdat deze exponentieel in de tijd groeit ten opzichte van het argument. Dit kan eenvoudig verklaard worden door te kijken naar de recursieve structuur van de functie.

Om deze inefficiëntie te verhelpen, kunnen we een staartrecursieve versie van de Fibonacci-functie implementeren, die de berekening in lineaire tijd uitvoert:

lean
Copy code
def fib' (n : Nat) : Nat := aux n 0 1

where
  aux | 0, x, _ => x
      | n+1, x, y => aux n y (x + y)

Dit verbetert de prestaties drastisch door de recursie op te slaan in twee variabelen, waardoor het geheugenverbruik en de tijdcomplexiteit verminderen. Het bewijs dat deze functie hetzelfde resultaat oplevert als de oorspronkelijke Fibonacci-functie wordt ook gegeven door inductie, waarbij we aantonen dat de helperfunctie aux dezelfde waarden produceert als de reguliere Fibonacci-functie:

lean
Copy code
theorem fib'_eq_fib : fib' = fib :=

by ext n erw [fib', fib'.aux_eq 0 n]; rfl

Bij het werken met inductie in Lean wordt vaak de generalizing-tactiek gebruikt, die een extra variabele in de inductieve hypothese introduceert, wat handig is wanneer we te maken hebben met functies die meerdere parameters vereisen. Dit zorgt ervoor dat de inductie niet alleen over de belangrijkste variabele gaat, maar over de gehele structuur van de functie.

Naast deze basale inductie-toepassingen kunnen we ook meer geavanceerde resultaten bewijzen, zoals de eigenschap van priemgetallen. De stelling hieronder stelt dat elk natuurlijk getal $n \neq 1$ een priemdivisie heeft. Het bewijs maakt gebruik van een inductieve aanpak, waarbij we de stelling zelf in zijn bewijs gebruiken:

lean
Copy code
theorem ne_one_iff_exists_prime_dvd : ∀ {n}, n ≠ 1 ↔ ∃ p : N, p.Prime ∧ p | n :=

by induction n with
| zero => simpa using Exists.intro 2 Nat.prime_two
| n + 2 => by have hn : n+2 ≠ 1 := by omega simp only [Ne, not_false_iff, true_iff, hn]

Dit bewijs toont aan hoe we inductie kunnen combineren met bekende eigenschappen van priemgetallen om een bewijs op te bouwen, waarbij Lean in staat is om een eerdere stelling opnieuw toe te passen in de inductieve stap.

Naast de toepassing van inductie is het belangrijk om te begrijpen dat Lean’s mechanismen voor recursieve definities van functies voldoende flexibel zijn om arbitraire recursieve oproepen toe te staan, zolang de complexiteit van de argumenten afneemt volgens een goed-onderbouwde maat. Dit maakt Lean tot een krachtig hulpmiddel voor het bewijzen van eigendommen van recursieve functies en het vaststellen van getaltheoretische stellingen.

Voor de lezer is het van belang te begrijpen dat inductie in Lean niet slechts een mechanisch proces is, maar een manier om wiskundige structuren formeel te begrijpen en vast te leggen. Het vermogen om recursieve functies efficiënt te definiëren en te bewijzen, evenals de kracht van inductie in het vaststellen van eigenschappen van getallenreeksen zoals de Fibonacci-reeks, is cruciaal voor het gebruik van Lean in de wiskunde en de getaltheorie.

Hoe de hiërarchie van morfismen in Lean werkt en de uitdagingen van coërcies

De basis van veel wiskundige theorieën is het gebruik van morfismen, die algebraïsche structuren met elkaar verbinden. In Lean, een geavanceerde wiskundige logica en bewijsassistent, wordt deze verbinding vaak uitgedrukt door middel van gemoduleerde structuren zoals monoid- en ringhomomorfismen. Wanneer we werken met deze structuren, moeten we rekening houden met de manier waarop Lean omgaat met coërcies en het correct toepassen van lemmata die betrekking hebben op deze morfismen.

Een eenvoudig voorbeeld is het concept van een monoid-homomorfisme, gedefinieerd als een functie tussen twee monoid-structuren die de monoidbewerking respecteert. Dit kan worden weergegeven met de structuur MonoidHom1, die in Lean als volgt wordt gedefinieerd: het bevat een functie toFun die de elementen van de eerste monoid naar de tweede monoid afbeeldt, en twee belangrijke eigenschappen: de afbeelding van het neutrale element is ook het neutrale element, en de afbeelding van het product van twee elementen is gelijk aan het product van de afbeeldingen van die elementen.

Er is echter een probleem dat snel opduikt wanneer we deze concepten in Lean willen uitbreiden naar meer geavanceerde structuren, zoals ringen. Het belangrijkste probleem is dat de lemmas die we definiëren voor monoid-homomorfismen niet direct toepasbaar zijn op ringhomomorfismen, omdat ringhomomorfismen een extra structuur (de optelling) vereisen. Een manier om dit te omzeilen is door een nieuwe typeklasse te introduceren, die de concepten van zowel monoid- als ringhomomorfismen omvat. Deze typeklasse, genaamd MonoidHomClass1, biedt een gemeenschappelijk raamwerk waarmee we lemmata kunnen definiëren die zowel voor monoid- als ringhomomorfismen gelden.

Dit vereist echter enige zorgvuldigheid in de manier waarop we coërcies (zoals de conversie van een homomorfisme naar een functie) behandelen. In de initiële benadering die in Lean werd geprobeerd, werd het MonoidHomClass1 gebruikt om een coërcie te creëren, maar dit leidde tot problemen bij het afleiden van de juiste instantiaties van de coërcie. De oplossing was het gebruik van de outParam functie, die ervoor zorgt dat Lean eerst de specifieke klasse van het homomorfisme bepaalt (bijvoorbeeld of het een monoid- of ringhomomorfisme is) en vervolgens de onderliggende monoid- of ringstructuren afleidt.

Deze oplossing, hoewel effectief, brengt een ander probleem met zich mee: de repetitieve code die nodig is om de toFun-functie en de bijbehorende coërcie- en coërcie-attributen te definiëren. Dit is opgelost door een extra abstractielaag toe te voegen met de DFunLike klasse. Deze klasse maakt het mogelijk om functies te behandelen die afhankelijk zijn van een extra parameter (zoals de monoid- of ringstructuur) en garandeert dat de coërcie-instantie injectief is, wat essentieel is om ambiguïteit bij het toewijzen van coërcies te voorkomen.

Naast deze technische aspecten is het belangrijk te begrijpen hoe Lean de hiërarchie van morfismen beheert en hoe dit bijdraagt aan de modulariteit en herbruikbaarheid van wiskundige bewijsvoering. Lean biedt een krachtig mechanisme voor het definiëren van abstracte wiskundige structuren, maar het vereist zorgvuldigheid bij het ontwerpen van deze structuren om fouten zoals de bovengenoemde te vermijden. Het correct toepassen van coërcies en het beheren van abstracties in Lean is een essentieel onderdeel van het werken met complexe wiskundige objecten en hun relaties.

De wiskundige structuren die we in Lean definiëren, zijn vaak niet alleen formele vertalingen van wiskundige concepten, maar vormen de basis voor verdere constructies en bewijsvoering. Het is cruciaal om te begrijpen dat, hoewel de syntaxis en semantiek van Lean de formele kracht en precisie van de wiskundige theorieën ondersteunt, het tegelijkertijd de noodzaak van zorgvuldig ontworpen abstracties benadrukt. Het doorgronden van de nuances van de typeklasse-hiërarchieën en coërcies in Lean kan helpen bij het ontwikkelen van meer robuuste en flexibele wiskundige modellen.

Wat zijn metrische ruimten en waarom zijn ze belangrijk voor topologie?

In de context van metrische ruimten kunnen open en gesloten verzamelingen gedefinieerd worden aan de hand van bollen. Dit is een fundamenteel concept in de topologie van metrische ruimten. Bollen worden gedefinieerd door een straal die een bepaalde afstand ten opzichte van een centraal punt geeft. Er zijn zowel open als gesloten bollen, afhankelijk van of de rand van de verzameling wordt meegenomen. Een gesloten bol rond een punt $a$ met straal $r$, bijvoorbeeld, omvat alle punten $b$ waarvoor de afstand $\text{dist}(b, a)$ kleiner dan of gelijk aan $r$ is. Dit is wiskundig uitgedrukt als:

In dit geval is $r$ een willekeurig reëel getal, zonder restricties op het teken. Er zijn echter gevallen waarin een specifieke voorwaarde voor de straal noodzakelijk is, zoals in de volgende voorbeelden. Als de straal groter dan nul is, dan geldt bijvoorbeeld dat het punt $a$ altijd binnen de bol ligt:

Als de straal nul of groter is, geldt iets vergelijkbaars voor de gesloten bol:

Compactheid is een ander cruciaal concept in de topologie, vooral in metrische ruimten. Compacte verzamelingen hebben verschillende eigenschappen die ze onderscheiden van andere verzamelingen, zoals het feit dat elke reeks van punten in een compacte verzameling een convergente deelverzameling heeft die binnen de verzameling blijft. Dit is vergelijkbaar met het gedrag van intervallen in de reële getallen.

In een compacte metrische ruimte is elke gesloten verzameling ook compact. Dit leidt tot het concept van een universeel compacte ruimte, wat een ruimte is die compact is op haar gehele verzameling.

Tot slot is volledigheid een essentieel concept in metrische ruimten. Een Cauchy-reeks in een metrische ruimte is een reeks waarvan de termen steeds dichter bij elkaar komen. In een complete ruimte zal elke Cauchy-reeks altijd naar een limiet punt convergeren. Dit wordt als volgt gedefinieerd:

Dit concept is van fundamenteel belang voor de analyse van metrische ruimten, vooral in de context van convergentie en het gedrag van reeksen in deze ruimten.