Lean 4: matemática, código e IA no mesmo lugar

Alexandre Rademaker
FGV/EMAp
V SEEMAp, FGV EMAp | 21 de outubro de 2026
arademaker.github.io/dama-2026
Lean

Sobre mim

  • Professor da EMAp desde 2010: matemática discreta, programação, algoritmos, teoria dos tipos, teoria das categorias, etc.

  • Mestrado (UFF, 2005): métodos formais, lógica de reescrita em Maude.

  • Doutorado (PUC-Rio, 2010): teoria da prova para lógicas de descrição. Estágios no SRI (PVS) e na Microsoft Research, com a equipe do Z3.

  • IBM Research Brasil (2012–2025): PLN, semântica computacional, ontologias.

  • Na comunidade Lean desde março de 2015; hoje também sou diretor da CSLib Initiative.

Lean

Roteiro

  1. O que é o Lean: uma linguagem de programação que também confere provas.

  2. A história do Lean: de projeto de pesquisa a infraestrutura.

  3. O momento do Lean: avanços na matemática, e com IA.

  4. A Mathlib: a biblioteca de matemática.

  5. IA e Lean: por que um verificador é o parceiro natural de um modelo.

  6. Ao vivo: um programa com provas, escrito aqui, no VS Code.

  7. A CSLib, e como começar.

Parte 1: O que é o Lean

Lean

O que é o Lean?

Logo do Lean

lean-lang.org: a proof assistant and programming language that is transforming how we approach mathematics, software verification, and AI.

  • Uma linguagem de programação funcional e um assistente de provas, no mesmo sistema.

  • Provas conferidas pela máquina, por um kernel pequeno e confiável.

  • Baseado em teoria dos tipos dependentes.

  • Escrito em Lean, e muito extensível: a comunidade cria suas próprias táticas e notações.

  • 325.000+ instalações únicas da extensão para VS Code.

Este slide e o do "jogo" são adaptados do deck FROCON 2026 de Leo de Moura (@leodemoura).

Lean

O Lean é um "jogo"

def odd (n : Nat) : Prop := ∃ k, n = 2 * k + 1 theorem square_of_odd_is_odd : odd n → odd (n * n) := by intro ⟨k₁, e₁⟩ simp [e₁, odd] exists 2 * k₁ * k₁ + 2 * k₁ lia

O "tabuleiro": você vê as metas e as hipóteses, e faz "jogadas" (táticas). Cada tática transforma o tabuleiro.

Exemplo do deck FROCON 2026 de Leo de Moura (@leodemoura).

Lean

Em quem confiar?

O Lean separa quem procura a prova de quem confere a prova.

  • Táticas, automação, e agora modelos de IA, procuram provas. Podem ser grandes, complicados, cheios de bugs.

  • O kernel só confere o termo de prova final. É pequeno, e pode ser reimplementado de forma independente.

  • Para confiar num teorema, basta ler o enunciado e confiar no kernel.

If your proof type-checks, it's correct.

— Leonardo de Moura, Why Lean? (abril de 2026)

Parte 2: A história do Lean

Lean

Uma breve história

Quando

Marco

jul 2013

Primeiro commit, de Leonardo de Moura

jan 2017

Lean 3; em julho nasce a mathlib

out 2019

Natural Number Game 1.0

jul 2021

Liquid Tensor Experiment concluído (desafio de Peter Scholze)

jul–set 2023

Lean FRO fundada; Mathlib portada para Lean 4; Lean 4.0

jun–jul 2024

Harmonic, primeira startup baseada em Lean; AlphaProof, prata na IMO

mai–set 2025

50+ cursos universitários; tática grind; Mathlib Initiative

jun 2026

A história vira livro: The Proof in the Code

Lean

Virou livro

Kevin Hartnett, The Proof in the Code: How a Truth Machine Is Transforming Math and AI (Quanta Books, junho de 2026).

Capa de The Proof in the Code

Lean is one of the most important things happening to math right now.

— Grant Sanderson (3Blue1Brown)

Parte 3: O momento do Lean

Avanços na matemática, e com IA.

Lean

