

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.

O que é o Lean: uma linguagem de programação que também confere provas.
A história do Lean: de projeto de pesquisa a infraestrutura.
O momento do Lean: avanços na matemática, e com IA.
A Mathlib: a biblioteca de matemática.
IA e Lean: por que um verificador é o parceiro natural de um modelo.
Ao vivo: um programa com provas, escrito aqui, no VS Code.
A CSLib, e como começar.


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).

def odd (n : Nat) : Prop := ∃ k, n = 2 * k + 1
theorem square_of_odd_is_odd : odd n → odd (n * n) := byn:ℕ⊢ odd n → odd (n * n)
intro ⟨k₁, e₁⟩n:ℕk₁:ℕe₁:n = 2 * k₁ + 1⊢ odd (n * n)
simp [e₁, odd]n:ℕk₁:ℕe₁:n = 2 * k₁ + 1⊢ ∃ k, (2 * k₁ + 1) * (2 * k₁ + 1) = 2 * k + 1
exists 2 * k₁ * k₁ + 2 * k₁n:ℕk₁:ℕe₁:n = 2 * k₁ + 1⊢ (2 * k₁ + 1) * (2 * k₁ + 1) = 2 * (2 * k₁ * k₁ + 2 * k₁) + 1
liaAll goals completed! 🐙
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).

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)

Quando | Marco |
|---|---|
jul 2013 | Primeiro commit, de Leonardo de Moura |
jan 2017 | Lean 3; em julho nasce a mathlib |
out 2019 | |
jul 2021 | Liquid Tensor Experiment concluído (desafio de Peter Scholze) |
jul–set 2023 | |
jun–jul 2024 | Harmonic, primeira startup baseada em Lean; AlphaProof, prata na IMO |
mai–set 2025 | 50+ cursos
universitários; tática |
jun 2026 | A história vira livro: The Proof in the Code |

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

Lean is one of the most important things happening to math right now.
— Grant Sanderson (3Blue1Brown)
Avanços na matemática, e com IA.

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.




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 |

OpenAI, 1º/8: dez problemas em aberto, cada um com um certificado em Lean.
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/9: Navier–Stokes, um Problema do Milênio, segundo a OpenAI, com a prova em Lean.



16/10: How to Formalize All of Mathematics. A Mathlib recebeu o Prêmio Jean-Pierre Demailly 2026.
17/10: Starting a new journal: uma revista que só aceita artigos com provas verificadas em Lean.

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.

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.


Á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 |

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.

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 := bya:ℝb:ℝ⊢ (a + b) ^ 2 = a ^ 2 + 2 * a * b + b ^ 2
ringAll goals completed! 🐙
example (x : ℝ) : 0 < x ^ 2 + 1 := byx:ℝ⊢ 0 < x ^ 2 + 1
positivityAll goals completed! 🐙
example (x y : ℝ) (h₁ : 2 * x + y ≤ 4) (h₂ : 1 ≤ x) : y ≤ 2 := byx:ℝy:ℝh₁:2 * x + y ≤ 4h₂:1 ≤ x⊢ y ≤ 2
linarithAll goals completed! 🐙
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.

