Hvordan vi kan definere den inverse funktion med Klassisk Valg i Lean

I matematik, når vi taler om funktioner og deres inverser, stødder vi ofte på nødvendigheden af at vælge et bestemt element ud af en uendelig mængde af muligheder. I teorien om funktioner betyder dette, at vi nogle gange skal bruge en metode til at vælge et element, når vi ikke har en naturlig måde at gøre det på. I sådanne tilfælde henviser vi til det matematiske "valgaxiom", som giver os ret til at vælge et element fra en mængde, uden nødvendigvis at kunne angive, hvordan dette valg skal foretages. Dette kan ske med brugen af klassisk logik, og Lean – et bevisværktøj og matematikprogrammeringssprog – gør det muligt at arbejde med sådanne koncepter ved hjælp af værktøjer som "Classical.choose".

Lean håndterer dette gennem brug af det klassiske valgoperator, som kan anvendes, når vi ved, at der eksisterer et sådant $x$, men ikke nødvendigvis kan udtrykke det konkret. Vi kan definere den inverse funktion som følger:

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

For at sikre, at dette fungerer som ønsket, skal vi også bevise, at den inverse funktion faktisk opfylder den korrekte egenskab. Det betyder, at hvis $y$ er et element af $\beta$, der kan opnås ved at anvende $f$ på et element $x$, skal det gælde, at $f(\text{inverse}(f, y)) = y$.

lean
Copy code
theorem inverse_spec {f : α → β} (y : β) (h : ∃ x, f x = y) : 

  f (inverse f y) = y := 
    by rw [inverse, dif_pos h] 
       exact Classical.choose_spec h

Teoremet siger, at hvis der eksisterer et $x$ sådan at $f(x) = y$, så vil $f$ anvendt på den inverse funktion returnere $y$, som vi forventer.

Et vigtigt aspekt af denne tilgang er forståelsen af de logiske operationer bag funktionerne og deres beviser. F.eks. er det, at funktionen "inverse" kun er korrekt defineret, hvis den faktisk kan vælge et passende element $x$ ud fra de givne betingelser. Hvis ikke, returneres et standardelement, som ikke nødvendigvis er "rigtigt", men blot et element, der opfylder kravene i det klassiske valgaxiom.

Så hvad betyder det, når vi siger, at en funktion har en "invers"? En invers funktion er, hvad vi kan bruge til at "annullere" virkningen af den oprindelige funktion, dvs. at hvis vi først anvender $f$ og derefter anvender $f^{ -1}$, skal vi ende med det oprindelige input. Denne egenskab er fundamentalt for mange områder af matematikken og er tæt forbundet med begreberne injektivitet (en funktion der "ikke mister" information) og surjektivitet (en funktion der dækker hele mængden).

Når vi arbejder med begreber som injektivitet og surjektivitet i Lean, kan vi bruge de relevante definitioner, som er implementeret i systemet, og kontrollere om de gælder i et konkret tilfælde. For eksempel:

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

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

I disse sætninger søger vi at vise, at en funktion er injektiv, hvis og kun hvis dens inverse funktion er en venstre invers, og at den er surjektiv, hvis og kun hvis dens inverse funktion er en højre invers. Bevisene kan være tricky, men de kan relativt let opbygges med Lean, når man forstår, hvordan de logiske konstruktioner fungerer.

Afslutningsvis skal vi nævne Cantors berømte sætning om, at der ikke eksisterer en surjektiv funktion fra et sæt til dets potensæt. Dette er et klassisk resultat i mængdeteorien, og det kan bevises ved at antage, at en sådan surjektiv funktion eksisterer, og derefter finde en kontradiktion. Formaliseringen af dette resultat i Lean kræver nogle avancerede teknikker, men den giver os et klart billede af, hvordan man arbejder med uendelige mængder og deres strukturer.

Hvordan bygget man de Gaussiske heltall?

Teoremet "not_norm_mul_left_lt_norm" viser, at når man multiplicerer to elementer i de Gaussiske heltall, vil den resulterende norm altid være større eller lig med normen af det første element. Med andre ord, for to GaussInt $x$ og $y$, hvor $y \neq 0$, gælder det, at normen af produktet $x \cdot y$ aldrig vil være mindre end normen af $x$. Denne egenskab er fundamental, når man arbejder med de Gaussiske heltall, da den understøtter den naturlige orden i de euklidiske domæner.