IA nas competições

  • IMO 2024: AlphaProof (Google DeepMind), prata.

  • IMO 2025: ouro para Aristotle (Harmonic), prata para Seed Prover (ByteDance). Também ouro para Gemini Deep Think (DeepMind) e OpenAI, mas em linguagem natural.

  • Putnam 2025 (6 de dezembro): AxiomProver resolveu 8 de 12 durante a prova, e os outros 4 nos dias seguintes.

AlphaProof, Aristotle, Seed Prover e AxiomProver usaram Lean: as provas deles foram conferidas pela máquina; as em linguagem natural, por juízes.

DeepMind, 21 jul 2025

Harmonic, 2 out 2025

ByteDance Seed, 23 jul 2025

Lean

2026 até aqui

Quando

O quê

jan

Problemas de Erdős em aberto resolvidos com ajuda de IA, com formalização em Lean

mar

Empacotamento de esferas em dimensões 8 e 24 formalizado (resultados de Viazovska, Medalha Fields)

abr

ChatGPT 5.5 encontra um resultado de Ramsey verificado em Lean

jun

Começa o Tau Ceti: IA escrevendo matemática em Lean

ago

OpenAI: dez problemas em aberto, com certificados em Lean

set

Anthropic: Último Teorema de Fermat; OpenAI: Navier–Stokes; os dois com provas em Lean

Lean

Os laboratórios de IA entregam provas em Lean

OpenAI, 1º ago 2026

OpenAI, 1º/8: dez problemas em aberto, cada um com um certificado em Lean.

Anthropic, 4 set 2026

Anthropic, 4/9: a primeira prova completa do Último Teorema de Fermat conferida por computador, em Lean: 13 milhões de linhas, em 11 dias.

OpenAI, 8 set 2026

OpenAI, 8/9: Navier–Stokes, um Problema do Milênio, segundo a OpenAI, com a prova em Lean.

Lean

Só na última semana

Xena, 16 out 2026

Blog de Terence Tao, 17 out 2026

Lean

Por que isso importa

Uma prova gerada por IA pode ter milhares de linhas. Quem confere?

  • Revisão humana não escala.

  • Teste não serve: um teorema fala de todos os casos.

  • O kernel do Lean confere, e não se cansa.

O gargalo deixa de ser escrever a prova e passa a ser enunciar o problema certo.

Parte 4: A Mathlib

Lean

Mathlib: a biblioteca de matemática do Lean

Criada em julho de 2017, em Lean 3. Aberta e mantida pela comunidade. Hoje:

  • 280.000+ teoremas formalizados.

  • 2,4M+ linhas de Lean. 50.000+ linhas de extensões.

  • 950 contribuidores e 65 revisores.

  • 1.500+ classes de tipos, 20.000+ instâncias.

  • github.com/leanprover-community/mathlib4

Grafo de dependências da Mathlib

Lean

O que tem dentro

Área

Exemplos

Álgebra

Grupos, anéis, corpos, teoria dos números, álgebra homológica

Álgebra linear

Espaços vetoriais, matrizes, formas bilineares

Topologia e análise

Espaços de Banach e Hilbert, medida e integração, análise complexa e de Fourier

Probabilidade

Variáveis aleatórias, processos estocásticos

Geometria

Variedades, geometria riemanniana e algébrica

Combinatória

Grafos, teoria de Ramsey, combinatória aditiva

Lógica e computação

Computabilidade, teoria dos modelos, teoria dos conjuntos

Visão geral da Mathlib

Lean

Usando a Mathlib

Teoremas clássicos já estão lá. Basta importar e usar:

/-- Euclides: para todo `n` existe um primo maior ou igual a `n`. -/ example (n : ℕ) : ∃ p, n ≤ p ∧ p.Prime := Nat.exists_infinite_primes n /-- `√2` é irracional. -/ example : Irrational (√2) := irrational_sqrt_two

O enunciado é o que importa: quem lê a linha do example sabe exatamente o que foi provado, sem precisar ler a prova.

Lean

...e a automação faz as contas

Táticas da Mathlib, escritas pela comunidade, resolvem classes inteiras de problemas:

