2022.2 FMC2, Unidade 3, da turma de João Marcos (⅔) & Thanos (⅓)

Horários de aula: 246T56 [16h50–18h30]
Contato:thanos@imd.ufrn.br
Playlists: FMC2 2019.1 (aulas gravadas)
FMC2 2018.2 (aulas gravadas)
Pré-requisitos para SetFunRel/FMC2
Monitoria/TA: fmc.imd.ufrn.br
Turmas anteriores: ..

Info

Pré-requisitos

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

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

(Obs.: aprenderpassar.)

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

Além disso, é necessário que os alunos matriculados têm tempo e vontade para estudar, fazer os (muitos) trabalhos atribuídos, etc.

(Obs.: estudarler.)

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

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

Conteúdo

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

Esta página refere à Unidade 3 (lecionada por Thanos).

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

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

Objetivos de aprendizagem

IEA: Introdução a Estruturas Algébricas

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

Bibliografia e referências

Conhece o libgen?

Principal

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

IEA: Introdução a Estruturas Algébricas

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

Auxiliar

  • Goldblatt (1979): Topoi
  • Crole (1993): Categories for Types (Cap: 1,2,3)
  • Lawvere & Schanuel (2009): Conceptual Mathematics, 2nd ed.

Dicas

Links

Tecnologias e ferramentas

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

  1. PAPEL (um caderno para dedicar à disciplina) e LAPIS/CANETA.
  2. Zulip (leia o FAQ).
  3. Pouco de (La)TeX (veja o minicurso TeX 2018.2). Online editor/compilador: Overleaf.

Regras

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

Uns deveres dos alunos

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

(Veja também os FAQs relevantes.)

Sobre plágio

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

Cadernos vs. celulares

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

Avaliação e faltas

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

Avaliação

A nota final de cada aluno vai ser principalmente baseada em um ou mais dos: (i) provas escritas; (ii) sua participação; (iii) trabalhos atribuidos; (iv) hw resolvidos (veja o FAQ relevante).

Cada aluno será responsável para manter organizado e bem escrito o seu caderno com todos os teoremas e exercícios que estudou durante a disciplina.

Presenças e faltas

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

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

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

Atrasados

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

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

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

FAQs

Dynamic content

Pontos de participação

Provas

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

U3 (IEA)

Homework (HW)

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

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

2022-11-08

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

2022-11-10

  1. Até a §«Tabelas Cayley».

2022-11-11

  1. Resolva os seguintes antes de estudar a §«Potências e ordens».
    1. Suponha que $o(a) = n$ para algum $n \in \mathbb{N}$ Demonstre que existem exatamente $n$ potências distintas de $a$
    2. Suponha que $o(a) = \infty$. Refute ou demonstre: todas as potências de $a$ são distintas dois a dois.
    3. Suponha que $a^k = e$ para algum inteiro $k$. O que podemos inferir sobre os $o(a)$ e $k$?
  2. Até o primeiro intervalo de problemas.

2022-11-17

  1. Capítulo «Teoria dos grupos»: resolva tudo até a §«Subgrupos».

2022-11-19

  1. Capítulo «Funções»:
    1. §«Funções de graça»
    2. §«Diagramas comutativos»
    3. §«Produtos e demais construções»
    4. §«Definições estilo point-free»
    5. §«Coproduto; união disjunta»
    6. Problemas: Π9.5; Π9.6
  2. Capítulo «Teoria dos grupos»
    1. §«Conjugação de grupo»
    2. Π11.9; Π11.10; Π11.11; Π11.14; Π11.15

