2022.1 FMC2, turma de Thanos

Horários de aula: 246N34 [20h35–22h15]
Contato:thanos@imd.ufrn.br
Playlists: FMC2 2019.1 (aulas gravadas)
FMC2 2018.2 (aulas gravadas)
Pré-requisitos para SetFunRel/FMC2
Monitoria/TA: fmc.imd.ufrn.br (Começou!)
Turmas anteriores: ..

Info

Pré-requisitos

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

¹ Imagine chegar em Polo Aquático I, sem ter aprendido mesmo as Natação I e II primeiro; ainda mais sem sequer ter entrado na agua na sua vida inteira!

(Obs.: aprenderpassar.)

Então—ANTES de começar—é bom ter estudado os capítulos 1,3,4 do fmcbook. Minha primeira aula de FMC2 no 2020.1 resume esses assuntos.

Além disso, é necessário que os alunos matriculados têm 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 Munkres.
  2. A parte Writing mathematics do livro The tools of mathematical reasoning, de Lakins.

Conteúdo

A disciplina FMC2 será dividida em 3 módulos–unidades. Essa divisão é influenciada pelos módulos correspondentes à FMC2 baseados nos módulos correspondentes desta proposta.

CFR1: Conjuntos, Funções, Relações 1 (30h)

  1. Especificações e implementações matemáticas de coleções (conjuntos, ênuplas, multiconjuntos, sequências), e de suas principais operações e predicados; extensão vs intensão. A notação construtor-de-conjunto (set-builder) e sua interpretação. Implementação da noção de cardinalidade, no caso finito.
  2. Operações sobre coleções, finitas ou não, de conjuntos: união, interseção, produto e coproduto de conjuntos (produto cartesiano e união disjunta). Para o caso de coleções finitas, definições recursivas e demonstrações indutivas das suas propriedades. Complemento relativo, diferença simétrica. Conjunto potência.
  3. Especificações de famílias indexadas. Operações sobre famílias indexadas de conjuntos. Coberturas e partições.
  4. Especificações e implementações matemáticas de associações (funções parciais, totais, e não-determinísticas); extensão vs intensão. Funções vs procedimentos em programação; funções puras e efeitos colaterais.
  5. Funções anônimas (notação lambda).
  6. Funções de ordem superior, e funções como cidadãos de primeira classe; closures. Espaço de funções.
  7. Curryficação e aplicação parcial de funções.
  8. Função identidade, composição de funções, iterações de uma função.
  9. Função inclusão, função vazia, função 0-ária, função constante. Projeções e demais funções associadas ao produto e ao coproduto de conjuntos, incluindo pairing e copairing. Funções indicadoras (ou características). Restrições de funções.
  10. Imagem direta e pré-imagem de conjuntos.
  11. A inversão de uma função, e a função inversa.

CFR2: Conjuntos, Funções, Relações 2 (30h)

  1. Funções injetivas e sobrejetivas, monos e epis. Retrações e seções. Condições de invertibilidade de uma função.
  2. O teorema de Cantor sobre a cardinalidade do conjunto potência, e as cardinalidades transfinitas.
  3. Breve introdução à teoria da computabilidade: funções computáveis, números computáveis, e conjuntos computáveis; semi-decidibilidade e decidibilidade.
  4. Relações e a sua implementação conjuntista. Operações sobre relações: composição, inversão, iterações, fechos. Descrição e propriedades do fecho transitivo: usando interseção (top-down) e usando união (bottom-up).
  5. Exemplos de conjuntos estruturados: espaços normados, espaços métricos, espaços topológicos, espaços de medida, grafos.
  6. Relações de equivalência e partições, classes de equivalência, e o conjunto quociente. Equivalências mais finas e mais grossas, e a relação de equivalência induzida pelo núcleo de uma função. Construções de classes de números usando quocientes.
  7. Relações de ordem: pré-ordens, ordens parciais e ordens estritas, ordens totais, elementos minimais e elementos maximais, supremos e ínfimos. Cadeias e funções que preservam ordem. Reticulados e reticulados completos. Ordens parciais completas. A construção de uma função a partir do limite de uma cadeia de funções parciais.
  8. Relações bem-fundadas: definição usando cadeias e definição usando elementos minimais, conexão com recursão e indução. Relações bem-fundadas induzidas pela imagem inversa de uma relação bem-fundada, pelo produto lexicográfico de relações bem-fundadas, e pelo fecho transitivo de uma relação arbitrária.
  9. Os Fundamentos da Matemática: uma breve introdução à Teoria Axiomática dos Conjuntos.