example (a b : ℝ) : (a + b) ^ 2 = a ^ 2 + 2 * a * b + b ^ 2 := by ring example (x : ℝ) : 0 < x ^ 2 + 1 := by positivity example (x y : ℝ) (h₁ : 2 * x + y ≤ 4) (h₂ : 1 ≤ x) : y ≤ 2 := by linarith
  • ring: igualdades em anéis comutativos.

  • positivity: metas da forma 0 < e ou 0 ≤ e.

  • linarith: desigualdades que seguem das hipóteses por combinação linear.

Lean

...e as táticas do próprio Lean

Mantidas pela Lean FRO, vêm com o Lean, sem importar nada:

example (n : Nat) (h : n % 2 = 1) : (n + 1) % 2 = 0 := by omega example (xs : List Nat) : (xs ++ []).length = xs.length := by simp example (f : Nat → Nat) (h₁ : a = b) (h₂ : f b = c) : f a = c := by grind example : 2 ^ 10 = 1024 := by decide
  • omega: aritmética linear sobre inteiros e naturais.

  • simp: reescreve com uma base de lemas de simplificação.

  • grind: combina fatos e igualdades até achar uma contradição (veremos no demo).

  • decide: calcula a resposta, quando a proposição é decidível.

Parte 5: IA e Lean

Lean

Um verificador é o parceiro natural de um modelo

  • Modelos de linguagem erram com confiança. O kernel não aceita confiança.

  • Para treinar com reforço, um agente precisa de um sinal de recompensa que ele não consiga trapacear. Uma prova conferida é esse sinal.

  • A Mathlib é também um dado: centenas de milhares de teoremas, escritos e anotados por pessoas.

Leituras: Proof Assistants in the Age of AI, Teaching AI to Make Proof Automation Work, Why Lean? · Comunidade: FMxAI

Lean

Tau Ceti: matemática escrita por agentes

taucetiproject.org, desde junho de 2026:

  • Agentes de IA escrevem as provas em Lean e abrem pull requests.

  • Matemáticos definem os alvos, num roteiro revisado por pessoas.

  • Revisores de IA julgam cada PR por critérios fixos e abertos.

  • Todo teorema é conferido pela máquina: sem sorry, sem axiomas extras.

Segundo o post do Xena (16/10), o Tau Ceti já é um pouco maior que a Mathlib.

Lean

Software também: lean-zip

lean-zip (Kim Morrison): DEFLATE em Lean puro, com um teorema conferido pelo kernel: descomprimir desfaz comprimir, para toda entrada e todo nível. Cerca de 1.100 teoremas, nenhum sorry.

  • Escrito por agentes de IA, com pouca supervisão.

  • A prova é o portão: um PR só entrava se a prova continuasse valendo.

  • Por isso otimizar é seguro: ficou mais rápido que o miniz_oxide do Rust com a mesma taxa de compressão.

Lean

Um exemplo: busca binária escrita por IA

lean-binsearch: implementação e prova feitas com o Claude Code, 283 linhas. Para confiar no resultado, basta ler dois enunciados:

theorem bsearch_sound (l : List Nat) (target : Nat) (i : Nat) : bsearch l target = some i → l[i]? = some target theorem bsearch_complete (l : List Nat) (target : Nat) (hs : Sorted l) (hm : target ∈ l) : ∃ i, bsearch l target = some i
  • Correção: se devolve i, então target está na posição i.

  • Completude: se a lista está ordenada e contém target, a busca acha.

E se escrevêssemos uma busca binária juntos, agora, deixando o Lean nos corrigir?

Parte 6: Ao vivo

Vamos escrever juntos um programa em Lean, com provas, no VS Code.

A ideia e o roteiro são do live demo de Joachim Breitner (Lean FRO).

Lean

O que o demo mostrou

O bingo de Joachim tem 33 recursos do Lean. ✅ o código que escrevemos usa (21 de 33); os outros ficam para outra vez.

lambdas anônimas (anonymous lambdas)

✅ terminação verificada automaticamente (automatic termination checking)

✅ automação com grind (automation with grind)

✅ parâmetros automáticos (auto-params)

✅ programação funcional básica (basic functional programming)

✅ sugestões clicáveis (clickable hints)

notação própria (custom notation)

✅ tipos dependentes (dependent types)

notação do (do notation)

do com retorno antecipado (do with early return)

do com atualização mutável (do with mutable update)

do com iteração paralela (do with parallel iteration)

✅ teste embutido (embedded test)

✅ avaliar código (evaluating code)