Når vi anvender dette, kan vi vise, at de Gaussiske heltall er et eksempel på et euklidisk domæne. I et euklidisk domæne defineres kvotient og rest som funktioner, og i dette tilfælde er de kvotienter og rester, som vi kender fra divisionen af naturlige tal. Mathlibs definition af et euklidisk domæne er dog mere generel end vores umiddelbare eksempel, da den giver os mulighed for at vise, at resten i en division falder i henhold til en velordnet måling, og det er netop normfunktionen, der giver os denne måling.

For at definere et euklidisk domæne for de Gaussiske heltall, definerer vi kvotienten og resten som divisionen og modulooperationen. Det kræver, at vi beviser, at disse operationer opfylder de nødvendige egenskaber, herunder, at normen af resten er mindre end normen af det oprindelige tal. Ved at definere de nødvendige egenskaber som teoremene "natAbs_norm_mod_lt" og "not_norm_mul_left_lt_norm", kan vi etablere, at de Gaussiske heltall faktisk udgør et euklidisk domæne.

Det er vigtigt at bemærke, at den euklidiske egenskab, der gør det muligt at definere normer og beregne divisioner og rester, ikke kun gælder for de Gaussiske heltall, men også for andre algebraiske strukturer, som kan have en normfunktion. Denne tilgang gør det muligt at analysere flere typer domæner i algebraen, ikke kun de Gaussiske heltall.

Ud over de rent tekniske aspekter af normberegning og division, er det væsentligt at forstå, hvordan disse matematiske strukturer kan anvendes til at udføre faktorisering i andre algebraiske systemer, især når vi bevæger os fra de Gaussiske heltall til mere generelle domæner som hele tal, polynomier eller endda mere komplekse algebraiske strukturer. Dette giver os mulighed for at udvide vores forståelse af normer og faktorisering til et bredt spektrum af matematiske områder.

Hvordan opbygger man algebraiske strukturer i Lean?

I Lean kan man definere algebraiske strukturer ved hjælp af den omfattende typeklassessystem og arvefunktionalitet, som gør det muligt at kombinere eksisterende strukturer på en effektiv og elegant måde. Dette åbner døren for at definere komplekse matematiske strukturer som semigrupper, monoider, grupper og ringe, ved at udnytte et hierarki af typeklasser.

lean
Copy code
class Semigroup2 (α : Type) extends Dia1 α where
  dia_assoc : ∀ a b c : α, a  b  c = a  (b  c)

I denne definition udvider Semigroup2 den grundlæggende struktur Dia1 α, hvor den associativitetsegenskab for operationen er angivet med dia_assoc. Ved at udvide eksisterende klasser kan man gradvist bygge mere komplekse strukturer. Et eksempel på dette er en monoid, der udvider både semigruppe-strukturen og en enhedsoperation, der sikrer, at der findes et neutralt element for operationen.

Når man arbejder med sådanne strukturer, kan man nemt få en symmetri mellem de udvidede klasser, selvom man kombinerer flere strukturer. For eksempel kan en monoid defineres ved at udvide både Semigroup1 og DiaOneClass1:

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

Denne tilgang skaber en symmetri, der forhindrer problemer som duplikering af operationer, der ellers kunne opstå, hvis man definerede en monoid manuelt ved at inkludere to uafhængige instanser af en diamantoperation. En vigtig funktion ved extends syntaksen i Lean er, at den automatisk løser dette problem, og dermed forenkler arbejdet med algebraiske strukturer.

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

lean
Copy code
class Group1 (G : Type) extends Monoid1 G, Inv1 G where
  inv_dia : ∀ a : G, a ¹  a = 1

Den tekniske udfordring ved at definere ringe i Lean er, at en ringstruktur kræver både en additiv gruppe og en multiplicativ monoid, hvilket betyder, at man skal kunne håndtere to forskellige typer af operationer på en konsistent måde. Lean håndterer dette problem ved at duplicere definitionerne af operationerne for både additive og multiplikative teorier og linker dem med en to_additive attribut. Dette sikrer, at både de additive og multiplicative versioner af strukturerne og deres beviser bliver korrekt genereret.

I praksis er det muligt at definere kommutative semigrupper, monoider og grupper, og senere udvide dem til ringe. For eksempel kan en kommutativ semigruppe defineres som:

lean
Copy code
class AddCommSemigroup3 (α : Type) extends AddSemigroup3 α where
  add_comm : ∀ a b : α, a + b = b + a

I sidste ende giver Lean et stærkt værktøj til at bygge algebraiske strukturer ved hjælp af typeklasser og inheritance. Det gør det muligt at definere komplekse strukturer som semigrupper, monoider, grupper og ringe på en ren og systematisk måde, hvilket letter både konstruktionen og bevisføringen af matematiske resultater.