IEA: Introdução a Estruturas Algébricas (30h)

  1. Grupos (6h) Permutações: notação de cíclos e verificação das leis de grupo para os Sₙ. De Sₙ para grupos: definições alternativas de grupo baseadas em assinaturas diferentes; notação, exemplos e não-exemplos, incluindo casos numéricos (em particular da aritmética modular), famílias de conjuntos, espaços de funções e relações, strings. Definições de grupo abeliano, monóide, semigrupo, magma. Definição de teoria e de modelo, e as primeiras conseqüências (teoremas) das leis (axiomas) dos grupos: unicidade de identidade e dos inversos, leis de cancelamento e de resolução de equações, inverso da identidade, de inversos, e de produtos, e sua expressão com diagramas comutativos. Independencia de axiomas: como demonstrar a não-demonstrabilidade. Critérios para verificar se uma estrutura é um grupo. Como definir um grupo: tabelas de Cayley. Construções: o produto direto de grupos, grupo livre. Potências (com expoentes de naturais até inteiros) e ordem de membro de grupo incluindo demonstrações das suas propriedades (por indução e usando o lema da divisão de Euclides).
  2. Subgrupos e o grupo quociente (6h) Subgrupos: definição, exemplos, nao-exemplos, critérios; “subgrupo de” como relação de ordem; propriedade de interseção de subgrupos; relações de equivalência determinadas por subgrupos. Subgrupo gerado por subconjunto: como definir tanto top-down quanto bottom-up e demonstração por indução da sua equivalência. Exemplos fora da teoria dos grupos, incluindo conjuntos convexos e o fecho convexo. Congruência (modulo subgrupo) e coclasses. Verificação que se trata de relação de equivalencia e partição. Subgrupos normais: definições alternativas e verificação da sua equivalencia. O grupo quociente. O teorema de Lagrange e o indice dum subgrupo num grupo. Aplicações em teoria dos números incluindo obter o teorema de Euler (e logo o pequeno Fermat também) como corolário de Lagrange.
  3. Homomorfismos e isomorfismos (6h) Simetrias, os grupos simetricos, e os diagramas Hasse dos reticulados dos seus subgrupos. Homomorfismos e preservação da estrutura algebrica. Critérios de homomorfismos para grupos. Monomorfismos, epimorfismos, isomorfismos, endomorfismos, e automorfismos. O grupo Aut(G). Núcleo, imagem, e o primeiro teorema de isomorfismos de Noether para grupos. Um esboço do teorema de representação para grupos (teorema de Cayley).
  4. Outras estruturas (6h) Outras estruturas, seus primeiros teoremas e as definições de homomorfismo: semigrupo, monoide, anel, anel booleano. O monoide livre e o fecho de Kleene (Kleene star). Corpos, corpos ordenados completos e o enunciado da sua unicidade a menos de isomorfismo (os números reais). Espaços Vetoriais. Reticulados como álgebras. Construções e mapeamentos (monotonos, order-embeddings, e ordem-isomorfismos). O reticulado de subgrupos e de subgrupos normais. Homomorfismos e subreticulados. Reticulados booleanos. Enunciado do teorema de representação de Stone. Algebras de termos.
  5. Categorias (6h) Definição de categoria e exemplos, incluindo categorias associadas à programação e à lógica, e categorias a partir de preordens e posets. Dualidade e a definição de categoria oposta. Mono, epi, split mono, split epi, e iso. Definições (como especificações) por propriedades universais e diagramas comutativos: objetos terminais e inicias, produtos e coprodutos. Suas unicidades a menos de isomorfismo. Subobjetos, objetos quocientes, objeto livre, e suas propriedades universais. Verificação da sua existencia nas categorias encontradas.

Objetivos de aprendizagem

CFR1: Conjuntos, Funções, Relações 1

Prática com o uso das técnicas de demonstração e refutação matemática. Familiarização com a linguagem e com as principais classes, operações e propriedades de conjuntos e funções, definidas extensionalmente ou intensionalmente. Familiarização com as noções do cálculo lambda usadas em programação e lógica: variáveis ligadas e livres, captura de variáveis, renomeamento de variáveis, sombreamento de variáveis, aplicações de funções aos seus argumentos. Reconhecer os objetos matemáticos relevantes às linguagens de programação e suas propriedades. Familiarização com a formulação de especificações, e suas implementações matemáticas. Familiarização com o uso de diagramas comutativos em definições e demonstrações, e com especificações via propriedades universais.

CFR2: Conjuntos, Funções, Relações 2

Prática com a escrita de especificações matemáticas e com o uso das técnicas de demonstração matemática, incluindo o método da diagonalização. Familiarização com as principais classes, operações e propriedades de relações. Familiarização com cardinalidades de conjuntos infinitos. Apreciar a conexão entre especificação e implementação. Familiarização com o raciocínio “sem pontos” (a saber, sem mencionar elementos dos conjuntos), através do composições de funções, e suas aplicações em programação.

IEA: Introdução a Estruturas Algébricas

Compreensão do papel da álgebra no estudo de estruturas de interesse computacional. Prática das técnicas de demonstração matemática e do uso do raciocínio equacional. Apreciar a conexão entre axiomas e seus modelos, e o conceito de independência lógica. Familiarização com a linguagem básica e as idéias elementares da Teoria das Categorias, incluindo o uso de diagramas comutativos para expressar proposições (leis e teoremas), especificações e definições.