✅ termos de prova explícitos (explicit proof terms)

✅ indução funcional (functional induction)

autocompletar nomes de funções (function name autocompletion)

ir para a definição (go to definition)

✅ hover

✅ atualizações imutáveis (immutable updates)

✅ parâmetros implícitos com táticas (implicit parameters with auto-tactics)

incrementalidade (incrementality)

✅ dicas embutidas no texto (inlay hints)

✅ inspecionar o estado do grind (inspecting grind states)

✅ argumentos nomeados (named function arguments)

✅ notação de ponto sobrecarregada (overloaded dot notation)

verificação de provas em paralelo (parallel proof checking)

✅ construtor de estrutura (structure constructor syntax)

✅ provas com táticas (tactic proofs)

dica de tipo (type hint)

✅ digitar unicode (unicode entry)

dicas para identificador desconhecido (unknown identifier code hints)

✅ recursão bem fundada (well-founded recursion)

Lista do "Lean Highlights Bingo" de Joachim Breitner (@nomeata).

Parte 7: A CSLib

A busca binária escrita pela IA definia o seu próprio Sorted, sem usar a Mathlib nem a CSLib. Cada projeto reinventando o vocabulário: é esse o problema que uma biblioteca resolve.

CSLib

O que é a CSLib?

Logo da CSLib

An open-source library of reusable components for proving theorems in computer science and writing formally verified code in the Lean programming language and proof assistant.

  • Formalizar a ciência da computação: modelos de computação, semântica, lógicas, algoritmos e estruturas de dados, com provas de correção e de complexidade.

  • Raciocinar sobre código do dia a dia: Boole, uma linguagem intermediária de verificação embutida no Lean.

  • Depende da Mathlib, e não refaz o que a Mathlib já tem.

github.com/leanprover/cslib · cslib.io

CSLib

A biblioteca e a Initiative

A biblioteca CSLib

A CSLib Initiative

leanprover/cslib, código aberto

Um programa na Renaissance Philanthropy

Governada pela comunidade; quase toda feita por voluntários

Um diretor e uma pequena equipe

Decide a sua própria direção técnica

Ajuda a biblioteca a crescer; não a comanda

Cresce organicamente

Investe onde o crescimento não acontece sozinho

O modelo é o da Mathlib: um projeto aberto e vivo, e ao lado dele uma equipe dedicada para o trabalho difícil de manter só com voluntários.

CSLib

Projetos que usam a CSLib

Projetos independentes, que não são da CSLib: dependem dela e devolvem a ela o que é geral. A CSLib Initiative apoia e colabora para que usem a CSLib.

  • Software Foundations in Lean: Benjamin Pierce, Michael Hicks e Harry Goldstein reescrevem em Lean o Software Foundations, o texto clássico de métodos formais, escrito originalmente em Rocq (antes Coq).

  • PolyFun (Verified-zkEVM): interação tipada entre programas e sistemas, com functores polinomiais e árvores de interação. Mantém uma área, ToCslib, com o que vai subir para a CSLib.

CSLib

A comunidade em volta da CSLib

github.com/cslib-community: projetos construídos com, em volta de, e para a CSLib.

Projeto

O quê

CSwL

Semântica computacional com Lean, o livro do curso de PLN da EMAp deste semestre, escrito em Verso como estes slides

fad

Functional Algorithms Design, o livro do curso de Estruturas de Dados e Algoritmos da EMAp, que também será escrito em Verso

AlgoLib

Algoritmos em grafos, com provas de correção e de tempo

alc

A lógica de descrição básica, ALC

sqlean

Formalização do SQLite em Lean

bignum

Porte das provas do s2n-bignum (Amazon) para Lean

EpsilonEridani

Agentes de IA escrevem o Lean; pessoas decidem o que vale provar

CSLib

Lean nas minhas aulas

Na EMAp

Fora

Dois deles estão na lista de cursos com Lean da comunidade, que já passou de 50 cursos universitários.

Como começar

Obrigado

Alexandre Rademaker

FGV/EMAp

arademaker.github.io/dama-2026

Apêndice

Exemplos em slides, para o caso de a demonstração ao vivo falhar.

CSLib

Lean é uma linguagem de programação

