2021.1 FMC2, turma de Thanos

Horários sincronizados: (quando tiver) será dentro dos 246N34 [20h35–22h15]
Contato:thanos@imd.ufrn.br
Playlists: FMC2 2019.1 (aulas gravadas)
TeX / LaTeX / ConTeXt (minicurso e sermões)
Monitoria/TA: fmc.imd.ufrn.br
Turmas anteriores: ..

Info

Pré-requisitos

É pré-requisito ter aprendido bem o conteudo transversal de FMC1. Sem aprender esses assuntos primeiro, não faz sentido se matricular em FMC2.

(Obs.: aprenderpassar.)

Então—ANTES de começar—é bom estudar os capítulos seguintes do fmcbook:

  • Introducções
  • Linguagens
  • Demonstrações
  • Naturais; recusão; indução

Alem disso, é pré-requisito que os alunos matriculados tem tempo e vontade para estudar, fazer os (muitos) trabalhos atribuídos, etc.

(Obs.: estudarler.)

Antes de começar é bom dar uma lida nos:

  1. Comments on style de James Munkres.
  2. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

Disclaimer. Eu suponho que os alunos desta turma verificaram os pré-requisitos da disciplina e assumam responsabilidade sobre o seu conhecimento. Lembrete:

pré-requisito

substantivo masculino

  1. condição prévia indispensável para se alcançar algo, seguir uma formação, fazer um curso, ocupar uma função etc.
  2. *(pedagogia)* num currículo, disciplina cursada obrigatoriamente antes de outra, por envolver conhecimentos prévios necessários ao estudo da segunda.

Conteúdo

Conteúdo transversal (durante todas as unidades)
Lógica proposicional e de predicados. Linguagem matemática de definições, teoremas, demonstrações, etc. Definições por recursão – provas por indução. A linguagem de conjuntos, funções, e relações.
Conjuntos, Funções, e Relações
Conjuntos, sua notação, suas operações, e seus leis. Uniões disjuntas, famílias e partições. Tuplas ordenadas e produto cartesiano. As operações unitárias de união e interseção. As relações de subconjunto, e de pertencer. Multiconjuntos e sequências.

Funções, o conceito de função e suas propriedades. Intensão x extensão. Domínio, codomínio. Imagem, pre-imagem. Funções totais e parciais, injetivas, sobrejetivas, bijetivas. Aridade. Função constante, função identidade, projeções, funções características. Funções recursivas; recursão mutual. Funções de ordem superior. A notação de λ-calculus. Funções x predicados.

Relações e suas propriedades. Relações de equivalência, clásses de equivalência. Operações em relações, inversão, composição, fechos.

Aplicações e assuntos auxiliares
Enumerações e conceito intuitivo de cardinalidade. λ-calculus, lógica combinatória. Elementos de teoria dos tipos. Fixpoints e recursão. Programação funcional. Programação lógica. Bancos de dados.

Bibliografia

(Conhece o libgen.rs?)

Principal

Zermelo–Fraenkel

Auxiliar