Bibliografia e referências

Conhece o libgen?

Principal

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

CFR1: Conjuntos, Funções, Relações I

  • Avigad, Lewis & van Doorn (2017): Logic and Proof (Cap. 11,12,15,16)
  • Steffen, Rüthing & Huth (2018): Mathematical Foundations of Advanced Informatics, vol 1 (Cap: 2)
  • Fejer & Simovici (1991): Mathematical Foundations of Computer Science, vol 1 (Cap: 2,3,4,5)

Auxiliar

  • Lawvere & Schanuel (2009): Conceptual Mathematics, 2nd ed.

CFR2: Conjuntos, Funções, Relações II

  • Avigad, Lewis & van Doorn (2017): Logic and Proof (Cap. 13,14,15,16)
  • Steffen, Rüthing & Huth (2018): Mathematical Foundations of Advanced Informatics, Vol. 1 (Cap: 3)
  • Moschovakis (2006): Notes on Set Theory, 2nd ed. (Cap: 1,2,4)
  • Davey & Priestley (2002): Introduction to Lattices and Order, 2nd ed. (Cap. 1, 2, 8)
  • Fejer & Simovici (1991): Mathematical Foundations of Computer Science, Vol 1 (Cap. 2,3,4,5)

Auxiliar

  • Halmos (1960): Naive Set Theory
  • Goldblatt (1979): Topoi (Cap: 1)
  • Moschovakis (2006): Notes on Set Theory, 2nd ed. (Cap: 3,5,6,A)
  • Spivak (2008): Calculus, 4th ed. (Cap: 29,30)

IEA: Introdução a Estruturas Algébricas

  • Aluffi (2009): Algebra, Chapter 0 (Cap: II)
  • Herstein (1975): Topics in Algebra, 2nd ed.
  • Birkhoff & Mac Lane (1977): A Survey of Modern Algebra, 4th ed.
  • Mac Lane & Birkhoff (1999): Algebra, 3rd ed.
  • Davey & Priestley (2002): Introduction to Lattices and Order, 2nd ed.
  • Barr & Wells (1998): Category Theory for Computing Science, 2nd ed., 2020 reprint

Auxiliar

  • Goldblatt (1979): Topoi
  • Crole (1993): Categories for Types (Cap: 1,2,3)

Dicas

Links

Tecnologias e ferramentas

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. Zulip (leia o FAQ).
  3. Pouco de (La)TeX (veja o minicurso TeX 2018.2). Online editor/compilador: Overleaf.

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 e 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, em modo privado ou aberto. Se um aluno não consegue explicar o que ele mesmo escreveu numa resolução, será considerado plágio (veja abaixo).
  3. Participando, nunca dê uma resposta que tu não pensou sozinho, exceto dando os créditos correspodentes.
  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 é no nosso Zulip (especificamente seus canáis públicos—não DM) e a monitoria.
  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.)

Uns deveres dos alunos

  1. Visitar o site e o Zulip da disciplina pelo menos uma vez por dia durante o semestre. (Qualquer coisa postada no site ou no Zulip da disciplina será considerada como conhecida por todos os alunos da turma.)
  2. Checar e atender seu email cadastrado no SIGAA pelo menos uma vez por dia durante o semestre.
  3. Participar nas aulas! Obs.: tendo uma dúvida durante a aula, levante a mão para solicitar “a fala” e assim que a receber, pergunte! Não espere o fim da aula para discutir tua dúvida em “modo particular”! A maioria das vezes eu vou negar isso e pedir ao aluno iniciar a discussão no Zulip ou na próxima aula.
  4. Estudar o conteúdo lecionado e tentar resolver todos os trabalhos atribuidos.
  5. Participar no Zulip diariamente.
  6. Participar nas aulas de exercícios de monitoria e utilizar seus horários de tirar dúvidas.

(Veja também os FAQs relevantes.)

Sobre plágio

  1. Plágio detectado implica que o aluno será reprovado imediatamente por nota e por faltas.
  2. Entregar tuas resoluções para um aluno copiar é proibido do mesmo jeito, e também não ajuda mesmo ninguém.

Cadernos vs. celulares

Não faz sentido aparecer na aula sem caderno. E não faz sentido aparecer na aula com celular ligado; bote no modo avião antes de entrar na sala. As aulas são interativas e se não pretende participar e concentrar nesses 100 minutos, sugiro ficar fora e escolher uma outra maneira de passar teu tempo. Não é necessário (e obviamente nem suficiente) aparecer nas minhas aulas para passar.

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 escritas; (ii) sua participação; (iii) trabalhos atribuidos; (iv) hw resolvidos (veja o FAQ relevante).

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 e faltas