Mantidas pela Lean FRO, vêm com o Lean, sem importar nada:
example (n : Nat) (h : n % 2 = 1) : (n + 1) % 2 = 0 := byn:ℕh:n % 2 = 1⊢ (n + 1) % 2 = 0
omegaAll goals completed! 🐙
example (xs : List Nat) : (xs ++ []).length = xs.length := byxs:List ℕ⊢ (xs ++ []).length = xs.length
simpAll goals completed! 🐙
example (f : Nat → Nat) (h₁ : a = b) (h₂ : f b = c) : f a = c := bya:ℕb:ℕc:ℕf:ℕ → ℕh₁:a = bh₂:f b = c⊢ f a = c
grindAll goals completed! 🐙
example : 2 ^ 10 = 1024 := by⊢ 2 ^ 10 = 1024
decideAll goals completed! 🐙
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.

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

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-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-binsearch: implementação e prova feitas com o Claude Code, 283 linhas. Para confiar no resultado, basta ler dois enunciados:
a:Array Nattarget:Natlo:Nathi:Nath:¬lo ≤ hi⊢ bsearchAux a target lo hi = nonea:Array Nattarget:Natlo:Nathi:Nath:¬lo ≤ hithis:bsearchAux a target lo hi =
if lo ≤ hi then
have mid := lo + (hi - lo) / 2;
if a[mid]! = target then some mid
else
if a[mid]! < target then if mid + 1 > hi then none else bsearchAux a target (mid + 1) hi
else if mid = 0 then none else bsearchAux a target lo (mid - 1)
else none⊢ bsearchAux a target lo hi = nonea:Array Nattarget:Natlo:Nathi:Nath:¬lo ≤ hithis:bsearchAux a target lo hi = none⊢ bsearchAux a target lo hi = noneAll goals completed! 🐙a:Array Nattarget:Natlo:Nathi:Nath:lo ≤ hi⊢ bsearchAux a target lo hi =
if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)a:Array Nattarget:Natlo:Nathi:Nath:lo ≤ hithis:bsearchAux a target lo hi =
if lo ≤ hi then
have mid := lo + (hi - lo) / 2;
if a[mid]! = target then some mid
else
if a[mid]! < target then if mid + 1 > hi then none else bsearchAux a target (mid + 1) hi
else if mid = 0 then none else bsearchAux a target lo (mid - 1)
else none⊢ bsearchAux a target lo hi =
if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)a:Array Nattarget:Natlo:Nathi:Nath:lo ≤ hithis:bsearchAux a target lo hi =
if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)⊢ bsearchAux a target lo hi =
if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)All goals completed! 🐙a:Array Natlo:Nathi:Nathle:lo ≤ hihbound:hi < a.size⊢ lo + (hi - lo) / 2 < a.sizeAll goals completed! 🐙a:Array Nattarget:Nat⊢ ∀ (lo hi : Nat), hi < a.size → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targeta:Array Nattarget:Natlo:Nathi:Nathbound:hi < a.size⊢ ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝⊢ ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:bsearchAux a target lo hi = some i⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:bsearchAux a target lo hi = some ihle:lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:bsearchAux a target lo hi = some ihle:¬lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:bsearchAux a target lo hi = some ihle:lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.size⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = targethres:some (lo + (hi - lo) / 2) = some i⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Nat⊢ ∀ (lo hi : Nat), hi < a.size → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = targetval_eq✝:lo + (hi - lo) / 2 = i⊢ i = lo + (hi - lo) / 2All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = targethres:some (lo + (hi - lo) / 2) = some ihi_eq:i = lo + (hi - lo) / 2⊢ i < a.size ∧ a[i]! = targetAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some i⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihlt:a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihlt:¬a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihlt:a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:none = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:none = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:none = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:lo + (hi - lo) / 2 + 1 > hi⊢ ¬none = some iAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ ¬lo + (hi - lo) / 2 + 1 > hiAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target (lo + (hi - lo) / 2 + 1) hi = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target (lo + (hi - lo) / 2 + 1) hi = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ hi + 1 - (lo + (hi - lo) / 2 + 1) < fuel✝All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target (lo + (hi - lo) / 2 + 1) hi = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ hi < a.sizeAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target (lo + (hi - lo) / 2 + 1) hi = some ihlt:a[lo + (hi - lo) / 2]! < targethstop:¬lo + (hi - lo) / 2 + 1 > hi⊢ hi + 1 - (lo + (hi - lo) / 2 + 1) = hi + 1 - (lo + (hi - lo) / 2 + 1)All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ihlt:¬a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ihlt:¬a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ihlt:¬a[lo + (hi - lo) / 2]! < target⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:none = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:none = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:none = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:lo + (hi - lo) / 2 = 0⊢ ¬none = some iAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:(if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ lo + (hi - lo) / 2 - 1 + 1 - lo < fuel✝All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ lo + (hi - lo) / 2 - 1 < a.sizeAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathle:lo ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethres:bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ihlt:¬a[lo + (hi - lo) / 2]! < targethzero:¬lo + (hi - lo) / 2 = 0⊢ lo + (hi - lo) / 2 - 1 + 1 - lo = lo + (hi - lo) / 2 - 1 + 1 - loAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:bsearchAux a target lo hi = some ihle:¬lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:none = some ihle:¬lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:none = some ihle:¬lo ≤ hi⊢ i < a.size ∧ a[i]! = targeta:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi < a.size → hi + 1 - lo = m → ∀ (i : Nat), bsearchAux a target lo hi = some i → i < a.size ∧ a[i]! = targetlo:Nathi:Nathbound:hi < a.sizefuel:hi + 1 - lo = fuel✝i:Nathres:none = some ihle:¬lo ≤ hi⊢ ¬none = some iAll goals completed! 🐙
theorem bsearch_sound (l : List Nat) (target : Nat) (i : Nat) :
bsearch l target = some i → l[i]? = some target l:List Nattarget:Nati:Nat⊢ bsearch l target = some i → l[i]? = some targetl:List Nattarget:Nati:Nath:bsearch l target = some i⊢ l[i]? = some targetl:List Nattarget:Nati:Nath:(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some i⊢ l[i]? = some targetl:List Nattarget:Nati:Nath:(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some ihemp:l.toArray.isEmpty = true⊢ l[i]? = some targetl:List Nattarget:Nati:Nath:(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some ihemp:¬l.toArray.isEmpty = true⊢ l[i]? = some targetl:List Nattarget:Nati:Nath:(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some ihemp:l.toArray.isEmpty = true⊢ l[i]? = some targetAll goals completed! 🐙l:List Nattarget:Nati:Nath:(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some ihemp:¬l.toArray.isEmpty = true⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray.isEmpty = trueh:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some i⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some i⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some i⊢ l[i]? = some targetl:List Nattarget:Nati:Nat⊢ bsearch l target = some i → l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihq:l.toArray.size = 0⊢ 0 < 0All goals completed! 🐙l:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some in:Nathq:l.toArray.size = n + 1⊢ 0 < n + 1All goals completed! 🐙l:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.size⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.size⊢ 0 < 1All goals completed! 🐙l:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.size⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizehi_lt:i < l.toArray.sizeheq:l.toArray[i]! = target⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizeheq:l.toArray[i]! = targethi_lt:i < l.length⊢ l[i]? = some targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizeheq:l.toArray[i]! = targethi_lt:i < l.length⊢ ∃ h, l[i] = targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizeheq:l.toArray[i]! = targethi_lt:i < l.length⊢ ∃ h, l[i] = targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizeheq:l.toArray[i]! = targethi_lt:i < l.length⊢ l[i] = targetl:List Nattarget:Nati:Nat⊢ bsearch l target = some i → l[i]? = some targetAll goals completed! 🐙l:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizeheq:l.toArray[i]! = targethi_lt:i < l.lengthhlt':i < l.toArray.size⊢ l[i] = targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizehi_lt:i < l.lengthhlt':i < l.toArray.sizeheq:l.toArray[i] = target⊢ l[i] = targetl:List Nattarget:Nati:Nathemp:¬l.toArray = #[]h:(if false = true then none else bsearchAux l.toArray target 0 (l.toArray.size - 1)) = some ihsize:0 < l.toArray.sizehbound:l.toArray.size - 1 < l.toArray.sizehi_lt:i < l.lengthhlt':i < l.toArray.sizeheq:l.toArray[i] = target⊢ l[i] = targetAll goals completed! 🐙l:List Naths:Sorted l⊢ ArraySorted l.toArray 0 (l.toArray.size - 1)l:List Naths:Sorted l⊢ ∀ (i j : Nat), 0 ≤ i → i < j → j ≤ l.length - 1 → j < l.length → l.toArray[i]! ≤ l.toArray[j]!l:List Nat⊢ ∀ (i j : Nat), 0 ≤ i → i < j → j ≤ [].length - 1 → j < [].length → #[][i]! ≤ #[][j]!l:List Nati:Natj:Nata✝²:0 ≤ ia✝¹:i < ja✝:j ≤ [].length - 1hj:j < [].length⊢ #[][i]! ≤ #[][j]!All goals completed! 🐙l:List Natx:Nat⊢ ∀ (i j : Nat), 0 ≤ i → i < j → j ≤ [x].length - 1 → j < [x].length → #[x][i]! ≤ #[x][j]!l:List Natx:Nati:Natj:Nata✝:0 ≤ ihij:i < jhj:j ≤ [x].length - 1hjs:j < [x].length⊢ #[x][i]! ≤ #[x][j]!l:List Natx:Nati:Natj:Nata✝:0 ≤ ihij:i < jhj:j ≤ [x].length - 1hjs:j < 1⊢ #[x][i]! ≤ #[x][j]!All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!⊢ ∀ (i j : Nat),
0 ≤ i →
i < j →
j ≤ (x :: y :: t).length - 1 → j < (x :: y :: t).length → (x :: y :: t).toArray[i]! ≤ (x :: y :: t).toArray[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Natj:Nata✝:0 ≤ ihij:i < jhjhi:j ≤ (x :: y :: t).length - 1hjsize:j < (x :: y :: t).length⊢ (x :: y :: t).toArray[i]! ≤ (x :: y :: t).toArray[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Natj:Nata✝:0 ≤ ihij:i < jhjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1⊢ (x :: y :: t).toArray[i]! ≤ (x :: y :: t).toArray[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Natj:Nata✝:0 ≤ ihij:i < jhjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1⊢ (x :: y :: t)[i]! ≤ (x :: y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!j:Nathjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1a✝:0 ≤ 0hij:0 < j⊢ (x :: y :: t)[0]! ≤ (x :: y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!j:Nathjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1i:Nata✝:0 ≤ i + 1hij:i + 1 < j⊢ (x :: y :: t)[i + 1]! ≤ (x :: y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!j:Nathjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1a✝:0 ≤ 0hij:0 < j⊢ (x :: y :: t)[0]! ≤ (x :: y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!j:Nathjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1a✝:0 ≤ 0hij:0 < j⊢ x ≤ (x :: y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0hjhi:0 ≤ t.length + 1 + 1 - 1hjsize:0 < t.length + 1 + 1hij:0 < 0⊢ x ≤ (x :: y :: t)[0]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:0 < j + 1⊢ x ≤ (x :: y :: t)[j + 1]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0hjhi:0 ≤ t.length + 1 + 1 - 1hjsize:0 < t.length + 1 + 1hij:0 < 0⊢ x ≤ (x :: y :: t)[0]!All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:0 < j + 1⊢ x ≤ (x :: y :: t)[j + 1]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:0 < j + 1⊢ x ≤ (y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0hjhi:0 + 1 ≤ t.length + 1 + 1 - 1hjsize:0 + 1 < t.length + 1 + 1hij:0 < 0 + 1⊢ x ≤ (y :: t)[0]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1⊢ x ≤ (y :: t)[j + 1]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0hjhi:0 + 1 ≤ t.length + 1 + 1 - 1hjsize:0 + 1 < t.length + 1 + 1hij:0 < 0 + 1⊢ x ≤ (y :: t)[0]!All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1⊢ x ≤ (y :: t)[j + 1]!l:List Naths:Sorted l⊢ ArraySorted l.toArray 0 (l.toArray.size - 1)l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ y ≤ (y :: t)[j + 1]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ 0 ≤ 0All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ 0 < j + 1All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j + 1 ≤ (y :: t).length - 1l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j + 1 ≤ t.lengthAll goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j + 1 < (y :: t).lengthl:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j < t.lengthAll goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!a✝:0 ≤ 0j:Nathjhi:j + 1 + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 + 1 < t.length + 1 + 1hij:0 < j + 1 + 1hyle:y ≤ (y :: t)[j + 1]!⊢ x ≤ (y :: t)[j + 1]!All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!j:Nathjhi:j ≤ t.length + 1 + 1 - 1hjsize:j < t.length + 1 + 1i:Nata✝:0 ≤ i + 1hij:i + 1 < j⊢ (x :: y :: t)[i + 1]! ≤ (x :: y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Nata✝:0 ≤ i + 1hjhi:0 ≤ t.length + 1 + 1 - 1hjsize:0 < t.length + 1 + 1hij:i + 1 < 0⊢ (x :: y :: t)[i + 1]! ≤ (x :: y :: t)[0]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1⊢ (x :: y :: t)[i + 1]! ≤ (x :: y :: t)[j + 1]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Nata✝:0 ≤ i + 1hjhi:0 ≤ t.length + 1 + 1 - 1hjsize:0 < t.length + 1 + 1hij:i + 1 < 0⊢ (x :: y :: t)[i + 1]! ≤ (x :: y :: t)[0]!All goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1⊢ (x :: y :: t)[i + 1]! ≤ (x :: y :: t)[j + 1]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)ih:∀ (i j : Nat),
0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t).toArray[i]! ≤ (y :: t).toArray[j]!i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1⊢ (y :: t)[i]! ≤ (y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ (y :: t)[i]! ≤ (y :: t)[j]!l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ 0 ≤ iAll goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ i < jAll goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j ≤ (y :: t).length - 1l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j ≤ t.lengthAll goals completed! 🐙l:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j < (y :: t).lengthl:List Natx:Naty:Natt:List Nathxy:x ≤ ya✝¹:Sorted (y :: t)i:Nata✝:0 ≤ i + 1j:Nathjhi:j + 1 ≤ t.length + 1 + 1 - 1hjsize:j + 1 < t.length + 1 + 1hij:i + 1 < j + 1ih:∀ (i j : Nat), 0 ≤ i → i < j → j ≤ (y :: t).length - 1 → j < (y :: t).length → (y :: t)[i]! ≤ (y :: t)[j]!⊢ j < t.length + 1All goals completed! 🐙a:Array Nattarget:Nat⊢ ∀ (lo hi : Nat),
hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natlo:Nathi:Nat⊢ hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝⊢ hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = target⊢ ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hi⊢ ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:¬lo ≤ hi⊢ ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hi⊢ ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hi⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hi⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Nat⊢ ∀ (lo hi : Nat),
hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some iAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hi⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.size⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = target⊢ (if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some (lo + (hi - lo) / 2)a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:a[lo + (hi - lo) / 2]! = target⊢ some (lo + (hi - lo) / 2) = some (lo + (hi - lo) / 2)All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! = target then some (lo + (hi - lo) / 2)
else
if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < target⊢ ∃ i, (if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < target⊢ ∃ i, (if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ia:Array Nattarget:Nat⊢ ∀ (lo hi : Nat),
hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethlt':k < lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 + 1 ≤ ka:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethge:k ≥ lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 + 1 ≤ ka:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethlt':k < lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 + 1 ≤ ka:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethlt':k < lo + (hi - lo) / 2⊢ lo ≤ kAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethlt':k < lo + (hi - lo) / 2this:a[k]! ≤ a[lo + (hi - lo) / 2]!⊢ lo + (hi - lo) / 2 + 1 ≤ kAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethge:k ≥ lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 + 1 ≤ ka:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < k⊢ lo + (hi - lo) / 2 + 1 ≤ ka:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hihle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethklo:lo ≤ lo + (hi - lo) / 2hkhi:lo + (hi - lo) / 2 ≤ hihkeq:a[lo + (hi - lo) / 2]! = targethge:lo + (hi - lo) / 2 ≥ lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 + 1 ≤ lo + (hi - lo) / 2a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < k⊢ lo + (hi - lo) / 2 + 1 ≤ kAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hihle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethklo:lo ≤ lo + (hi - lo) / 2hkhi:lo + (hi - lo) / 2 ≤ hihkeq:a[lo + (hi - lo) / 2]! = targethge:lo + (hi - lo) / 2 ≥ lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 + 1 ≤ lo + (hi - lo) / 2a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hihle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethklo:lo ≤ lo + (hi - lo) / 2hkhi:lo + (hi - lo) / 2 ≤ hihkeq:a[lo + (hi - lo) / 2]! = targethge:lo + (hi - lo) / 2 ≥ lo + (hi - lo) / 2⊢ ¬a[lo + (hi - lo) / 2]! = targetAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ ∃ i, (if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ ¬lo + (hi - lo) / 2 + 1 > hiAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ ∃ i, bsearchAux a target (lo + (hi - lo) / 2 + 1) hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ hi + 1 - (lo + (hi - lo) / 2 + 1) < fuel✝All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ hi + 1 - (lo + (hi - lo) / 2 + 1) = hi + 1 - (lo + (hi - lo) / 2 + 1)All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ hi < a.sizeAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ lo ≤ lo + (hi - lo) / 2 + 1All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:a[lo + (hi - lo) / 2]! < targethk_right:lo + (hi - lo) / 2 + 1 ≤ k⊢ hi ≤ hiAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < target⊢ ∃ i,
(if a[lo + (hi - lo) / 2]! < target then
if lo + (hi - lo) / 2 + 1 > hi then none else bsearchAux a target (lo + (hi - lo) / 2 + 1) hi
else if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) =
some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < target⊢ ∃ i, (if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < target⊢ ∃ i, (if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!⊢ ∃ i, (if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ia:Array Nattarget:Nat⊢ ∀ (lo hi : Nat),
hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hlt':k < lo + (hi - lo) / 2⊢ k ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2⊢ k ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hlt':k < lo + (hi - lo) / 2⊢ k ≤ lo + (hi - lo) / 2 - 1All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2⊢ k ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt✝:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < k⊢ k ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hihle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hklo:lo ≤ lo + (hi - lo) / 2hkhi:lo + (hi - lo) / 2 ≤ hihkeq:a[lo + (hi - lo) / 2]! = targethge:lo + (hi - lo) / 2 ≥ lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt✝:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < k⊢ k ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt✝:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < k⊢ k ≤ hiAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt✝:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < k⊢ k < a.sizeAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt✝:target < a[lo + (hi - lo) / 2]!hge:k ≥ lo + (hi - lo) / 2hgt:lo + (hi - lo) / 2 < kthis:a[lo + (hi - lo) / 2]! ≤ a[k]!⊢ k ≤ lo + (hi - lo) / 2 - 1All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hihle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hklo:lo ≤ lo + (hi - lo) / 2hkhi:lo + (hi - lo) / 2 ≤ hihkeq:a[lo + (hi - lo) / 2]! = targethge:lo + (hi - lo) / 2 ≥ lo + (hi - lo) / 2⊢ lo + (hi - lo) / 2 ≤ lo + (hi - lo) / 2 - 1a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hihle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hklo:lo ≤ lo + (hi - lo) / 2hkhi:lo + (hi - lo) / 2 ≤ hihkeq:a[lo + (hi - lo) / 2]! = targethge:lo + (hi - lo) / 2 ≥ lo + (hi - lo) / 2⊢ ¬a[lo + (hi - lo) / 2]! = targetAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1⊢ ∃ i, (if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ia:Array Nattarget:Nat⊢ ∀ (lo hi : Nat),
hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hmid0:lo + (hi - lo) / 2 = 0⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hmid0:lo + (hi - lo) / 2 = 0hk0:k = 0⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hmid0:lo + (hi - lo) / 2 = 0hk0:k = 0hlo0:lo = 0⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0 + (hi - 0) / 2]!hmid0:0 + (hi - 0) / 2 = 0hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0 + (hi - 0) / 2]!hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1hmid0:hi < 2⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0 + hi / 2]!hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1hmid0:hi < 2⊢ Falsea:Array Nattarget:Nat⊢ ∀ (lo hi : Nat),
hi < a.size → ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some iAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0 + hi / 2]!hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1hmid0:hi < 2this:hi / 2 = 0⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0 + 0]!hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1hmid0:hi < 2this:hi / 2 = 0⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0 + 0]!hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1hmid0:hi < 2this:hi / 2 = 0⊢ Falsea:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ihi:Nathbound:hi < a.sizehkhi:0 ≤ hihkeq:a[0]! = targetfuel:hi + 1 - 0 = fuel✝hsorted:ArraySorted a 0 hihle:0 ≤ hihmid_lo:0 ≤ 0 + (hi - 0) / 2hmid_hi:0 + (hi - 0) / 2 ≤ hihmid_lt:0 + (hi - 0) / 2 < a.sizeheq:¬a[0 + (hi - 0) / 2]! = targethlt:¬a[0 + (hi - 0) / 2]! < targethgt:target < a[0]!hklo:0 ≤ 0hk_left:0 ≤ 0 + (hi - 0) / 2 - 1hmid0:hi < 2this:hi / 2 = 0⊢ FalseAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ ∃ i, (if lo + (hi - lo) / 2 = 0 then none else bsearchAux a target lo (lo + (hi - lo) / 2 - 1)) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ ∃ i, bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ ∃ i, bsearchAux a target lo (lo + (hi - lo) / 2 - 1) = some ia:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ lo + (hi - lo) / 2 - 1 + 1 - lo < fuel✝All goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ lo + (hi - lo) / 2 - 1 + 1 - lo = lo + (hi - lo) / 2 - 1 + 1 - loAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ lo + (hi - lo) / 2 - 1 < a.sizeAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ lo ≤ loAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:lo ≤ hihmid_lo:lo ≤ lo + (hi - lo) / 2hmid_hi:lo + (hi - lo) / 2 ≤ hihmid_lt:lo + (hi - lo) / 2 < a.sizeheq:¬a[lo + (hi - lo) / 2]! = targethlt:¬a[lo + (hi - lo) / 2]! < targethgt:target < a[lo + (hi - lo) / 2]!hk_left:k ≤ lo + (hi - lo) / 2 - 1hzero:lo + (hi - lo) / 2 ≠ 0⊢ lo + (hi - lo) / 2 - 1 ≤ hiAll goals completed! 🐙a:Array Nattarget:Natfuel✝:Natih:∀ (m : Nat),
m < fuel✝ →
∀ (lo hi : Nat),
hi + 1 - lo = m →
hi < a.size →
ArraySorted a lo hi → (∃ k, lo ≤ k ∧ k ≤ hi ∧ a[k]! = target) → ∃ i, bsearchAux a target lo hi = some ilo:Nathi:Natfuel:hi + 1 - lo = fuel✝hbound:hi < a.sizehsorted:ArraySorted a lo hik:Nathklo:lo ≤ khkhi:k ≤ hihkeq:a[k]! = targethle:¬lo ≤ hi⊢ ∃ i, bsearchAux a target lo hi = some iAll goals completed! 🐙
theorem bsearch_complete (l : List Nat) (target : Nat)
(hs : Sorted l) (hm : target ∈ l) :
∃ i, bsearch l target = some i l:List Nattarget:Naths:Sorted lhm:target ∈ l⊢ ∃ i, bsearch l target = some il:List Nattarget:Naths:Sorted lhm:target ∈ l⊢ ∃ i,
(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some il:List Nattarget:Naths:Sorted lhm:∃ i h, l[i] = target⊢ ∃ i,
(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some il:List Nattarget:Naths:Sorted lhm:∃ i h, l[i] = target⊢ ∃ i,
(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some il:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = target⊢ ∃ i,
(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some il:List Nattarget:Naths:Sorted lhm:target ∈ l⊢ ∃ i, bsearch l target = some il:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targetheq:l.toArray = #[]⊢ Falsel:List Nattarget:Naths:Sorted lhm:target ∈ l⊢ ∃ i, bsearch l target = some il:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targetheq:l.toArray = #[]h:#[].size = l.length⊢ l.length = 0l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targetheq:l.toArray = #[]h:0 = l.length⊢ l.length = 0All goals completed! 🐙l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targetheq:l.toArray = #[]hlen:l.length = 0⊢ FalseAll goals completed! 🐙l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]⊢ ∃ i,
(have a := l.toArray;
if a.isEmpty = true then none else bsearchAux a target 0 (a.size - 1)) =
some il:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]⊢ ∃ i, bsearchAux l.toArray target 0 (l.toArray.size - 1) = some il:List Nattarget:Naths:Sorted lhm:target ∈ l⊢ ∃ i, bsearch l target = some il:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]⊢ 0 < l.lengthAll goals completed! 🐙l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ ∃ i, bsearchAux l.toArray target 0 (l.toArray.size - 1) = some il:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l.toArray.size - 1 < l.toArray.sizel:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ ArraySorted l.toArray 0 (l.toArray.size - 1)l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ ∃ k, 0 ≤ k ∧ k ≤ l.toArray.size - 1 ∧ l.toArray[k]! = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l.toArray.size - 1 < l.toArray.sizel:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ 0 < 1All goals completed! 🐙l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ ArraySorted l.toArray 0 (l.toArray.size - 1)All goals completed! 🐙l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ ∃ k, 0 ≤ k ∧ k ≤ l.toArray.size - 1 ∧ l.toArray[k]! = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ k ≤ l.toArray.size - 1l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l.toArray[k]! = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ k ≤ l.toArray.size - 1l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ k ≤ l.length - 1All goals completed! 🐙l:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l.toArray[k]! = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l[k]! = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l[k]! = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l[k] = targetl:List Nattarget:Naths:Sorted lk:Nathk:k < l.lengthhkeq:l[k] = targethne:l.toArray ≠ #[]hsize:0 < l.toArray.size⊢ l[k] = targetAll goals completed! 🐙
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?
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).

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 |
✅ 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 |
|
|
|
✅ 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 |
✅ 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).
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.
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.
A biblioteca CSLib | A CSLib Initiative |
|---|---|
| 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.
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.
github.com/cslib-community: projetos construídos com, em volta de, e para a CSLib.
Projeto | O quê |
|---|---|
Semântica computacional com Lean, o livro do curso de PLN da EMAp deste semestre, escrito em Verso como estes slides | |
Functional Algorithms Design, o livro do curso de Estruturas de Dados e Algoritmos da EMAp, que também será escrito em Verso | |
| Algoritmos em grafos, com provas de correção e de tempo |
| A lógica de descrição básica, ALC |
| Formalização do SQLite em Lean |
| Porte das provas do s2n-bignum (Amazon) para Lean |
| Agentes de IA escrevem o Lean; pessoas decidem o que vale provar |
Na EMAp
Matemática Discreta (material).
Técnicas e Análise de Algoritmos (TAA, mestrado; antes Estruturas de Dados e Algoritmos), com o livro Functional Algorithms Design.
Recuperação de Dados e PLN (graduação em Ciência de Dados e IA), com o livro CSwL.
Curso de verão de Lean, e eletivas sobre Lean e métodos formais.
Fora
Programming with Proofs, Universidade de Aveiro (2026).
Dois deles estão na lista de cursos com Lean da comunidade, que já passou de 50 cursos universitários.
Jogar: Natural Number Game.
Programar: Functional Programming in Lean.
Provar: Theorem Proving in Lean 4 e Mathematics in Lean.
Aprofundar: Lean 4 for Program Verification in the Age of AI, quatro aulas de Leonardo de Moura (Marktoberdorf, agosto de 2026).
Conversar: o Zulip do Lean.
Contribuir: Mathlib e CSLib aceitam PRs, e revisar também é contribuir.
Alexandre Rademaker
FGV/EMAp
Exemplos em slides, para o caso de a demonstração ao vivo falhar.
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)
#eval55 fib 10
55#eval[0, 1, 1, 2, 3, 5, 8, 13, 21, 34] (List.range 10).map fib
A saída ao lado de cada #eval foi calculada pelo Lean quando estes slides
foram gerados.
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[("Ana", 9), ("Bruno", 7)] turma.map fun a => (a.nome, a.media)
[("Ana", 9), ("Bruno", 7)]#checkAluno.media : Aluno → Nat @Aluno.media
Tudo tem um tipo, e #check mostra qual é.
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 := byn:Nat⊢ 0 + n = n
induction n with
| zero =>⊢ 0 + 0 = 0 rflAll goals completed! 🐙
| succ k ih =>k:Natih:0 + k = k⊢ 0 + (k + 1) = k + 1 rw [Nat.add_succ,k:Natih:0 + k = k⊢ (0 + k).succ = k + 1 ihk:Natih:0 + k = k⊢ k.succ = k + 1]All goals completed! 🐙
Por que n + 0 = n sai direto da definição, mas 0 + n = n precisa de
indução?
Uma afirmação falsa não passa, por mais convincente que pareça:
theorem errado (n : Nat) : n - 1 + 1 = n := byn:Nat⊢ n - 1 + 1 = n
omegaAll goals completed! 🐙omega could not prove the goal:
No usable constraints found. You may need to unfold definitions so `omega` can see linear arithmetic facts about `Nat` and `Int`, which may also involve multiplication, division, and modular remainder by constants.
O contraexemplo é n = 0, porque em Nat temos 0 - 1 = 0:
#eval1 (0 - 1 + 1 : Nat)
1Com a hipótese certa, a mesma tática fecha a prova:
theorem certo (n : Nat) (h : 0 < n) : n - 1 + 1 = n := byn:Nath:0 < n⊢ n - 1 + 1 = n
omegaAll goals completed! 🐙
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).
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)
#eval[1, 2, 3, 4, 5] ⟪insertionSort [5, 3, 1, 4, 2]⟫
[1, 2, 3, 4, 5]#eval[1, 2, 3, 4, 5] ⟪mergeSort [5, 3, 1, 4, 2]⟫
[1, 2, 3, 4, 5]#eval499500 (insertionSort (List.range 1000).reverse).time
499500#eval4932 (mergeSort (List.range 1000).reverse).time
4932⟪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α:Typeinst✝:LinearOrder αx:αl:List α⊢ (insertSorted x l).ret = List.orderedInsert (fun x1 x2 => x1 ≤ x2) x l
fun_induction insertSorted with grindAll goals completed! 🐙
@[simp, grind =]
theorem ret_insertionSort (xs : List α) :
⟪insertionSort xs⟫ = xs.insertionSort (· ≤ ·) := byα:Typeinst✝:LinearOrder αxs:List α⊢ (insertionSort xs).ret = List.insertionSort (fun x1 x2 => x1 ≤ x2) xs
fun_induction insertionSort with grindAll goals completed! 🐙
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).
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α:Typeinst✝:LinearOrder αxs:List α⊢ (mergeSort xs).ret = (insertionSort xs).ret
obtain ⟨hs, hp⟩ := mergeSort_correct xsα:Typeinst✝:LinearOrder αxs:List αhs:IsSorted (mergeSort xs).rethp:(mergeSort xs).ret.Perm xs⊢ (mergeSort xs).ret = (insertionSort xs).ret
simpa using List.Perm.eq_of_sortedLE hs.sortedLE List.sortedLE_insertionSort
(hp.trans (List.perm_insertionSort _ xs).symm)All goals completed! 🐙
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.
insertionSort é n²theorem insertSorted_time (x : α) (l : List α) :
(insertSorted x l).time ≤ l.length := byα:Typeinst✝:LinearOrder αx:αl:List α⊢ (insertSorted x l).time ≤ l.length
fun_induction insertSorted with grindAll goals completed! 🐙
@[simp] theorem insertionSort_length (xs : List α) :
⟪insertionSort xs⟫.length = xs.length := byα:Typeinst✝:LinearOrder αxs:List α⊢ (insertionSort xs).ret.length = xs.length
simpAll goals completed! 🐙
theorem insertionSort_time (xs : List α) :
(insertionSort xs).time ≤ xs.length ^ 2 := byα:Typeinst✝:LinearOrder αxs:List α⊢ (insertionSort xs).time ≤ xs.length ^ 2
fun_induction insertionSortα:Typeinst✝:LinearOrder α⊢ (pure []).time ≤ [].length ^ 2α:Typeinst✝:LinearOrder αy✝:αys✝:List αih1✝:(insertionSort ys✝).time ≤ ys✝.length ^ 2⊢ (do
let __do_lift ← insertionSort ys✝
insertSorted y✝ __do_lift).time ≤
(y✝ :: ys✝).length ^ 2 <;>α:Typeinst✝:LinearOrder α⊢ (pure []).time ≤ [].length ^ 2α:Typeinst✝:LinearOrder αy✝:αys✝:List αih1✝:(insertionSort ys✝).time ≤ ys✝.length ^ 2⊢ (do
let __do_lift ← insertionSort ys✝
insertSorted y✝ __do_lift).time ≤
(y✝ :: ys✝).length ^ 2 simpα:Typeinst✝:LinearOrder αy✝:αys✝:List αih1✝:(insertionSort ys✝).time ≤ ys✝.length ^ 2⊢ (insertionSort ys✝).time + (insertSorted y✝ (List.insertionSort (fun x1 x2 => x1 ≤ x2) ys✝)).time ≤ (ys✝.length + 1) ^ 2
grind [insertSorted_time, insertionSort_length]All goals completed! 🐙
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α:Typeinst✝:LinearOrder αxs:List α⊢ let n := xs.length;
(mergeSort xs).time ≤ n * clog 2 n
grind [mergeSort_time_le, timeMergeSortRec_le]All goals completed! 🐙O pior caso exato da inserção é aceito:
set_option maxRecDepth 4000 in
example :
(insertionSort (List.range 100).reverse).time = 100 * 99 / 2 := byα:Typeinst✝:LinearOrder α⊢ (insertionSort (List.range 100).reverse).time = 100 * 99 / 2
decideAll goals completed! 🐙
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α:Typeinst✝:LinearOrder α⊢ (mergeSort (List.range 1000).reverse).time = 5000
native_decideα:Typeinst✝:LinearOrder α⊢ (mergeSort (List.range 1000).reverse).time = 5000Tactic `native_decide` evaluated that the proposition
(mergeSort (List.range 1000).reverse).time = 5000
is false
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).
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:
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.
Com uma lógica: achar uma fórmula que uma máquina satisfaz e a outra não.
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.
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.
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.
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⊢ ¬(«const» Machine.good) ~[machines] («const» Machine.bad)
rintro ⟨r, hr, hb⟩r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines r⊢ False
let p₁ := `(CCS| (tea. const Machine.good) + (coffee. const Machine.good))r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))⊢ False
let q₁ := `(CCS| tea. const Machine.bad)r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))q₁:Process String Machine := pre tea («const» Machine.bad)⊢ False
have hdet : machines.DeterministicStateLabel (const .good) coin := by⊢ ¬(«const» Machine.good) ~[machines] («const» Machine.bad)
intro _ _ h₁ h₂r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))q₁:Process String Machine := pre tea («const» Machine.bad)s₁✝:Process String Machines₂✝:Process String Machineh₁:machines.Tr («const» Machine.good) coin s₁✝h₂:machines.Tr («const» Machine.good) coin s₂✝⊢ s₁✝ = s₂✝
grind [const_tr h₁, const_tr h₂]All goals completed! 🐙r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))q₁:Process String Machine := pre tea («const» Machine.bad)hdet:machines.DeterministicStateLabel («const» Machine.good) coin⊢ False
have h : r p₁ q₁ :=
match_deterministic hb hr hdet
(.const rfl .pre) (.const rfl (.choiceL .pre))r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))q₁:Process String Machine := pre tea («const» Machine.bad)hdet:machines.DeterministicStateLabel («const» Machine.good) coinh:r p₁ q₁⊢ False
have hpq : p₁ ~[machines] q₁ := ⟨r, h, hb⟩r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))q₁:Process String Machine := pre tea («const» Machine.bad)hdet:machines.DeterministicStateLabel («const» Machine.good) coinh:r p₁ q₁hpq:p₁ ~[machines] q₁⊢ False
have hc : machines.Tr p₁ coffee (const .good) := .choiceR .prer:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines rp₁:Process String Machine := (pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good))q₁:Process String Machine := pre tea («const» Machine.bad)hdet:machines.DeterministicStateLabel («const» Machine.good) coinh:r p₁ q₁hpq:p₁ ~[machines] q₁hc:machines.Tr p₁ coffee («const» Machine.good)⊢ False
grind [hpq.follow_fst]All goals completed! 🐙
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 ⊨ φ] := byState:Type u_2Label:Type u_1Atom:Type u_3m:HML.Model State Label Atomr:State → State → Props1:States2:Statehrb:m.lts.IsHomBisimulation rhv:∀ {s1 s2 : State}, r s1 s2 → ∀ (p : Atom), m.v s1 p ↔ m.v s2 phr:r s1 s2φ:HML.Proposition Label Atom⊢ ⇓Modal[m.toModal,s1 ⊨ φ] ↔ ⇓Modal[m.toModal,s2 ⊨ φ]Autores na CSLib: Fabrizio Montesi (@fmontesi), Marco Peressotti (@mperessotti), Alexandre Rademaker (@arademaker).
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 → PropO 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⟩ ⊤)
theorem good_ok : ⇓HML[m, const Machine.good ⊨ teaAfterCoin] := by⊢ ⇓Modal[m.toModal,«const» Machine.good ⊨ teaAfterCoin]
rw [teaAfterCoin,⊢ ⇓Modal[m.toModal,«const» Machine.good ⊨ d[coin](d⟨tea⟩⊤)] Satisfies.hml_dynBox_iff_forall⊢ ∀ (s' : Process String Machine), m.lts.Tr («const» Machine.good) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]]⊢ ∀ (s' : Process String Machine), m.lts.Tr («const» Machine.good) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]
rintro s' htrs':Process String Machinehtr:m.lts.Tr («const» Machine.good) coin s'⊢ ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]
obtain ⟨_, ⟨⟩, ⟨⟩⟩ := const_tr htrhtr:m.lts.Tr («const» Machine.good) coin ((pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good)))⊢ ⇓Modal[m.toModal,(pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good)) ⊨ d⟨tea⟩⊤]
exact Satisfies.hml_dynDiamond_intro (Tr.choiceL Tr.pre) (byhtr:m.lts.Tr («const» Machine.good) coin ((pre tea («const» Machine.good)).choice (pre coffee («const» Machine.good)))⊢ ⇓Modal[m.toModal,«const» Machine.good ⊨ ⊤] grind [modal]All goals completed! 🐙)
theorem bad_fails : ¬ ⇓HML[m, const Machine.bad ⊨ teaAfterCoin] := by⊢ ¬⇓Modal[m.toModal,«const» Machine.bad ⊨ teaAfterCoin]
rw [teaAfterCoin,⊢ ¬⇓Modal[m.toModal,«const» Machine.bad ⊨ d[coin](d⟨tea⟩⊤)] Satisfies.hml_dynBox_iff_forall⊢ ¬∀ (s' : Process String Machine), m.lts.Tr («const» Machine.bad) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]]⊢ ¬∀ (s' : Process String Machine), m.lts.Tr («const» Machine.bad) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]
intro hh:∀ (s' : Process String Machine), m.lts.Tr («const» Machine.bad) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]⊢ False
have := h (pre coffee (const .bad)) (Tr.const rfl (Tr.choiceR Tr.pre))h:∀ (s' : Process String Machine), m.lts.Tr («const» Machine.bad) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]this:⇓Modal[m.toModal,pre coffee («const» Machine.bad) ⊨ d⟨tea⟩⊤]⊢ False
obtain ⟨_, htr, -⟩ := Satisfies.hml_dynDiamond_iff_exists.mp thish:∀ (s' : Process String Machine), m.lts.Tr («const» Machine.bad) coin s' → ⇓Modal[m.toModal,s' ⊨ d⟨tea⟩⊤]this:⇓Modal[m.toModal,pre coffee («const» Machine.bad) ⊨ d⟨tea⟩⊤]w✝:Process String Machinehtr:m.lts.Tr (pre coffee («const» Machine.bad)) tea w✝⊢ False
grindAll goals completed! 🐙
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.
theorem good_not_bisim_bad :
¬ ((const Machine.good) ~[machines] (const Machine.bad)) := by⊢ ¬(«const» Machine.good) ~[machines] («const» Machine.bad)
rintro ⟨r, hr, hb⟩r:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines r⊢ False
grind [bisimulation_satisfies (m := m) (hrb := hb) (byr:Process String Machine → Process String Machine → Prophr:r («const» Machine.good) («const» Machine.bad)hb:machines.IsBisimulation machines r⊢ ∀ {s1 s2 : Process String Machine}, r s1 s2 → ∀ (p : Empty), m.v s1 p ↔ m.v s2 p simpAll goals completed! 🐙) 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.
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ó.
Quinze meses e meio depois do primeiro commit:
Métrica | Valor |
|---|---|
Arquivos Lean em | 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).
Área | Linhas | Destaques |
|---|---|---|
| 12,319 | Autômatos, máquinas de Turing, URM, circuitos, FLP |
| 7,836 | LTS, bissimulação, relações, mônadas, dados, sintaxe |
| 7,004 | Cálculos λ, F<:, CCS, coreografias, processos |
| 3,327 | Linear, modal, HML, proposicional |
| 1,423 | Sigilo perfeito, compartilhamento de segredos, PRGs |
| 872 | Aprendizado PAC, dimensão VC |
| 660 | Mônada de tempo, ordenação, Diffie–Hellman |
| 251 | PMF, distância estatística |