2018.1 FMC2, turma 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. Das minhas notas (em progresso) Matemática fundacional para computação, os capítulos:
   • Teoría elementar de números
   • Congrüências
   • Combinatória enumerativa
   • Recursão
   • Indução
4. 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 (minhas notas em progresso)
• Goldrei: Classic set theory, for guided independent study (4, 7, 8)
• Moschovakis: Notes on set theory (1, 2, 3–5, 6–7)
• Davey & Priestley: Introduction to lattices and order (1, 2)

Auxiliar

• Pinter: A book of abstract algebra (2–5, 6, 12, 17)
• Velleman: How to prove it (1.3, 1.4, 2.3, 4, 5, 7)
• Chartrand, Polimeni, Zhang: Mathematical Proofs (0–9)
• Doets & van Eijck: The Haskell Road to Logic, Maths and Programming (3, 4, 5, 6, 7)
• Paul Halmos: Naïve set theory
• Raymond Smullyan: Satan, Cantor, and Infinity
• Raymond Smullyan: A beginner's guide to mathematical logic (Volume 1)
• 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)
• Mac Lane & Birkhoff: Algebra (1.1–1.3)
• Herstein: Topics in Algebra (2.1–2.5 [skip # and *])
• Loomis & Sternberg: Advanced Calculus (0)
• Simmons: Introduction to topology and modern analysis (1)
• Munkres: Topology (1)
• João Marcos: Lógica Aplicada à Computação website (TdC, R&I)

Programação

• Friedman & Felleisen: The Little Schemer
• Bird: Introduction to Functional Programming using Haskell
• Hutton: Programming in Haskell
• Lipovača: Learn you a Haskell for great good
• Sterling & Shapiro: The art of Prolog

Dicas

• Jean-Pierre Serre: «How to write mathematics badly» (video lecture)
• Paul Halmos: How to write mathematics
• 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

Provinha 0

• Provinha 0 (pts: 0; bônus: 0) (dia: 21/02/2018)
  { uncensored, answers }
  correções: p1 (7M), p2 (5M), p3 (3M), tudo (16M).

Unidade 1

• Prova 1.1 (pts: 28; bônus: 0) (dia: 23/03/2018)
  { censored, uncensored, answers }
• Prova 1.X (pts: 8; bônus: 8) (dia: 06/04/2018)
  { censored, uncensored, answers }
• Prova 1.2 (pts: 42; bônus: 0) (dia: 20/04/2018)
  { censored, uncensored, answers }
• Prova 1.3 (pts: 30; bônus: 0) (dia: 30/04/2018)
  { censored, uncensored, answers }

Unidade 2

• Prova 2.X (pts: 14; bônus: 0) (dia: 23/05/2018)
  { censored, uncensored, answers }
• Prova 2.1 (pts: 156; bônus: 0) (dia: 11/06/2018)
  { censored, uncensored, answers };

Unidade 3

• Prova 3.X (pts: 8; bônus: 0) (dia: 29/06/2018)
  { censored, uncensored, answers }
• Prova 3.1 (pts: 158; bônus: 0) (dia: 02/07/2018)
  { censored, uncensored, answers }

Reposição

• Prova 4 (pts: 100; bônus: 0) (dia: 06/07/2018) [participantes]
  { prova oral }

Pontos extra

Unidade 1

Unidade 2

Unidade 3

Homework

23/02/2018

1. Resolvam completamente sozinhos os A, B, C, D da Provinha 0.
2. Estudem o gabarito.

26/02/2018

1. Resolvam completamente sozinhos o I da Provinha 0.
2. Estudem o gabarito.
3. Estudem o capítulo «Linguagens» do meu livro e resolvam seus exercícios e problemas.
4. Estudem o capítulo sobre indução no livro de Velleman e resolvam seus exercícios e problemas.
5. Estudem os capítulos «Recursão» e «Indução» do meu livro e resolvam seus exercícios e problemas.

28/02/2018

1. Estudem o capítulo «Linguagens» do meu livro e resolvam seus exercícios e problemas.
2. Estudem bem as correções da Provinha 0. Todas, não apenas as suas! Podem buscar da minha sala, e discutir qualquer dúvida.

04/03/2018

1. Estudem os capítulo «Recursão» e «Indução» do meu livro e resolvam seus exercícios e problemas.

05/03/2018

1. Escrevam sozinhos a definição completa de fórmula bem formada, dada uma FOL.
2. Improvesem criando várias FOLs, e escrevam fórmulas que correspondem em várias afirmações interessantes sobre um universo escolhido.

09/03/2018

1. Estudem do meu livro: Capítulo «Conjuntos»; até o final da secção «Umas provas simples».

12/03/2018 – 14/03/2018

1. Estudem do meu livro: Capítulo «Conjuntos»; até o final da secção «Powerset» (Resolvam todos os problemas!)
2. Prove diretamente: se A Δ B = Ø então A = B.
3. Prove a mesma coisa atacando sua contrapositiva.

16/03/2018

1. Estudem todo o capítulo «Conjuntos» do meu livro, e resolvam todos os seus exercícios e problemas!
2. Sejam A um conjunto, e A_n uma seqüência de subconjuntos de A. Defina:
   A_* = ⋃_i=0^∞ ⋂_j=i^∞ A_j
   A^* = ⋂_i=0^∞ ⋃_j=i^∞ A_j
   • Como descreveria os elementos dos A_* e A^*?
   • É verdade que um desses conjuntos é subconjunto do outro? São iguais? São disjuntos?
3. Estudem as secções 1.4 e 2.3 de Velleman, e resolvam todos os exercícios e problemas.

19/03/2018

1. Resolvem sozinhos das Provas 1.1 das turmas de 2017.2 e 2017.1, todos os problemas que têm a ver com conjuntos.

26/03/2018

1. Estudem o gabarito da Prova 1.1 e depois resolvam sozinhos todos os seus problemas.
2. Estudem todo o capítulo «Conjuntos» do meu livro e resolvam todos seus exercícios e problemas.

01/04/2018

1. Estudem as primeiras secções do capítulo «Funções» do meu livro (até e incluindo a secção «A notação λ») e resolvam todos os exercícios.

02/04/2018

1. Estudem a secção «Funções de ordem superior» do capítulo «Funções» do meu livro e resolvam todos os exercícios.

04/04/2018

1. Provem a lei de associatividade da composição de funções.

05/04/2018

1. Estudem (resolvendo todos os exercícios) as secções
   • Conceito, notação, igualdade
   • Como definir e como não definir funções
   • Expressões com buracos
   • A notação λ
   • (Co)domínios vazios
   • Composição
   • Leis de composição
   • Funções de ordem superior

09/04/2018

1. Estudem (resolvendo todos os exercícios) as secções
   • Funções de graça
   • Aplicação parcial
   • Leis de composição
   • Diagramas comutativos

12/04/2018

1. Provem que se f é injetora, entao: f∘g = f∘h ⇒ g = h
2. Provem que se f é sobrejetora, entao: g∘f = h∘f ⇒ g = h
3. As afirmações conversas são válidas?
4. Prove que para cada operação associativa *, definindo as potências como definimos (como nos naturais), não importa se escolher a*aⁿ ou aⁿ*a
5. Estudem (resolvendo todos os exercícios) as secções
   • Definições recursivas
   • Mais construções e operações em funções
   • Injetoras, sobrejetoras, bijetoras

13/04/2018

1. Escrevam do zero as duas direções das duas provas do homework anterior.
2. Estudem (resolvendo todos os exercícios) as secções
   • Injetoras, sobrejetoras, bijetoras
   • Mais construções e operações em funções
   • Imagens e preimagens
3. Resolvam o problemas no fim do capítulo «Funções»

20/04/2018

1. Estudem (resolvendo todos os exercícios) a secção «Imagens, preimagens»
2. Revisem os capítulos «Conjuntos» e «Funções»

21/04/2018

1. Estudem o gabarito
2. Revisem os capítulos «Conjuntos» e «Funções»

25/04/2018 — 30/04/2018

1. Resolvam os plickers;
2. Mostrem como, começando com uma partição dum conjunto, podemos definir uma realção de equivalência nele, tal que seu conjunto quociente é a partição;
3. Definam formalmente os fechos: reflexivo; simétrico; transitivo;
4. Estudem as provas 1.* de 2017.1 e 2017.2 (a de 2017.1 tem o assunto de contabilidade que vamos estudar na unidade 3);
5. Provem que o conjunto quociente de qualquer relação de equivalência num conjunto A é uma partição do A;
6. Estudem o capítulo «Relações» do fmcbook, e resolvem todos os seus exercícios e problemas
7. Revisem/estudem os capítulo «Conjuntos» e «Funções» do fmcbook, e resolvem todos os seus exercícios e problemas

01/05/2018

1. Estudem o gabarito da Prova 1.3
2. Revisem os capítulos: «Conjuntos»; «Funções»; «Relações»

04/05/2018

1. Resolva o plicker: RT = T? RF = F?
2. Estude o glossário do capítulo «Conjuntos Estruturados»
3. Para o conjunto estruturado (S₃; ∘), decida quais das propriedades desse glossário são satisfeitas e quais não.
4. Estude a secção «Permutações» do capítulo «Teoria dos grupos» e resolva seus exercícios.

07/05/2018

1. Estudem até a secção «Primeiras conseqüências», resolvendo todos os exercícios.

09/05/2018

1. Verdade ou falso? Se num grupo existem x, y distintos tais que inv(xy) = inv(x) inv(y), então o grupo é abeliano.
2. Achem todos os grupos com 3 elementos e com 4 elementos (usando tabelas Cayley).
3. Quais são as regras do «Grupoku»?
4. Estudem até a secção «Tabelas Cayley» e resolvam seus exercícios.

09/05/2018

1. Verdade ou falso? Se num grupo existem x, y distintos tais que inv(xy) = inv(x) inv(y), então o grupo é abeliano.
2. Achem todos os grupos com 3 elementos e com 4 elementos (usando tabelas Cayley).
3. Quais são as regras do «Grupoku»?
4. Estudem até a secção «Tabelas Cayley» e resolvam seus exercícios.

11/05/2018 – 15/05/2018

1. Prove que as duas definições de exponenciação são equivalentes se a operação é associativa com identidade.
2. Prove ou refute: para todo n, Z_n é um grupo com operação a subtraição modular.
3. Prove ou refute: para todo n, C_n (coprimos de n) é um grupo com operação a multiplicação modular.
4. Prove ou refute: para todo n, D_n (divisores de n menores que n) é um grupo com operação a multiplicação modular.
5. Estudem até a secção «Subgrupos» e resolvam os exercícios.
6. Resolvem os problemas Π18.1, Π18.2, Π18.3.

22/05/2018

1. Estude a secção «Subgrupos» e resolva os exercícios.

23/05/2018

1. Estude a secção «Ordens, geradores, grupos cíclicos» e resolva os exercícios.

25/05/2018 – 28/05/2018

1. Estude a secção «Congruências e cosets» e resolva os exercícios.
2. Especialmente o Teorema Θ18.110!

30/05/2018

1. Estude a secçãozinha «Teoria de números revisitada» e resolva os exercícios.
2. Estude a secção «Subgrupos normais» e resolva os exercícios.

01/06/2018

1. Estude a secção «Subgrupos normais» e resolva os exercícios.
2. Especificamente escreva provas sobre as equivalências de todas as definições alternativas de «ser subgrupo normal».

06/06/2018

1. Estude a secção «Simetrias» e resolva os exercícios.
2. Estude a secção «Morfismos» e resolva os exercícios.

08/06/2018

1. Estude a secção «Kernel, Image» e resolva os exercícios.
2. Revise todo o capítulo «Teoria dos grupos».

12/06/2018

1. Estude o gabarito da Prova 2.1
2. Estude o capítulo «Mais estruturas algébricas»
3. Estude o capítulo «Os números reais»

13/06/2018

1. Ache estratégias para o jogo de imortais com os conjuntos seguintes
   • ℤ²; ℕ^k;
   • ℘_fℕ; ℘_f℘_fℕ;
   • A^*;
   • ℚ
   • ℕ^*;

22/06/2018

1. Ache uma nova prova do teorema de Cantor, baseada no Hypergame
2. Resolva todos os exercícios e problemas do Capítulo «O paraiso de Cantor»
3. Estude bem o capítulo «Teoria axiomática de Conjuntos» até o item x33.4.

24/06/2018

1. Estude a «Part VI» (Cap.18–25) do livro Satan, Cantor, and Infinity de Smullyan

25/06/2018

1. Mostre que o operador de par ordenado de Kuratowski satisfaz a OP2.
2. Mostre que: A ≤c B sse existe função sobrejetora de B para A
3. Estude o capítulo «Teoria axiomática de Conjuntos» até o primeiro intervalo de problemas (e resolva esses problemas e todos os exercícios até esse ponto).

Histórico de aulas

19/02/2018: Apresentação

• Apresentação dos assuntos principais
• Erros de tipo na escrita
• Típos de: conjuntos, funções, relações
• Algebra abstrata e suas métodos
• Teoria de conjuntos, fundações de matemática
• Axiomas – Teoremas
• Noções primitivas – Definições
• Sinônimos de «teorema» e seus usos: lema, corolário
• Como provar que não existe prova de alguma dada proposição

21/02/2018: Provinha 0

23/02/2018

• Sermão
• Resolução da prova
• O contexto duma definição
• Os dois erros principais em dando definição:
  • Não aceitar objetos que deveriam ser aceitos
  • Aceitar objetos que não deveriam ser aceitos
• para todo vs. existe
• Variáveis ligadas vs. variáveis livres
• Os conectivos ¬, ∨, ∧, →, ↔ e sua semântica
• Açúcar sintáctico
  • (∀x∈A) P(x)
  • (∃x∈A) P(x)
• Provas como jogos

26/02/2018

• Indução
• Indução forte
• Como usar (como dados) e como atacar (como alvos) proposições de várias fórmas de lógica: ¬P; P∨Q; P∧Q; P→Q; (∀x∈A) P(x); (∃x∈A) P(x)
• Diferença entre as duas frases:
  • «Como __A__, logo __B__.»
  • «Se __A__, então __B__.»
• Erro comum 1: ``provar'' repetindo a definição
• Erro comum 2: supor o que queremos provar para concluir algo já conhecido

28/02/2018

• Linguagens formais
• Alfabetos, espressões
• Sintáxe vs. semántica
• Linguagem-objeto vs. metalinguagem
• «meta-»: metalinguagem, metavariáveis, etc.
• Definições recursivas
• A linguagem de expressões de aritmética (com numerais e/ou variáveis)
• Arvores sintáticas (árvores de derivação)
• A notação BNF
• Mais açúcar sintáctico
• Associatividade a esquerda e a direita

02/03/2018

• Resolução de problemas
• Uma gramática BNF para as fórmulas da lógica proposicional
• Recursão e indução revisitadas: nas fórmulas e nos naturais

05/03/2018: Lógica

• Traduções de lógica para português e vice-versa
• Limitações de lógica proposicional
• Lógica da primeira ordem (FOL)
• Termos vs. Fórmulas (objetos vs. proposições)
• A sintáxe das linguágens de FOL
• Símbolos de funções vs. símbolos de predicados
• Definição formal de well-formed formula (wff) [fórmula bem formada (fbf)]

07/03/2018: Lógica; Escrita; Conjuntos

• Lógica
  • Recap: a linguagem de lógica proposicional e suas limitações
  • Recap: as linguagens de FOL
  • Funções de aridade 0 vs. constantes
  • O significado da implicação
  • Wason's selection task
• Escrita
  • afirmações e suas justificativas (escritas por linha)
  • = vs. ⟺
  • os «def» em cima de = e de ⟺
  • época de typewriters: não escreva ->; escreva →
• Conjuntos
  • O tipo Conjunto
  • Conceito e notação
  • Homogeneidade e heterogeneidade de conjuntos
  • Noções primitivas: ser conjunto (Set(–)), pertencer (–∈–)
  • Conjuntos como “black boxes”
  • Igualdade entre conjuntos: A = B

09/03/2018: Lógica; Conjuntos

• Lógica e matemática
  • Abreviações e açúcar sintáctico
    • (∀x∈A) P(x)
    • (∃x∈A) P(x)
    • ∃!x P(x)
    • (∃!x∈ A) P(x)
  • Erro comum: artigo definido vs. artigo indefinido
  • Dois jeitos de uma definição ser errada
• Conjuntos
  • Conceito e notação
  • Sinónimos de “conjunto”: família, colecção, etc.; fontes usados e seus usos
  • Set comprehension (Set-builder notation)
  • Variações de set-builder como açúcar sintáctico da set-builder padrão
  • Noções primitivas: ser conjunto (Set(–)), pertencer (–∈–)
  • Igualdade entre conjuntos: A = B
  • Extensão vs. Intensão
  • Igualdade extensional vs. igualdade intensional
  • Conjuntos como “black boxes”
  • Definição: A subconjunto de B: A⊆B
  • Definições: vazio, singleton
  • Provas de unicidade: existe pelo menos um & existe no máximo um
  • Erro comum: quantos elementos {x,y,z} tem?
  • Podemos concluir Ø∈A? Podemos concluir Ø⊆A?

12/03/2018: Conjuntos

• Oito afirmações sobre o Ø e um conjunto A
• Escolhendo a ordem de atacar teoremas
• As relações binárias: =, ⊆, ⊇, ⊊, ⊋
• Operações entre conjuntos e dois jeitos de as definir
• As operações binárias: ∩, ∪, \
• O perador de Powerset (℘)
• A operação unária de complemento: ^~
• Conjunto universal
• Unicidade do conjunto vazio e do conjunto universal
• Definindo Conjuntos
• Relações entre conjuntos e como as definir
• Provando iqualdades entre conjuntos
• Generalizando as operações de união e intersecção: as operações unárias ⋂, ⋃

14/03/2018: Conjuntos

• Recap: definição de operadores e de relações entre conjuntos
• Conjuntos definidos pela notação set-builder e suas variações (açúcares sintácticas)
• Provas por casos
• Variáveis ligádas e livres
• Provar a afirmação: w satisfaz a afirmação para todo x, P(x,w)
• Refutar a afirmação: w satisfaz a afirmação para todo x, P(x,w)
• { t | ___t___ } vs. { t | ___(fórmula fechada)___ }
• Fórmulas abértas e fechadas
• O que realmente acontece escrevendo: { x | ___x___ para algum x }
• A diferença simétrica: definição e intuição
• Contrapositivo de implicação
• Como provar vs. como refutir uma implicação
• teorema: se A Δ B = Ø então A = B
• Aplicando (e iterando) as ℘, ⋂ e ⋃ no Ø

16/03/2018: Conjuntos; Tuplas; Seqüências; Famílias indexadas

• Seqüências de conjuntos
• Aplicando (e iterando) as ℘, ⋂ e ⋃ no Ø
• Intuição sobre os ⋂, ⋃, e ℘ e as {, }
• ⋂ e ⋃ com subscripts (mais notações)
• Família de conjuntos indexada por algum conjunto I: (A_i | i∈I)
• Exemplos: Os conjuntos A_p e F_p de todos os ancestrais e todos os filhos de p, respeitivamente.
• Traduzindo afirmações da linguagem natural para relações entre conjuntos e vice-versa
• Como usar um fato do tipo D≠Ø em nossas provas: «Seja d∈D.»
• projeções: π_i
• Produto cartesiano (×)
• Aⁿ para n≥2: definição “direta” e recursiva
• Intervalos de reais, suas intersecções e uniões arbitrárias

19/03/2018: Conjuntos

• Conjuntos
  • tuplas como noções primitivas: igualdade, tamanho, projeções
  • Conjuntos disjuntos
  • Cardinalidade de conjuntos finitos e propriedades
  • Um teorema de igualdade de conjuntos:
    Suponha que A, B ≠ Ø.
    A×B = B×A ⇔ A = B.
  • Os operadores binários ∪ e ∩ como açucar sintático (definido pelos operadores unários ⋃ e ⋂ respeitivamente)
  • Conjuntos disjuntos dois-a-dois («pairwise disjoint»): definição com e sem índices
  • Resolução de uns problemas da Prova 1.1-N de 2017.2
  • ⋂Ø = ?
• Análise
  • 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

21/03/2018: Apagão

23/03/2018: Conjuntos; Prova 1.1

• Conjuntos
  • (a,b,c) vs. ((a,b),c) vs. (a,(b,c))
  • Produto cartesiano generalizado (de família indexada de conjuntos)
• Prova 1.1

26/03/2018: Sermão; Funções

• Sermão!
  • Erros de tipos na escrita
  • Resolução dos B2, C1, C2 da Prova 1.1
  • Revisão das definições relevantes
• Funções
  • Conceito e notação
  • Funções como black boxes
  • Domínio e codomínio
  • Intensão vs extensão
  • Igualdade: f = g
    Quaisquer duas das:
    • dom(f) = dom(g)
    • para todo x ∈ dom(f), f(x) = g(x)
    • para todo x ∈ dom(g), f(x) = g(x)
  • A operação binária de conjuntos (•→•)
  • Diagramas internos
  • Como definir funções e notação relevante (I)
  • O espaço de funções de A para B: (A→B)
  • |(A→B)| = ?

28/03/2018: Funções

• Recap: definição de função (duas condições) e igualdade
• Duas abordagens diferentes sobre o que é uma função: o codomínio faz/não faz parte
• O tipo de uma função
• Como definir funções e notação relevante (II)
• sin vs. sin(x)
• «buracos» em expressões com –, •, etc.; com lambdas (λ)
• A notação de λ-calculus
• Como não definir funções: erros comuns
• Quantas funções injetoras de A para B

02/04/2018: Funções

• Recap: como definir e como não definir funções
• Mais sobre os pontos de vistas diferentes de funções e seus codomínios
• Igualdade de funções f,g:A→B
• Definindo por fórmula
• Notação de λ-calculus
• λ e ligadores de variáveis em geral
• Cuidados com renomeamentos de variáveis
• η-equivalência: f = (λx. f x)
• α-equivalência: (λx.x) = (λy.y)
• (λx. 2 + (λy. x-y) 8) 50 = ?
• Testando lambdas e tipos de funções em Python
• Higher-order functions (funções de ordem superior) com buracos e com lambdas
• A → (B → C) vs. (A → B) → C

04/04/2018: Funções

• Mais exemplos de funções de ordem superior
• Aplicação parcial
• Aplicação parcial como black box
• Aplicação parcial e «buracos»: com –, •, etc.; com lambdas (λ)
• O que podemos concluir se: f : A → Ø; g : Ø → B
• Função vazia
• O que podemos concluir se |A×B| = 1?
• Função identidade de A: id_A
• Identidades, constantes
• Composição
• Composição com black boxes
• Similaridades (e diferençás) com multiplicação de números
• O lei da associatividade da composição: h∘(g∘f) = (h∘g)∘f; prova e intuição
• Composição como operação associativa

06/04/2018: Funções; Prova 1.X

• Diagramas internos e externos
• Diagramas internos de endomapas
• Como definir o que é uma função constante
• A ordem dos quantificadores diferentes importa!
• As leis das identidades e suas provas
• Diagramas comutativos
• Como expressar os dois leis da composição e da identidade usando diagramas comutativos
• Prova 1.X
• endomapa (ou endomapeamento): f:A→A
• função idempotente: f∘f = f
• Quantos endomapas satisfazem f∘f = f?

09/04/2018: Funções

• Sermão: type-errors com o ∘
• Como contar endomapas indepotentes
• Uma notação alternativa do (A→B): B^A
• Podemos definir a g∘f se codf⊊domg
• Mais sobre a definição de «função constante»
• Mais diagramas comutatívos
• Mais funções de graça: inclusão; cross (f×g); pair (f,g);
• Funções injetoras, sobrejetoras, bijetoras: formalmente e informalmente
• Usando propriedades da g∘f para deduzir propriedades das f e g

11/04/2018: Funções

• Uma definição equivalente de bijetora
• Diferençá nas fórmulas lógicas das definições de injetora e sobrejetora
• Um diagrama comutativo com a função pair (f,g)
• Mais comparações entre multiplicação de números e composição de funções
• Identidade esquerda; identidade direita; identidade (de operação binária)
• Iterações de algum endomapeamento f:A→A
• Recursão
  • cuidados com definições
  • Equações como sistema onde o desconhecido é a f
  • definições perigosas
  • definições seguras
  • recursão mutual: even; odd
• O que deminua na definição recursiva com logs e potências de 2?

13/04/2018: Funções

• Duas provas completas: definições equivalentes para injetora e sobrejetora usando apenas composição e diagramas comutativos
• A função-imagem f[–]
• A f[–] respeita as uniões? As intersecções?

16/04/2018: Funções

• Imagem; pre-imagem: ideia/noção, definições dos conjuntos f[A] e f^–1[B]
• Função inversa; definição, notação
• A função inversa é bijetora
• Justificação da notação ambigua: f^–1[–]
• f[f^–1[Υ]] =?= Υ
• f^–1[f[Χ]] =?= Χ
• Propriedades preservadas por composição

18/04/2018: Funções

• Resolução de homeworks
• A função-preimagem respeita a união e a intersecção?
• Restrição
• Funções de ordem superior: noção, exemplos
• Currificação: de f:(A×B)→C para F:A→(B→C); com função epônima (com nome); com função anônima (usando λ)

20/04/2018: Funções; Prova 1.2

• O inverso da composição
• Funções parciais
• Funções não-deterministas
• Prova 1.2

23/04/2018: Relações

• Noção, relações como black-boxes
• Igualdade
• Extensão vs. intensão
• Relações binárias e notações alternativas
• Definindo relações: com frases e buracos
• Aplicação parcial em relações
• Propriedades de relações binárias num conjunto A
  • reflexiva; irreflexiva
  • simétrica; asimétrica; antisimétrica
  • transitiva
  • circular
• Composição entre relações
• Relação inversa
• Relações como generalização de função
• Comparação com funções
• Seja ε real com 0<ε<1. Definimos nos reais a relação ~ com: x~y sse (x–y)²<ε.
  Ela é simétrica? Reflexiva? Transitiva?

25/04/2018: Relações

• Reflexividade: reflexiva; irreflexiva
• Simetria: simétrica; asimétrica; antisimétrica
• Transições: transitividade; circular; left-euclidean; right-euclidean
• Totalidade: total; tricotômica
• Gráfico de função
• Gráfico de relação
• Notação conjuntista e notação funcionista para relações
• Diagramas internos
• Propriedades de relações e em que correspondem nos diagramas internos
• Relações de equivalência
• Partições
• De relação de equivalência para partição e vice versa
• Classe de equivalência
• O conjunto quociênte
• Fechos de relação: reflexivo; simétrico; transitivo
• A ordem de fechos importa? t(r(R)) = r(t(R))? t(s(R)) = s(t(R))?

27/04/2018: Relações

• Relação de equivalência no A vs. partição de A
• Fechos formalmente: reflexivo, transitivo, simétrico, etc.
• Potências de ∘: intuição e definição formal
• Associatividade e elemento neutro de ∘
• Duas relações no conjunto de seqüências infinitas de naturais (ℕ→ℕ): são relações de equivalência?

30/04/2018: Relações; Prova 1.3

• Dividindo conjuntos por relações
• Interpretações de conjuntos quocientes
• Prova 1.3

02/05/2018: Revisão; Programação declarativa; Algebra abstrata

• Revisão
  • Conjuntos
  • Funções
  • Relações
  • Resolução dos I1–I2 da Prova 1.3
• Algebra abstrata
  • Introdução e idéia
  • Conjuntos estruturados
  • Estrutura e assinatura
  • Abusos notacionais
  • frame ou carrier set
  • Duas operações binárias nos reais: são associativas?
• Programação declarativa
  • Programação funcional
  • Programação lógica
  • Funções como relações, relações como funções

04/05/2018: História; Algebra abstrata; Teoria dos grupos

• História: de Euclides (300 BC) para Galois (1830)
  • Geometria euclideana, teoria de números, e os Elementos de Euclides
  • Construções com régua e compasso
  • Construções impossíveis
  • Fórmulas para as raizes de polinómios de grau 5 ou superior
  • Galois e suas idéias
  • Abel
  • Wantzel (provas de impossibilidade de resolver)
  • Independência de axiomas
• Álgebra abstrata
  • Operações e propriedades: glossário
• Teoria dos grupos
  • S_n
  • Notações para representar elementos de S_n: completa e com cíclos
  • S₃ e seus elementos
• RT=T? RF=F?

07/05/2018: Teoria dos grupos

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

09/05/2018: Teoria dos grupos

• Primeiras conseqüências:
  • O que ganhamos?
  • Duas perguntas e duas respostas erradas
  • 3 leis sobre inversos e seus diagramas comutativos: inv de e; inv de inv; inv de prod.
  • Resolução de equações
  • G abeliano sse para todo a,b, inv(ab) = inv(a)inv(b) ?
• Tabelas Cayley: grupoku e suas regras

11/05/2018: Teoria dos grupos

• Corolários da resolução de equações: identidade e inversos mais baratos
• Tabelas Cayley: grupoku e suas regras
• «Todos» os grupos de ordens: 0, 1, 2, 3, 4.
• Mais exemplos de grupos
• Ordem de grupo
• Potências
• Ordem de membro de grupo

14/05/2018: Teoria dos grupos

• Recap: teoria dos grupos
• Grupoku: mais regras
• duas possíveis definições de a^–2
• a^w para w inteiro
• Teoremas sobre ordem
• Strings um alfabeto com concatenação: grupo ou não?

16/05/2018: Aula cancelada

18/05/2018: Teoria dos grupos

• Dois teoremas sobre o(a)
• «Existem exatamente n objetos tais que...»
• S.p.d.g. («sem perda de generalidade...»)

21/05/2018: Teoria dos grupos

• Subgrupos
• Critéria de ser subgrupo
• O que ganhamos sabendo que um conjunto é finito?
• Intersecção de subgrupos é subgrupo
• União de subgrupos não é necessariamente subgrupo
• A relação ≤ é uma ordem parcial

23/05/2018: Teoria dos grupos; Prova 2.X

• Prova 2.X
• A relação: a R_H b sse ab^–1 ∈ H
• Geradores de grupos
• Pode escolher o H tal que R_H será a igualdade? A True?

25/05/2018: Teoria dos grupos

• O H sendo fechado pela operação não nos permite concluir a,b∈H pela ab∈H
• Bottom-up
• Top-down
• Grupos cíclicos
• Congrüências e cosets
• Índice de subgrupo no grupo (G:H)
• A idéia do teorema de Lagrange
• Tem grupo infinito G com subgrupo H com índice finito?

28/05/2018: Teoria dos grupos

• O teorema de Lagrange
• Corolários do teorema de Lagrange
• HK = KH? HK ≤ G? KH ≤ G?

30/05/2018: Teoria dos grupos

• KH = HK sse HK ≤ G
• Mais uma explicação do Teorema de Lagrange
• Índice de subgrupo num grupo
• (G:H) = o(G) / o(H)
• Teoria dos números revisitada
• O teorema de Euler como corolário de Lagrange
• Coclasses esquerdas e direitas de N={id, ψ, ψ²}
• Subgrupos normais: primeira definição
• (Teorema Lucas–JP') H≤G & 2 o(H) = o(G) ⇒ H normal

01/06/2018: Teoria dos grupos

• Propriedades de coclasses esquerdas/direitas e das relações de congruência módulo esquerdo/direito
• Conjugados
• «Ser conjugado de» é uma relação de equivalência
• Subgrupos normais: definições alternativas
• Grupos de matrices 2×2

04/06/2018: Teoria dos grupos

• O grupo quociente G/N
• Lemma: (Na)(Nb) = N(ab)
• Teorema: O grupo quociente realmente é um grupo
• O que é uma simetria?
• As simetrias do triangulo
• O grupo dihedral D₃ das simetrias do triangulo
• Isomorfia; grupos isomórficos (ou isómorfos)
• As simetrias dum quadrado

06/06/2018: Teoria dos grupos

• Isometrias e simetrias
• O grupo dihedral D₄
• Propriedades grupoteóricas
• Objetos isomórficos: a idéia de isomorfia
• Como provar que dois grupos não são isómorfos
• Posets
• Diagramas Hasse
• O Hasse do poset (℘{0,1,2};⊆)
• O Hasse do poset (Sub(D₄);≤)
• Quantos essencialmente distintos grupos existem de ordem n?
• (Homo)morfísmos
• Preservar/respeitar a estrutura
• Respeitar a operação dum grupo
• Respeitar os inversos
• Respeitar a identidade
• O respeito da operação e dos inversos como diagramas comutativos
• (mono; epi; iso; endo; auto)-morfismos
• Como provar que dois grupos são isómorfos
• Criterion 1 (homomorfismo): φ que respeita op & inv é homomorfismo
• (Aut(G); ∘) é um grupo?

08/06/2018: Teoria dos grupos & estruturas algébricas

• Kernel e Image de homomorfismos
• kerφ é normal?

11/06/2018: Algebra; Prova 2.1

• Teorema fundamental de homomorfismos
• Prova 2.1

13/06/2018: Os reais (cálculo de verdade) & o paraiso de Cantor

• Outras estruturas algebricas
  • Semigrupos
  • Monóides
  • Aneis
  • Corpos
• Quais dos G,H precisam ser abelianos para o (Hom(A,G);+) ser um grupo abeliano?
• Corpos ordenados
• Corpos ordenados completos
• Os axiomas dos números reais
• upper/lower bounds
• lub/glb; sup/inf; join/meet
• História: o fim dos 1800's, AC e DC (Antes Cantor e Depois Cantor)
• Cantor 1870–1872: melhorando seu teorema sobre as Fourier series
• As primeiras ideias de comparar o tamanho de conjuntos infinitos
• Georg Cantor: matemática A.C.&D.C.
• Jogos imortais
• Conjuntos contáveis/enumeráveis
• Estrategias para garantir vitoria no jogo de imortais «adivinhe o s que eu estou pensando» se s∈…:
  • {1,2,3};
  • ℕ;
  • ℤ;
  • ℕ²;
• Stratificação dos palpites
• O primeiro argumento diagonal de Cantor

15/06/2018: Paraiso de Cantor

• O que significa contar?
• Como podemos comparar o tamanho de dois conjuntos finitos?
• Como podemos comparar o tamanho de dois conjuntos infinitos?
• Mais conjuntos-segredos para o jogo:
  • ⋃{ C_n | n∈ℕ }
• Um conjunto incontável: [0,1]
• O segundo argumento diagonal de Cantor
• O powerset respeita a equinumerosidade
• Quais operações “respeitam” as cardinalidades?
• Uma definição errada de A<_cB
• O Cantor set e a prova que é incontável
• Definições:
  • Equinumerosidade: conjuntos equinúmeros (A =_c B)
  • O conjunto n = {0, 1, …, n–1}
  • Conjunto finito, infinito, contável/(d)enumerável, incontável
• Representação dos números reais no [0,1] em forma 0,... para varias bases: interpretação geometrica na linha como instruções
• Números racionais e irracionais
• O conjunto dos racionais é contável
• O conjunto dos irracionais é incontável
• Kleene star

18/06/2018: Paraiso de Cantor

• Duas definições equivalentes de A≤_cB
• Procurando bijeções entre intervalos de reais
• Casamentos infinitos: a questão
• O teorema Schröder–Bernstein e suas aplicações
• Provas de equinumerosidade com e sem o teorema Schröder–Bernstein
• Um teorema de Cantor: A<_c℘A
• Os conjuntos de polinómios
• Os ℤ[x] e ℚ[x] são contáveis!
• Números algébricos e transcendentais
• O conjunto dos algébricos é contável
• O conjunto dos transcendentais é incontável
• A relação =_c é relação de equivalência?

20/06/2018: De Cantor para Russel e de Russel para Zermelo

• Casamentos infinitos: uma dica
• Uma infinidade contável de «infinidades diferentes»:
  ℕ <_c ℘ℕ <_c ℘℘ℕ <_c ℘℘℘ℕ <_c …
• Tem algum conjunto «maior»?
• Os cardinais: ℵ₀ (aleph 0), 𝖈 (continuum)
• Recap: o teorema de Cantor e suas conseqüências
• Não existe cardinalidade máxima
• Codificações em números
• O powerset dos naturais – as seqüências infinitas de 0s e 1s
• Uma carta de Cantor para Dedekind
• A resposta de Dedekind
• A frase «tende ao…»
• Aplicação: teoria de medida
  • teoria de medida (Borel, Lebesgue, Baire)
  • Generalização de comprimento e probabilidadem
  • Por que a probabilidade de escolher x racional, escolhendo entre o [0,1] é 0?
  • Probabilidade de escolher transcendental nos reais em [0,1]

22/06/2018: Teoria de Conjuntos Axiomática

• Paraiso de Cantor
  • Seja A conjunto não vazio e f:A→℘A a função definida pela f(x)={x}. Prove que f não é sobrejetora.
  • O que significa cardinalidade de um conjunto A?
  • A dupla abstração: a notação de cardinalidade A de Cantor
  • Hypergame
  • O números transfinitos de Cantor: cardinais e ordinais, e sua aritmética
  • As perguntas grantes: Principle of Cardinal Comparability, Continuum Hypothesis, Generalized Continuum Hypothesis
• Teoria de Conjuntos Axiomática
  • Revisão: conjuntos, tuplas, relações, funções
  • O paraiso de Cantor
  • Axioma de Extensionalidade e Princípio da Comprehensão Geral
  • O parádoxo de Russell (1902)
  • Russell: teoria de tipos
  • Zermelo: teoria axiomática de conjuntos ZF
  • Os axiomas ZFC
  • ZF1 e suas conseqüências
  • ZF2 e suas conseqüências
  • ZF3 e suas conseqüências
  • Com ZF1–ZF3 podemos construir apenas conjuntos com cardinalidade 0, 1, ou 2.
  • Traduções de FOL para português e vice-versa
  • Definições de: Ø; {–}; {–,–};

25/06/2018: Teoria de Conjuntos Axiomática

• Axiomas vs. leis
• ZF4, sua interpração e uma comparação com o Princípio da Comprehensão Geral
• ZF4 e suas conseqüências
• ZF5 e suas conseqüências
• Definições de: Ø; {–}; {–,–}; ℘–
• Definições de: –∩–; –∪–; –\–; ℘–; ⋂–; ⋃–; –Δ–
• ZF6 e suas conseqüências
• Não podemos definir a operação ⋂Ø
• Teoria de conjuntos como uma “assembly” para a matemática de nível “alto”
• Representação fiel de matemática dentro da teoria de conjuntos
• Tuplas e produto cartesiano
• O operador de par ordenado de Kuratowski
• Tuplas na ZF
• União-disjunta na ZF
• Relações na ZF
• Funções na ZF

27/06/2018: Teoria de Conjuntos Axiomática

• Não podemos definir a operação ~ de complemento
• Classes e classes próprias
• O V é uma classe própria
• Grupos e conjuntos estruturados na ZF
• ZF7 e suas conseqüências
• A existência de quantos conjuntos infinitos é garantida pelos axiomas ZF1–ZF7?
• Conjunto-sucessor de Zermelo e de von Neumann
• O paradoxo de Russell virando teorema: para cada conjunto A, existe algum r(A) fora do A. Ainda mais, r(A) ⊆ A.
• Top-down definições
• Existência dos naturais

29/06/2018: Teoria de Conjuntos; Teoria de Ordem; Tópicos

• Teoria de Conjuntos Axiomática
  • Axiomas de Peano
  • Existência e unicidade dos naturais
  • Teorema de recursão
  • Funções parciais
  • Funções compatíveis e incompatíveis
  • Aproximações de função: bottom-up
• Teoria de Ordem
  • Posets
  • Exemplos
  • pointwise ordem de funções
  • Pointwise ordem: para todo ponto no domínio…
  • Exemplos de posets: informação, funções parciais
  • Elementos máximos, mínimos, maximais, minimais
  • A relação de «cobrir»
  • ↑x; ↓x
• Quantas funções consigo programar na minha linguagem de programação favorita?

02/07/2018: Prova 3.1

04/07/2018: E agora o que?

• Teoria axiomática de conjuntos
  • (Dedekind-)infinito na ZF
  • O axioma de escolha e conseqüências
• Teoria de ordem
  • order-preserving (monótona)
  • order-embedding
  • order-isomorfísmo
  • Up-set; down-set
  • Um toque de aritmética ordinal
• Computabilidade
  • Quantos programas diferentes existem?
  • Funções computáveis; números computáveis
  • Limitações de computação
  • The halting problem
  • Turing-complete vs. Pacman-complete

06/07/2018: Prova de reposição

Futuro (fluido)