A presença pela regulação da UFRN é obrigatória. Os alunos que não gostam/querem/podem aparecer nas minhas aulas ainda tem chances de ganhar até nota máxima e aprovar na disciplina. Ou seja: alunos que escolhem não participar ou aparecer nas aulas, e mesmo assim aparecem nas provas escritas e conseguem nota final de aprovação vão ter sua porcentagem de faltas ajustada para não reprovar por faltas. Esclarecimento: alunos que não conseguem nota final de aprovação não terão sua porcentagem de presença ajustada.

Obviamente, alunos que não aparecem nas aula não terão como ganhar pontos de participação—duh!—nem acesso nos pontos de possíveis provas-surpresas.

As presenças/faltas serão cadastradas usando o sistema Plickers (veja o FAQ relevante).

Atrasados

Definição (atrasado). Seja $a$ aluno desta turma. Dizemos que $a$ é atrasado sse $a$ não está já sentado na sua mesa, com seu caderno já aberto, seu celular já desligado e na mochila, no momento que a aula começa.

Tentem estar presentes na sala da aula ANTES do horário do seu começo, e fiquem até o fim da aula.

Caso que alguém chega atrasado: não faz sentido bater na porta da sala de aula; não faz sentido cumprimentar nem o professor (não é mostra educação cumprimentar nesse caso—pelo contrário!) nem os amigos/colegas da aula. Entrando numa sala onde a aula já começou, tentem fazer sua entrada o menos possível notada por os participantes pois atrapalha a concentração de todos.

FAQs

Dynamic content

Pontos de participação

Provas

Provas surpresa. Note que em qualquer aula pode ter prova surpresa, cujos pontos são considerados «pontos extra», assim sendo possível tirar nota máxima (100), mesmo perdendo todas as provas surpresas.

U1 (CFR1)

U2 (CFR2)

U3 (Álgebra)

Homework (HW)

Leia bem o FAQ sobre hw. Note também que:

  • Homeworks são atribuidos também durante as aulas e no Zulip.
  • Homeworks marcados assim são auxiliares; tente apenas se tu tem resolvido uma parte satisfatória dos outros.

2022-03-31

  1. Capítulo 1.

2022-04-01

  1. Para cada uma das proposições acima tente demonstrar escrevendo na linguagem de demonstrações que elaboramos nas aulas até agora. Evite os LEM e RAA quando possível.
    1. Proposições de dupla negaço:
      1. P ⇒ ¬¬P
      2. ¬¬P ⇒ P
    2. Comutatividade dos ∨,∧:
      1. (P ∨ Q) ⇒ (Q ∨ P)
      2. (P ∧ Q) ⇒ (Q ∧ P)
    3. Proposições de interdefinabilidade dos ⇒,∨:
      1. (P ⇒ Q) ⇒ (¬P ∨ Q)
      2. (P ⇒ Q) ⇐ (¬P ∨ Q)
      3. (P ∨ Q) ⇒ (¬P ⇒ Q)
      4. (P ∨ Q) ⇐ (¬P ⇒ Q)
    4. Proposições de contraposição:
      1. (P ⇒ Q) ⇒ (¬Q ⇒ ¬P)
      2. (¬Q ⇒ ¬P) ⇒ (P ⇒ Q)
    5. A irrefutabilidade do LEM:
      1. ¬¬(P∨¬P)
    6. A lei de Peirce e sua versão “fraca”:
      1. ((P ⇒ Q) ⇒ P) ⇒ P
      2. ((P ⇒ Q) ⇒ P) ⇒ ¬¬P
    7. Proposições de interdefinabilidade dos ∨,∧:
      1. P∨Q ⇒ ¬(¬P∧¬Q)
      2. P∨Q ⇐ ¬(¬P∧¬Q)
      3. P∧Q ⇒ ¬(¬P∨¬Q)
      4. P∧Q ⇐ ¬(¬P∨¬Q)
    8. As leis de De Morgan para ∨,∧:
      1. ¬(P∨Q) ⇒ (¬P ∧ ¬Q)
      2. ¬(P∨Q) ⇐ (¬P ∧ ¬Q)
      3. ¬(P∧Q) ⇒ (¬Q ∨ ¬P)
      4. ¬(P∧Q) ⇐ (¬Q ∨ ¬P)
    9. Proposições de distributividade dos ∨,∧:
      1. P∧(Q∨R) ⇒ (P∧Q)∨(P∧R)
      2. P∧(Q∨R) ⇐ (P∧Q)∨(P∧R)
      3. P∨(Q∧R) ⇒ (P∨Q)∧(P∨R)
      4. P∨(Q∧R) ⇐ (P∨Q)∧(P∨R)
    10. Currificação
      1. ((P∧Q)⇒R) ⇒ (P⇒(Q⇒R))
      2. ((P∧Q)⇒R) ⇐ (P⇒(Q⇒R))
    11. Reflexividade da ⇒:
      1. P ⇒ P
    12. Weakening and contraction:
      1. P ⇒ (P∨Q)
      2. Q ⇒ (P∨Q)
      3. (P∧Q) ⇒ P
      4. (P∧Q) ⇒ Q
      5. P ⇒ (P∧P)
      6. (P∨P) ⇒ P
    13. As leis de De Morgan para ∃,∀:
      1. ¬(∀x)[φ(x)] ⇒ (∃x)[¬φ(x)]
      2. ¬(∀x)[φ(x)] ⇐ (∃x)[¬φ(x)]
      3. ¬(∃x)[φ(x)] ⇒ (∀x)[¬φ(x)]
      4. ¬(∃x)[φ(x)] ⇐ (∀x)[¬φ(x)]
    14. Proposições de interdefinabilidade dos ∃,∀:
      1. (∃x)[φ(x)] ⇒ ¬(∀x)[¬φ(x)]
      2. (∃x)[φ(x)] ⇐ ¬(∀x)[¬φ(x)]
      3. (∀x)[φ(x)] ⇒ ¬(∃x)[¬φ(x)]
      4. (∀x)[φ(x)] ⇐ ¬(∃x)[¬φ(x)]
    15. Proposições de distributividade de quantificadores:
      1. (∃x)[φ(x) ∧ ψ(x)] ⇒ (∃x)[φ(x)] ∧ (∃x)[ψ(x)]
      2. (∃x)[φ(x) ∧ ψ(x)] ⇐ (∃x)[φ(x)] ∧ (∃x)[ψ(x)]
      3. (∃x)[φ(x) ∨ ψ(x)] ⇒ (∃x)[φ(x)] ∨ (∃x)[ψ(x)]
      4. (∃x)[φ(x) ∨ ψ(x)] ⇐ (∃x)[φ(x)] ∨ (∃x)[ψ(x)]
      5. (∀x)[φ(x) ∧ ψ(x)] ⇒ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
      6. (∀x)[φ(x) ∧ ψ(x)] ⇐ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
      7. (∀x)[φ(x) ∨ ψ(x)] ⇒ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]
      8. (∀x)[φ(x) ∨ ψ(x)] ⇐ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]

