2017.2 FMC2, turmas de Thanos

Prerequisitos

Prerequisito ter aprendido bem e profundamente o conteudo de FMC1. Sem mandar bem nesses assuntos, não faz sentido se matricular em FMC2. (Obs.: mandar bem ≠ passar.)

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

1. How to prove it, de Velleman (1, 2, 3, 6) [pode achar no LibGen—link na bibliografia]
2. Das minhas notas (em progresso) Matemática fundacional para computação, os capítulos:
   • Indução
   • Teoría elementar de números
   • Congrüências
   • Combinatória enumerativa
3. 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. Lógicas não-clássicas, elementos de lógica intuitionística e de lógica linear.

Bibliografia

Principal

(Conhece o libgen.io?)

• Eu: Matemática fundacional para computação (minhas notas em progresso)
• Pinter: A book of abstract algebra (2–5, 6, 12, 17)
• Moschovakis: Notes on set theory (1, 2, 3–5, 6–7)
• Goldrei: Classic set theory, for guided independent study (4, 7, 8)
• Davey & Priestley: Introduction to lattices and order (1, 2)

Auxiliar

• Velleman: How to prove it (1.3, 1.4, 2.3, 4, 5, 7)
• Paul Halmos: Linear Algebra Problem Book (1)
• Paul Halmos: Naïve set theory
• 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)

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.

Programação

• 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

Provas

Provinha 0

• Provinha 0 (pts: 0; bonus: 0) (dia: 26/07/2017)
  { uncensored, answers }
  correções: p1 (5M), p2 (3M), p3 (2M), p4 (3M), tudo (13M).

Unidade 1

• Prova 1.1 (pts: 28/100; bonus: 9) (dia: 18/08/2017)
  N = { censored, uncensored, answers }
• Prova 1.2 (pts: 72/100; bonus: 0) (dia: 13/09/2017)
  N = { censored, uncensored, answers }

Unidade 2

• Prova 2 (pts: 112/100; bonus: 0) (dia: 08/11/2017)
  T = { censored, uncensored, answers };
  N = { censored, uncensored, answers };

Unidade 3

• Prova 3 (pts: 128/100; bonus: 0) (dia: 08/12/2017)
  T&N = { censored, uncensored, answers };

Prova de recuperação

• Prova 4 (pts: ?/100; bonus: 0) (dia: 13/12/2017)
  T&N = { censored, uncensored, answers };

Pontos extra

Unidade 1

Unidade 2

Unidade 3

Homework

14/07/2017

1. Estude os itens nos prerequisitos: resolve os problemas nesses capítulos do Velleman e das minhas notas, e resolva as minhas provas de FMC1 2016.2 (e estude seus gabaritos).

31/07/2017

1. Estude, e resolva os exercícios e os exemplos do Velleman, cap.1.

04/08/2017

1. Estude, e resolve os exercícios e os exemplos do Velleman, §§2.1–2.2.

08/08/2017

1. Estude, e resolve os exercícios e os exemplos do Velleman, capítulos 1–3.
2. Resolva os problemas que postei no grupo.

14/08/2017

1. Estude as pp.1–3 de Moschovakis e resolva os problemas x1.1–x1.3.
2. Estude as §1.4 & §2.3 de Velleman, e resolva todos os seus exercícios, exemplos, e problemas.
3. Um teorema de igualdade de conjuntos:
   Suponha que A, B ≠ Ø.
   A×B = B×A ⇔ A = B.

23/08/2017

