2018.2 FMC2, turmas de Thanos

Prerequisitos

É prerequisito ter aprendido bem o conteudo de FMC1. Sem aprender esses assuntos primeiro, não faz sentido se matricular em FMC2. (Obs.: aprender ≠ passar.)

Então—ANTES de começar—é bom estudar os:

1. How to prove it, de Velleman (1, 2, 3, 6)
2. Mathematical Proofs, de Chartrand, Polimeni, Zhang (0, 2)
3. Do fmcbook (minhas notas em progresso) os capítulos:
   • Linguagens
   • Estratégias de provas
   • Os numeros naturais: recursão; indução
   • Combinatória enumerativa
   • Teoría elementar de números
   • Congrüências
4. Comments on style de James Munkres.
5. A parte “Writing mathematics” do livro The tools of mathematical reasoning, de Lakins.

(Obs.: estudar ≠ ler.)

Conteúdo

Conteúdo transversal

Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e provas. A linguagem da teoria de conjuntos. Definições pelo recursão – provas por indução. Demonstrações diretas e indiretas, refutaçõ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. 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.

Elementos de Álgebra abstrata

Conjuntos com estrutura. Operações. Grupos, subgrupos, aneis, monoides. Demonstrações com o uso de identidades algébricas. Homomorfísmos. Álgebras booleanas.

Elementos de Teoria de Conjuntos

Enumerações e conceito intuitivo de cardinalidade. Paradoxos e os axiomas Zermelo–Fraenkel. Representações de matemática (traduções). Os números naturais; axiomas Peano.

Elementos de Teoria de Ordem

Ordens parciais, totais, densas, bem-fundadas. Diagramas de Hasse. Elementos notáveis (majorantes, máximos, supremos). Conjuntos ordenados, reticulados, reticulados completos. Construções de conjutos ordenados. Dualidade. Ordens canônicas, ordens lexicográficas. Monotonicidade. Teoremas de ponto fixo. Reticulados como álgebras. Conjuntos bem-ordenados. Indução bem-fundada.

Aplicações e outros assuntos

Tipos de dados algébricos. Relações bem-fundadas e indução transfinita. Números ordinais. Limites de computação. Noções de decidibilidade e de semi-decidibilidade. λ-calculus, lógica combinatória. Elementos de teoria dos tipos. Noções de semántica de linguagens de programação. Y-combinator, fixpoints e recursão. Axiom of choice e suas conseqüências.

Bibliografia

Principal

(Conhece o libgen.io?)

• Eu: Matemática fundacional para computação [fmcbook]

Auxiliar

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