2022-04-02

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

2022-04-05

  1. Capítulo 7 (Conjuntos): §§107,108,113

2022-04-07

  1. Capítulo 7 (Conjuntos): até o primeiro intervalo de problemas

2022-04-10

  1. Pense no que mesmo significa a frase «como poderiamos implementar os típos primitivos cujas especificações encontramos na aula? (Set, Multiset, Seqüência, Tuplas)
  2. Tente implementá-los, escolhendo cada vez menos deles como primitivos.

2022-04-19

  1. Estude bem o gabarito da Prova 1.1.

2022-04-19

  1. Sobre implementações de 2-tupla (par ordenado):
    1. A implementação de [quem?] de 2-tupla definindo (a,b) ≝ {{L,{a}},{R,{b}}} funciona?
    2. Verifique (como?) que a implementação (a,b) ≝ {{a}, {a,b}} funciona.
    3. A implementação (a,b) ≝ {a, {a,b}} funciona?
  2. Capítulo 7 (Conjuntos): até o fim
  3. Tendo apenas os Nat como tipo primitivo, implementa o tipo Nat × Nat (ou seja, 2-tuplas de nats). Depois, implementa o tipo FinList(Nat) de listas finitas de Nat.

2022-04-26

  1. Entenda o que é uma ℐ-tupla, e o que é o produto duma ℐ-família de conjuntos.
  2. Como definiarias as operações ⋃,⋂ para ℐ-famílias de conjuntos?
  3. Tem conjunto que não pode ser indexado?

2022-04-28

  1. Nas aulas percebemos que uma seqüência pode ser vista como uma ℕ-família. Dada seqüência $A_n$ de conjuntos, como definarias sua união $\bigcup_{n=0}^{\infty} A_n$ e sua interseção $\bigcap_{n=0}^{\infty}$? E seu produto $\prod_{n=0}^{\infty} A_n$?
  2. Para os casos finitos como $\bigcup_{n=4}^{12} A_n$ dê duas definições uma de acorda com as anteriores, e outra recursiva, e demonstre sua equivalência.
  3. Resolva (novamente?) os problemas do capítulo 7.

2022-04-30

  1. Defina as noções de cobertura e de partição dum conjunto.
  2. Defina as funções curry e uncurry.
  3. Estuda e resolva tudo que tem na § «Um toque de lambda».
  4. Estuda e resolva tudo que tem antes dessa seção, ainda no capítulo «Funções».

2022-05-04

  1. Na última aula discutimos as “reduções” β e η no cálculo-λ, e percebemos que, na verdade ambas elas são “presentes” nos conjuntos também. Ficou como hw identificar as β e η para as 2-tuplas.

2022-05-04

  1. (Re)escreva sozinho as definições de curry e uncurry: (i) usando notação-λ; (ii) usando Python; (iii) usando notação matemática “comum”
  2. Conteudo: tudo que temos feito, principalmente: os capítulos 7 (inteiro) e do capítulo 8 até o primeiro intervalo de problemas.