Funcional, com tipos estáticos, compilada para C. Funções são definidas por casos, e #eval roda o código:

def fib : Nat → Nat | 0 => 0 | 1 => 1 | n + 2 => fib n + fib (n + 1) #eval fib 10
55
#eval (List.range 10).map fib

A saída ao lado de cada #eval foi calculada pelo Lean quando estes slides foram gerados.

CSLib

...tipos, listas e estruturas

structure Aluno where nome : String notas : List Nat def Aluno.media (a : Aluno) : Nat := a.notas.sum / a.notas.length def turma : List Aluno := [⟨"Ana", [9, 8, 10]⟩, ⟨"Bruno", [6, 7, 8]⟩] #eval turma.map fun a => (a.nome, a.media)
[("Ana", 9), ("Bruno", 7)]
#check @Aluno.media

Tudo tem um tipo, e #check mostra qual é.

CSLib

Lean é um assistente de provas

Uma proposição é um tipo; uma prova é um programa desse tipo. O Lean confere a prova como confere o tipo de qualquer outro termo.

theorem dois_mais_dois : 2 + 2 = 4 := rfl theorem soma_zero (n : Nat) : n + 0 = n := rfl theorem zero_soma (n : Nat) : 0 + n = n := by induction n with | zero => rfl | succ k ih => rw [Nat.add_succ, ih]

Por que n + 0 = n sai direto da definição, mas 0 + n = n precisa de indução?

CSLib

...e a máquina diz não

Uma afirmação falsa não passa, por mais convincente que pareça:

theorem errado (n : Nat) : n - 1 + 1 = n := by omega

O contraexemplo é n = 0, porque em Nat temos 0 - 1 = 0:

#eval (0 - 1 + 1 : Nat)
1

Com a hipótese certa, a mesma tática fecha a prova:

theorem certo (n : Nat) (h : 0 < n) : n - 1 + 1 = n := by omega
CSLib

O programa simples já é a especificação

Para saber se um programa rápido está correto, precisamos de uma especificação. Muitas vezes o programa mais simples que resolve o problema é a especificação: obviamente correto, mas lento demais.

  • Especificação: ordenação por inserção, seis linhas, nada de esperto.

  • Implementação: o mergeSort verificado da CSLib, no papel da versão otimizada que um engenheiro, ou um agente de IA, escreveria.

  • Objetivo: provar que os dois dão a mesma resposta para toda entrada, e contar quantas comparações cada um faz.

Os dois são escritos na mônada de tempo TimeM da CSLib: um programa devolve o resultado junto com um custo, e cada ✓ cobra uma comparação.

Exemplo: Jesse Alama (@jessealama). Autores na CSLib: Sorrachai (@sorrachai), Eric Wieser (@eric-wieser), Kim Morrison (@kim-em).

CSLib

...a ordenação óbvia

variable {α : Type} [LinearOrder α] def insertSorted (x : α) : List α → TimeM ℕ (List α) | [] => return [x] | y :: ys => do ✓ let c := (x ≤ y : Bool) if c then return x :: y :: ys else return y :: (← insertSorted x ys) def insertionSort : List α → TimeM ℕ (List α) | [] => return [] | x :: xs => do insertSorted x (← insertionSort xs)
CSLib

...mesma resposta, conta diferente

#eval ⟪insertionSort [5, 3, 1, 4, 2]⟫
[1, 2, 3, 4, 5]
#eval ⟪mergeSort [5, 3, 1, 4, 2]⟫
[1, 2, 3, 4, 5]
#eval (insertionSort (List.range 1000).reverse).time
499500
#eval (mergeSort (List.range 1000).reverse).time
4932
CSLib

...ligada à Mathlib

⟪p⟫ descarta o custo e fica com o resultado. Sem o custo, a nossa ordenação por inserção é o List.insertionSort da Mathlib:

@[simp, grind =] theorem ret_insertSorted (x : α) (l : List α) : ⟪insertSorted x l⟫ = l.orderedInsert (· ≤ ·) x := by fun_induction insertSorted with grind @[simp, grind =] theorem ret_insertionSort (xs : List α) : ⟪insertionSort xs⟫ = xs.insertionSort (· ≤ ·) := by fun_induction insertionSort with grind