• Pierce et al: Software Foundations, Volume 1: Logical Foundations [SF1]
• Velleman: How to prove it (1–3)
• Pinter: A book of abstract algebra (2–5, 6, 12, 17)
• Davey & Priestley: Introduction to lattices and order (1, 2)
• Paul Halmos: Naïve set theory
• Moschovakis: Notes on set theory (1, 2, 3–5, 6–7)
• Goldrei: Classic set theory, for guided independent study (4, 7, 8)
• Raymond Smullyan: Satan, Cantor, and Infinity
• Raymond Smullyan: A beginner's guide to mathematical logic (Volume 1)
• Doets & van Eijck: The Haskell Road to Logic, Maths and Programming (3, 4, 5, 6, 7)
• Paul Halmos: Linear Algebra Problem Book (1)
• Birkhoff & Mac Lane: A survey of modern algebra (1.11; 1.1–1.5, 1.10, 1.12)
• Aluffi: Algebra: Chapter 0
• Mac Lane & Birkhoff: Algebra (1.1–1.3)
• Herstein: Topics in Algebra (2.1–2.5 [skip # and *])
• Simmons: Introduction to topology and modern analysis (1)
• Munkres: Topology (1)
• Loomis & Sternberg: Advanced Calculus (0)
• João Marcos: Lógica Aplicada à Computação website (TdC, R&I)

Programação

• Bird: Thinking Functionally in Haskell
• Hutton: Programming in Haskell
• Lipovača: Learn you a Haskell for great good
• Sterling & Shapiro: The art of Prolog

Links

• Coq

Dicas

• Jean-Pierre Serre: How to write mathematics badly (video lecture)
• Paul Halmos: How to write mathematics
• James Munkres: Comments on style
• Don Knuth: Mathematical writing
• Por que tantos livros? Qual é o melhor? Vale a pena ler esse excerto do livro Linear Algebra de Jänich.

Provas

As provas serão avisadas com antecedência de pelo menos 48 horas.

Provinha 0

• Provinha 0 (pts: 0; bônus: 0) (dia: 03/08/2018)
  { uncensored, answers }
  correções: p1 (8M), p2 (7M), p3 (5M), tudo (20M).

Unidade 1

• Prova 1.1 (pts: 24; bônus: 0) (dia: 31/08/2018)
  T = { censored, uncensored, answers };
  N = { censored, uncensored, answers }
• Prova 1.2
  • T (pts: 76; bônus: 8) (dia: 14/09/2018)
    { censored, uncensored, answers };
  • N (pts: 34; bônus: 8) (dia: 19/09/2018)
    { censored, uncensored, answers }
• Prova 1.3 (pts: 42; bônus: 8) (dia: 08/10/2018)
  N = { censored, uncensored, answers }

Unidade 2

• Prova 2 (pts: 100; bônus: 0) (dia: 16/11/2018)
  N = { censored, uncensored, answers }

Unidade 3

• Prova 3 (pts: 100; bônus: 0) (dia: 10/12/2018)
  N = { censored, uncensored, answers }

Reposição

• Prova escrita (pts: 100; bônus: 0) (dia 14/12/2018)

Pontos extra

Unidade 1

Pontos de participação

Pontos de homework

Unidade 2

Pontos de participação

Pontos de homework

Unidade 3

Pontos de participação

Pontos de homework

Homework

Obs.: Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas.

10/07/2018

1. Estude os ítens que tenho nos prerequisitos
2. Brinque com Haskell

06/08/2018

1. Estude a (pouca) coisa que tá escrita no capítulo «Estratégias de provas» do fmcbook.
2. Estude e resolve os exercícios/problemas do capítulo 3 de Velleman.

08/08/2018

1. Estude o capítulo «Linguagens» do fmcbook.
2. Estude o capítulo «A linguagem de lógica proposicional» do fmcbook.
3. Estude os capítulos 1–2 de Velleman.

11/08/2018

1. Pense sobre os → e ← e as frases «somente se» e «se» até ficar claro o qual é qual!
2. Defina sozinho as linguagens de lógica que encontramos: L₀ e FOL.
3. Usando árvores (sintácticas) de derivação teste que várias expressões são realmente fórmulas.
4. Estude o capítulo «A linguagem de lógica de predicados» do fmcbook.

13/08/2018

1. Mostre como definir as expressões
   • (∀x∈A)[ φ(x) ]
   • (∃x∈A)[ φ(x) ]
   • ∃!x φ(x)
   • (∃!x∈ A)[ φ(x) ]
   como açúcar sintáctico em qualquer FOL que tenha o ∈ nos seus predicados.
2. Se φ(x) é uma fórmula que envolve o x, como podes escrever uma fórmula que afirma que:
   • Existe no máximo 1 objeto x tal que a φ(x)
   • Existe pelo menos 1 objeto x tal que a φ(x)
   • Existem pelo menos 2 objetos x tais que φ(x)
   • Existem no máximo 2 objetos x tais que φ(x)
   • Existem exatamente 2 objetos x tais que φ(x)

15/08/2018

1. Estude a secção «92. Os números naturais formalmente» do capítulo XI «Os números naturais: recursão; indução» do fmcbook.
2. Usando apenas a estrategia de sejar para atacar ∀, e de separar em casos, tente provar que a operação + que definimos na aula é uma operação associativa.

17/08/2018

1. Defina sozinho as operações adição, multiplicação, exponenciação, e prove que a adição é associativa.
2. Estude todo o capítulo XI «Os números naturais: recursão; indução» do fmcbook.
3. [Moisés:] prove que para todo a, b ∈ Nat, a + b ∈ Nat

18/08/2018

1. Na aula tentamos provar sem indução que adição é associativa, e um momento a gente se ligou que não tem como. Começamos então backtrack nossos passos, até chegar no início da prova, e continuamos, essa vez escolhendo começar com outro caminho. Mostre como seria possível conseguir provar o mesmo teorema sem backtrackar até o início, mas apenas até nosso segundo passo inicial. Ou seja, continue a prova dessa teorema começando assim: «Seja a ∈ Nat. Seja m ∈ Nat.»
2. Installe o Coq; dê uma lida no «Preface» do SF1 (link na Bibliografia); estude o capítulo «Basics» do SF1.
3. Estude o capítulo «Induction» do SF1.

19/08/2018

1. Pense sobre os ⇒ e ⇐ e as frases «é suficiente para» e «é necessário para» até ficar claro o qual é qual!

23/08/2018

1. § Conceito; notação; igualdade [do capítulo «Conjuntos»]
2. § Intensão vs. Extensão
3. § Relações entre conjuntos e como definí-las
4. § Mais set-builder

24/08/2018

1. § Vazio, universal, singletons
2. § Oito proposições simples
3. § Operações entre conjuntos e como definí-las
4. § Provando igualdades e inclusões
5. § Cardinalidade
6. § Powerset

25/08/2018

1. [F. Igor:] Podemos definir o `∃!' assim?
   ∃!x φ(x) ⇔ ∃x φ(x) ∧ ∀y ( φ(y) → φ(x) )

27/08/2018

1. § União grande; intersecção grande
2. § Tuplas
3. Problemas: Π12.4; Π12.5

29/09/2018

1. § Produto cartesiano
2. § Seqüências
3. § Intervalos na reta real
4. § Famílias indexadas
5. § Disjuntos dois-a-dois
6. § Traduzindo de e para a linguagem de conjuntos
7. § Produto cartesiano generalizado
8. Problemas: Π12.1; Π12.2; Π12.3; Π12.6

02/09/2018

1. § Multisets
2. Problemas: Π12.7

03/09/2018

1. § Conceito, notação, igualdade
2. § Diagramas internos e externos
3. § Como definir e como não definir funções
4. § (Co)domínios vazios

05/09/2018

1. § Expressões com buracos
2. § A notação lambda
3. § Funções de graça
4. Problemas: Π13.2; Π13.3; Π13.4.
5. [T34] § Composição
6. [T34] § Aplicação parcial
7. [T34] § Leis de composição
8. [T34] Problemas: Π13.1.

10/09/2018

• Turma T34
  1. § Injetoras; sobrejetoras; bijetoras
  2. § Inversas
  3. § Imagens; preimagens
  4. § Funções de ordem superior
  5. Problemas: Π13.6; Π13.7; Π13.8; Π13.9; Π13.10; Π13.11
• Turma N12
  1. § Composição
  2. § Aplicação parcial
  3. § Leis de composição
  4. § Diagramas comutativos
  5. Problemas: Π13.1

12/09/2018

• Turma T34
  1. § Diagramas comutativos
  2. § Mais construções e operações em funções
  3. § Currificação
  4. § Funções parciais
  5. § Fixpoints
  6. Problemas: Π13.5; Π13.12; Π13.13
• Turma N12
  1. § Injetoras; sobrejetoras; bijetoras
  2. § Inversas
  3. § Imagens; preimagens
  4. Problemas: Π13.5; Π13.6; Π13.7; Π13.8; Π13.9; Π13.10; Π13.11

14/09/2018

1. Resolva sozinho a Prova 1.2-T34
2. § Funções de graça
3. § Definições recursivas
4. § Mais construções e operações em funções

17/09/2018

1. § Definições recursivas (re-leia!)
2. § Funções de ordem superior
3. § Currificação
4. § Funções parciais
5. § Fixpoints
6. Problemas: Π13.2; Π13.3; Π13.4; Π13.12; Π13.13; Π13.14; Π13.15
7. Problemas: Π12.3; Π12.5; Π12.8; Π12.9

23/09/2018

1. Revisem os capítulos de Conjuntos e de Funções
2. Instalem e brinquem com Haskell e com Coq (veja homework do dia 18/08/2018)

26/09/2018

1. § Conceito, notação, igualdade
2. § Definindo relações
3. § Diagramas internos
4. § Construções e operações em relações
5. § Propriedades de relações

01/10/2018

1. § Fechos
2. § Relações de equivalência
3. § Partições
4. § Relações de ordem
5. Problemas: Π15.5; Π15.7; Π15.8; Π15.13; Π15.14; Π15.15; Π15.16; Π15.17

05/10/2018

1. § Conjunto quociente
2. Problemas: Π15.1; Π15.2; Π15.3; Π15.4; Π15.6; Π15.9; Π15.10; Π15.12

08/10/2018

1. Resolva sozinho a Prova 1.3
2. Estude bem o gabarito da Prova 1.3
3. Resolva sozinho a Prova 1.3; se não conseguir, GOTO 2
4. § Conceito, notação, igualdade
5. § Conjuntos estruturados com operações
6. § Permutações

10/10/2018

1. Termina todo o homework de 08/10/2018
2. § O que é um grupo?
3. Termine o plicker: com a operação certa prove que é um grupo; com as outras prove/refute cada uma das (G0)–(G4)
4. Prove (só) os teoremas:
   1. unicidade da identidade
   2. leis de cancelamento
   3. unicidade dos inversos
5. Prove (só) as leis dos inversos, ou seja, adivinha quem é cada um dos seguintes e prove tua afirmação
   1. inverso da identidade = ?
   2. inverso de inverso = ?
   3. inverso de produto = ?
6. Prove (só) as leis de resolução de equações
   1. Se existe x tal que ax=b, então é único
   2. Se existe y tal que ya=b, então é único

16/10/2018

1. § Primeiras conseqüências
2. § Tabelas Cayley
3. Problemas: Π18.1; Π18.2; Π18.3

20/10/2018

1. § Potências e ordens
2. Prove as afirmações que afirmamos no fim da aula de 19/10/2018

22/10/2018

1. § Subgrupos
2. Problemas: Π18.7

25/10/2018

1. § Exemplos e nãœxemplos
2. § Geradores
3. Problemas: Π18.8; Π18.9

27/10/2018

1. § Geradores
2. § Um desvio: bottom-up e top-down
3. Problemas: Π18.10; Π18.11

29/10/2018

1. § Um desvio: bottom-up e top-down
2. § Congruências e coclasses: até o x18.86

31/10/2018

1. Revisem TODO o capítulo de grupos
2. Provem o Lema: todas as coclasses direitas de H têm a mesma cardinalidade.

02/11/2018

1. Sejam H,K≤G. Prove que: HK = KH ⇐⇒ HK ≤ G

05/11/2018

1. § O teorema ``de Lagrange''
2. § Subgrupos normais
3. § O grupo quociente
4. § Simetrias: até Exercício x18.111

07/11/2018

1. § Simetrias
2. § Morfismos
3. Problemas: Π18.12; Π18.13; Π18.14; Π18.15

12/11/2018

1. § Kernel, Image
2. Problemas: Π18.18

15/11/2018

1. Capítulo XIX: Estruturas Algebricas (todo!)

21/11/2018

1. Capítulo XX: Os números reais: até a secção «Os reais»

24/11/2018

1. Capítulo XXI: O paraiso de Cantor: até a secção «O primeiro argumento diagonal de Cantor»
2. Ache estratégias para ganhar no jogo imortal com conjunto-segredo o:
   • ℕ²;
   • ℤ²;
   • ℕ^k;
   • A^*, onde A é um conjunto finito de símbolos (alfabeto);
   • P_L = {p | p é um programa na linguagem de programação L};
   • ℘_fℕ;
   • ℕ^*;
   • ℘_f℘_fℕ;
   • ℘_fℚ;
   onde ℘_fX denota o conjunto de todos os subconjuntos finitos de X.

27/11/2018

1. Capítulo XXI: O paraiso de Cantor: até a secção «Procurando bijecções»

29/11/2018

1. Resolva os problemas A e C da Prova 3.1 do 2018.1

02/12/2018

1. Capítulo XXI: O paraiso de Cantor: até a secção «As menores infinidades»
2. Problemas: Π21.1; Π21.2; Π21.3; Π21.5

03/12/2018

1. Capítulo XXI: O paraiso de Cantor (todo o capítulo)
2. Problemas: Π21.4
3. Capítulo XXXIII: Teoria axiomática dos conjuntos: até (incluindo!) a «§239. Traduções de e para a FOL de conjuntos»

05/12/2018

1. Capítulo XXXIII: Teoria axiomática dos conjuntos: até (incluindo!) a «§ Construindo as tuplas»
2. Problemas: Π33.1; Π33.2; Π33.3; Π33.4; Π33.5; Π33.6; Π33.7

07/12/2018

1. Capítulo XXXIII: Teoria axiomática dos conjuntos: até o segundo intervalo de problemas
2. Capítulo XXII: Posets; Reticulados; Álgebras Booleanas: até (incluindo!) a «§ Mapeamentos»

Histórico de aulas

01/08/2018: Apresentação; erros; o «jogo» de matemática

• Apresentação dos assuntos principais
• Cronograma
• Coisas burocráticas: provas, site, monitoria, pontos, etc.
• Erros comuns:
  • Type error
  • Erro de lógica
  • Erro de matemática
  • Erro de semântica
• Diferença entre as duas frases:
  • «Se __A__, (então) __B__.»
  • «Como __A__, (logo) __B__.»
• Os dois erros principais em definições:
  • Não aceitar objetos que deveriam ser aceitos
  • Aceitar objetos que não deveriam ser aceitos
• O contexto duma definição
• Não use nem «sendo» nem «com»!
• Noções primitivas – Definições
• Axiomas – Teoremas
• Sinônimos de «teorema» e seus usos: lema, corolário
• Programando programas vs. provando teoremas
• Lemmata como funções e bibliotecas de programação
• Teoria
• Uma prova errada não quis dizer teorema errado
• Conseqüência de teorema errado não quis dizer que a conclusão é errada
• Exemplos de definições na geometria euclideana.
• Prova vs. refutação

03/08/2018: Prova 0

06/08/2018: Estratégias de prova

• provas como jogo com «prova», «dados», «alvos»
• fórmulas de lógica informalmente
• variáveis ligadas e livres (ou abertas)
• predicate vs. function symbols
• Como matar e como usar:
  • conjunção
  • implicação
  • disjunção
  • negação
  • universal
  • existencial

08/08/2018: Linguagens

• Não use «|» como abreviação de «tal que» nas fórmulas existenciais
• Linguagens formais
• Alfabetos, espressões
• Sintaxe vs. semântica
• A linguagem da lógica proposicional (sentencial)
• Definição de wff (ou fbf ou fórmula bem formada)
• Definições recursivas
• Uma linguagem para expressões aritméticas
• Árvores de derivação
• Parsing: de forma linear para arvore sintática
• A notação BNF
• Uma gramática em BNF para a linguagem da lógica proposicional (wffs)

10/08/2018: Linguagens

• →: ``somente se''; ←: ``se''
• linguagem(-objeto) vs. metalinguagem
• variáveis vs. metavariáveis
• definições
• como nos livrar dos ... na BNF da L₀
• açúcar sintáctico
• convenções
• associatividade
• semântica de uma linguagem
• limitações da lógica proposicional
• a linguagem da primeira ordem

13/08/2018: Matemática; Erros; Lógica

• Type erros (de novo)
• a|b vs. a/b
• Hipótese; tese
• = vs. ⟺
• os «def» em cima de = e de ⟺
• época de typewriters: não escreva ->; escreva →; mesma coisa sobre ^ vs. ∧
• Escrita alinhada e o que significa
• Prova errada: por afirmação do conseqüente
• Prova errada: por negação do antecedente
• Prova errada: por repetição de definição
• FOL e suas linguagens
• Exemplos de FOLs
• Abreviações e açúcar sintáctico
  • (∀x∈A)[ φ(x) ]
  • (∃x∈A)[ φ(x) ]
  • ∃!x φ(x)
  • (∃!x∈ A)[ φ(x) ]

15/08/2018: Recursão–indução [video]

• Como escrever uma prova mais humana de ∀x( φ(x) → ψ(x) )
• Os naturais formalmente (Nat)
• 3 jeitos de descrever a idéia da definição de Nat
• arvore sintáctica dos numerais de Nat
• Por que esses nats? O bom e o ruim.
• Recursão
• Definindo funções no Nat recursivamente
• Definindo a adição
• Calculando usando a definição
• Focos, casamentos, e substituições
• Cálculo: 3 + 2 = 5
• Desafio: definir a multiplicação
• Recursão «no tal argumento»
• Casos para cada argumento?
• Cade a recursão?
• O poder da recursão
• Definição recursiva da multiplicação
• Cálculo: 2(0 + 1) = 2
• Provando propriedades sobre nossas operações
• A + é associativa
  • O que significa?
  • Posso escrever a afirmação como uma fórmula?
  • Agora, bora provar!
  • Um aparente deadend
  • Não: posso separar casos
  • Prove então!

17/08/2018: Recursão–indução [video]

• Tentando provar sem indução: separando em casos, e casos, e casos…
• Indução
• O feitiço da indução e seu efeito no tabuleiro do jogo de provar
• A base da indução e o passo indutivo
• (Quando) podemos trocar a ordem que os quantificadores aparecem?
• Associatividade de adição com todos os detalhes

20/08/2018: Recursão–indução [video]

• Comutatividade da adição
• Sub-(sub-sub-...-sub)-indução
• O uso de lemmata para provar nossos teoremas
• Conseguiu provar por indução sem usar a H.I.?

22/08/2018: Conjuntos [video]

• Escrita
  • Dicas para escrever bem uma prova por indução
  • os «def» em cima de = e de ⟺
  • → vs ⇒ etc.
• Conjuntos
  • Tipos de objetos e como introduzí-los
  • Conceito de conjunto
  • Intensão vs extensão
  • Igualdade entre conjuntos: A = B
  • Noções primitivas: ser conjunto, pertencer (∈)
  • Conjuntos como “black boxes”
  • Notação
  • Set comprehension (Set-builder notation)
  • Açucar sintáctico no set-builder
  • Erro comum: quantos elementos {x,y,z} tem?

24/08/2018: Conjuntos [video]

• Definindo o conjunto vazio
• O predicado Empty(–)
• Obrigação de definir notação (nome) para objeto: artigo definido vs. indefinido
• Provas de unicidade: existe pelo menos um & existe no máximo um
• Teorema: existência do conjunto vazio
• Teorema: unicidade do conjunto vazio
• Conjunto universal
• Unicidade do conjunto universal
• O predicado Singleton(–)
• Definição: A subconjunto de B: A⊆B
• Relações entre conjuntos e como definí-las
• As relações binárias: =, ⊆
• Operações entre conjuntos e dois jeitos de definí-las
• Definindo conjuntos
• As operações binárias: ∩, ∪, \
• A operação unária de complemento: ^~
• O operador Powerset (℘)
• Oito proposições sobre o Ø e um conjunto A
• Escolhendo a ordem de atacar teoremas
• Verdade por vacuidade
• {Ø} ≠ Ø

27/08/2018: Conjuntos [video]

• Resolução do homework de F. Igor
• Podemos decidir se A∈A dado um conjunto A arbitrário?
• Homogeneidade e heterogeneidade de conjuntos
• As relações binárias: =, ⊆, ⊇, ⊊, ⊋
• ⊈ vs. ⊊
• Como usar um fato do tipo D≠Ø em nossas provas: «Seja d∈D.»
• Conjuntos disjuntos
• A diferença simétrica: definição e intuição
• Teorema: A Δ B = Ø ⇔ A = B
• Cardinalidade.
• Cardinalidade de conjuntos finitos e propriedades
• Powerset.
• União grande; intersecção grande.
• Aplicando (e iterando) as ℘, ⋂ e ⋃ no Ø
• Intuição sobre os ⋂, ⋃, e ℘ e as {, }
• Diferença e semelhança entre ⋃ e Σ.
• Um toque do Riemann rearrangement theorem
• Os operadores binários ∪ e ∩ como açucar sintático (definido pelos operadores unários ⋃ e ⋂ respeitivamente)
• Tuplas.
• tuplas como noções primitivas: igualdade, tamanho, projeções
• (a,b,c) vs. ((a,b),c) vs. (a,(b,c))
• projeções: π_i; proj_i; fst/snd; outl/outr; ...
• Seqüências.
• Seqüências de conjuntos
• União e intersecção de seqüência de conjuntos

29/08/2018: Conjuntos [video]

• O tipo de 1-tuplas
• O tipo de 0-tuplas
• A única 0-tupla: ()
• Comprehensão em linguagens de programação
• Como pensar no tipo void da C
• Produto cartesiano (×)
• Aⁿ para n≥2: definição “direta” e recursiva
• Seqüências.
• Seqüências de conjuntos
• Um exercício para aprender como atacar e como usar alvos que involvem operações grandes com índices
• União e Intersecção de seqüências de conjuntos
• Famílias indexadas.
• União e Intersecção de famílias indexadas
• ⋂Ø = ?
• Produto cartesiano generalizado (de família indexada de conjuntos)
• Um teorema de igualdade de conjuntos:
  A × (B ∪ C) = (A × B) ∪ (A × C)

31/08/2018: Conjuntos; Prova 1.1 [video]

• Generalizando o produtório para famílias indexadas
• liminf & limsup de seqüência de conjuntos
• Intervalos na reta real.
• Prova 1.1

03/09/2018: Conjuntos; Funções [video]

• Conjuntos
  • Disjuntos dois-a-dois.
  • Conjuntos disjuntos dois-a-dois («pairwise disjoint»): definição com e sem índices
  • Uma diferença importantíssima entre os operadores Σ e ⋃ e seus indices: um somatório infinito não é nem associativo nem comutativo!
  • Riemann's rearrangement theorem
  • Multisets.
• Funções
  • Conceito, notação, igualdade.
  • Igualdade extensional vs. intensional
  • Duas religiões sobre funções e seus black boxes
  • Diagramas internos e externos.
  • O conjunto (A→B) (também denotado por B^A)
  • Cardinalidade de (A→B)
  • (Co)domínios vazios.
  • Como definir e como não definir funções [1]
  • Expressões com buracos.
  • A notação lambda.

05/09/2018: Funções [video]

• Como definir e como não definir funções [2]
• Expressões com buracos
• A notação lambda
• Calcular uma expressão-λ
• Funções de graça
• Identidade
• Inclusão
• Constante: duas definições (equivalentes?)
• Aplicação parcial
• Composição
• Leis de composição

10/09/2018: Funções [video]

• Composição
• Leis de composição
• Iterações
• Aplicação parcial
• Quantos endomapas idempotentes existem num conjunto de cardinalidade 3?
• Injetoras, sobrejetoras, bijetoras
• Inversas
• Imagens, preimagens
• Funções de ordem superior
• Diagramas comutativos

12/09/2018: Funções [video]

• Diagramas comutativos
• Funções de graça: restrições
• Mais construções e operações em funções: cross, pair
• Currificação
• Funções parciais
• Funções não-deterministas
• Injetoras, sobrejetoras, bijetoras
• Inversas
• Imagens, preimagens
• A f-imagem respeita uniões e intersecções?

14/09/2018: Funções; Prova 1.2-T [video]

• O que podemos concluir se (gf) é bijetora?
• Turma T (última aula com a turma T)
  • Funções de graça: característica
  • Definições recursivas
  • Fixpoints
  • Prova 1.2-T
• Turma N
  • Recap: um exercício em diagramas comutativos
  • Funções de graça: característica
  • 0 e 1 como valores de verdade
  • O shell de Unix
  • Funções de graça: restrições
  • Mais construções e operações em funções: cross; pair; pointwise
  • Definições recursivas

17/09/2018: Funções [video]

• Recap: definições recursivas como sistemas para resolver
• (Por que) podemos realmente definir a função fibonacci assim?
• Funções de ordem superior
• Currificação
• Funções parciais
• Se |A×B| = 1, o que podemos concluir sobre os A, B?

19/09/2018: Funções; Programação; Prova 1.2-N [video]

• Funções
  • Regras de tipagem
  • Teaser: o isomorfismo Curry–Howard
  • Revisitando e redefinindo tipos e operadores
  • Seqüências; famílias indexadas; produto generalizado
  • Um ponto de vista interessante sobre injecções e sobrejecções
  • inverso-esqeurdo e inverso-direito
• Programação
  • funções de ordem superior em Python
• Prova 1.2-N

21/09/2018: Funções; Programação; Relações [video]

• Funções
  • Resolução de problemas da prova
• Programação
  • Programação imperativa
  • Programação declarativa
  • Programação funcional
  • Programação lógica
  • Exemplos em Haskell e Idris
• Relações
  • Trailer

24–28/09/2018: Aulas canceladas

01/10/2018: Relações [video]

• Conceito, notação, igualdade
• Definindo relações
• Diagramas internos
• Construções e operações em relações
• Propriedades de relações
• Fechos
• Relações de equivalência
• Partições
• A ordem dos fechos importa?

05/10/2018: Relações; Programação [video]

• Relações
  • Relações de ordem
  • Classes de equivalência
  • Conjunto quociente
  • Relações recursivas
  • Relações de ordem superior
  • ε-perto é uma relação de equivalência?
  • Relações como funções
  • Funções como relações
• Programação lógica

08/10/2018: Relações; Algebra abstrata; Teoria dos grupos; Prova 1.3 [video]

• Relações
  • Mais trocas de quantificadores
  • Conjuntos cofinitos
  • Dos inteiros para os racionais através duma relação de equivalência
• Algebra abstrata
  • Idéia & motivação
  • Conjuntos estruturados
  • Estrutura algébrica
  • Carrier set
  • Assinatura
  • Exemplos
  • Mais ou menos leis?
  • Modelos de estruturas algébricas
• Teoria dos grupos
  • História: Galois, Abel, …
  • Uns problemas antigos e abertos na época
  • Raízes de polinóimos com fórmulas
  • Construções com régua e compasso
  • Permutações
  • Notação com parenteses e com cíclos
• Prova 1.3

10/10/2018: Teoria dos grupos [video]

• Leis abstratas satisfeitas por S₃
• Escolhendo leis
• O que significa teoria dos grupos
• Umas definições equivalentes de grupo, com outros tipos de estrutura (assinaturas)
• Grupos abelianos
• Exemplos e nãœxemplos de grupos
• Primeiras conseqüências:
  • unicidade de identidade
  • O que ganhamos?
  • unicidade dos inversos
  • leis de cancelamento: (GCL) & (GCR)
• ℘A é grupo com qual das operações binárias conhecidas de conjuntos?

15/10/2018: Teoria dos grupos [video]

• Teorema: unicidade dos inversos
• Notação: Grupos aditivos e multiplicativos
• Teorema: inverso da identidade
• Maneiras diferentes de ler afirmações
• Como podemos provar que algo é a identidade do grupo?
• Uma resposta erradas
• potências de membros de grupo
• Teorema: inverso de inverso
• G abeliano ⇒ (ab)^-1 = b^-1a^-1
• Precisamos da comutatividade?
• Um raciocinio errado: usei a comutatividade na prova, então é necessária
• O converso é válido?
• Um raciocinio errado: supor o que quero provar par achegar em algo que já sei
• Teorema: inverso de produto
• Teorema: resolução de equações
• Identidade e inversos mais baratos
• Tabelas Cayley
• Jogando grupoku
• {2^n | n inteiro} vira um grupo com adição? Com multiplicação?

17/10/2018: Teoria dos grupos [video]

• Recap
• Identidade e inversos mais baratos
• Um critério para ser abeliano
• O (ab)²
• Se (ab)²=a²b² para todos os a,b, podemos concluir que o grupo é abeliano?
• Um raciocinio errado de novo: usei a comutatividade na prova, então é necessária
• Por que não incluir o (GA) nas leis de grupo
• Tabelas de Cayley
• Ordem de grupo: o(G) ou |G|
• Se a é um membro dum grupo, todas as suas potências também são
• O grupo ({0,1};+₂) e sua tabela Cayley
• As potências aⁿ para n=-1,0,1,2,…
• Duas definições razoáveis para o a^-2
• Teorema: as duas definições são equivalentes
• As potências aⁿ para n inteiro
• Teoremas: propriedades sobre potências
• Diagramas comutativos
• Um diagrama cuja comutatividade é a lei (a^-1)² = (a²)^-1
• Um diagrama cuja comutatividade é a lei (ab)^-1 = b^-1a^-1
• Lembrete: A função (f×g)
• Ordem de membro de grupo: o(a)
• o(2) = ∞ no grupo aditivo de reais
• Quantas ordens diferentes dentro dos membros do S₃

19/10/2018: Teoria dos grupos [video]

• Teoria até agora
• Definição: ordens: o(G), o(a)
• G abel ⇐⇒ ∀a∀b ( (ab)⁻¹ = a⁻¹b⁻¹ )
• quantas de todas as potências de a são distintas?
• teorema: tem exatamente o(a) potências distintas de a
• sinonimo: existem exatamente k potências de a
• distintos dois-a-dois
• s.p.d.g. (sem perda de generalidade)
• sermão: divisão de Euclides
• O que podemos concluir se...
  • Se aᵐ = e para algum m inteiro, então..?
  • Se o(a) = ∞, então..?
  • Se a⁻ᵖ = e para algum p positivo, então..?
• G abel ⇐⇒ ∀a∀b ( (ab)² = a²b² )

22/10/2018: Teoria dos grupos [video]

• G abel ⇐ ∀a∀b ( (ab)² = a²b² )
• aᵐ = e ⇐ o(a)|m
• aᵐ = e ⇒ o(a)|m
• o(a) = ∞ ⇒ todas as potências de a são distintas
• Subgrupos: definição
• Observação: associatividade de graça no H
• Observação: H e G não podem ter identidades diferentes
• Critério 1: quando H é não vazio, basta fechado pela operação e pelos inversos
• Critério 2: quando H é finito e não vazio, basta fechado pela operação
• Uma relação de equivalência: a RH b ⇐def⇒ ab⁻¹∊H
• ≤ é uma ordem parcial

24/10/2018: Teoria dos grupos [video]

• Mais um critérion de subgrupo
• Exemplos e nãœxemplos de (sub)grupos
• Teorema: intersecção de subgrupos é subgrupo
• Em geral não é verdade para união
• O subgrupo gerado por um membro de grupo
• Uns subconjuntos dum grupo de matrizes. São subgrupos?

26/10/2018: Teoria dos grupos [video]

• Geradores
• Bottom-up
• Top-down
• Subconjuntos convexos do plano
• Grupos cíclicos
• O S₃ é cíclico?
• (ℤ₆; +₆); (ℤ₆\{0}; ∙₆)

29/10/2018: Teoria dos grupos [video]

• Fecho convexo
• Congruences and cosets
• Existem H≤G tais que G infinito e {Ha₁, Ha₂, …, Haₙ} finito?

31/10/2018: Teoria dos grupos [video]

O caminho para o teorema de Lagrange

• Congruência modulo subgrupo
• Coclasses esquerdas/direitas
• Aviso: o que Ha = H significa
• Lema: Ha = H ⇔ a ∈ H
• Conseqüência: a ∉ H ⇔ Ha ≠ H
• Lema: a ∉ H ⇔ Ha, H disjuntos
• Para quais a∈G, temos Ha ≤ G?
• As coclasses direitas são disjuntas duas-a-duas
• O que podemos concluir sobre a colecção de todas as coclasses direitas
• Lema: todas as coclasses direitas têm a mesma cardinalidade
• Teorema: a colecção de coclasses direitas é uma partição do G
• Assim que tiver um H ≤ G…
• Como provar que as duas famílias são iguais
• Por que as coclasses direitas?
• Os HK, KH
• HK ≤ S₃? KH ≤ S₃?
• Dicas: como provar que as coclasses têm a mesma cardinalidade

05/11/2018: Teoria dos grupos [video]

• Todas as coclasses tem a mesma quantidade de membros
• O teorema de Lagrange
• Teoria dos números revisitada
• O teorema de Euler
• Subgrupos normais
• Conjugação em grupos
• O grupo quociente
• «é conjugado de» é uma relação de equivalência
• Simetrias do triângulo

07/11/2018: Teoria dos grupos [video]

• Simetrias
• Grupos isómorfos
• (Homo)morfismos de grupos
• Uns diagramas comutativos
• Diagramas de Hasse
• Critéria de homomorfismo

12/11/2018: Teoria dos grupos [video]

• -morfismos, Aut(G), Inn(G)
• Kernel, Image

13/11/2018: Teoria dos grupos [video]

• Teoria dos grupos: Revisão
• O primeiro teorema de isomorfismo de grupos

14/11/2018: Estruturas Algébricas [video]

• Teoria dos grupos
  • Recap: esboço do primeiro teorema de isomorfismo de grupos
  • Verificando se uma função é bem definida
• Estruturas Algébricas
  • Monóide
  • Anel
  • Anel comutativo
  • Divisores de zero
  • Domínio de integridade
  • Domínio de cancelamento
  • DI ⇐?⇒ DC
  • Anel booleano

16/11/2018: Álgebra abstrata; Prova 2 [video]

• Hom(G,H) & End(G)
• H abel ⇒ Hom(G,H) abel
• Corpos
• D domínio de integridade finito ⇒ D corpo
• Corpos ordenados

19/11/2018: Os reais [video]

• Corpo
• Corpo ordenado
• Como diferenciar os reais dos racionais?
• infimum, supremum, upper/lower bound, bounded above/below
• Um exemplo de subconjunto de reais interessante
• infA ≤ supA ?
• Lei de completude
• Corpo ordenado completo
• "único a menos de isomorfismo" (unique up to isomorphism)

23/11/2018: O paraíso de Cantor [video]

• Os irracionais
• O √2 é irracional
• Algébricos e transcendentais
• Duas definições equivalentes de algébrico
• O √2 é algebrico
• Uns números transcendentais
• Series Fourier
• Convergência ponto a ponto (pointwise)
• Uns teoremas de Cantor
• Pontos de acumulação
• Conjunto derivado
• Os conjuntos como objetos de estudos (first-class citizens)
• Como comparar conjuntos infinitos
• As relações =c, ≤c, <c
• Jogos imortais
• O conjunto de naturais é contável
• Os inteiros são contáveis
• Os racionais são contáveis
• O primeiro argumento diagonal de Cantor
• O strings finitos dum alfabeto finito são contáveis
• ≤c é equiantisimétrica? total?

26/11/2018: O paraíso de Cantor [video]

• Jogando o jogo de enumeração de Smullyan
• ℕ; ℤ; ℕ²; ℚ; ℕᵏ; Kleene star; A*; P_L; ℘fℕ; ℕ*; ℘f℘fℕ; ℘fᵏℕ
• Conjuntos incontáveis
• Numeros selvagens (ou domesticados?)
• O segundo argumento diagonal de Cantor
• Uma interpretação geométrica da expansão decimal de reais
• O conjunto de Cantor
• Aplicações da teoria de Cantor
• Irracionais
• Algebricos & transcendentais
• Respeitando e desrespeitando equinumerosidades

28/11/2018: O paraíso de Cantor [video]

• A ~ A' & B ~ B' ⇒ A✕A' = B✕B'
• f✕g
• A ≤c B ⇔ existe injetora f : A → B
• A ≤c B ⇒ existe sobrejetora f : B → A
• A ≤c B ⇐ existe sobrejetora f : B → A
• TEASER: Axioma da escolha
• Currificação: sem λ (matemática; python); com λ
• Qual o problema com o 3o problema resolvido?

30/11/2018: O paraíso de Cantor [video]

• Os programas de Nat para Nat
• Por que o mesmo argumento não serve para os racionais?
• Cantor vs Liouville
• Procurando bijecções
• Higher-order functions
• Teorema de Bernstein (CSB)
• Casamentos infinitos
• Teorema de Cantor
• Uma carta de Cantor para Dedekind

03/12/2018: O paraíso de Cantor; Russell; Teoria axiomática dos conjuntos [video]

• Cantor
  • Infinidades até agora
  • Codificações
  • Conseqüências do teorema de Cantor
  • Hipótese do continuum e da comparabilidade de cardinalidades: corretas ou não?
  • Hypergame de Zwicker
  • Um toque de teoria da medida
• De Russell para Zermelo
  • O paradoxo de Russell
  • Teoria dos tipos de Russell
  • Teoria dos conjuntos de Zermelo
• ZF
  • Noções primitivas
  • Revisão: traduzindo de e para a FOL dos conjuntos

05/12/2018: Teoria axiomática dos conjuntos [video]

• Interpretação de uma FOL
• Leis vs axiomas
• ZF1–ZF6 e suas conseqüências
• Quais axiomas preciso para construir conjuntos de qualquer cardinalidade finita desejada?
• Implementando outros tipos
• O par ordenado (2-tupla)

07/12/2018: Teoria axiomática dos conjuntos [video]

• União disjunta (coprodúto)
• Implementando relações, funções, números
• O ZF7 e suas conseqüências
• Quantos axiomas até agora?

10/12/2018: Teoria axiomática dos conjuntos; Prova 3 [video]

• Outros axiomas
• Outras axiomatizações
• Outros fundamentos
• Quantos conjuntos infinitos consigo construir?

12/12/2018: Futuro

• liminf e limsup
• Limites de seqüências
• Espaços métricos
• Topologia
• Mais posets
• Reticulados (como posets)
• Reticulados (como álgebras)

14/12/2018: Provas de recuperação

Futuro (fluido)