1. Brinque com esse programa (em Python) de ordem superior, e siga seus comentários. (O arquivo para acessar offline está no higher.py

28/08/2017

1. Moschovakis: Capítulo 1, com todos os problemas (x1.1–8).
2. Pinter: Capítulo 6, com os exercícios nos: A, B, C(1–3), D(1–5), F, G.
3. Experimente com as construções que viermos: o que tu pode concluir sobre as funções construidas sabendo propriedades dos seus componentes e vice-versa?

30/08/2017

1. Considerando funções no (A→B), qual seria o domínio e o codomínio da Graph?
2. Generalize a questão do plicker de |A|=3 e |B|=6 para |A|=m e |B|=n.
3. Seja A≠Ø. Quantas funções existem com tipo...:
   • A→A
   • A→Ø
   • Ø→A
   • Ø→Ø
4. Seja B o conjunto de pessoas que moram no Brasil; seja E o conjunto dos estados do Brasil.
   Considere s : B→E a função definida pela regra: s(b) = o estado onde b mora
   Considere g : E→B a função definida pela regra: g(x) = o governador do estado x
   Quais são os fixpoints da função (g∘s)?
   Qual seria um nome bom para a (g∘s), e qual seu "tipo" (dom/cod)?
5. Desenha um diagrama cuja comutatividade será equivalente com a afirmação sequinte: «o endomapa f no A é idempotente»
6. Mostre que não existe problema com a notação f^–1[–]

01/09/2017

1. Generalize a questão do plicker de |A|=3 para |A|=n.
2. Seja f:A→A. Considere as afirmações: (i) f é idempotente; (ii) f é uma involução. (i)⇒(ii)? (i)⇐(ii)?
3. Resolve os exercícios x17.1–4 das minhas notas

04/09/2017

1. Escreva claramente como definir uma partição dum conjunto A, dada uma relação de equivalência ~ no A, e vice versa. Prove tuas afirmações.
2. Prove em detalhe todas as tuas afirmações na questão do plicker do dia (04/09/2017).
3. Seja R uma relação binária num conjunto A. O.s.s.e.:
   (i) R é uma relação de equivalência (ii) R é reflexiva e circular (iii) R é reflexiva e triangular
4. Seja m natural. Prove que a relação binária nos inteiros definida pela
   a ~_m b sse a≡b (mod m)
   é uma relação de equivalência. Qual é a partição correspondente nos inteiros?
5. Seja f:X→Y e defina a relação binária no X pela x~x' sse f(x)=f(x'). Mostre que ~ é uma relação de equivalência e descreva as classes da correspondente partição. O que podemos concluir se f é injetora?
6. Estude o capítulo 12 de Pinter, e resolva todos os problemas nos A,B,C,E.
7. Resolva os exercícios e problemas das minhas notas.

06/09/2017

1. A operação ∘ tem identidade (elemento neutro)? Quantas/quais/qual? Prove!
2. Defina a exponenciação Rⁿ de uma relação R para cada n natural.

13/09/2017

1. Capitulo «Conjuntos» das minhas notas: estude bem e resolva todos os exercícios e problemas.
2. Capitulo «Funções» das minhas notas: estude bem e resolva todos os exercícios e problemas.
3. Capitulo «Relações» das minhas notas: estude bem e resolva todos os exercícios e problemas.
4. Brinque com programação lógica, seguindo os exemplos no SWI-Prolog online.
5. Brinque com programação funcional, seguindo o livro LYAH.

18/09/2017

1. Capitulo «Teoria de grupos», secção «Permutações» das minhas notas: estude bem e resolva todos os exercícios.
2. Para cada uma propriedade de operação que conhece, decida se o (S_n;∘) satisfaz a correspondente lei.
3. Resolva os problemas 1–12 do «Linear Algebra Problem Book» de Halmos.
4. Estude (e resolva todos os seus problemas) do capítulo 2 de Pinter.
5. Brinque com geometria euclideana, usando os Elementos e/ou o euclidea.xyz.

20/09/2017

1. Capitulo «Teoria de grupos», até secção «Exemplos» das minhas notas: estude bem e resolva todos os exercícios.
2. Resolva os problemas 13–15 do «Linear Algebra Problem Book» de Halmos.
3. Estude (e resolva todos os seus problemas) do capítulo 3 de Pinter.

22/09/2017 – 25/09/2017

1. Mostre porque o diagrama “comutativo” D que desenhei na aula não é comutativo!
2. Verifique que D não é equivalente à afirmação que as duas razoáveis interpretações do a^-2 são iguais, mostrando qual é a afirmação que corresponde à comutatividade do D mesmo.
3. Desenha o diagrama correto, cuja comutatividade corresponde a essa afirmação mesmo.
4. Prove os dois próximos lemata nas minhas notas (terceiro e quarto lema na secção de seqüências das leis).
5. Verifique os dois sentidos da equivalência: G abeliano ⇐?⇒ D é comutativo.
6. Tem como achar um grupo com ordem n para qualquer natural n?
7. Capitulo «Teoria de grupos», até secção «primeiras conseqüências» das minhas notas: estude bem e resolva todos os exercícios.
8. Estude (e resolva todos os seus problemas) do capítulo 4 de Pinter.

25/09/2017

1. Prove o lema da resolução de equações
2. Ache todas as tabelas de operações possíveis para formar um grupo com ordem 3 ou 4
3. Prove que realmente (a^-1)² = (a²)^-1
4. Generalize: (a^-1)ⁿ = (aⁿ)^-1, para qualquer natural n.
5. Desenha digramas cujas comutatividades correspondem na lêmata que provamos na aula: Lema 4, Lema 5

27/09/2017