Por que usar as definições da Mathlib: ela já prova que List.insertionSort devolve uma permutação ordenada da entrada. Com um lema de ligação, reaproveitamos essas provas em vez de refazê-las.

Autores na Mathlib: Jeremy Avigad (@avigad), Wrenna Robson (@wrenna-robson).

CSLib

...equivalentes, para toda entrada

As duas saídas são permutações ordenadas da entrada, e uma lista só tem uma permutação ordenada:

/-- A rápida concorda com a óbvia. Não foi testado. Foi provado. -/ theorem mergeSort_eq_insertionSort (xs : List α) : ⟪mergeSort xs⟫ = ⟪insertionSort xs⟫ := by obtain ⟨hs, hp⟩ := mergeSort_correct xs simpa using List.Perm.eq_of_sortedLE hs.sortedLE List.sortedLE_insertionSort (hp.trans (List.perm_insertionSort _ xs).symm)
  • Da CSLib: mergeSort_correct, a saída de mergeSort está ordenada e é uma permutação de xs.

  • Da Mathlib: List.sortedLE_insertionSort e List.perm_insertionSort, o mesmo para a inserção; e List.Perm.eq_of_sortedLE, duas listas ordenadas que são permutações uma da outra são iguais.

CSLib

...e o custo de insertionSort é n²

theorem insertSorted_time (x : α) (l : List α) : (insertSorted x l).time ≤ l.length := by fun_induction insertSorted with grind @[simp] theorem insertionSort_length (xs : List α) : ⟪insertionSort xs⟫.length = xs.length := by simp theorem insertionSort_time (xs : List α) : (insertionSort xs).time ≤ xs.length ^ 2 := by fun_induction insertionSort <;> simp grind [insertSorted_time, insertionSort_length]

O de mergeSort é n ⌈log₂ n⌉, como provado na CSLib:

theorem mergeSort_time (xs : List α) : let n := xs.length (mergeSort xs).time ≤ n * clog 2 n := by grind [mergeSort_time_le, timeMergeSortRec_le]
CSLib

...e o verificador diz não

O pior caso exato da inserção é aceito:

set_option maxRecDepth 4000 in example : (insertionSort (List.range 100).reverse).time = 100 * 99 / 2 := by decide

Uma afirmação falsa sobre o merge sort é recusada. Clique em native_decide para ver o motivo:

example : (mergeSort (List.range 1000).reverse).time = 5000 := by native_decide
CSLib

Duas máquinas de vendas

Milner, Communication and Concurrency (1989).

  • Boa: moeda, e depois você escolhe chá ou café. \mathit{Good} \stackrel{\text{def}}{=} \mathit{coin}.(\mathit{tea}.\mathit{Good} + \mathit{coffee}.\mathit{Good})

  • Ruim: moeda, e a máquina escolhe. \mathit{Bad} \stackrel{\text{def}}{=} \mathit{coin}.\mathit{tea}.\mathit{Bad} + \mathit{coin}.\mathit{coffee}.\mathit{Bad}

Os registros são idênticos: coin tea, coin coffee, … Os mesmos traços. Um teste baseado em traços não distingue as duas.

Depois da moeda, a máquina ruim pode já ter escolhido café, e aí o botão do chá não faz nada. Um traço registra as ações que aconteceram; nunca registra uma ação que foi recusada.

Exemplo: Jesse Alama (@jessealama). Autor na CSLib: Fabrizio Montesi (@fmontesi).

CSLib

Traços são grosseiros demais

A equivalência de traços ignora quais ações estão disponíveis a cada passo.

Bissimilaridade: cada movimento de uma máquina precisa ser imitado por um movimento da outra, e os estados alcançados precisam de novo estar relacionados, a cada passo.

Duas maneiras de provar que as nossas máquinas não são bissimilares:

  1. Diretamente, como faz o vm_ltsD_ltsND_not_bisim da própria CSLib: supor uma bissimulação e seguir as transições até ela quebrar.

  2. Com uma lógica: achar uma fórmula que uma máquina satisfaz e a outra não.

CSLib

...no CCS da CSLib

