Conjuntos e relações são a notação que todo texto de matemática pressupõe.
Este capítulo é onde eles se tornam objetos do Lean — e onde as afirmações
que se costuma fazer sobre eles passam a ser teoremas a demonstrar.
Um conjunto de elementos de α por sua função característica: a função
que, dado um elemento, responde se ele pertence ao conjunto. Há duas
maneiras de responder:
α → Bool calcula a resposta. O resultado é true ou false, e
pode-se rodar.
α → Prop enuncia a resposta. O resultado é uma afirmação, que se pode
provar.
A segunda versão é, literalmente, como conjuntos são definidos no Lean.
defSet.{u} : Type u→Type u :=funα=>α→Prop#printSet
Um Set α é uma função α → Prop, e nada mais. A notação de conjunto que
se escreve na prática é açúcar para construir essa função, e pertencer é
aplicá-la — as duas coisas são a mesma, e o rfl prova:
Escrever x ∈ A em vez de A x é comodidade de leitura. Vale saber
disso porque, quando uma prova sobre conjuntos empacar, desdobrar a
notação até a aplicação costuma destravar — e o desdobramento é rfl,
não um passo que precise de justificativa. Então above2, aplicado, é o
predicado aplicado — e above2 3 é literalmente 3 > 2, sem nenhuma
camada de conjunto no meio:
decide sozinho não fecha 3 ∈ above2: a mensagem é failed to
synthesize Decidable (3 ∈ above2). O motivo é que above2 é um def, e
decide não desdobra definições — para ele o objetivo é opaco. unfold
faz esse desdobramento manualmente, e depois decide calcula:
A3. Prove a inclusão. unfold above2 above5 desdobra as duas
definições; simp only [Set.mem_ofPred_eq] at h desdobra a pertinência
em h até a desigualdade, que omega então resolve.
União e interseção são disjunção e conjunção elemento a elemento. As duas
inclusões abaixo valem para conjuntos quaisquer, e as provas não
precisam saber nada sobre eles.
Exercício★(union-contains)
A4. Todo conjunto está contido na sua união com outro. Depois do
intro, Or.inl prova uma disjunção pelo lado esquerdo.
A Mathlib (Community, 2020)Marginal noteThe mathlib Community, 2020. “The Lean mathematical library”. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020). tem esses dois últimos prontos, com os nomes
Set.subset_union_left e Set.inter_subset_left. Aqui o exercício é
escrever a prova, não encontrá-los — mas vale procurar depois, para ver
como as coisas se chamam.
Explique por que ∅ ⊆ A vale para todo conjunto A. Prove-o. O
argumento é vacuoso, e a prova deve exibir isso.
Não vale usar Set.empty_subset (nem simp, que o encontra): esse
lema é exatamente o enunciado, e citá-lo apagaria o exercício.
declaration uses `sorry`example:∅⊆A:=sorry
Exercício★(empty-vs-singleton)
Explique a diferença entre ∅ e {∅}.
∅ é o conjunto que não tem elemento nenhum; {∅} é um conjunto que tem
exatamente um elemento, e esse elemento é o conjunto vazio. São,
portanto, objetos distintos: um está vazio, o outro não. A confusão vem
de olhar para o "conteúdo do conteúdo" — o único elemento de {∅} é ele
mesmo vazio, mas isso não faz o recipiente ficar vazio.
Cardinalidades: |∅| = 0 e |{∅}| = 1. (A prova abaixo explora
justamente isso: ∅ ∈ {∅} vale por rfl, e transportar essa
pertinência pela igualdade suposta daria ∅ ∈ ∅, isto é, False.)
Não vale usar Set.singleton_ne_empty, Set.empty_ne_singleton nem
simp.
Verifique que o complemento do complemento de A é A.
Use Set.ext. Uma das duas direções precisa de raciocínio clássico: vale
Classical.byContradiction, Classical.em ou Classical.byCases.
Não vale usar compl_compl (nem simp, nem tauto, nem grind): a
Mathlib prova esse lema para qualquer álgebra de Boole, e conjuntos são
uma. Aqui o exercício é o argumento sobre elementos.
Qual inclusão precisou do argumento clássico? A direção que precisa é
Aᶜᶜ ⊆ A, isto é, ¬¬(x ∈ A) → x ∈ A (eliminação da dupla negação). A
outra, A ⊆ Aᶜᶜ, ou seja x ∈ A → ¬¬(x ∈ A), é construtiva: dados
hx : x ∈ A e hnx : x ∈ Aᶜ, basta aplicar hnx hx para obter
False. A razão é que, na leitura construtiva, ¬ P é P → False; de
uma função que transforma "refutações de P" em absurdo não se extrai,
por meios construtivos, uma prova de P. Passar de ¬¬P para P é
exatamente o conteúdo do terceiro excluído.
α → Prop enuncia a pertinência. Existe também α → Bool, que a
calcula, e é o que se usa quando o conjunto é finito e a resposta tem
que ser computada — é o caso da verificação de modelos, no fim do livro,
onde decidir se uma sentença vale num modelo é percorrer um domínio finito.
A versão que se enuncia já existe na biblioteca: Even n afirma que n
é o dobro de algum número, sem dizer como encontrá-lo. Aqui está a
distinção em ato. isEven é um algoritmo — divide e compara o resto.
Even é uma condição de verdade — existe um r tal que n = r + r.
São conteúdos diferentes, e por isso vale a pena que sejam objetos
diferentes.
Provar Even 4 é exibir o r que a afirmação promete, junto com a
verificação de que ele serve.
example:Even4:=by⊢ Even4unfoldEven⊢ ∃r,4=r+rapplyExists.intro2⊢ 4=2+2-- alternative `use`rflAll goals completed! 🐙
Nada obriga, a priori, uma afirmação e um algoritmo a dizerem a mesma
coisa. Que estes dois digam é um fato sobre os naturais, Mathlib já traz
a prova, sob o nome Nat.even_iff:
example(n:Nat):Evenn↔n%2=0:=Nat.even_iff
Provado isso, Even n passa a ser uma afirmação que se pode calcular
para um n dado — e o Lean faz isso sem que se peça nada:
true#evalEven4
true
Vale reparar no que acabou de acontecer. Even 4 é uma afirmação, não
um programa; ainda assim o #eval respondeu true. Há um mecanismo por
trás disso, que registra quais afirmações admitem esse cálculo e como
fazê-lo — e ele é uma classe de tipos, como o BEq e o DecidableEq de
Programação Funcional no Lean. A classe se chama Decidable.
Um conjunto representa a função que responde se um elemento pertence.
Uma relação binária faz o mesmo com pares: é a função que, dados dois
elementos, responde se estão na relação. Em Lean isso não é analogia
nenhuma — é a definição:
Rel α β é α → β → Prop. É a primeira vez neste capítulo que o
domínio deixa de ser um tipo qualquer e passa a ter conteúdo linguístico:
um domínio de duas entidades, e a relação de gostar entre elas.
O domínio de entidades. Duas bastam para os exemplos deste capítulo.
A inversa de uma relação troca a ordem dos argumentos, e é flip quem
faz isso. Em língua, é o que a voz passiva faz: Dorothy likes Toto e
Toto is liked by Dorothy descrevem o mesmo par, em ordens opostas.
Compor duas relações é encadeá-las por um elemento intermediário: R
composta com S relaciona x a z quando existe um y com x R y e
y S z. É Relation.Comp, e provar uma composição é exibir esse
intermediário.
Composição é o que define parentesco em cadeia: "avô" é "pai" composto
com "pai". Aqui, quem gosta de quem gosta de quem:
Vale a mesma escolha da seção de conjuntos. A divisibilidade vem na
biblioteca na versão que enuncia — m ∣ n afirma que existe um fator
que leva de m a n, e provar é exibi-lo — e ainda assim se calcula,
porque a instância Decidable existe:
example:(3:Nat)∣12:=⟨4,rfl⟩true#eval(3∣12:Prop)
true
false#eval(5∣12:Prop)
false
example:∀n:Nat,n∣n:=fun_=>Nat.dvd_refl_
Relação é a estrutura que a verificação de modelos vai usar para dar
modelo a um fragmento — um domínio de entidades e, para cada verbo, a
relação que ele denota — e à qual o tratamento de verbos de mais de dois
lugares, e do escopo entre eles, volta mais tarde.
Exercício★★(cartesian-square)
Tome A como o conjunto {Kasparov, Karpov, Anand}. Encontre A × A.
Como A é finito, o produto cartesiano é finito e a Mathlib o calcula:
Finset é o tipo dos conjuntos finitos, Fintype α é a evidência de
que α tem finitos elementos (e dá Finset.univ, o conjunto de todos
eles), e s ×ˢ t é o produto cartesiano de dois Finset. Construa A ×
A e prove que tem nove elementos.
A evidência de que Player é finito: a lista dos seus elementos, mais a
prova de que não falta ninguém. (O normal seria deriving Fintype, mas
o gerador automático está quebrado nesta versão da Mathlib — então a
instância vai à mão, o que também mostra o que um Fintype é.)
A Mathlib tem Std.Symm.flip_eq : flip r = r para relações simétricas.
Usá-lo é permitido — mas então o trabalho é seu de construir a instância
Std.Symm R a partir de h, que é o mesmo argumento. A prova direta é
mais curta.
Estas relações são finitas, e por isso podem ser dadas como o Finset
dos seus pares — e aí a transitividade se decide: escreva-a como uma
proposição sobre os pares do Finset e o decide calcula a resposta.
Complete isTransitive e depois decida os cinco casos. É abbrev, e
não def, para que a instância Decidable seja encontrada através da
definição — trocar por def faz o decide falhar com failed to
synthesize Decidable (isTransitive r3), porque a busca de instâncias
não desdobra um def.
Verifique que uma relação R é transitiva se e somente se R ∘ R ⊆ R.
Não vale usar SetRel.isTrans_iff_comp_subset_self, que é este
enunciado na versão "relação como conjunto de pares" (vale abrir
Mathlib/Data/Rel.lean e ver: o exercício aparece lá provado, com esse
nome). Prove as duas direções.
Funções já apareceram — o capítulo sobre Lean as apresentou como tipo
primitivo, α → β. O que se acrescenta aqui é a ligação com as relações:
uma função é uma relação com uma restrição. Para cada a, no máximo um
b está relacionado a ele. Rel α β, do jeito que ficou definido acima,
não impõe isso — likesR bem poderia relacionar dorothy a duas
entidades diferentes. Uma função é o caso particular em que a resposta é
única, e é justamente essa unicidade que permite escrever f x em vez de
"algum b tal que (x, b) ∈ f".
Toda relação, vista como conjunto de pares, tem uma função
característica: a função que decide se um par está nela. Reaproveitando
likesR de acima — que já é a própria função característica da relação
de gostar, escrita como Entity → Entity → Prop: dados x e y,
likesR x y é a afirmação "x gosta de y", nem mais nem menos. Isto
prepara a leitura da seção seguinte: conjunto e relação são funções
para Prop (ou Bool), não apenas "correspondem" a elas.
Exercício★(successor-as-relation)
A função sucessor s : ℕ → ℕ é dada por n ↦ n + 1. Qual é a
composição de s com ela mesma?
∘ é Function.comp, e duas funções são iguais quando concordam em
todo ponto — é o que funext diz.
≤ é uma relação binária sobre os naturais. Qual é a função
característica correspondente?
Escreva a função e prove que ela é adequada — que responde true
exatamente quando a relação vale.
Aqui Prop e Bool se encontram: m ≤ n é uma proposição, leChar m
n é um cálculo. A ponte é decide, e os lemas que a atravessam são
decide_eq_true_iff, of_decide_eq_true e decide_eq_true.
Seja f : A → B uma função. Mostre que a relação R dada por (x, y) ∈
R se e somente se f x = f y é uma relação de equivalência sobre A.
Equivalence R é a estrutura com os três campos refl, symm e
trans; Setoid α é a mesma coisa empacotada com a relação, e é o que
a Mathlib usa para quocientes.
Não vale usar Setoid.ker: é exatamente esta relação, já construída
na Mathlib com a prova de que é de equivalência. Prove os três campos.