2022-05-10

  1. Capítulo «Funções» até o ~~primeiro~~ segundo intervalo de problemas.

2022-05-12

  1. Capítulo «Funções» até o segundo intervalo de problemas.
  2. (Esclarecimentos no Zulip!) Compare com =, ⊆, ⊇, os conjuntos seguintes, mas primeiramente esclarece que tipo de coisas são os f,A,B, e o que é presuposto sobre eles pelo contexto:
    • f[A∪B] ? f[A]∪f[B]
    • f[A∩B] ? f[A]∩f[B]

2022-05-15

  1. Capítulo «Funções» até o terceiro intervalo de problemas (cuidádo pois umas seções foram adicionadas dentro dessa parte—verifiquem!)

2022-05-21

  1. Capítulo «Funções» até o fim mesmo.
  2. Investigue: $(g \circ f)_\ast = (g_\ast \circ f_\ast)$
  3. Investigue: $(f \circ g)^\ast = (f^\ast \circ g^\ast)$

2022-05-23

  1. Resolva o que não deu tempo para resolver da prova 1.3.
  2. Estude o gabarito da prova 1.3.
  3. Investiga se as categorias que encontramos tem produtos e coprodutos.

2022-05-28

  1. Capítulo «O paraíso de Cantor», até a §223.
  2. Demonstre (sem olhar para nenhuma fonte) que para todo conjunto A, A é estritamente menor em cardinalidade que o ℘A.
  3. Nos reais estendidos: inf A ≤ sup A?
  4. Existem a e b irracionais tais que aᵇ racional?
  5. Alguém dos π + e, πe é irracional?
  6. A equinumerosidade é uma relação de equivalência?

2022-06-02

  1. Dê uma olhada no von Neumann.
  2. Capítulo «O paraiso de Cantor» até o fim, incluindo os problemas, exceto os: Π15.6, Π15.7, Π15.9.

2022-06-11

  1. Capítulo «Relações» até o fim, exceto as §«Relações recursivas» e §«Relações de ordem superior»

2022-06-19

  1. Capítulo «Posets; Reticulados», até o §«Posets de graça: operações e construções»
  2. Capítulo 1 do livro dos Davey e Priestley

2022-06-23

  1. Capítulo «Teoria axiomática dos conjuntos», até o primeiro intervalo (pule a seção sobre a aritética dos cardinais, e sobre classes vs conjuntos).

2022-06-28

  1. Capítulo «Teoria dos grupos», até a §«primeiras conseqüências».

2022-07-03

  1. §«Tabelas Cayley»
  2. §«Potências e ordens»
  3. §«Escolhendo as leis»
  4. §«Simetrias»
  5. §«Morfismos»

2022-07-10

  1. Até o §«Teoria dos números revisitada»

2022-07-19

  1. Capítulo «Estruturas algébricas»
  2. Capítulo «Teoria dos Grupos»

2022-07-20

  1. Capítulo «Posets; Reticulados»
  2. Capítulo 2 de Davey & Priestley

Histórico

2022-03-28: Aula 01: Overview; tipos

  • tipos e type errors
  • proposiões vs objetos
  • sintaxe vs semântica

2022-03-30: Aula 02: Tipos; definições; linguagem de demonstrações

  • comandos vs proposições
  • se..então.. vs como..logo..
  • variáveis ligadas vs livres
  • escopos de variáveis
  • sombreamento (shadowing) de variáveis
  • abuso de gerúndios, vírgula mágica, etc.
  • definição e seu contexto
  • açúcar sintáctico, abreviações
  • convenção: notação infixa
  • os conectivos ⇐,⇒,⇔

2022-04-01: Aula 03: Tipos; definições; linguagem de demonstrações

  • = vs ⇔
  • «def»
  • intensão vs extensão
  • o resto dos conectivos para nossa linguagem de demonstrações
  • escolha boa de variável, variável fresca
  • bairros de variáveis
  • variável fresca

2022-04-04: Aula 04: Tipos; linguagem de demonstrações; Coleções

  • Tipos de dados matemáticos
  • Especificação e igualdade
  • Conjuntos: black box
  • Duas maneiras duma definição ser erradas
  • Operações sobre conjuntos e como definí-las
  • união, interseção, diferença (complemento relativo), diferença simétrica, complemento
  • Operações “grandes”: união unária e interseção

2022-04-06: Aula 05: Linguagem de demonstrações; Coleções

  • Proposição mais forte vs mais fraca que outra
  • Necessário e suficiente, se e somente se
  • P ⇒ ¬¬P
  • ¬¬P ⇒ P
  • Set builder (apenas com variável na parte esquerda)
  • Mais set builder (com _ ∈ _ na parte esquerda)
  • Ainda mais set builder (com termo envolvendo variáveis na parte esquerda)
  • Relações sob conjuntos e como defini-las: ⊆
  • Universo, conjunto vazio, singleton
  • 8 proposições simples
  • Demonstração (low level) da Ø⊆A
  • O predicado Singleton e como defini-lo
  • Cardinalidade de conjunto (finito)