1. Resolva todos os exercícios das secções «Tabelas Cayley» e «Potências e ordens» das minhas notas.
2. Estude (ou seja, resolva seus problemas) o capítulo 10 de Pinter.

29/09/2017

1. Estude bem (e resolva todos os exercícios) da secção «Potências e ordens» das minhas notas.
2. Estude bem (e resolva todos os exercícios) da secção «Subgrupos» das minhas notas.
3. Pinter, cap. 5: estude bem e resolva seus A, B, C, D.

04/10/2017

1. Pinter, cap. 5: prob E.
2. Estude bem (e resolva todos os exercícios) da secção «Ordens, geradores e grupos cíclicos» das minhas notas.
3. Pinter, cap. 10: com todos os problemas
4. Termine a questão do plicker
5. Generaliza o resultado de 2 subgrupos e sua intersecção para o caso arbitrario: Prova 2N-2017.1, prob: E2

13/10/2017 – 16/10/2017

1. Pinter, cap. 13: prob A, B, C, D, E
2. Secção «Congruências e cosets» das minhas notas: resolve todos os exercícios
3. Complete a prova do teorema: HK=KH sse HK≤G.

18/10/2017

1. N⊴G sse para todo g∊G, gN=Ng.

23/10/2017

1. Pinter, cap. 14: prob A, B, C, D, E, F, G

27/10/2017 – 03/11/2017

1. Pinter, cap. 14: prob A–D, F–M
2. Capítulo «Estruturas Algébricas» das minhas notas

01/11/2017 – 09/11/2017

1. Mostre como ganhar no jogo onde o conjunto de segredos é o conjunto de todos os strings (finitos) feitos pelo alfabeto ℕ.
2. Resolve o problema dos casamentos infinitos
3. Traduza tua solução para uma prova do teorema Schröder–Bernstein
4. Prove que A<_c℘A
5. Moschovakis, cap. 2: todos os exercícios e todos os problemas

14/11/2017

1. Goldrei, cap. 6, com todos os exercícios e exemplos

17/11/2017

1. Minhas notas, capítulo «Teoria axiomática de conjuntos», todos os exercícios até o ZF5.

17/11/2017

1. Minhas notas, capítulo «Teoria axiomática de conjuntos», todos os exercícios até o ZF6.
2. Goldrei, capítulo 4: até o axioma 6

24/11/2017

1. Minhas notas, capítulo «Teoria axiomática de conjuntos», todos os exercícios até o ZF7.
2. Goldrei, capítulo 4: até o axioma 7
3. Defina formalmente as operações de funções (composição, produto, restrição, etc.) e de relações (composição, fechos, etc.)

28/11/2017

1. Minhas notas, capítulo «Recursão», estude a secção «o conjunto dos números naturais formalmente» e resolva os problemas do capítulo
2. Minhas notas, capítulo «Teoria axiomática de conjuntos», resolve todos os problemas do «Intervalo de problemas» e todos os exer ícios das secções «construindo as funções» e «construindo os números naturais»
3. Defina recursivamente as funções de adição, multiplicação, explinenciação, e prove por indução que satisfazem as propriedades e leis comuns.

01/12/2017

1. Exercícios de Davey&Priestley: 1.1, 1.3, 1.4
2. Prove todas as afirmações que deixamos sem prova na aula: verifique que as ordens que definimos são realmente ordens; prove as propriedades de maximais/suprema/máxima/etc.
3. Qual é o sup e qual o inf de um subconjunto de naturais ordenados por a relação de |?
4. Tome dois objetos fora do ℝ, chamados -∞ e ∞, e define o conjunto R = ℝ∪{-∞,∞}. No R estenda a ordem usual de ℝ botando: -∞ ≤ x ≤ ∞ para todo real x. No poset R, quais são os infℝ e supℝ? Prove ou refute: Para todo subconjunto A de R, infA ≤ supA.
5. Estude as 3as provas de 2017.1 e seus gabaritos

04/12/2017

1. No produto cartesiano P×Q, defina formalmente duas ordens: a pointwise; a lexicográfica
2. Definam formalmente os conceitos duais «down-set» e «up-set»

Histórico de aulas

24/07/2017: Apresentação

• Apresentação dos assuntos principais
• Definições e afirmações: erros comuns
• Variáveis livres e ligadas
• Funções e predicados/relações; aridade; aplicação parcial

26/07/2017: Provinha 0

28/07/2017: Revisão & Linguagens

• Revisão
  • Resolução da Provinha 0
  • Erros comuns na escrita
  • Formas de escrever matemática
  • Indução
  • Provas como jogos