abbrev coin := Act.name "coin" abbrev tea := Act.name "tea" abbrev coffee := Act.name "coffee" inductive Machine | good | bad /-- good = coin.(tea + coffee) bad = coin.tea + coin.coffee -/ @[grind =] def defs : Machine → Option (Process String Machine) | .good => some `(CCS| coin. ((tea. const .good) + (coffee. const .good))) | .bad => some `(CCS| (coin. tea. const .bad) + (coin. coffee. const .bad)) /-- As duas máquinas vivem num só sistema de transições: o do CCS, da CSLib. -/ abbrev machines := CCS.lts (defs := defs)

Um único sistema de transições rotuladas (LTS), machines, com duas constantes: a máquina boa é const .good, a ruim, const .bad.

CSLib

...e a sua semântica

As transições de um processo CCS são uma relação indutiva, uma regra por construção. A CSLib a declara como um LTS com @[lts lts]:

@[lts lts] inductive Tr : Process Name Constant → Act Name → Process Name Constant → Prop where | pre : Tr (pre μ p) μ p | parL : Tr p μ p' → Tr (par p q) μ (par p' q) | parR : Tr q μ q' → Tr (par p q) μ (par p q') | com : μ.Co μ' → Tr p μ p' → Tr q μ' q' → Tr (par p q) Act.τ (par p' q') | choiceL : Tr p μ p' → Tr (choice p q) μ p' | choiceR : Tr q μ q' → Tr (choice p q) μ q' | res : μ ≠ Act.name a → μ ≠ Act.coname a → Tr p μ p' → Tr (res a p) μ (res a p') | const : defs k = some p → Tr p μ p' → Tr (const k) μ p'

As nossas máquinas usam quatro regras: pre, choiceL, choiceR e const, que desdobra uma constante usando defs.

CSLib

...como grafos de transição

Good tea.Good + coffee.Good coin tea coffee tea.Bad Bad coffee.Bad coin coin tea coffee

As duas têm os traços coin tea, coin coffee, … Depois de coin, a boa ainda oferece as duas bebidas; a ruim já se comprometeu com uma.

CSLib

...não bissimilares, diretamente

Suponha uma bissimulação r. Depois de coin, a máquina boa tem um único sucessor, então r precisa relacionar tea.Good + coffee.Good com tea.Bad. Só o primeiro pode fazer coffee:

theorem good_not_bisim_bad_direct : ¬ ((const Machine.good) ~[machines] (const Machine.bad)) := by rintro ⟨r, hr, hb⟩ let p₁ := `(CCS| (tea. const Machine.good) + (coffee. const Machine.good)) let q₁ := `(CCS| tea. const Machine.bad) have hdet : machines.DeterministicStateLabel (const .good) coin := by intro _ _ h₁ h₂ grind [const_tr h₁, const_tr h₂] have h : r p₁ q₁ := match_deterministic hb hr hdet (.const rfl .pre) (.const rfl (.choiceL .pre)) have hpq : p₁ ~[machines] q₁ := ⟨r, h, hb⟩ have hc : machines.Tr p₁ coffee (const .good) := .choiceR .pre grind [hpq.follow_fst]
CSLib

Lógica de Hennessy–Milner

Uma lógica modal para sistemas de transições rotuladas. As fórmulas descrevem que ações um estado pode fazer, e o que vale depois delas:

\begin{aligned} s \models \langle a\rangle\,\varphi &\iff \exists s'.\; s \xrightarrow{a} s' \text{ e } s' \models \varphi && \text{algum } a \text{ é possível, e depois } \varphi \\ s \models [a]\,\varphi &\iff \forall s'.\; s \xrightarrow{a} s' \text{ implica } s' \models \varphi && \text{depois de todo } a,\ \varphi \end{aligned}

mais ⊤, ¬ e ∧.

Teorema de Hennessy–Milner (1985):

  • Estados bissimilares satisfazem as mesmas fórmulas.

  • Para sistemas de imagem finita vale a volta: estados não bissimilares são sempre separados por alguma fórmula.

Usamos a primeira direção, que na CSLib é bisimulation_satisfies:

lemma bisimulation_satisfies {hrb : m.lts.IsHomBisimulation r} (hv : ∀ {s1 s2}, r s1 s2 → ∀ p, m.v s1 p ↔ m.v s2 p) (hr : r s1 s2) (φ : HML.Proposition Label Atom) : ⇓HML[m,s1 ⊨ φ] ↔ ⇓HML[m,s2 ⊨ φ] := by