2022-11-24

  1. Até o §«Teorema de Lagrange»
  2. Π11.16; Π11.17; Π11.18; Π11.19
  3. Desafio: ache um conjunto C ⊆ ℝ² tal que o processo bottom-up para encontrar «o melhor convexo gerado por C» demora! (Na aula o mais “lento” que conseguimos foi chegar no melhor na versão 2 (começando com versão 0 sendo o próprio C).

2022-11-26

  1. Até o §«Subgrupos normais»
  2. Π11.16; Π11.17; Π11.20; Π11.21

2022-11-28

  1. Até o §«Simetrias»

2022-12-01

  1. Θ. (Critério de homomorfismo de grupos) Sejam A,B grupos e φ : A → B tal que φ respeita a operação. Demonstre que φ é um homomorfismo.
  2. Desenhe o diagrama Hasse do poset dos subgrupos de 𝒟₄
  3. Estabeleça que 𝒟₄ é isomorfo àlgum subgrupo de S₄.
  4. Até o §«Morfismos».

2022-12-03

  1. Até o §«Kernel, Image».
  2. (Re)demonstre sozinho tudo que foi demonstrado na aula
  3. Demonstre ou refute: para quaisquer H,G com H ⊆ G: $$H \leq G \iff \text{$\iota : H ↪ G$ é homo}$$
  4. Demonstre/refute que no mundo dos grupinhos: mono ⇔ homo & inj epi ⇔ homo & sobre iso ⇔ homo & bij
  5. Resolva os problemas no fim do capítulo

2022-12-13

  1. Capítulo «Estruturas algébricas» até §«Corpos»
    • Exercícios destacados: 11.15, x11.11, x11.12, x11.13, x11.14, Λ11.32, 11.40, 11.46
  2. Verifique que todos os exemplos que encontramos na aula são categorias mesmo.
  3. Responde para cada uma delas nas pergunas:
    • possui iniciais?
    • possui terminais?

2022-12-14

  1. Responde para cada categoria que conhecemos nas perguntas: possui (co)produtos?
  2. Demonstre que iniciais e terminais são únicos (lembre o que unicos significa aqui)
  3. Ache categoria sem iniciais; sem terminais; sem nem iniciais nem terminais
  4. Ache uma cat e uma flecha f nela, tal que: f mono, f epi, mas não f iso
  5. Demonstre: f, g mono ⇒ gf mono
  6. Demonstre: gf mono ⇒ ??
  7. Dualize o que foi cobrado nas duas questões anteriores sobre flechas mônicas, para épicas
  8. Sejam C,D cats. Como definirias uma categoria que mereceria o nome C×D? Verifique o que precisa ser verificado.
  9. A categoria Set×Set possui iniciais? Terminais?
  10. Seja C uma cat. Como definirias uma categoria Arr(C), cujos objetos serão as flechas da C. Quais seriam as flechas da Arr(C)? Verifique o que precisa ser verificado.
  11. Demonstre a unicidade dos produtos e dos coprodutos.
  12. Seja Poset a cat dos posets com as funções monotonas. Verifique se possui iniciais, terminais, produtos, coprodutos.
  13. Seja C uma cat com produtos. Mostre como definir a flecha f×g.
  14. Dualize a idéia para definir uma flecha f⨿g.
  15. Denotamos a flecha garantida pelo produto por ⟨f,g⟩ e a garantida pelo coproduto por [f,g]. (Ambas foram “azuis” na aula.) Demonstre:
    1. ⟨fh, gh⟩ = ⟨f,g⟩ h
    2. (f×h) ⟨g,k⟩ = ⟨fg, hk⟩
    3. (f×h) (g×k) = (fg) × (hk)
  16. Ache uma categoria C e dois objetos dela sem produtos.
  17. A categoria que encontramos de tipos de uma linguagem de programação com programas possui produtos? Coprodutos? iniciais/terminais? Quais dessas respostas dependem em forma essencial da linguagem escolhida?

2022-12-15

  1. Enuncie e demonstre um teorema fundamental de homomorfismos para aneis.
  2. Enuncie e demonstre o que precisa para justificar o «reticulados e lattices: dois lados da mesma moeda»
  3. Pratique com os exercícios dos primeiros 4 capítulos do [Halmos-Givant].

Histórico

2022-11-07: Grupos

  • introdução
    • dois exemplos de problemas abertos
      • trisetar um ângulo
      • achar uma “bhaskara” para o 5o grau
    • enter Galois, Abel
  • as permutações de 3 objetos
    • notação
    • operação
    • propriedades
  • a idéia da álgebra abstrata
  • Definição de Grupo
    • tentativas com assinaturas diferentes
    • nossa definição oficial

2022-11-09: Grupos

  • convenções sintácticas: grupo aditivo vs grupo multiplicativo
  • carrier set e 𝒢 vs G
  • definindo potências dentro dum grupo G
  • monoid, semigroup, magma
  • especificação (e axiomas) vs implementações (e modelos):
    • maior/menor especificação traz maior/menor teoria (quantidade e teoremas) mas menos/mais modelos
  • grupos da aritmética modular: aditivo e multiplicativo
  • nossos primeiros teoremas da teoria dos grupos:
    • (id-uni), (inv-uni)
    • (canL), (canR)
    • (resL), (resR), (id-barata), (inv-barata)
    • (inv-id), (inv-inv), (inv-op)
  • tabelas Cayley e o “groupoku”

2022-11-11: Grupos

  • igualdade não é exatamente simétrica
  • maneiras de ler/enxergar umas igualdades algébricas e como extrair demonstrações diferentes a partir disso
  • equivalência entre duas definições sensatas para o g⁻¹: enunciado
  • Como escrever demonstrações
    • Cancelamento
  • Como justificar o «operando nos dois lados pela esquerda com _»
  • Ordem de Grupo
  • Ordem de membro de Grupo
  • Esboços de:
    • Θa. se o(a) < ∞, então a possui exatamente o(a) potências distintas
    • Θb. se a(a) = ∞, então todas as potências de a são distintas

2022-11-16: Grupos; Subgrupos

  • Exemplos de grupos:
    • Grupos cíclicos
    • (ℝ→ℝ) com (+) pointwise
    • ℘A com ?
  • 4 teoremas sobre a ordem
  • Produto direto de grupos
  • Grupo oposto
  • Subgrupos: op-fechado, inv-fechado, id-fechado
    • associatividade gratúita
  • Interseção de subgrupos é subgrupo
  • União de subgrupos não é garantidamente subgrupo

2022-11-18: Diagramas comutativos; Subgrupos

  • Diagramas comutativos
  • Expressando umas proposições de grupos usando diagramas comutativos
  • Critéria para subgrupos
  • Uma relação de equivalência garantida a partir de H ≤ G

2022-11-23: Subgrupos e o grupo quociente

  • subgrupo gerado por a ∈ G
  • fecho convexo (convex hull) de subconjunto de ℝ²
    • top-down e bottom up
  • investigação da relação $R_H$
  • Teorema de Lagrange

2022-11-25: Subgrupos e o grupo quociente

  • subgrupo gerado por A ⊆ G: top-down e bottom-up
  • Corolários de Lagrange
  • coclasses esquerdas e direitas
  • subgrupos normais
  • o grupo quociente G / N

2022-11-28: Subgrupos normais; Simetrias; Isomorfismos

  • 6 proposições equivalentes dois a dois
  • como solicitar membro arbitrário dum conjunto indexado
  • Isometrias
  • Simetrias dum triangulo equilátero
  • O conjunto das simetrias pode ser promovido para Grupo
  • A idéia de isomorfismo

2022-11-30: Homomorfismos e isomorfismos

  • Recap sobre subgrupos normais e o grupo quociente
  • Definição de homomorfismo
  • Definição de isomorfismo
  • O grupo 𝒟₃ e o diagrama Hasse dos seus subgrupos
  • O grupo 𝒟₄ e o diagrama Hasse dos seus subgrupos
  • Mais diagramas comutativos

2022-12-03: Homomorfismos e isomorfismos

  • prefixos para -morfismo
  • equivalências no mundinho dos grupos
  • Kernel, imagem de homomorfismo
  • Uma definição legal de subgrupo
  • o teorema fundamental de homomorfismo para grupos, dos teoremas de isomorfismo da Noether

2022-12-07: Prova 3.1; Outras estruturas

  • Monóides, semigrupos, grupos abelianos
  • Critério de homomorfismos para monóides

2022-12-12: Outras estruturas; Categorias

  • Aneis, Domínios de Integridade, Corpos
  • Algo diferente nos axiomas de corpo
  • Homomorfismo de aneis e critério relevante
  • Duas operações binárias para o End(A)
  • De anel para corpo para corpo ordenado para corpo ordenado completo (de álgebra para análise)
  • Categorias
    • Definição
    • Exemplos
    • Definição categorial: inicial
    • Definição categorial: terminal

2022-12-13: Categorias

  • Definições “categoriais”
  • Unicidade e o uso do artigo definido
  • Unicidade dos objetos iniciais e dos terminais
  • Definição de produto e coproduto
  • Verificação das noções categoriais (até agora) para os exemplos de categorias que temos visto até agora
  • Princípio da dualidade

2022-12-14: Reticulados; Álgebra Booleana; Aneis

  • Produtos e coprodutos para linguagens de programação
  • Reticulados como posets: recap
  • Reticulados como álgebras
  • Reticulados distributivos
  • Reticulados cotados
  • Álgebras Booleanas
  • Teoremas de Representação
    • Para grupos (Cayley)
    • Para álgebras booleanas (Stone)
  • Como seria o teorema fundamental de homomorfismos para aneis?
  • Quem assumiria o papel de subgrupo normal?

2022-12-16: Prova 3.1

Futuro (fluido)

Sem futuro! Acabou!

Last update: Mon Mar 27 20:57:08 -03 2023