• Linguagens
  • Uma linguagem para expressões aritméticas
  • Parsing: de forma linear para arvore sintática
  • A notação BNF

31/07/2017: Linguagens; Lógica

• Linguágens
  • Resolução do homework
  • «meta-»: metalinguagem, metavariáveis, etc.
  • Abreviações
• Lógica
  • A linguagem L₀ da lógica proposicional (sentencial)
  • Os conectivos ¬, ∨, ∧, →, ↔ e sua semântica
  • Uma gramática em BNF para a L₀ (wffs)
  • Traduções de português e de português matemático para lógica proposicional e vice versa
  • Afirmações/proposições/fórmulas atómicas e não-atómicas

02/08/2017: Lógica

• Conectivos binários da lógica proposicional
• Tabelas de verdade
• Açúcar sintáctico
• Limitações da linguagem L₀
• Termos da L₁
• Definição recursiva do conjunto de termos
• Traduções de português e de português matemático para lógica proposicional e vice versa

04/08/2017: Lógica

• Fórmulas (wffs) da FOL (L₁)
• Termos vs. fórmulas
• Definição recursiva do conjunto de fórmulas
• Gramática BNF para fórmulas
• Abreviações e açúcar sintáctico
  • (∀x∈A) P(x)
  • (∃x∈A) P(x)
  • ∃!x P(x)
  • (∃!x∈ A) P(x)
• Árvores de derivação
• Traduções de português e de português matemático para lógica de primeira ordem e vice versa

07/08/2017: Lógica; Recursão; Conjuntos

• Lógica
  • Leis de equivalências lógicas
  • “Enterrando” todas as negações em frente de fórmulas atômicas
  • Estrategias de prova
    • Provas como jogo de cartas
    • Provas diretas
• Recursão estrutural em conjuntos definidos indutivamente/recursivamente
• Conjuntos
  • Tipos
  • Conceito e notação
  • Noções primitivas: ser conjunto, pertencer (∈)
  • Homogeneidade e heterogeneidade de conjuntos
  • Set comprehension (Set-builder notation)
  • Intensão vs extensão
  • Igualdade entre conjuntos: A = B

09/08/2017: Conjuntos

• Noções primitivas: ser conjunto, pertencer (∈)
• Conjuntos como “black boxes”
• Relações entre conjuntos e como as definir
• As relações binárias: =, ⊆, ⊇, ⊊, ⊋
• Mais convenções de açúcar sintáctico
• Os predicados Singleton(–) e Empty(–)
• Obrigação de definir notação (nome) para objeto: artigo definido vs. indefinido
• Teorema: unicidade do conjunto vazio
• O conjunto vazio Ø: definição e suas propriedades
• 7 teoremas sobre ∈, ⊆, Ø, e um conjunto arbitrario A
• Como usar um fato do tipo D≠Ø em nossas provas: «Seja d∈D.»

11/08/2017: Lógica; Conjuntos

• Lógica
  • Conjuntos completos de conectivos
  • Prova por indução na L₀ (indução na «complexidade» da fórmula)
• Conjuntos
  • Falta de ordem e de multiplicidade
  • Conjuntos, seqüências, multisets
  • Operações entre conjuntos e dois jeitos de as definir
  • As operações binárias: ∩, ∪, \
  • A operação unária de complemento: ^~
  • Mais um jeito de definir operações: usando outras já-definidas!
  • Diferença simétrica (△)
  • Generalizando as operações de união e intersecção: as operações unárias ⋂, ⋃

14/08/2017: Tuplas; Conjuntos

• Wason's selection task
• Conjuntos disjuntos
• ⋂ e ⋃ com subscripts (mais notações)
• Os operadores binários ∪ e ∩ como açucar sintático (definido pelos operadores unários ⋃ e ⋂ respeitivamente).
• 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
• tuplas como noções primitivas: igualdade, tamanho
• tuplas como black boxes
• projeções: π_i
• Produto cartesiano (×)
• Aⁿ para n≥2: definição “direta” e recursiva

16/08/2017: Conjuntos; Análise

• Conjuntos
  • Cardinalidade de conjuntos finitos e propriedades
  • Powerset (℘)
  • Iterando os ⋂, ⋃, e ℘ no Ø
  • Intervalos de reais, suas intersecções e uniões arbitrárias
• 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

18/08/2017: Conjuntos; Funções; Prova 1.1

• Conjuntos
  • Intuição sobre os ⋂, ⋃, e ℘ e as {, }
  • Conjuntos disjuntos dois-a-dois («pairwise disjoint»): definição com e sem índices