2022-04-08: Aula 06: Coleções

  • Powerset
  • Seqüências
  • Multisets
  • Tuplas
  • Mais operações sob conjuntos

2022-04-11: Aula cancelada

2022-04-13: Aula cancelada

2022-04-15: Feriado

2022-04-18: Prova 1.1

2022-04-20: Coleções

  • Especificação x implementação
  • Sacolas implementadas como conjuntos de tuplas
  • Implementação-agnóstico: usar apenas o interface da especificação e não os detalhes da implementação
  • Tuplas: especificação e implementação como conjuntos
  • Famílias indexadas
  • Produto cartesiano e soma (união disjunta)

2022-04-22: "Feriado"

2022-04-25: Conjuntos

  • Implementações de $n$-tuplas para $n > 2$
  • Casos extremos de tuplas: 1-tupla, ω-tupla, 0-tupla
  • Unicidade de habitante de 0-tupla
  • Família indexada x Seqüências
  • ∏ para famílias indexadas e definições recursivas para seqüências
  • Conjunto indexado x Família indexada (igualdade)
  • Tomando elementos arbitrários de conjuntos indexados

2022-04-27: Conjuntos; Funções

  • Operações em ℐ-famílias de conjuntos: Π,⋃,⋂
  • Cada conjunto pode ser indexado por ele mesmo
  • Especificações e implementações de associações
  • Função como black box
  • Função matemática: totalidade e univocidade
  • domínio e codomínio (source e target)
  • ↦ vs →
  • abordagem categorista/tipista vs conjuntista
  • range de função
  • Funções vs procedimentos
  • Funções puras e efeitos colaterais
  • O que é o void mesmo? (1)

2022-04-29: Conjuntos; Funções

  • Como implementar n-tuplas de nats como nats
  • União e interseção de seqüências
  • Definições recursivas de Σ,Π,⋃,⋂,{1,..,_}
  • União de conjuntos vs somatório de números
  • Coberturas e partições
  • igualdade de funções: extensão vs intensão
  • graph(f)
  • Como definir funções
  • Currificação
  • notação λ
  • Funções de ordem superior, funções como cidadãos da primeira classe
  • Exemplo de currificão em python
  • Subconjunto próprio vs não-subconjunto (notação)