Para cada um dos assuntos que tratamos, procure a secção «Leitura complementar» no capítulo correspondente do fmcbook para mais referências.

  • Pinter: A book of abstract algebra (2–5, 6, 12, 17)
  • Aluffi: Algebra: Chapter 0 (1, 2)
  • Davey & Priestley: Introduction to lattices and order (1, 2) [DP]
  • Lawvere & Schanuel: Conceptual Mathematics: A first introduction to categories (I, II)
  • Raymond Smullyan: A beginner’s guide to mathematical logic (Volume 1)
  • Birkhoff & Mac Lane: A survey of modern algebra (1.11; 1.1–1.5, 1.10, 1.12)
  • Herstein: Topics in Algebra (2.1–2.5 [skip # and ∗])
  • Simmons: Introduction to topology and modern analysis (1)
  • Loomis & Sternberg: Advanced Calculus (0)
  • João Marcos: Lógica Aplicada à Computação website (TdC, R&I)

Programação e proof assistants

Links

Dicas

Tecnologias e ferramentas necessárias

Obs.: As tecnologías/ferramentas seguintes podem mudar durante a disciplina—exceto a primeira.

  1. PAPEL (um caderno para dedicar à disciplina) e LAPIS/CANETA
  2. TeX / LaTeX / ConTeXt. (Online editor/compilador: Overleaf.)
  3. Um aparelho com câmera e uma ferramenta para escanear teu caderno
  4. Zulip: leia as instruções
  5. Google Meet
  6. O proof assistant Coq para algumas atividades. (Coq à la pastebin: CollaCoq.)
  7. Possivelmente usaremos outros proof assistants e linguagens de programação também.
  8. Git e uma conta no github ou gitlab.
  9. Muito recomendado mas não necessário: um sistema Unix (Minicurso Unix 2019.2)
  10. Muito recomendado mas não necessário: (neo)vim e Emacs

(Instalem e criem uma conta para usar onde necessário.)

Regras

  1. Nunca escreva algo que você mesmo não sabe explicar: (i) o que significa; (ii) seu papel na tua resolução. Por exemplo: um aluno escreveu a frase seguinte na sua demonstração: «Como f é cancelável pela esquerda temos que g=h». Ele deve saber o que significa ser cancelável pela esquerda é também explicar como isso foi usado e/ou o que isso tem a ver com essa parte da sua demonstração.
  2. Qualquer trabalho poderá ser questionado em forma de prova oral via videochamada, em modo privado ou aberto. Se um aluno não consegue explicar o que ele mesmo escreveu numa resolução, será considerado plágio e o aluno será reprovado imediatamente por nota e por faltas.
  3. Participando, nunca dê uma resposta que tu não pensou sozinho.
  4. Não tente “forçar a barra” perguntando ou respondendo coisas aleatórias com objetivo único de ganhar pontos. Os pontos de participação não correspondem em apenas perguntas ou dúvidas que mostram interesse. O interesse é implícito pelo fato que tu escolheu matricular nesta turma—não vale pontos.
  5. Não procurem resoluções em qualquer lugar fora dos indicados em cada homework. O único recurso aceitável para procurar ajuda é o nosso Zulip, especificamente seus canáis públicos (não DM).
  6. Proibido consultar o apêndice de resoluções do fmcbook durante a disciplina exceto quando for explicitamente permitido por mim. (Os apêndices de dicas são permitidos sim.)

Avaliação e faltas

Disclaimer. Eu suponho que os alunos desta turma escolheram se matricular por interesse em aprender seu conteudo. O ideal seria ignorar assuntos irrelevantes de avaliação, presenças, carga horária, etc., e se jogar nos estudos.

Avaliação

A nota final de cada aluno vai ser principalmente baseada em um ou mais dos: (i) provas orais com videochamada em modo privado e/ou aberto; (ii) sua participação (que inclue correação de trabalhos de outros alunos); (iii) suas resoluções de problem sets escritas e submetidas em TeX/LaTeX/ConTeXt; (iv) caderno escaneado com resoluções de homeworks; (v) resoluções em algum proof assistant, possivelmente publicadas em repositório git

Note que:

  • Os problem sets / homeworks podem envolver simular uma prova escrita em tempo real.
  • Cada aluno será responsável para manter organizado e bem escrito o seu caderno com todos os teoremas e exercícios que estudou durante a disciplina.

Presenças / Faltas

As presenças/faltas serão cadastradas baseadas na participação, na entrega dos trabalhos, e na entrega de caderno. Nenhuma dessas coisas é opcional, logo aluno que não as faz com a devida freqüência será reprovado por faltas.

FAQs

Dynamic content

Pontos

Pontos de participação

Problem Sets (PS)

U1

Homework (HW)

Homeworks são atribuidos também: durante as aulas gravadas e no Zulip.

Obs.:

  • Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas.
  • «Até» é sempre inclusivo.
  • Homeworks marcados assim são opcionais; considero o resto obrigatório.
  • Depois de cada aula, um homework é sempre válido, obrigatório, e essencial: sem olhar para teu caderno, defina todas as noções e demonstre TODOS os teoremas da aula;
    while (não conseguiu) {
      estude o assunto;
      tente novamente;
    }
    
  • Exceto quando é explicitamente pedido, faça os homework sem consultar nenhum livro/texto/etc. auxiliar
  • Para os trabalhos em proof assistant vou postar mais informações logo.

08/06/2021

  • URGENTE: Nem tente resolver nada desta disciplina sem terminar esses HW relacionados aos prerequisitos:
    1. Estude os capítulos 1–3 («Introducções», «Linguagens», «Demonstrações»). As minhas aulas relevantes do FMC1/2019.2 (24/07/2019–12/08/2019) podem ajudar, estão no playlist do link acima.
    2. Resolva sozinho o A da Prova 1.1 de FMC1/2019.2.
    3. Estude a resposta do A no seu gabarito.
    4. Assiste a aula com o sermão e a resolução (09/09/2019)
  • Os seguintes (também sobre pré-requisitos) podem ser trabalhos em paralelo com os da disciplina:
    1. Estude brutalmente o capítulo «Os números naturais: recursão; indução» do fmcbook e e assista minhas aulas relevantes do FMC1/2019.2 (24/07/2019–11/09/2019).
    2. Estude as «Prova 0» de FMC2 dos semestres passados e tente resolvê-las sozinho: 2020.1; 2019.1; 2018.2; 2018.1; 2017.2; 2017.1.
    3. Depois, leia bem todas as correções digitalizadas (que tem nos sites) para aproveitar dos comentários disponíveis e evitar erros comuns.

09/06/2021

  1. Estude os:
    • § Conceito, notação, igualdade
    • § Intensão, extensão
    • § Relações entre conjuntos e como defini-las
    • § Mais set-builder

11/06/2021

  1. § Vazio, universal, singletons
  2. § Oito proposições simples
  3. § Operações entre conjuntos e como defini-las
  4. § Demonstrando igualdades e inclusões
  5. Entenda bem o «Não escreva assim!» da 7.63, e não escreva assim!
  6. § Cardinalidade
  7. § Powerset
  8. Π7.3; Π7.4; Π7.7

14/06/2021

  1. Capítulo 7: até o primeiro intervalo de problemas
  2. Π7.1,2,5,6,8
  3. § Tuplas

16/06/2021

  1. Nesse problema é proibido usar os «feitiços fortes»: nem LEM, nem dupla negação, e logo não podes demonstrar algo por Reductio ad absurdum. E logo, para atacar uma disjunção precisa escolher um dos dois componentes e matá-lo! Suponha que P denota uma proposição arbitrária. Quais das propriedades seguintes consegues demonsrar?
    1. P ⇒ ¬¬P
    2. P ⇐ ¬¬P
    3. ¬¬(P∨¬P)
    4. se P⇒Q então ¬Q⇒¬P
    5. se ¬Q⇒¬P então P⇒Q
  2. Para aquela das duas últimas que tu não conseguiu demonstrar (por justa causa!), tem como demonstrar «quase» isso, ou seja, tem como demonstrar uma coisa parecida mas mais fraca. Adivinha qual é, e demonstre!
  3. § Produto cartesiano
  4. § Implementação de tipo
  5. § n-tuplas
  6. § Seqüências
  7. § Intervalos na reta real
  8. Π7.8–10
  9. § Famílias indexadas
  10. § Conjuntos indexados vs famílias indexadas
  11. § Disjuntos dois-a-dois
  12. § Traduzindo de e para a linguagem de conjuntos
  13. § Produto cartesiano generalizado
  14. § Multisets
  15. Π7.11–15

17/06/2021

  1. Capítulo 7
  2. Resolva as provas 1.1 embaixo; use o #set-fun-rel; e depois de tentar cada uma, estude bem o seu gabarito!

18/06/2021

  1. § Conceito, notação, igualdade
  2. § Diagramas internos e externos
  3. § Como definir e como não definir funcões
  4. § Expressões com buracos

21/06/2021

  1. § Um toque de lambda
  2. § Composição
  3. § Funcções de graça
  4. § Aplicação parcial
  5. § Leis de composição
  6. § Diagramas comutativos

24/06/2021

  1. Capítulo 8: até o primeiro intervalo de problemas
  2. § Injecções, Sobrejecções, bijecções

25/06/2021

  1. § Funcções inversas
  2. Problemas: Π8.9, Π8.10, Π8.11, Π8.12

29/06/2021

  1. § Produtos e demais construções
  2. § Funcções inversas
  3. § Funcções de ordem superior
  4. § Imagens, preimagens
  5. § Uma viagem épica
  6. Problemas: Π8.13–Π8.20

01/07/2021

  1. § Currificação
  2. § Funcções estilo pointfree
  3. § Funcções parciais
  4. § Definições recursivas [até a nota 8.241: «O que tá acontecendo?»]

02/07/2021

  1. Jogue o The Natural Number Game. (Até o fim!)

06/07/2021

  1. § Definições recursivas
  2. Resolva as provas 1.2 seguintes, use o #set-fun-rel, e depois de tentar cada uma, estude bem o seu gabarito!:

08/07/2021

  1. § Coproduto; união disjunta
  2. § Duma resolução para um problema para uma teoria
  3. § Pouco de cats—um primeiro toque de categorias
  4. Π8.21–Π8.30

14/07/2021

  1. Capítulo 8: até o fim
  2. § Conceito, notação, igualdade
  3. § Definindo relações
  4. § Diagramas internos
  5. § Construções e operações em relações
  6. § Propriedades de relações
  7. § Fechos
  8. § Bottom-up vs. top-down
  9. § Relações de equivalência

19/07/2021

  1. Capítuo 10: até o fim
  2. Π10.1–Π10.25

20/07/2021

  1. Resolva as provas 1.3 seguintes, use o #set-fun-rel, e depois de tentar cada uma, estude bem o seu gabarito!:

27/07/2021

  1. Leia o artigo Revenge of the nerds, de Paul Graham
  2. Brinque com Haskell/Agda/Idris, usando as idéias que temos encontrado na disciplina
  3. Conheça uma LISP: Racket e/ou Clojure
  4. Para programadores de Java, C++, e C#: palestra introduzindo Scala por Venkat Subramaniam

29/07/2021

  1. Estude o Capítulo 12 até a § «Primeiras conseqüências»

01/08/2021

  1. Estude o Capítulo 12 até a § «Escolhendo as leis»
  2. Critério: ∀a∀b (ab)⁻¹ = a⁻¹b⁻¹ ⇒ G abeliano
  3. Critério: ∀a∀b (ab)² = a²b² ⇒ G abeliano
  4. Teorema: se a é um membro dum grupo, todas as suas potências (naturais) também são
  5. Teorema: se a é um membro dum grupo, todas as suas potências (inteiros) também são
  6. G abel ⇔ ∀a∀b ( (ab)² = a²b² )

03/08/2021

  1. § «Subgrupos»
  2. Problemas: Π12.{1,2,3,7,8}

06/08/2021

  1. Até § «Congruências e coclasses»
  2. Revise o 121: «Conjuntos indexados vs. famílias indexadas» se não sente confortável com esse assunto.
  3. O resto dos problemas do primeiro intervalo

09/08/2021

  1. Capítulo 12: Até o segundo intervalo de problemas.

14/08/2021

  1. Capítulo 12: todo.

16/08/2021

  1. Capítulo 13: todo
  2. Capítulo 14: todo
  3. O contexto histórico do capítulo 15
  4. Existem irracionais a,b tais que ab é racional?
  5. Dado que π,e são transcendentais; algum dos π + e, eπ é racional?

23/08/2021

  1. Capítulo 15: todo.

26/08/2021

  1. Resolva o problema dos casamentos infinitos e demonstre o teorema de Bernstein (CSB)
  2. Estude bem o problema do «Áristos vs Blammenos» e tente resolvê-lo sozinho antes de olhar na resposta depois do «spoiler alert»

30/08/2021

  1. Capítulo 16: até o primeiro intervalo de problemas

01/09/2021

  1. Capítulo 16: até o segundo intervalo de problemas

03/09/2021

  1. Justifique as definições de adição e de multiplicação: a recursão usada não é imediata pelo teorema da recursão mas pode ser reduzida pra ser; como?

07/09/2021

  1. § «Mais axiomas (ZF)»
  2. § «Axiomas de escolha (ZFC)»
  3. Demonstre o Teorema Schröder–Bernstein formalmente (sem falar de casamentos)
  4. Demonstre o princípio da boa ordem para o sistema Peano que construimos
  5. Capítulo 16: o resto das secções
  6. Ultima Problemas: Π16.9; Π16.10; Π16.11; Π16.12; Π16.13; Π16.14; Π16.15

08/09/2021

  1. [fmcbook]: Capítulo 17
  2. [DP]: Itens 1.1–1.33
  3. [DP]: Exercícios (pp. 25–32): 1.1; 1.2; 1.3; 1.4; 1.5; 1.9; 1.12; 1.13; 1.14; 1.16; 1.17

10/09/2021

  1. Justifique matematicamente (i.e., sem handwaving) o termo «preordem»
  2. [DP]: Itens 1.34–1.38
  3. [DP]: Itens 2.1–2.7
  4. [DP]: Exercícios (pp. 25–32): 1.7; 1.8; 1.10; 1.11; 1.23; 1.24; 1.27

14/09/2021

  1. Como definirias o subláttice?
  2. Como definirias o homomorfismo entre láttices?
  3. Como definirias o subláttice gerado por um subconjunto dum lattice L?

15/09/2021

  1. Demonstre (sozinho com notas/textos fechados) o teorema de Knaster–Tarski
  2. Enuncie o princípio da indução Noetheriana
  3. Resolva todo o homework que tu não resolveu na hora certa
  4. Resolva os problemas do capítulo 2 de [DP]. Cuidado: a definição no [DP] de sublattice não aceita o vazio; por isso ele denota por Sub(L) a colecção dos seus (deles) sublattices de L, e por Sub₀(L) a colecção dos nossos sublattices de L. Ou seja: Sub₀(L) = Sub(L) ∪ {Ø}.

Histórico

Vamos acompanhar as aulas gravadas de FMC2, e discutir no Zulip.

07/06/2021: Intro, Demonstrações [video]

  • type errors
  • = vs ⇔
  • «def»
    • cuidado com os quantificadores
    • por que «praticamente»? qual a excessão?
  • intensão vs extensão
  • demonstrações: linha de código vs comentário
    • se..então.. vs como..logo..
    • «seja..» vs «existe..»
    • quantificador existencial: como atacar e como usar
    • variáveis ligadas vs livres
    • escolha de variável, variável fresca
    • escopos de variáveis
    • sombreamento (shadowing) de variáveis
    • indentação em cálculos
  • Três exercísios: mesma coisa ou não?
    • quantificador universal: como atacar
    • implicação: como atacar
    • conjunção: como usar e como atacar
  • vício de absurdo
  • a rendundância dos «… é verdade»
  • abuso de gerúndios, vírgula mágica, etc.
  • «para algum» e perigos de ambigüidade
    • não podemos trocar a ordem de quantificadores diferentes
  • definição e seu contexto
  • não misturem símbolos de fórmulas com texto, não são abreviações
  • setinhas mágicas
    • ⇒ vs «logo»
  • tipografia, caligrafia
    • matemática é case sensitive
    • afirmações secas

08/06/2021: Linguagens

  • (toda): [video]
    • Expressões aritméticas (ArEx)
    • Expressões aritméitcas com variáveis (AlgEx)
      • Usando recursão para matar os “…”
    • Números, numerais, dígitos
    • A linguagem da lógica proposicional (L₀)
    • Metalinguagem; metavariáveis
    • Usos e limitações da L₀
    • As linguagens de FOL
  • (00:25:40–01:11:58): [video]
    • Açúcar sintáctico, abreviações
    • Convenção: notação infixa
    • Existenciais e universais restritos
    • Existência e unicidade
    • A expressão x₁,…,xₙ
    • Metalinguagem enriquecida e as setinhas ⇐,⇒,⇔

09/06/2021: Conjuntos

  • (a partir de 00:41:53): [video]
    • Tipos de objetos e como introduzí-los
    • Conceito de conjunto
    • Noções primitivas: ser conjunto, pertencer (∈)
    • Conjuntos como “black boxes
    • Igualdade entre conjuntos: A=B
    • As relações binárias: ⊆, ⊇
    • Notação
    • Set comprehension (Set-builder notation)
      • Nunca use «|» como abreviação de «tal que» nem em texto nem nas fórmulas existenciais!
    • Intensão vs extensão
    • «um conjunto é determinado por seus membros»
    • os «def» em cima de = e de ⟺
    • Açucar sintáctico no set-builder
    • ⊊ vs ⊈ vs

11/06/2021: Conjuntos [video]

  • Cuidado: O uso de ⊂ na literatura
  • Definindo o conjunto vazio: nossos deveres
  • O predicado Empty(–)
  • Variáveis livres e ligadas; sombreamento de variável
  • Obrigação de definir notação (nome) para objeto: artigo definido vs. indefinido
  • Demonstrações de existência e unicidade
  • Teorema: existência do conjunto vazio
  • Teorema: unicidade do conjunto vazio
  • O conjunto vazio (Ø)
  • Singletons
  • O conjunto universal
  • Oito proposições sobre o Ø e um conjunto A
  • Escolhendo a ordem de atacar teoremas
  • {Ø} ≠ Ø
  • Operações entre conjuntos e dois jeitos de defini-las
  • As operações binárias: ∩, ∪, , Δ
  • A operação unária de complemento: ~
  • O operador Powerset (℘)
  • Iterando o ℘ no Ø
  • Cardinalidade de ℘A

14/06/2021: Conjuntos [video]

  • Demonstrando igualdades e inclusões
  • Convenções de notação e nomenclatura
  • As operações unárias de união e intersecção ⋂, ⋃
  • O que é «dual(mente)»?
  • Seguindo as definições
  • Mecanicamente vs. no coração
  • «prova por repetição da definição»
  • Iterando os ⋂ e ⋃ no Ø
  • «por vacuidade»
  • Mais um jogo de demonstração
  • Tuplas
  • igualdade, tamanho, black boxes
  • projeções: πᵢ; projᵢ; fst, snd; outl, outr
  • n-tuplas
  • Implementando um tipo: 3-tuplas

16/06/2021: Conjuntos [video]

  • Recap
  • O tipo de 1-tuplas
  • O tipo de 0-tuplas
  • A única 0-tupla: ()
  • Como pensar no tipo void da C
  • Equações fundamentais de tuplas
  • Produto cartesiano (×)
  • Cardinalidade do A×B
  • Definindo o Aⁿ
  • Implementação-agnóstico
  • Seqüências
  • outras notações
  • União e Intersecção de seqüências de conjuntos
  • Famílias indexadas
  • Exemplo: Os conjuntos Aₚ e Cₚ de todos os ancestrais e todos os filhos de p
  • Traduzindo afirmações da linguagem natural para relações entre conjuntos e vice-versa
  • União e Intersecção de famílias indexadas de conjuntos
  • Família indexada como generalização de n-tuplas e seqüências
  • Σ vs. ⋃
  • Riemann’s rearrangement theorem
  • Produto cartesiano generalizado (de família indexada de conjuntos)
  • Um exercício para aprender como atacar e como usar alvos que involvem operações grandes

17/06/2021: Conjuntos

  • Conjuntos: [video até 00:50:55]
    • Conjuntos disjuntos dois-a-dois («pairwise disjoint»): definição com e sem índices
    • Os operadores binários ∪ e ∩ como açucar sintático (definido pelos operadores unários ⋃ e ⋂ respeitivamente)
    • Como usar um fato do tipo D≠Ø em nossas provas: «Seja d∈D.»
    • lim inf, lim sup

18/06/2021: Funções; Conjuntos

  • Funções: [video a partir de 00:50:56]
    • Conceito, notação, igualdade.
    • Igualdade extensional vs. intensional
    • Duas religiões sobre funções e seus black boxes
    • O conjunto (A→B) (também denotado por BA)
    • (Co)domínios vazios.
    • Diagramas internos e externos.
    • Como definir e como não definir funções
    • Expressões com buracos.
  • Conjuntos, Funções: [video]
    • Seqüências de conjuntos: lim inf, lim sup, lim
    • Cuidado: “sejando” membros de conjuntos sem usar apenas uma variável
    • Diagramas internos e externos
    • Como definir e como não definir funções
    • Diferença entre f(x) e f
    • Expressões com buracos
    • A notação lambda

21/06/2021: Funções: [video]

  • Mini-sermão sobre provas escritas
  • Um toque de λ-cálculo
  • Computação com λ
  • β-redex; β-reducção
  • α-renomeamento (α-equivalência) e captura de variável
  • η-equivalência
  • essas idéias vistas em conjuntos (set builder)
  • first-class citizens
  • desafio: achar almas (lambdas) para habitar corpos (típos)
  • funções de graça: identidade
  • composição
  • mais funções de graça: inclusão A↪B
  • leis de composição
  • operações totais vs parciais
  • associatividade da composição
  • comutatividade?
  • possui identidade(s)?
  • aplicação parcial
  • mais funções de graça: restricção
  • diagramas comutativos

24/06/2021: Funções: [video]

  • constante: três definições
  • função com (co)domínio vazio
  • função característica
  • Unix shell: um calculador de booleanos
  • if-then-else expressions vs branching statements
  • mais funções de graça:
    • cross (f×g);
    • pair (f,g);
    • pointwise (f*g)
    • diagonal Δ
  • Funções injetoras, sobrejetoras, bijetoras: formalmente e informalmente
  • Exemplo: codificação dos pares de Nats nos Nats
  • Cardinalidade de (A↣B)

25/06/2021: Funções: [video

  • iterações
  • uma prova errada não quis dizer teorema errado
  • conseqüência de teorema errado não quis dizer que a conclusão é errada
  • a composição preserve as «-jetividades»;
  • a frase «pela escolha de»
  • inversas com pontos–«por dentro»;
  • exercícios
  • leis da inversa
  • o que podemos concluir se uma composição é bijetora

28/06/2021: Funções: [video]

  • uma viagem épica: mono e epi
  • estilo pointfree (ou pointless)
  • imagem e preimagem
  • problema na notação
  • possível definição alternativa de preimagem
  • problema na notação alternativa f(X)?
  • funções de ordem superior
  • a função-imagem respeita as uniões e as intersecções?

01/07/2021: Funções [video]

  • função-imagem: nível coração
  • funções parciais
  • funções não-determinísticas
  • funções para implementar outros típos
  • seqüências, famílias indexadas
  • restrição com buraco: seu tipo
  • tipos dependentes
  • currificação
  • programando funções: escopos; dados; alvos;
  • definindo funções por recursão
  • quantas das k,d,c aceitas como definidas?

06/07/2021: Funções [video]

  • definindo funções por recursão
  • associatividade algebrica de operador vs. associatividade sintáctica de conectivo
  • higher-order fun
  • um λ não terminante
  • Quantas idempotentes no 3?
  • de união para o coproduto

08/07/2021: Funções; Categorias [video até 01:21:21]

  • funções
    • Sermão: poluição do escopo
    • de união para o coproduto
    • o problema de definir a f∪g
    • união disjunta ; coproduto ; sum type
    • conjuntos isomórficos/isómorfos
    • definindo a f+g
    • produtos vs. coprodutos: nível coração
  • categorias
    • definição
    • exemplos
    • o conceito de produto

13/07/2021: Relações

  • relações [video a partir de 01:21:21]
    • conceito, notação
    • diagramas internos
    • definindo relações
    • igualdade
    • intensional vs extensional
    • construções e operações em relações
    • relação oposta
    • composição
    • RT=T? RF=F?
  • relações [video]
    • notação: R∘S vs S∘R
    • propriedades de relações
    • fechos informalmente
    • a ordem dos fechos importa?
    • fechos formalmente
    • potências/iterações de relação
    • preguiças nos diagramas internos
    • um exemplo de fecho
    • relações de equivalência
    • classes de equivalência

19/07/2021: Relações; Programação [video] e [video]

  • Relações
    • fechos: top-down vs bottom-up
    • partições
    • o conjunto quociente
    • enxergando o conjunto quociente
    • subconjuntos finitos vs cofinitos
    • relações de ordem
    • relações recursivas
    • relações de ordem superior
    • perigos de funções mal-definidas
    • ε-perto é uma relação de equivalência?
  • Programação
    • paradigmas
    • programação imperativa (procedural; OO)
    • puramente OO
    • programação declarativa (funcional; lógica)
    • side effects
    • lazy vs strict
    • static vs dynamic types
    • puramente funcional
  • Relações
    • Quantas relações de equivalência num conjunto com 3 membros?
  • Programação
    • Lazy vs strict (call-by-name, call-by-value, call-by-need, call-by-push-value)
    • turing-completeness
    • higher-order
    • dependent types
    • Lisps
    • Abuso de linguagens
    • Conselhos
    • Programação Funcional
    • Indução e recursão nas listas
    • Programação Lógica
    • Funções como relações

29/07/2021 [1/2]: Programação; Algebra abstrata; Teoria dos grupos [video]

  • Programação
    • Turing complete vs Pacman complete
    • Bancos de dados
  • Algebra abstrata
    • História: de Euclides até Galois
    • uns problemas antigos e abertos na época
    • construções com régua e compasso
    • raízes de polinómios com fórmulas
    • a idéia da álgebra abstrata
    • Conjuntos estruturados
    • abusos notacionais
  • Teoria dos grupos
    • permutações
    • notação com parenteses e com cíclos
    • achando os membros do S₃
    • leis abstratas satisfeitas por S₃
    • primeira defição de grupo
    • ℘A é grupo com qual das operações binárias conhecidas de conjuntos?

29/07/2021 [2/2]: Teoria dos grupos [video]

  • Umas definições de grupo, com outros tipos de estrutura
  • Grupos abelianos
  • O que significa teoria dos grupos
  • Teorema: unicidade de identidade
  • Escolhendo leis
  • Nãœxemplo de grupo: strings com concatenação
  • Teorema: leis de cancelamento: (GCL) & (GCR)
  • operando por o mesmo lado
  • propriedade de igualdade: substituir iguais por iguais
  • cuidado com o uso do “⇒” nas demonstrações
  • Teorema: unicidade dos inversos
  • não podemos operar nos dois lados por lados diferentes
  • Notação: Grupos aditivos e multiplicativos
  • potências em grupos
  • Propriedades de inversos
  • G abeliano ⇒ (ab)⁻¹ = a⁻¹b⁻¹
  • Enxergando a mesma igualdade em maneiras diferentes
  • Teorema: inverso da identidade
  • Como podemos provar que algo é inverso/identidade?
  • Umas respostas erradas
  • Teorema: resolução de equações: (RESL) & (RESR)
  • Critério: Identidade e inversos mais baratos: (Id-bar) & (Inv-bar)
  • Teoremas: inverso de inverso & inverso de produto
  • {2ⁿ | n inteiro} vira um grupo com adição? Com multiplicação?

01/08/2021: Teoria dos grupos [video]

  • números com adição
    • definição recursiva do 𝐧 = {0,…,n-1}
    • adição módulo n
    • matrízes com adição
    • números com multiplicação
    • multiplicação módulo n
    • os inversos chegam em pares/casais
    • matrízes com multiplicação
    • (℘A;Δ)
    • strings com concatenação
    • funções reais com pointwise adição e multiplicação
    • as potências de 2
  • duas maneiras de tomar membros dum conjunto indexado
  • previously on FMC2…
  • escolhendo leis (axiomas)
    • como demonstrar que algo não é demonstrável pelumas leis
    • Critérion: G finito + (G0) + (G1) + (GCL) + (GCR) ⇒ G grupo
    • Critérion: (G0) + (G1) + (G2L) + (G3L) ⇒ G grupo
    • o que é «critérion»
    • econômia vs claricidade/intuitividade
    • Critérion: (G0) + (G1) + (G2R) + (G3R) ⇒ G grupo
    • modularidade
    • (G0),(G1),(G2L)
    • magma, semigrupo, monóide, grupo, grupo abeliano
  • ordem de grupo: o(G) ou |G|
  • tem grupos de ordem 0?
  • tem grupos de ordem 1?
  • tabelas Cayley
  • jogando grupoku
  • o grupo ({0,1,2};+₃) e sua tabela Cayley
  • potências de membros de grupo
  • as potências aⁿ para n=-1,0,1,2,…
  • duas definições razoáveis para o a⁻²
  • Teorema: (a⁻¹)² = (a²)⁻¹
  • Definição: As potências aⁿ para n inteiro
  • um diagrama cuja comutatividade é a lei (a⁻¹)² = (a²)⁻¹
  • um diagrama cuja comutatividade é a lei (ab)⁻¹ = b⁻¹a⁻¹
  • ∀a∀b (ab)⁻¹ = a⁻¹b⁻¹ ⇐?⇒ G abeliano

03/08/2021: Teoria dos grupos [video]

  • Definição: ordem de membro de grupo: o(a)
  • membros com ordem infinita e finita em grupos
  • quantas ordens diferentes dentro dos membros do S₃
  • pelo menos n potências
  • «sem perda de generalidade»
  • no máximo n potências
  • tomando membros arbitrários de conjuntos indexádos
  • sermão: divisão de Euclides
  • o(a) = ∞ ⇒ todas as potências de a são distintas
  • aᵐ = e ⇔ o(a)|m
  • Subgrupos: intuição, conceito, definição
  • Exemplos e nãœxemplos
  • Observação: associatividade de graça no H
  • Observação: H e G não podem ter identidades diferentes
  • Critério: quando H é não vazio, basta fechado pela operação e pelos inversos
  • Critério: quando H é finito e não vazio, basta fechado pela operação

06/08/2021: Teoria dos grupos [video]

  • one-test critérion
  • a R(H) é uma relação de equivalência
  • ≤ é uma ordem parcial
  • intersecção de subgrupos é subgrupo
  • união de subgrupos é subgrupo?
  • Geradores
  • subgrupo gerado por membro de grupo
  • subgrupo gerado por dois membros de grupo
  • subgrupo gerado por subconjunto de grupo
  • palavras
  • bottom-up
  • top-down
  • conjuntos convexos, bichos e subbichos
  • não intersectarás famílias vazias
  • exemplos de geradores, e grupos cíclicos
  • três casos para decidir se a relaciona com b
  • coclasse direitas e esquerdas
  • as coclasses direitas é uma partição do G
  • coclasses direitas e a relação anterior
  • congruência módulo subgrupo
  • por que as coclasses direitas?
  • módulo direito e módulo esquerdo
  • as coclasses têm a mesma cardinalidade?
  • atores
  • HK≤S₃? KH≤S₃?

09/08/2021: Teoria dos grupos [video]

  • assim que tiver um H≤G…
  • H = {e,φ}; K = {e,ψφ}
  • 𝓛(K) =?= 𝓡(K)
  • conjuntos indexados
  • igualdade e tomando membros arbitrários
  • o teorema de Lagrange
  • índice de subgrupo em grupo
  • o que precisamos mais demonstrar?
  • exemplos com grupos de números
  • corolário: de novo: HK≤S₃? KH≤S₃?
  • corolário: subgrupos de grupo com ordem primo
  • corolário: o(a) | o(G)
  • corolário: a^(o(G)) = e
  • teoria dos números revisitada: o teorema de Euler
  • HK = KH ⇔ HK ≤ G
  • subgrupos normais: L(H) = R(H)
  • assim que tiver um N⊴G…
  • afastando até G/N
  • C * D = ?
  • o grupo quociente: G/N
  • conjugação em grupos
  • «é conjugado de» é uma relação de equivalência
  • N⊴G ⇔ …
  • {e,ψ,ψ²}⊴S₃?

11/08/2021: Teoria dos grupos [video]

  • subgrupos normais e o grupo quociente
  • justificar o nome/notação: congruência (mod H)
  • congruências
  • simetrias
  • as simetrias do triângulo
  • o grupo Dih₃
  • Dih₃ ≅ S₃
  • grupos isómorfos
  • propriedades grupoteóricas os subgrupos de Dih₃ e diagramas Hasse
  • (homo)morfismos de grupos
  • preservar/respeitar estrutura
  • primeiro momento que a assinatura da estrutura de grupo importa?
  • critérion de homomorfismo
  • (mono,epi,split-mono,split-epi)-morfismos
  • isomorfismo; isómorfos/isomórficos
  • «preservar estrutura» com diagramas comutativos
  • diagramas de Hasse
  • (℘{1,2,3} ; ⊆)
  • (ℕ ; ≤)
  • (ℕ ; |)
  • (Sub(Dih₃) ; ≤)
  • homework: Sub(Dih₄)
  • Dih₄ vs. S₄
  • o(Dih₄)

14/08/2021: Categorias; Teoria dos grupos; Álgebra abstrata

  • Cats; grupos; álgebra [video]
    • Categorias
      • definição e revisão
      • três categorias: SET, N(≤) e N(|)
      • lembrete de produtos e coprodutos
      • objetos iniciais e terminais numa categoria
      • categoria dos grupos GRP
      • iniciais e terminais nessas quatro categorias
      • «ao menos de isomorfismo»
      • mono, epi, split mono, split epi, iso
    • Teoria dos grupos
      • kerφ (definição)
      • kerφ ≤ Α
      • kerφ ⊴ Α
      • Teorema: kerφ singleton ⇔ φ injetiva
      • injecção vs mono
      • o primeiro teorema de isomorfismo
      • kernel ⇔ normal
    • Outras estruturas algébricas
      • Monóides
      • definição
      • submonóides e homomorfismos
      • critéria?
  • Álgebra abstrata [video]
    • Hom(G,H) em categorias
    • Hom(G,H) é um grupo? abeliano?
    • grupos: mais -morfismos: endo-; auto-
    • outras estruturas
    • anel
    • mais exemplos de aneis: inteiros módulo m, End(G)
    • primeiras conseqüências das leis de anel
    • zerodivisores
    • domínios de integridade e domínios de cancelamento
    • DI ⇐?⇒ DC

16/08/2021

  • Álgebra abstrata; Os números reais [video]
    • revisão: estruturas algébricas
    • teorema: domínio de integridade ⇔ domínio de cancelamento
    • corpos
    • teorema: domínio de integridade finito ⇒ corpo
    • reticulado
    • anel booleano
    • exemplos de reticulados
    • reticulado bounded (limitado)
    • corpos
    • corpos ordenados
    • como diferenciar os reais dos racionais?
    • ordem densa
    • bounded
    • bounded above/below; upper/lower bound
    • desenhando os dois corpos ordenados
    • o corpo ordenado dos racionais tem buracos
    • lei de completude
    • supremum/infimum
    • sup/inj; lub/glb; join/meet; ⋁/⋀
    • corpo ordenado completo
    • unicidade dos reais
    • único «a menos de isomorfismo»
  • Os reais; História [video]
    • recap: corpos ordenados completos; infimum, supremum
    • infA ≤ supA ?
    • infimum e supremum do Ø
    • calculus de verade
    • definição de limite
    • ε-perto
    • o que preciso demonstrar para usa a frase «x,y são…»
    • definição como jogo
    • mais gírias matemáticas
    • «a partir de…»
    • «eventualmente…»
    • não ter limite
    • definição de continuidade
    • interpretação geométrica da expansão decimal de reais
    • algébricos e transcendentais
    • exemplos e nãœxemplos
    • o √2 é algebrico
    • duas definições equivalentes de algébrico
    • história: de 1700 até Cantor
    • números transcendentais
    • Cantor sobre series Fourier (1870,1871,1872)
    • convergência ponto a ponto (pointwise)
    • pontos de acumulação
    • conjunto derivado
    • nascimento da teoria dos conjuntos: os conjuntos como objetos de estudos (first-class citizens)

23/08/2021

  • O paraíso de Cantor [video]
    • Hermite e von Lindemann
    • existem a e b irracionais tais que aᵇ racional?
    • alguem dos π + e, πe é irracional?
    • como comparar conjuntos infinitos
    • as relações =c, ≤c, <c
    • 2ℕ =c ℕ
    • definições: contável, finito
    • cardinalidade
    • cardinais vs ordinais
    • jogos imortais de enumeração [Smullyan]
    • qualquer conjunto finito é contável
    • o conjunto de naturais é contável
    • o que estamos fazendo formalmente?
    • definição: enumeração de conjunto
    • os inteiros são contáveis
    • os racionais são contáveis
    • ℕ² e o primeiro argumento diagonal de Cantor
    • stratificação
    • Kleene star
    • os strings finitos dum alfabeto finito são contáveis
    • strings com alfabeto infinito: ℕ⋆
    • ℘fℕ; ℘f℘fℕ; ℘fᵏℕ
    • conjuntos incontáveis
    • o segundo argumento diagonal de Cantor
    • união contável de contáveis é contável
    • numeros selvagens (ou domesticados?)
    • racionais vs. irracionais
    • algebricos vs. transcendentais
    • teorema fundamental da algebra
    • primeira grande aplicação da teoria de Cantor
    • =c é uma relação de equivalência?
  • O paraíso de Cantor [video]
    • ≤c é uma preordem
    • ≤c não é antissimétrica
    • ≤c é ``equiantissimétrica’’
    • todos os intervalos ``da mesma forma’’ são equinúmeros
    • respeitando e desrespeitando equinumerosidades
    • A x B =c A’ x B’
    • ℘A =c ℘A’
    • (A → B) =c (A’ → B’)
    • uniões e intersecções
    • currificação de novo
    • A ≤c B: afirmações equivalentes
    • A ≤c B ⇐?⇒ existe sobrejetora f : B → A
    • A ≤c B ⇒?⇒ existe sobrejetora f : B → A
    • A ≤c B ⇐?⇐ existe sobrejetora f : B → A
    • TEASER/SPOILER: axioma da escolha
    • por que o 2o argumento diagnoal de Cantor não serve para os racionais?
    • Cantor vs Liouville
    • procurando bijecções
    • teorema de Bernstein (CSB)
    • ℝ, ℝ², ℝ³, ℝⁿ, (ℕ→ℝ): equinúmeros?
    • casamentos infinitos [Smullyan]

26/08/2021

  • O paraíso de Cantor: [video]
    • bijecções entre intervalos de reais
    • casamentos infinitos: uma dica
    • o conjunto de Cantor
    • teorema de intervalos aninhados de Cantor
    • Devil’s staircase
    • dicas para demonstrar equinumerosidades
    • codificações
    • trocando conjuntos por equinumeros
    • teorema de Cantor (com depressivos)
    • Uma carta de Cantor para Dedekind
  • O paraíso de Cantor; O paradoxo de Russell [video]
    • prova alternativa do teorema de Cantor
    • lembrete: dica do problema dos casamentos
    • conseqüências do teorema de Cantor
    • aleph-0, beth-0, e continuum: ℵ₀, ℶ₀, 𝔠
    • Continuum Hypothesis (CH)
    • comparabilidade de cardinalidades
    • hypergame de Zwicker
    • o hypergame é terminante?
    • quantos programas de tipo Nat → Nat tem?
    • Áristos vs Blammenos
    • da Devil’s staircase para medida
    • um toque de teoria de medida
    • o paradoxo de Russell

27/08/2021: Teoria axiomática dos conjuntos ZF (1) [video]

  • recap: o paradoxo de Russell
  • metáforas para descrever o paradoxo
  • resoluções
  • teoria dos tipos (Russell)
  • teoria dos conjuntos (Zermelo)
  • leis vs axiomas
  • noções primitivas: pertencer e ser conjunto
  • o princípio da puridade
  • fundação de matemática
  • revisão: FOL
  • traduzindo de e para a FOL dos conjuntos
  • interpretação de uma FOL
  • tautologias
  • a palavra de Zermelo
  • ZF1 [Extensionalidade] e suas conseqüências
  • ZF2 [Emptyset] e suas conseqüências
  • existência e unicidade do vazio
  • Ø
  • ZF3 [Pairset] e suas conseqüências
  • mais conjuntos
  • {–,–}; {–}
  • com ZF1–ZF3 podemos construir apenas conjuntos com cardinalidade 0, 1, ou 2
  • uma infinidade de conjuntos
  • um padrão nas formulas de ZF
  • ZF4 [Separation] e suas conseqüências
  • sua interpração
  • {x∈–|–}
  • uma comparação com o Princípio da Comprehensão Geral
  • o paradoxo de Russell revisitado
  • como usar o [Separation]
  • o universo não é um conjunto
  • ZF5 [Poweset] e suas conseqüências
  • ℘–
  • conjuntos de qualquer cardinalidade finita
  • –∩–; ⋂–
  • ZF6 [Unionset] e suas conseqüências
  • ⋃–; –∪–
  • classes vs conjuntos; classe própria

30/08/2021: Teoria axiomática dos conjuntos ZF (2) [video]

  • ZF1–ZF6: recap
  • –\–
  • –∪–
  • –Δ–
  • teorema dos singletons
  • implementando outros tipos
  • Russell: de paradoxo para teorema
  • o par ordenado (2-tupla)
  • o par de Kuratowski
  • relações; funções; famílias
  • espaços de relações e funções
  • conseguimos implementar o powerset-finito?
  • ZF1–ZF6: impossibilidade de construir o conjunto dos naturais
  • números cardinais e sua aritmética
  • união disjunta (coprodúto)
  • dois enunciados do ZF7: Zermelo; von Neumann
  • a existência de quantos conjuntos infinitos é garantida pelos axiomas ZF1–ZF7?

01/09/2021: Teoria axiomática dos conjuntos ZF (3) [video]

  • recap: os ZF1–ZF6
  • união-disjunta na ZF
  • mais sobre a aritmética dos cardinais e suas leis
  • grupos e conjuntos estruturados na ZF
  • o sucessor de Zermelo e de von Neumann
  • o ZF7 e suas conseqüências
  • temos de graça uma implementação do conjunto dos naturais
  • axiomas de Peano
  • existência dos naturais: top-down
  • unicidade dos naturais
  • Teorema da Recursão
  • aproximações de função: bottom-up
  • funções parciais
  • funções compatíveis e incompatíveis

03/09/2021: Teoria axiomática dos conjuntos ZF (4) [video]

  • recap: construção dos naturais
  • existência dos naturais
  • unicidade dos naturais
  • teorema da recursão
  • funções parciais
  • funções compatíveis e incompatíveis
  • função converge
  • igualdade de Kleene
  • aproximações de funções
  • lemma: as aproximações são compativeis
  • como usar o princípio da indução
  • definindo operações e relações nos naturais
  • isomorfismos respeitam tudo isso
  • esboço: como implementar os outros conjuntos de numeros
  • de naturais para inteiros para racionais para reais para complexos
  • uma idéia para implementar os inteiros
  • quantos axiomas encontramos até agora?
  • axioma vs. esquema axiomático

07/09/2021: Teoria axiomática dos conjuntos ZF (5) [video]

  • igualdade de Kleene
  • outras formas de recursão: com parametros, etc.
  • Dedekind-(in)finito na ZF1–ZF6
  • boas ordens e o princípio da boa ordem
  • Construindo os inteiros
  • Construindo os racionais
  • Construindo os reais
  • completude com suprema (ou infima)
  • completude com seqüências
  • seqüência convergente
  • seqüência Cauchy
  • definição do conjunto dos reais (Cantor)
  • Dedekind cuts
  • downwards-closed
  • resto ta definição de Dedekind cut
  • definição do conjunto dos reais (Dedekind)
  • definição das operações e relações entre reais
  • hipótese do continuum e da comparabilidade de cardinalidades
  • Outros axiomas
  • ZF8 [Replacement] e suas conseqüências
  • Class-functions e fórmulas function-like
  • ZF9 [Foundation] e suas conseqüências
  • AC: Axiomas de escolha e suas conseqüências
  • Antifoundation de Aczel
  • conseqüências controversiais do AC
  • versões de escolha mais fracas que a do AC
  • outras teorias de conjuntos
  • limitações
  • outros fundamentos
  • casamentos: discussão
  • Áristos vs Blammenos: discussão
  • limitações de computação
  • o halting problem
  • tem Nats infinitos na linguagem?
  • o problema de Josephus não tem nada a ver com o ZF9
  • a comparabilidade das cardinalidade é demonstrável?
  • ataques injustos contra o axioma da escolha
  • igualdade e o axioma da extensionalidade

08/09/2021: Teoria da ordem (1) [video]

  • recap
  • posets
  • ordem: fraca vs estrita
  • máximo/mínimo
  • upper/lower bounds
  • A ≤ m ; m ≤ A
  • subposet
  • maximal/minimal
  • relação de cobrir
  • diagramas Hasse
  • pontos incomparáveis
  • ↑x ; ↓x
  • ↑A ; ↓A
  • downset ; upset
  • exemplos: posets feitos por números
  • naturais com ordem comum
  • naturais com ordem de divide
  • inteiros com ordem comum
  • exemplo: números (ordinais como posets)
  • poset discreto
  • exemplo: números (como posets discretos) [1:00:42]
  • flat posets
  • bottom ou zero ; top ou one
  • construindo ordens
  • poset discreto
  • lift(P)
  • P⊎Q ; P⊕Q
  • desenhando posets construidos por ⊕ e ⊎
  • associatividade dos ⊎, ⊕
  • exemplo: powerset
  • duas maneiras de desenhar
  • dual(P)
  • lift(P) como somatório
  • 𝒪(P): o poset de todos os downsets de P
  • 𝒪(N) = ?

10/09/2021: Teoria da ordem (2) [video]

  • chain, antichain
  • exercício: downsets dos N, Z, Q, R.
  • ordinais de von Neumann como posets
  • strings (finitos ou infinitos)
  • espaços de funções parciais como posets
  • P×Q
  • com (anti)lexicográfica
  • com componentwise
  • como desenhar o Hasse dela
  • Pᴬ, ou seja, (A→P) com pointwise
  • por que «preordem»?
  • a categoria POS dos posets
  • order-preserving (monótona); -embedding; -isomorfísmo
  • critérion de embédding (e logo de isomorfismo)
  • definição categórica de iso?
  • sup/inf, lub/glb, join/meet
  • duas maneiras de faltar o join ou o meet
  • ache os joins: a∨b, b∨c

13/09/2021: ZF (6); Ordem (3) [video]

  • ZF
    • {–,…,–}
    • construindo uns conjuntos
    • uma classe que é conjunto
    • duas classes próprias
    • Someset is the new Emptyset
    • Triset it is the new Pairset
    • umas conseqüências do foundation
    • Replacement is the Pairset, Separation, etc.
    • a φ que definimos para ser Peano-isomorfismo é sobrejetiva
    • e ela respeita a soma
  • Ordem
    • ordem pointwise e seus joins e meets
    • ordem pointwise e sua relação de cobrir nos (ℕ→ℕ) e (ℝ→ℝ)
    • ordem antilexicográfica e o P·Q
    • como desenhar uns posets
    • são reticulados?
    • dá pra embutar um em outro?

14/09/2021: Teoria da ordem (4) [video]

  • desenhando posets de naturais com divisibilidade
  • reticulado e reticulado completo
  • desafio: construir um poset tal que…
  • tem poset isomorfo com um powerset poset?
  • os naturais com divisibilidade eh um poset
  • join e meet do vazio e do P (P poset)
  • D₀ não é isomorfo com nenhum powerset poset
  • os primeiros ordinais de von Neumann
  • Lembrando: P×Q ; P·Q ; P⊎Q ; P⊕Q
  • mais sobre ordinais
  • a multiplicação não é comutativa
  • o que podemos concluir sobre os ordinais α,β se…?
  • como os ordinais contáveis aparecem
  • números transfinitos: cardinais vs. ordinais
  • aritmética ordinal
  • Lattices: reticulados algebricamente
  • Lattices e reticulados: conexão
  • Chains
  • length
  • no infinite chains ⇒?⇒ length infinito?
  • ACC e DCC

15/09/2021: Teoria da ordem (5) [video]

  • reticulados
  • homomorfismos entre reticulados
  • subreticulado
  • subreticulado gerado por conjunto
  • ACC, DCC, axioma da escolha
  • relações bem-fundadas e indução Noetheriana (bem-fundada)
  • teorema de ponto fixo de Knaster–Tarski
  • previsão das notas

17/09/2021: Assuntos auxiliares; Prova [video]

  • Resolução da Prova 3.1
    • o princípio da boa ordem e o princípio da indução nos naturais
    • o axioma CONS na ZF
    • embutindo ordinais nos racionais
    • um teorema de ponto fixo de Kleene
  • Ordinais: recursão e indução transfinita
    • Como parecem os primeiros ordinais
    • Recursão e indução transfinita
  • λ-calculus
    • recap: α, β, η, …
    • implementações no λ-calculus
    • Nats no λ-calculus
    • Church numerals
    • succ
    • Bools no λ-calculus
    • Church booleans
    • not
    • ifthenelse
    • plus, times, etc.
    • fixpoints e definições recursivas
    • desafio: definir o factorial
    • o Y combinator
    • e agora..?

Futuro (fluido)

Sem futuro; o semestre acabou!

Last update: Sat Sep 18 22:59:23 -03 2021