• Funções
  • Conceito e notação
  • Funções como black boxes
  • Domínio e codomínio
  • Intensão vs extensão
  • Igualdade: f = g
• Prova 1.1

21/08/2017: Sermão; Funções

• Sermão
  • Resolução da prova
  • Erros comuns
  • Type errors
  • Mistura de fórmulas de lógica com a metalinguágem (português)
  • Hand-waving
• Funções
  • 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)
  • Diagramas internos
  • Como definir funções e notação relevante
  • A notação de λ-calculus
  • Composição
  • O lei da associatividade da composição: h∘(g∘f) = (h∘g)∘f; prova e intuição
  • Aplicação parcial como black box

23/08/2017: Funções

• Diagramas internos e externos
• tipo de função
• Como definir funções e notação relevante
• A notação de λ-calculus
• Como não definir funções: erros comuns
• Diagramas comutativos: como expressar os dois leis da composição
• Identidade, constante
• As leis das identidades e suas provas
• Aplicação parcial e «buracos»: com –, •, etc.; com lambdas (λ)
• Composição como operação associativa
• Similaridades (e diferençás) com multiplicação de números
• Função identidade de A
• Identidade esquerda; identidade direita de operação binária
• Higher-order functions (funções de ordem superior)
• A → (B → C) vs. (A → B) → C
• O espaço de funções de A para B: (A→B)
• endomapeamento: f:A→A
• função idempotente: f∘f = f
• Iterações de algum endomapeamento f:A→A

25/08/2017: Funções