Autores na CSLib: Fabrizio Montesi (@fmontesi), Marco Peressotti (@mperessotti), Alexandre Rademaker (@arademaker).

CSLib

...uma fórmula, na HML da CSLib

Na CSLib, as fórmulas são avaliadas num modelo, um LTS mais uma valoração das proposições atômicas (Cslib/Logics/HML/Basic.lean):

structure Model State Label Atom where /-- The labelled transition system. -/ lts : LTS State Label /-- Valuation of atoms at states. -/ v : State → Atom → Prop

O nosso modelo m é o LTS das duas máquinas, sem proposições atômicas (Atom := Empty): só as transições importam. A fórmula [coin] ⟨tea⟩ ⊤: depois de toda coin, tea é possível.

/-- Sem proposições atômicas: só as transições importam. -/ abbrev m : HML.Model (Process String Machine) (Act String) Empty := ⟨machines, fun _ _ => False⟩ /-- "Depois de toda moeda, há chá à disposição." -/ def teaAfterCoin : HML.Proposition (Act String) Empty := d[coin] (d⟨tea⟩ ⊤)
CSLib

...que a máquina boa satisfaz e a ruim não

theorem good_ok : ⇓HML[m, const Machine.good ⊨ teaAfterCoin] := by rw [teaAfterCoin, Satisfies.hml_dynBox_iff_forall] rintro s' htr obtain ⟨_, ⟨⟩, ⟨⟩⟩ := const_tr htr exact Satisfies.hml_dynDiamond_intro (Tr.choiceL Tr.pre) (by grind [modal]) theorem bad_fails : ¬ ⇓HML[m, const Machine.bad ⊨ teaAfterCoin] := by rw [teaAfterCoin, Satisfies.hml_dynBox_iff_forall] intro h have := h (pre coffee (const .bad)) (Tr.const rfl (Tr.choiceR Tr.pre)) obtain ⟨_, htr, -⟩ := Satisfies.hml_dynDiamond_iff_exists.mp this grind

Em obtain ⟨_, ⟨⟩, ⟨⟩⟩, cada ⟨⟩ faz análise de casos numa hipótese e a substitui: depois de uma moeda, a máquina boa tem um único sucessor, e a meta passa a falar desse sucessor.

CSLib

...e um teorema

theorem good_not_bisim_bad : ¬ ((const Machine.good) ~[machines] (const Machine.bad)) := by rintro ⟨r, hr, hb⟩ grind [bisimulation_satisfies (m := m) (hrb := hb) (by simp) hr teaAfterCoin, good_ok, bad_fails]

Uma fórmula verdadeira para uma máquina e falsa para a outra é um certificado de que elas não são bissimilares.

CSLib

Três partes da CSLib em 35 linhas

  • Uma linguagem: CCS, com a sua semântica operacional.

  • Uma lógica: HML, avaliada nessa semântica.

  • A infraestrutura semântica que liga as duas: sistemas de transições, bissimulação, o teorema de Hennessy–Milner.

Linguagens produzem sistemas de transições. Lógicas os consomem. A metateoria é provada uma vez só.

CSLib

Onde a CSLib está hoje

Quinze meses e meio depois do primeiro commit:

Métrica

Valor

Arquivos Lean em Cslib/

253

Linhas não vazias

33,727

Teoremas e lemas

2,579

Definições, estruturas, classes

1,179

Contribuidores

57

Pull requests aceitos

622

Estrelas / forks no GitHub

728 / 202

leanprover/cslib, main em c149a9d (2026-10-01).

CSLib

O que tem dentro

Área

Linhas

Destaques

Computability

12,319

Autômatos, máquinas de Turing, URM, circuitos, FLP

Foundations

7,836

LTS, bissimulação, relações, mônadas, dados, sintaxe

Languages

7,004

Cálculos λ, F<:, CCS, coreografias, processos

Logics

3,327

Linear, modal, HML, proposicional

Crypto

1,423

Sigilo perfeito, compartilhamento de segredos, PRGs

MachineLearning

872

Aprendizado PAC, dimensão VC

Algorithms

660

Mônada de tempo, ordenação, Diffie–Hellman

Probability

251

PMF, distância estatística