Implementazione della teoria matematica dell'aritmetica in Haskell tramite corrispondenza Curry-Howard

Question

Devo chiedere perdono in anticipo se l'intera domanda non ha molto senso, ma sfortunatamente non ho una migliore intuizione in questo momento e questo sembra il miglior punto di partenza che potrei inventare.

Sto leggendo il libro di Tarski "Introduzione alla logica: e alla metodologia delle scienze deduttive", sono nella parte VII Capitolo 43 "Termini primitivi della teoria in costruzione; assiomi relativi alle relazioni fondamentali tra i numeri". Inizia esprimendo una teoria matematica elementare dell'aritmetica dei numeri reali.

I termini primitivi sono:

• Numero reale (indicato come variabili come x, y)
• è meno di (<)
• è più grande di (>)
• somma (+)
• N significa "l'insieme di tutti i numeri". Pertanto, un'espressione "x è un numero" verrebbe scritta come x ∈ N
• non è inferiore a (≮)
• non è maggiore di (≯)

Tra gli assiomi della teoria in esame, due gruppi possono essere distinti. Gli assiomi del primo gruppo esprimono proprietà fondamentali delle relazioni meno e maggiori di, mentre quelle del secondo sono principalmente interessate all'aggiunta. Per il momento, considereremo solo il primo gruppo; Consiste, del tutto, di cinque dichiarazioni:

• Axiom 1. Per qualsiasi numero x e y (EG, per elementi arbitrari del set N) noi abbiamo: x = y o x < y o x > y
• Axiom 2. if x < y, poi y ≮ x
• Assioma 3. if x > y, poi y ≯ x
• Assioma 4. if x < y e y < z, poi x < z
• Assioma 5. se x > y e y > z, poi x > z

Il nostro prossimo compito consiste nella derivazione di un numero di teoremi dagli assiomi adottati da noi:

• Teorema 1. Nessun numero è più piccolo di se stesso x ≮ x
• Teorema 2. Nessun numero è maggiore di se stesso: x ≯ x

Ora devo fermarmi e infine spiegare le mie intenzioni. Ho sentito molte volte di una cosiddetta corrispondenza "Curry-Howard-Alimbek", e ha senso ogni volta che ne ho letto esempi. Inoltre, non mi sento a mio agio nel scrivere manualmente il ragionamento per dimostrare i teoremi, vorrei il macchinario di passare attraverso i passi di ragionamento per essere controllati da un computer per me.

Quindi, ho cercato di codificare i termini, gli assiomi e i teoremi potenzialmente (sono rimasto bloccato in precedenza) in Haskell, ma ho fallito in molti modi. Non ti mostrerò tutti gli esempi di quello che ho fatto, ma ecco l'approccio più ingenuo delle proposizioni di codifica come tipi e le loro prove come programmi:

data Nats
  = NatX
  | NatY
  | NatZ

x :: Nats
x = NatX

data OpGt =
  OpGt Nats
       Nats

data OpLt =
  OpLt Nats
       Nats

data OpEq =
  OpEq Nats
       Nats

data OpNotLt =
  OpNotLt Nats
          Nats

data OpNotGt =
  OpNotGt Nats
          Nats

data Ax1Res
  = Ax1ResLt OpLt
  | Ax1ResGt OpGt
  | Ax1ResEq OpEq

-- how to implement best?
ax1 :: Nats -> Nats -> Ax1Res
ax1 = undefined

-- this doesn't describe the x and y in the type
ax2 :: OpLt -> OpNotGt
ax2 = undefined

Questo pezzo di codice porta più domande di quelle che danno risposte:

• Gli assiomi dovrebbero essere implementati o mantenuti come funzioni non implementate che supponiamo che esistano?
• Come posso limitare l'implementazione delle mie funzioni per fare affidamento su teoremi e assiomi disponibili solo se posso costruire sostanzialmente qualche termine? Dovrei nascondere i costruttori?
• i tipi dovrebbero ovviamente contenere variabili come x e y, L'ho provato in altri approcci ma questo diventa ancora più peloso

Le mie domande sono:

• Quale sarebbe una corretta attuazione di tali prove in Haskell?
• Quali materiali dovrei leggere per rendere me stesso una corretta implementazione e comprendere meglio l'argomento?

Spero che la vaghezza e il mio livello di ignoranza nella domanda non ti rimandino dal rispondere. Grazie!