• função caraterística
• projeções
• produto cartesiano de funções
• Funções de ordem superior
• Resolução de homework (versão final
• Função epônima (com nome); função anônima (usando λ)
• Ligantes de variáveis:
  • ∃x_ ; ∀x_
  • ∫_dx ; D_x_
  • Σ_i_ ; Π_i_
  • ⋃_j_ ; ⋂_j_
  • { _ | P(x) } ; { x∈A | _ }
  • λx._
• Aplicação parcial
• Type-Variáveis nos típos de funções
• Currying (currificação)

28/08/2017: Funções

• Currying (currificação)
• λa.λb.a^b vs. λb.λa.a^b
• Cardinalidades entre finitos A,B,C, e os conjuntos ((A×B)→C) e (A→(B→C))
• Currificação e multiplicação/exponenciação de inteiros
• Operações “pointwise”
• Injetora, Sobrejetora, Bijetora
• Função inversa
• Imagem e preimagem de função
• Notação e intuição sobre funções injetoras, sobrejetoras, e bijetoras
• Como construir possíveis contraexemplos
• Usando propriedades da g∘f para deduzir propriedades das f e g

30/08/2017: Funções; Tuplas

• Unit type e os tipos void e int da C, como (co)domínios de funções matemáticas
• Aⁿ revisitado
• Gráfico de função graph(f): definição
• função vazia: «a» ou «uma»?
• função de aridade 0: «a» ou «uma»?
• |(A↣B)| = ?; |(A→B)| = ?
• Possível problema na notação da função inversa / pre-imagem
• λx.f(x) = ?

01/09/2017: Funções; Relações

• Funções
  • Endomapas: f:A→A
    • Involução: f = f^–1
    • Idempotência: f∘f=f
  • Quantas funções idempotentes num conjunto de cardinalidade 3?
• 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

04/09/2017: Relações

• Exemplos de fórmulas bem formadas, e «mal-tipadas» (ill-typed)
• Definindo relações: usando outras relações e funções
• Propriedades de relações binárias num conjunto A
  • circular; right-euclidean; left-euclidean
  • total; tricótoma
• Relações de equivalência; classes de equivalência
• Partições de conjunto
• Seja ε real com 0<ε<1. Definimos nos reais a relação ~ com: x~y sse (x–y)²<ε.
  Ela é simétrica? Reflexiva? Transitiva?
• Relações de equivalência, classes de equivalência, conjunto quociente: exemplos no ℝ² e no conjunto P de pessoas

06/09/2017: Relações

• Relações como grafos direcionados (diagrama interno de relação)
• Propriedades de relações e suas interpretações nos diagramas
• Construindo relações
• Fechos (reflexivo, simétrico, transitivo, circular, etc.)
• Fechos como operadores
• Composição entre relações (e entre funções)
• Composição como operador
• Definições formais e completas de fechos, composição, etc.
• A ordem de aplicação de fechos (transitivo, reflexivo, simétrico, etc.) numa relação, importa?

08/09/2017: Relações

• Relações como generalização de função
• Definindo formalmente o fecho transitivo e o fecho reflexivo-transitivo
• Exponenciação de relações: Rⁿ
• Comparação com funções
• Relações recursivamente definidas
• Recursão mutual: Even/Odd
• Duas relações no conjunto de seqüências infinitas de naturais (ℕ→ℕ): são relações de equivalência?
• Jogos de lógica com jogadores ∀ e ∃

11/09/2017: Relações

• Relações
  • Relações de ordem
  • Revisão: provas sobre relações
  • R∘T = T?; R∘F = F?
• Aplicações
  • Bancos de dados

13/09/2017: Prova 1.2

15/09/2017: Relações; Programação declarative

• Resolução da Prova 1.2
• Sermão & revisão
• Linguagens de programação
  • Paradigmas: imperativos vs declarativos
• Programação Funcional
  • Haskell
• Programação Lógica
  • Emulando funções por relações
  • Prolog
  • SWI-Prolog online

18/09/2017: História; Álgebra abstrata

• História: de Euclides (300 BC) para Galois (1830)
  • Geometria euclideana 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 & Abel e suas ideias
  • Wantzel (provas de impossibilidade de resolver)
  • Independência de axiomas
• Álgebra abstrata
  • Conjuntos estruturados: carrier set + estrutura; assinatura
  • Estruturas feita por: constantes; funções; relações
  • Operações e propriedades
  • Duas operações binárias nos reais: são associativas?
  • S_n
  • Notações para representar elementos de S_n: completa e com cíclos

20/09/2017: Teoria de grupos

• Abusos notacionais
• S₃, sua estrutura, e seus elementos
• Leis abstratas satisfeitas por S₃
• Grupo, e as leis (G0)–(G3) de grupos
• Grupos abelianos (lei (G4))
• Os strings dum alfabeto Σ formam um grupo com concatenação?
• Umas definições equivalentes de grupo, com outros tipos de estrutura

22/09/2017: Teoria de grupos

• Grupos aditivos e grupos multiplicativos
• Exemplos de grupos
• Dois conjuntos estruturas compartilhando o mesmo carrier set. São grupos?
• Teaser: grupos isomórficos
• Ordem de grupo
• Os grupos simétricos S_n
• Definição de a^m para qualquer inteiro m
• Diagramas comutativos; produto cartesiano de funções
• Lema 1: Unicidade da identidade
• Lema 2: Unicidade dos inversos
• Lema 3: Leis de cancelação (GCL) & (GCR)

25/09/2017: Teoria de grupos

• Por que o diagrama D da aula 22/09 não foi nem o correto, nem comutativo
• (ab)² = ?
• Motivação: inverso do inverso
• Lema 4: Inverso do inverso
• Lema 5: Inverso de produto
• Erros/problemas comuns em provas: direção oposta, roubando ou restringindo com exemplos específicos
• Desafio: seja n natural. Podes achar grupo com ordem n?
• Tabelas de operações
• Lema 6: Resolução de equações

27/09/2017: Teoria de grupos

• Exemplos de grupos
• Tabelas Cayley e suas regras
• Ordem de membro de grupo
• Quantas ordens diferentes aparecem nos membros de S₃?
• Lema: existem exatamente o(a) potências distintas de a

29/09/2017: Teoria de grupos

• Ordens e propriedades
• Membros com ordem finitas e infinitas
• Subgrupos: definição e exemplos
• Critérion 1: basta provar que H é fechado pela operação e pelos inversos
• Critérion 2: se H finito, basta provar que é fechado pela operação
• ℘A é grupo com qual das operações binárias conhecidas de conjuntos?

02/10/2017: Teoria de grupos

• Os dois critéria de ser subrgrupo
• Subgrupo gerado por a∊G
• Exemplos de subgrupos gerados por membros de vários grupos: ℝ, ℤ, S₃, etc.
• Subgrupo gerado por A⊆G
• Exemplos de subgrupos gerados por subconjuntos de ℤ

04/10/2017: Teoria de grupos

• Interseção de subgrupos é subgrupo
• A união não comporta tão bem!
• Geradores de (sub)grupos <a> & <W> e suas definições alternativas
• Definições top-down & bottom-up
• Grupos cíclicos: exemplos e nãœxemplos
• Seja H≤G. Seja R a relação no G definida pela: aRb sse ab^-1. R é uma relação de equivalência.

09/10/2017: Teoria de grupos

• Exercícios (aula de monitoria)

11/10/2017: Teoria de grupos

• Geradores de grupo: revisão
• A relação do plicker anterior é uma relação de equivalência
• a ≡ b (mod H)
• justificação da notação
• Exemplos nos inteiros
• a ≡ b (mod H)? Como responder em 3 casos.
• left/right cosets (coclasses laterais)
• Se a∊H então aH=H=Ha
• Exemplos de cosets nos inteiros
• G abeliano ⇐?⇒ para todo a,b∊G, (ab)^–1 = a^–1 b^–1

13/10/2017: Teoria de grupos

• A relação de congruência módulo um subgrupo H
• Partição e coclasses
• Por que à direita? E as coclasses esquerdas?
• O teorema de Lagrange: esboço de prova
• 3 corolários de Lagrange
• Dois subgrupos de S₃. HK≤G? KH≤G?

16/10/2017: Teoria de grupos

• Revisão: congruência e coclasses; Lagrange e corolários
• Grupos multiplicativos de inteiros
• Teorema de Euler como corolário de Lagrange
• HK = KH sse HK≤G
• São todas as coclasses direitas, coclasses esquerdas?

18/10/2017: Teoria de grupos

• Indice de subgrupo
• Coclasses-L = Coclasses-R?
• Conjugados de n∈N
• «ser conjugado de» é uma relação de equivalência
• Subgrupos normais
• Três definições equivalentes
• O grupo quociente G/N
• HH=H

20/10/2017: Teoria de grupos

• Revisão: Grupos, subgrupos, coclasses, subgrupos normais, grupo quociente
• Simetrias
• O grupo dihedral D₃
• (Homo)morfismos
• Monomorfismos
• Epimorfismos
• Isomorfismos
• Endomorfismos
• Automorfismos
• Preservar a operação do grupo garanta preservação da identidade e dos inversos
• φ : G → G/N com φ(x) = Nx é um epimorfismo

23/10/2017: Teoria de grupos

• Revisão: homomorfismos
• ≅ é uma relação de equivalência
• Kernel de homomorfismo
• kerφ ≤ G
• kerφ ⊴ G

25/10/2017: Teoria de grupos

• Kernel e Imagem de morfismos
• φ mono sse kerφ={e}
• O primeiro teorema de isomorfimos de grupos
• Revisão: morfismos e subgrupos normais
• Os D₃, D₄ e o diagrama dos seus subgrupos
• Morfismos entre conjuntos estruturados

27/10/2017: Outras estruturas

• Monóides
• Homomorfísmos entre monóides
• Aneis (Rings)
• Primeiras consequências das leis de anel
• Subaneis (subrings)
• Homomorfísmos de aneis

30/10/2017

• Resolução das provas de 2017.1

01/11/2017: O paraiso de Cantor

• 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
• O que significa contar?
• Como podemos comparar o tamanho de dois conjuntos finitos?
• Como podemos comparar o tamanho de dois conjuntos infinitos?
• |ℕ| = |ℤ|
• Estrategias para garantir vitoria no jogo de imortais «adivinhe o s que eu estou pensando» se…:
  • s∈ℕ
  • s∈ℤ
• Jogo de imortais com conjuntos «aparentemente» maiores—so que não:
  • ℕ²; ℤ²; ℕ^k;
  • ℘_fℕ; ℘_f℘_fℕ;
  • A^*;
  • ℚ
  • ℕ^*;
• Stratificação dos palpites
• Bijeções como outros nomes dos elementos dum conjunto
• O primeiro argumento diagonal de Cantor
• Um conjunto incontável: [0,1]
• O segundo argumento diagonal de Cantor
• 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
• A relação ≤_c parece ser relação de ordem.. parcial? total?
• Casamentos infinitos: a questão

03/11/2017: Equinumerosidade

• Recap: todos os conjuntos que temos encontrado e classificado até agora entre contáveis e incontáveis
• Conjuntos densos: ℚ vs. ℕ
• Mais conjuntos-segredos para o jogo:
  • ⋃{ C_n | n∈ℕ }
• O que significa cardinalidade de um conjunto A?
• A dupla abstração: a notação de cardinalidade A de Cantor
• Duas definições equivalentes de A≤_cB
• Uma definição errada de A<_cB
• Representação dos números reais no [0,1] em forma 0,... para varias bases: interpretação geometrica na linha como instruções
• O Cantor set e a prova que é incontável
• Procurando bijeções entre intervalos de reais
• O teorema Schröder–Bernstein e suas aplicações
• Provas de equinumerosidade com e sem o teorema Schröder–Bernstein
• Casamentos infinitos: uma dica

08/11/2017: Prova 2

10/11/2017: Equinumerosidade

• O powerset respeita a equinumerosidade
• Quais operações “respeitam” as cardinalidades?
• Um teorema de Cantor: A<_c℘A
• Uma infinidade contável de «infinidades diferentes»:
  ℕ <_c ℘ℕ <_c ℘℘ℕ <_c ℘℘℘ℕ <_c …
• Tem algum conjunto «maior»?
• Seja A conjunto não vazio e f:A→℘A a função definida pela f(x)={x}. Prove que f não é sobrejetora.
• Mais conjuntos-segredos para o jogo:
  • ℤ[x]; ℚ[x];
• Números racionais e irracionais
• O conjunto dos racionais é contável
• O conjunto dos irracionais é incontável
• Números algébricos e transcendentais
• Definições equivalentes; definições erradas
• O conjunto dos algébricos é contável
• O conjunto dos transcendentais é incontável
• Kleene star

13/11/2017: Equinumerosidade & aplicações

• Os cardinais: ℵ₀ (aleph 0), 𝖈 (continuum)
• As perguntas grantes: Principle of Cardinal Comparability, Continuum Hypothesis, Generalized Continuum Hypothesis
• Recap: o teorema de Cantor e suas conseqüências
• Não existe cardinalidade máxima
• Codificações em números
• Entre dois reais existe racional
• A frase «tende ao…»
• Aplicação: teoria de medida
  • teoria de medida: Borel, Lebesgue, Baire
  • Generalização de comprimento, probabilidadem e integração
  • Por que a probabilidade de escolher x racional, escolhendo entre o [0,1] é 0?
  • Probabilidade de escolher transcendental nos reais em [0,1]

17/11/2017: Equinumerosidade & aplicações; problems in Paradise: Cantor, Frege, Russell, Zermelo

• Uma carta de Cantor para Dedekind
• A resposta de Dedekind
• Aplicação: Computabilidade
  • Quantos programas diferentes existem?
  • Funções computáveis; números computáveis
  • Reais definíveis
  • O paradoxo de Berry
  • Limitações de computação
  • The halting problem
• 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
• Axiomas vs. leis
• 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.
• 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: Ø; {–}; {–,–}; ℘–

20/11/2017: ZF

• Traduções de FOL para português e vice-versa
• Definições de: Ø; {–}; {–,–}; –∩–; –∪–; –\–; ℘–; ⋂–; ⋃–; –Δ–
• ZF6 e suas conseqüências
• O paradoxo de Russell virando teorema: para cada conjunto A, existe algum r(A) fora do A. Ainda mais, r(A) ⊆ A.
• Classes e classes próprias
• O V é uma classe própria
• Não podemos definir a operação ⋂Ø
• Não podemos definir a operação ~ de complemento
• 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

24/11/2017: ZF

• União-disjunta na ZF
• Relações na ZF
• Funções na ZF
• Grupos e conjuntos estruturados na ZF
• Números cardinais e sua aritmética
• 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
• Axiomas de Peano
• Top-down definições

27/11/2017: ZF

• 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
• Quantos axiomas até agora?

29/11/2017: ZF; teoria de ordem

• ZF
  • (Dedekind-)infinito na ZF
  • Construindo os inteiros
  • Construindo os racionais
  • Construindo os reais
• Teoria de ordem
  • Posets
  • Exemplos e não-exemplos
  • pointwise ordem de funções

01/12/2017: Posets & Reticulados

• Bottom e top
• Pointwise ordem: para todo ponto no domínio…
• Não-exemplo de poset: existe ponto no domínio tal que…
• Exemplos de posets: strings, informação, funções parciais
• Elementos máximos, mínimos, maximais, minimais
• Unicidade de máximo/mínimo
• Diagramas Hasse
• A relação de «cobrir»
• inf e sup nos reais
• Axiomatização dos reais
• sup/inf, lub/glb, join/meet
• Reticulados

04/12/2017

• Joins e meets
• sup de racionais nos reais
• Construindo ordens
• Ordem discreta
• P_⊥
• P⊎Q
• P⊕Q
• P×Q com pointwise e (anti)lexicográfica ordem
• P^∂
• O princípio da dualidade
• order-preserving (monótona)
• order-embedding
• order-isomorfísmo
• Up-set; down-set
• ↑x; ↓x

06/12/2017: Reticulados algébricos, booleanos, completos

• Reticulados algébricos
• Reticulados completos
• Reticulados algebricamente
• Reticulados completos
• Fixpoints
• o teorema fixpoint de Knaster–Tarski
• Um toque de aritmética ordinal
• Resolução da Prova 3 de 2016.1

08/12/2017: Prova 3

13/12/2017: Prova 4

Futuro (fluido)