2022-05-02: Funções

  • λ-cálculo crash course
  • α-renomeamento
  • β,η em funções, conjuntos, tuplas
  • O que é o void mesmo? (2)
  • aplicação de função por espaço e não por (
  • aridade de função

2022-05-04: Funções

  • curry e uncurry: implementação em λ em python
  • a curry como demonstração
  • a ideia de demonstrações-como-tipos
  • vantagens de currificação e aplicação parcial de funções
  • Como definir e como não definir funções
  • o significado de «função bem definida»
  • aplicação de função associando à esquerda, → à direita: notação conveniente
  • função identidade dum dado conjunto

2022-05-06: Prova 1.2; Funções

  • Resolução da D1 da prova
  • «f x ≝ …» vs «f ≝ λx . …»
  • composição: definição, tipo, e associatividade (demonstração)
  • composição de conjuntista vs de categorista/tipista
  • definindo funções estilo pointless (point-free)

2022-05-09: Funções

  • funções de graça: identidade, inclusão, constante, característica
  • usos de 0 e 1 como valores de verdade
  • unix shell e como os && e || funcionam
  • diagramas comutativos
  • exercício: se o quadrado esquerdo e o quadrado direito comutam, todo comuta
  • Leis da composição e identidades
  • funções associadas ao produto (1)

2022-05-11: Funções

  • Funções anônimas
  • Funções associadas ao produto e coproduto: pair, copair, produto, coproduto
  • pattern matching
  • imagem e pré-imagem (1)

2022-05-13: Funções

  • imagem e pré-imagem (2)
  • funções injetivas e sobrejetivas

2022-05-16: Funções

  • imagem e pré-imagem (3)
  • Inversão de função e função inversa
  • Funções parciais
  • Funções não-determinísticas
  • Dado um conjunto B, como podemos construir um objeto fora dele?
  • Investigação: quando funcionam definições recursivas mesmo?

2022-05-18: Categorias

  • uma viagem épica
  • point-free definição e raciocínio
  • aplicação ≟ composição?
  • mono, epi, split-mono, split-epi
  • initiais e terminais, no mundo de conjuntos

2022-05-20: Categorias

  • um toque de categorias
  • definição de categoria
  • quatro exemplos de categorias
  • definições categoriais: objeto inicial, objeto terminal, produto, coproduto

2022-05-23: Prova 1.3

  • ∐ para famílias indexadas e definições recursivas para seqüências
  • Espaço de funções
  • Iterações de endomapa
  • Fixpoints
  • Definições recursivas como resoluções de sistemas onde incognitos são funções
  • Funções parciais computadas pelos sistemas

2022-05-25: História; Cantor-Dedekind

  • calculus de verdade
  • reais vs racionais
  • a completude dos reais
  • upper bound, lower bound
  • conjuntos limitados por cima e por baixo (bounded above, bounded below)
  • as notações x ≤ A, A ≤ B
  • inf, sup
  • pontos de acumulação
  • conjunto derivado
  • números algébricos e transcendentais
  • definição de equinumerosidade
  • nascimento dos conjuntos como objetos de estudos (first-class citizens)
  • duas definições equivalentes de algébrico
  • o √2 é algebrico, o ³√(2 + √2) também
  • Conjuntos contáveis
  • jogos imortais de enumeração [Smullyan]
  • o ℤ é contável

2022-05-27: Cantor-Dedekind

  • Teorema de interseção de Cantor
  • O conjunto de Cantor
  • Devil’s staircase
  • interpretação geométrica da expansão decimal de reais
  • o ℚ 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 dum alfabeto infinito
  • ℘fℕ; ℘f℘fℕ; ℘fᵏℕ
  • conjuntos incontáveis
  • o segundo argumento diagonal de Cantor
  • por que o 2o argumento diagonal de Cantor não serve para os racionais?

2022-05-30

  • As definições de relações sobre cardinalidades e umas equivalências
  • Teorema de Cantor: A é estritamente menor em cardinalidade que ℘A
  • Os números algébricos são contáveis
  • Corolário: os transcendentais são incontáveis

2022-06-01

  • o teorema de Cantor: versão antropomórfica
  • a hipotese do continuum (CH: Continuum Hypothesis)
  • procurando bijeções
  • (0,1) e (0,1)² têm a mesma cardinalidade
  • a $(=_c)$ é uma relação de equivalência
  • a $(\leq_c)$ é reflexiva e transitiva mas não antissimétrica. (Mas quase isso.)
  • Um esboço do teorema CSB
  • Uma carta de Cantor para Dedekind e sua resposta
  • os alephs: ℵ₀, ℵ₁, ℵ₂, …
  • os beths: ℶ₀, ℶ₁, ℶ₂, …

2022-06-03

  • GCH
  • Comparabilidade de cardinalidades
  • Aritmética transfinita
  • «a partir de…»
  • «eventualmente…»
  • ε-perto, ε-bola
  • definição de limite
  • definição como jogo
  • Um toque de teoria da medida
  • Um toque de computabilidade e decidabilidade
  • Números computáveis
  • Áristos vs Blammenos
  • Jogos terminantes
  • Problemas no paraíso

2022-06-06: Relações

  • Descrição com black box e notação
  • Propriedades notáveis de relações
  • Pré-ordens

2022-06-08: Relações

  • Relações de equivalência
  • Partições
  • Classe de equivalência
  • Conjunto quociente
  • Fechos: construção bottom-up

2022-06-10: Relacões

  • Composição de relações
  • Implementação de funções como relações
  • Relação dual
  • Relação completa
  • Relação vazia
  • Fechos: construção top-down
  • Posets
  • Diagramas Hasse
  • Relação de «coberto por»

2022-06-13: Relações

  • A relação de ε-perto
  • Como visualizar conjuntos quocientes
  • Os reais extendidos e sua ordem
  • infØ e supØ
  • joins e meets binários
  • meet-reticulado, join-reticulado, reticulado
  • o (℘A;⊆)

2022-06-15: Relações

  • Posets de graça
  • Justificativa do nome pré-ordem

2022-06-22: Relações


2022-06-24: Teoria dos Conjuntos

  • Os primeiros 6 axiomas de ZF

2022-06-27: Teoria dos Grupos

  • Contexto Histórico: da grécia antiga até Galois
  • Permutações e sua notação
  • Leis de grupo

2022-06-29: Teoria dos Grupos

2022-07-01: Teoria dos Grupos

2022-07-02: Teoria dos Grupos (3 aulas)

  • Partes das aulas:
  • ordem de membro de grupo
  • isometrias e simetrias
  • grupo de simetrias dum triangulo regular
  • grupos isomórficos
  • homomorfismo
  • critério de homomorfismo

2022-07-04: Teoria dos Grupos

2022-07-06: Teoria dos Grupos

  • relação de equivalência módulo um subgrupo H

2022-07-08: Teoria dos Grupos

  • conjugação em grupo
  • O teorema Lagrange
  • Subgrupos normais: definição

2022-07-11: Teoria dos Grupos

2022-07-13: Teoria dos Grupos

2022-07-15: Teoria dos Grupos

2022-07-18: Teoria dos Grupos

2022-07-20: Prova 3.1

2022-07-22: Prova 2.2

Futuro (fluido)

Sem futuro. Acabou!

Last update: Wed Mar 8 14:36:44 -03 2023