Horários de aula: | 246N12 [18h45–20h25] |
Sala: | A102 |
Contato: | thanos@imd.ufrn.br |
Playlists: |
FMC2:
( CFR
| IEA
) Pré-reqs: ( Intro | IDMa | IRI | IDMb ) |
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 II, sem ter aprendido mesmo as Natação I e II primeiro; ainda mais sem sequer ter entrado na agua na sua vida inteira!
(Obs.: aprender ≠ passar.)
Então—ANTES de começar—é bom ter estudado:
- FMC1-Intro: cap. 1,2 do fmcbook, playlist;
- FMC1-IDMa: cap. 3 do fmcbook, playlist;
- FMC1-IRI: cap. 4 do fmcbook, playlist;
- FMC1-IDMb: cap. 6 do fmcbook, playlist.
Além disso, é necessário que os alunos matriculados têm tempo e vontade para estudar, fazer os (muitos) trabalhos atribuídos, etc.
(Obs.: estudar ≠ ler.)
Antes de começar é bom dar uma lida nos:
- Comments on style de Munkres.
- A parte Writing mathematics do livro The tools of mathematical reasoning, de Lakins.
Conteúdo
A disciplina FMC2 será dividida em 3 módulos–unidades. Essa divisão é influenciada pelos módulos correspondentes à FMC2 baseados nos módulos correspondentes desta proposta.
CFR1: Conjuntos, Funções (30h)
Especificações e implementações matemáticas de coleções (conjuntos, ênuplas, multiconjuntos, sequências), e de suas principais operações e predicados; extensão vs intensão. A notação construtor-de-conjunto (set-builder) e sua interpretação. Implementação da noção de cardinalidade, no caso finito. Operações sobre coleções, finitas ou não, de conjuntos: união, interseção, produto e coproduto de conjuntos (produto cartesiano e união disjunta). Para o caso de coleções finitas, definições recursivas e demonstrações indutivas das suas propriedades. Complemento relativo, diferença simétrica. Conjunto potência. Especificações de famílias indexadas. Operações sobre famílias indexadas de conjuntos. Coberturas e partições. Especificações e implementações matemáticas de associações (funções parciais, totais, e não-determinísticas); extensão vs intensão. Funções vs procedimentos em programação; funções puras e efeitos colaterais. Funções anônimas (notação lambda). Funções de ordem superior, e funções como cidadãos de primeira classe. Curryficação e aplicação parcial de funções. Função identidade, composição de funções, iterações de uma função. Função inclusão, função vazia, função 0-ária, função constante. Projeções e demais funções associadas ao produto e ao coproduto de conjuntos (pairing, copairing, …). Funções indicadoras (ou características). Restrições de funções. Imagem direta e pré-imagem de conjuntos. A inversão de uma função, e a função inversa.
CFR2: Funções, Relações (30h)
Funções injetivas e sobrejetivas, monos e epis. Retrações e seções. Condições de invertibilidade de uma função. O teorema de Cantor sobre a cardinalidade do conjunto potência, e as cardinalidades transfinitas. Breve introdução à teoria da computabilidade: funções computáveis, números computáveis, e conjuntos computáveis; semi-decidibilidade e decidibilidade. Relações e a sua implementação conjuntista. Operações sobre relações, com ênfase no caso binário: inversa, composição, iterações, fechos. Descrição e propriedades do fecho transitivo: usando interseção (top-down) e usando união (bottom-up). Exemplos de conjuntos estruturados (e.g. espaços normados, espaços métricos, espaços topológicos, espaços de medida, grafos). Relações de equivalência e partições, classes de equivalência, e o conjunto quociente. Equivalências mais finas e mais grossas, e a relação de equivalência induzida pelo núcleo de uma função. Construções de classes de números usando quocientes. Relações de ordem: pré-ordens, ordens parciais e ordens estritas, ordens totais, elementos minimais e elementos maximais, supremos e ínfimos. Cadeias e funções que preservam ordem. Reticulados e reticulados completos. Ordens parciais completas. A construção de uma função a partir do limite de uma cadeia de funções parciais. Relações bem-fundadas: definição usando cadeias e definição usando elementos minimais, conexão com recursão e indução. Relações bem-fundadas induzidas pela imagem inversa de uma relação bem-fundada, pelo produto lexicográfico de relações bem-fundadas, e pelo fecho transitivo de uma relação arbitrária. Os Fundamentos da Matemática: uma breve introdução à Teoria Axiomática dos Conjuntos.
IEA: Introdução a Estruturas Algébricas (30h)
- 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).
- 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.
- 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).
- 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.
- Categorias (6h) Definição de categoria e exemplos, incluindo categorias associadas à programação e à lógica, e categorias a partir de preordens e posets. Dualidade e a definição de categoria oposta. Mono, epi, split mono, split epi, e iso. Definições (como especificações) por propriedades universais e diagramas comutativos: objetos terminais e inicias, produtos e coprodutos. Suas unicidades a menos de isomorfismo. Subobjetos, objetos quocientes, objeto livre, e suas propriedades universais. Verificação da sua existencia nas categorias encontradas.
Objetivos de aprendizagem
CFR1: Conjuntos, Funções
Prática com o uso das técnicas de demonstração e refutação matemática. Familiarização com a linguagem e com as principais classes, operações e propriedades de conjuntos e funções, definidas extensionalmente ou intensionalmente. Familiarização com as noções do cálculo lambda usadas em programação e lógica: variáveis ligadas e livres, captura de variáveis, renomeamento de variáveis, sombreamento de variáveis, aplicações de funções aos seus argumentos. Reconhecer os objetos matemáticos relevantes às linguagens de programação e suas propriedades. Familiarização com a formulação de especificações, e suas implementações matemáticas. Familiarização com o uso de diagramas comutativos em definições e demonstrações, e com especificações via propriedades universais.
CFR2: Funções, Relações
Prática com a escrita de especificações matemáticas e com o uso das técnicas de demonstração matemática, incluindo o método da diagonalização. Familiarização com as principais classes, operações e propriedades de relações. Familiarização com cardinalidades de conjuntos infinitos. Apreciar a conexão entre especificação e implementação. Familiarização com o raciocínio “sem pontos” (a saber, sem mencionar elementos dos conjuntos), através do composições de funções, e suas aplicações em programação.
IEA: Introdução a Estruturas Algébricas
Compreensão do papel da álgebra no estudo de estruturas de interesse computacional. Prática das técnicas de demonstração matemática e do uso do raciocínio equacional. Apreciar a conexão entre axiomas e seus modelos, e o conceito de independência lógica. Familiarização com a linguagem básica e as idéias elementares da Teoria das Categorias, incluindo o uso de diagramas comutativos para expressar proposições (leis e teoremas), especificações e definições.
Bibliografia e referências
Conhece o libgen?
Principal
- Eu: Matemática fundacional para computação [fmcbook]
Para cada um dos assuntos que tratamos, procure também a secção «Leitura complementar» no capítulo correspondente do fmcbook para mais referências.
CFR1: Conjuntos, Funções
- [fmcbook]: Cap: «Conjuntos»; «Funções»
- Moschovakis (2005): Notes on Set Theory, 2nd ed. (cap: 1)
CFR2: Funções, Relações
- [fmcbook]: Cap: «Relações»; «Posets; reticulados»; «O paraíso de Cantor»; «Teoria dos conjuntos axiomática»
- Moschovakis (2005): Notes on Set Theory, 2nd ed. (cap: 2,3,4,5,A)
- Davey & Priestley (2002): Introduction to Lattices and Order, 2nd ed. (cap: 1, 2, 4, 8)
- Moschovakis (2005): Notes on Set Theory, 2nd ed. (cap: 6)
IEA: Introdução a Estruturas Algébricas
- [fmcbook]: Cap: «Teoria dos Grupos»; «Estruturas Algébricas»; «Teoria das Categorias»
- 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.
- Barr & Wells (1998): Category Theory for Computing Science, 2nd ed., 2020 reprint
- Bird & de Moore (1997): The Algebra of Programming
- Halmos (1960): Naive Set Theory
- Wells (1993): Communicating Mathematics: Useful ideas from computer science (in American Mathematical Monthly, Vol 120, No. 5, pp.397–408)
- Mendelson (1973): Number Systems and the Foundations of Analysis (Cap. 2, 3, 4, 5, E, F)
Dicas
- James Munkres: Comments on style
- Jean-Pierre Serre: How to write mathematics badly
- Don Knuth: Mathematical writing
- Paul Halmos: How to write mathematics
- Por que tantos livros? Qual é o melhor? Vale a pena ler esse excerto do livro Linear Algebra de Jänich.
Links
- NNG
- Lean (veja também o Lean web editor e o livro Theorem Proving in Lean)
- Minicurso TeX 2018.2
- Detexify
- Minicurso Unix 2019.2
- The Missing Semester of your CS Education
Tecnologias e ferramentas
Obs.: As tecnologías/ferramentas seguintes podem mudar durante a disciplina—exceto a primeira.
- PAPEL (um caderno para dedicar à disciplina) e LAPIS/CANETA.
- Zulip (leia o FAQ).
- Pouco de (La)TeX (veja o minicurso TeX 2018.2). Online editor/compilador: Overleaf.
Regras
- 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.
- 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).
- Participando, nunca dê uma resposta que tu não pensou sozinho, exceto dando os créditos correspodentes.
- 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.
- 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.
- 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
- 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.)
- Estudar o conteúdo lecionado e tentar resolver todos os trabalhos atribuidos.
- Participar no Zulip diariamente, compartilhando tuas resoluções para receber feedback, e checando as resoluções de outros colegas para dar feedback.
- Checar e atender seu email cadastrado no SIGAA pelo menos uma vez por dia durante o semestre.
- 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.
- 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
- Plágio detectado implica que o aluno será reprovado imediatamente por nota e por faltas.
- 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.
U1 (CFR1)
- Prova CFR1.1 / 18pts (2023-04-14) { censored , uncensored , answers , correções }
- Prova CFR1.2 / 82pts (2023-05-26) { censored , uncensored , answers , correções }
U2 (CFR2)
- Prova CFR2.1 / 42pts (2023-07-05) { censored , uncensored , answers , correções }
- Prova CFR2.2 / 58pts (2023-07-19) { censored , uncensored , answers , correções }
U3 (IEA)
- Prova IEA.1 / 18pts (2023-04-14) { censored , uncensored , answers , correções }
- Prova IEA.2 / 45pts (2023-06-05) { censored , uncensored , answers , correções }
- Prova IEA.3 / 37pts (2023-07-05) { censored , uncensored , answers , correções }
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.
2023-03-08 (Intro) (1)
- Trabalhe nos pré-requisitos.
- Dê uma lida nos Capítulos 1 e 2.
2023-03-10 (IEA) (1)
- Cap. 10: §«Permutações»
- Escreva sozinho uma demonstração completa da unicidade de identidade numa estrutura de grupo. Quais leis tu precisou mesmo?
- Demonstre a unicidade dos inversos.
- Infira teoremas que envolvem mais que um dos três protagonistas da alma de grupo: a operação (binária), a identidade, e os inversos. Por exemplo: o inverso do inverso deve ser o quê? O inverso da identidade? Etc. (O Etc é importantíssimo!)
- (Para quem não trabalhou ainda no IDMa:) Cap. 3: §«Primeiros passos»
2023-03-14 (CFR1) (1)
- Cap. 8: §«Expressões com buracos»
- Cap. 7: até §«Oito proposições simples»
2023-03-26 (Intro) (2)
- A gente viu no
#intro-lang-proofs › aplicando a mesma função nos dois lados
como justificar (demonstrar) isso, descubrindo que é uma propriedade fundamental das funções. Desafio: usando uma linguagem de programação que já usou no IMD, mostre que ela não merece usar o termo «função» mostrando como quebrar essa regra. Proibido usar qualquer coisa de random. Postem tentativas/brigas/dúvidas no#programming
. - Uma tentativa para resolver o hw anterior foi a seguinte: considerar, em JavaScript, que temos
1 == '1'
masf(1) != f('1')
ondef
é “a função”x => x + 1
. O desafio deste hw é achar um motivo bom para desconsiderar essa como resposta válida para o hw anterior.
2023-03-30 (CFR1) (2)
- Capítulo «Conjuntos»: até o primeiro intervalo de problemas
2023-03-31 (IEA) (2)
- Capítulo «Teoria dos grupos»: até §«Tabelas de Cayley»
2023-04-03 (CFR1) (3)
- Capítulo «Conjuntos»: até §«Tuplas».
2023-04-05 (IEA) (3)
- Capítulo «Teoria dos grupos»: até p.447.
- Demonstre a equivalência entre as duas definições alternativas de potência (x10.40)
- Ache as ordens de todos os membros do grupo S₃
- Sejam $G$ grupo e $a \in G$. Se $a^m = e$ para algum $m\in\mathbb{Z}_{\neq0}$, então $o(a)<\infty$.
- Demonstre ou refute: G abeliano ⇔ (∀a,b:G)[ (ab)⁻¹ = a⁻¹b⁻¹ ]
- Demonstre ou refute: G abeliano ⇔ (∀a,b:G)[ (ab)² = a²b² ]
- Demonstre: Se para 3 consecutivos inteiros i, temos (∀a,b:G)[ (ab)ⁱ = aⁱbⁱ ], então G é abeliano.
- Demonstre que trocando o 3 por 2 no hw anterior, vira-se indemonstrável.
- Problemas: Π10.1, Π10.2, Π10.4, Π10.5, Π10.6, Π10.7
2023-04-10 (CFR1) (4)
- Capítulo «Conjuntos»: até §«n-tuplas».
- Como implementarias 2-tuplas usando (apenas) conjuntos “sujos”?
2023-04-12 (CFR1) (5)
- Capítulo «Conjuntos»: até o fim
2023-04-18 (CFR1) (6)
- Revise sobre conjuntos:
- Exercícios: x7.57; x7.58; x7.59; x7.63; x7.66; x7.67;
- Problemas: Π7.9; Π7.10; Π7.11; Π7.12; Π7.13; Π7.14; Π7.15; Π7.16
- Capítulo «Funções»: até §«Expressões com buracos»
- Justifique a notação Bᴬ para o espaço de funções (A→B)
2023-04-24 (CFR1) (7)
- Capítulo «Funções»: até §«Currificação»
- Ache as noções de conjuntos que correspondem às: 0, 1, (+), dos números.
- Demonstre as “igualdades-entre-aspas” correspondentes às leis conhecidas desde ensino fundamental.
2023-04-28 (IEA) (5)
- Capítulo «Teoria dos grupos»: até §«Subgrupos»
- O que foi o
?
da aula que apareceu nos tipos? → G
e? → H
? - Qual o tipo da (≤) que definimos na aula?
- A (≤) é uma preordem? Ela é uma ordem parcial?
- Sejam G grupo e K ⊆ H ⊆ G. Suponha que K,H≤G. Podemos inferir que K≤H?
- No segundo critério visto na aula consideramos o dado
G fin
. Podemos substituir porH fin
? O teorema/critério fica mais fraco ou mais forte assim? - No mesmo critério quais dados exatamente precisamos?
2023-05-04 (CFR1) (8)
- Capítulo «Funções»: até §«Funções de graça»
2023-05-05 (IEA) (6)
- Capítulo «Teoria dos grupos»: até §«Geradores» (cuidado: re-baixe o fmcbook pois o §«Conjugação de grupo», foi locomovido, e faz parte deste hw!
- Problemas: Π10.1; Π10.2; Π10.7; Π10.8; Π10.11; Π10.12; Π10.13
2023-05-09 (IEA) (6)
- Desafio: achar conjunto inicial $A$ no plano que demora chegar no $\langle A \rangle$ (conjunto convexo gerado pelo $A$).
2023-05-09 (CFR1) (8)
- §«Jecções: injecções, sobrejecções, bijecções»
- Problemas: Π8.5, Π8.6, Π8.14, Π8.17
2023-05-12 (IEA) (7)
- Demonstre que as abordagens top-down e bottom-up concordam para a definição de ⟨A⟩.
- Demonstre o que faltou para o teorema de Lagrange
- (i) cada linha tem membros frescos
- (ii) cada linha tem membros distintos dois-a-dois
- Demonstre que $\mathcal L_H$ é uma partição de $\mathcal G$, e a $\mathcal R_H$ também.
- Ache H≤𝒢 tais que $\mathcal L_H \neq \mathcal R_H$.
2023-05-12 (CFR1) (9)
- Seja (~) uma relação de equivalência num conjunto $A$. Para qualquer $a ∈ A$, denote por $[a]_{\sim}$ o conjunto $\{x \mid x \sim a \}$. O $\{ [a]_{\sim} \mid a \in A \}$ é uma partição do $A$?
- Alguém definiu: «Uma partição num conjunto A é uma função …». Adivinhe o
…
e justifique tal frase! - Defina uma ordem interessante no Partition(A).
- Demonstre que se os dois quadradinhos do diagrama da aula comutam, o diagrama todo comuta.
- Qual deve ser a próxima pergunta para perguntar depois de descubrir que
const = curry outl
? - Demonstre as leis de composição estilo point-full.
- Qual seria a especificação do produto?
- Qual seria a especificação de soma?
- Tente achar outras implementações de união-disjuntora (soma)
- Quais seriam os diagramas e funções relacionados à união-disjuntora?
- Melhore nossa definição de iterações de funções, e demonstre umas propriedades interessantes sobre elas.
- Até §«Definições estilo point-free»
- Reveja a §«Funções de graça» e seus exercícios.
- Problemas: Π8.12; Π8.13; Π8.14; Π8.16; Π8.19; Π8.20; Π8.22
2023-05-17 (CFR1) (10)
- §«Funções parciais»
- §«Funções inversas»
- §«Definições recursivas»
- Problemas: Π8.7; Π8.8; Π8.9; Π8.10; Π8.11; Π8.30
2023-05-19 (IEA) (8)
- Demonstre que a
improve : Set G → Set G
é (⊆)-monotônica - Θ. Sejam H,K ≤ G. Demonstre: HK = KH ⇔ HK ≤ G
- Seja N ≤ G. O.s.s.e.:
- (i) $\mathcal R_H = \mathcal L_H$
- (ii) $(\mathrm R_H) = (\mathrm L_H)$
- (iii) $N$ é fechado pelas conjugações
- (iv) $(\forall g \in G)[ gNg^{-1} \subset N ]$
- (v) $(\forall g \in G)[ gNg^{-1} = N ]$
- (vi) $(\forall g \in G)[ gN = Ng ]$
- Até §«Teoria dos números revisitada»
2023-05-25 (IEA) (9)
- Capítulo «Teoria dos grupos», até §«Morfismos»
2023-05-29 (IEA) (10)
- Demonstre sem nenhuma consulta o último palpite da aula: $G/\ker{\varphi} \cong \mathrm{im}\varphi$
- Capítulo «Teoria dos grupos», §«Kernel, Image»
- Problemas: Π10.22; Π10.23; Π10.27; Π10.28
2023-05-31 (CFR2) (1)
- Verifique cada uma das 8 implicações:
- f inj ⇔ f L-cancelável ⇔ f L-invertível
- f sobre ⇔ f R-cancelável ⇔ f R-invertível
- Capítulo «Funções»: §«Uma viagem épica»; §«Retracções e secções»
2023-06-02 (CFR2) (2)
- Escreva sozinho as especificações de produto e de coproduto.
- Verifique que B×A com as
toA
etoB
que definimos, é um produto de A e B - o A×B×A com as
toA (x,y,z) = x
etoB (x,y,z) = y
, é um produto de A e B? - Mostre que o A∪B não é um coproduto (soma) dos A e B
- Generalize as especificações de produto e coproduto do caso binário para o caso geral, aplicável em qualquer ℐ-família de conjuntos.
- Tente formular uma especificação para o que seria a exponenciação Bᴬ de um conjunto B elevado a um conjunto A (dica: lembra da
eval
?)
2023-06-08 (IEA) (11)
- Resolva finalmente os não resolvidos hw! (Especialmente sobre: Hom(G,G’), Aut(G), Inn(G), etc.)
- Capítulo «Estruturas Algébricas»: até §«Anéis»
- Problema: Π11.1
2023-06-13 (CFR2) (3)
- Capítulo «O paraíso de Cantor»; até §«O segundo argumento diagonal de Cantor»
- Para cada uma das operações seguintes, decida (demonstre/refute) se (=c) é uma congruência: ℘f, ℘, ⋃, ⋂, ∪, ∩, Δ, , (→), (×), (+)
- Demonstre/refute as (=c) seguintes sobre intervalos de números reais, com $a < b$ e $c < d$:
- [0,0] =c [0,0)
- (0,1) =c (0,2)
- (a,b) =c (c,d)
- [a,b] =c [c,d]
- (0,1] =c [0,2)
- (0,1) =c [0,1]
- (0,1) =c [0,1)
- [0,1] =c [0,1)
- Demonstre/refute as =c onde α,β∈ℝ∪{-∞,+∞} com α<β.
- (α,β) =c (0,1)
- (α,β) =c (0,1)
- Problemas: Π12.6; Π12.7
2023-06-14 (CATS) (1) – (CFR2) (4) & (IEA) (12)
- Como definarias a categoria 𝟛?
- Como definarias a categoria 𝕟?
- Para cada uma das categorias que encontramos, determina seus objetos iniciais e seus objetos terminais, caso existam. Caso contrário, verifique tal ausência.
- As categorias 𝟘, 𝟙, 𝟚, 𝟛, …
- A categoria ℂ[ℳ] baseada a um monóide ℳ.
- A categoria ℂ[(ℕ;≤)], i.e., a categoria baseada no ℕ com sua (pre)ordem canônica (≤))
- A categoria ℂ[(ℤ;≤)]
- A categoria ℂ[(ℤ;|)]
- A categoria ℂ[(℘S;⊆)]
- As categorias de umas estruturas algébricas: $\mathbf{Semigroup}$, $\mathbf{Monoid}$, $\mathbf{Group}$, $\mathbf{Abel}$, $\mathbf{Ring}$
2023-06-17 (CATS) (2) – (CFR2) (5) & (IEA) (13)
- Para cada uma das categorias que encontramos até agora traduza os conceitos de «produto» e «coproduto» e verifique se elas possuem ou não
- A mesma coisa sobre os conceitos de «terminal», «inicial», «zero», já que conhecemos mais categorias desde a aula anterior
- Verifique que a (≅) de «é isômorfo a» é uma relação de equivalências nos objetos de qualquer categoria
- Demonstre que todos os produtos de dois objetos A,B são isômorfos («unicidade» de produtos)
- Demonstre que todos os coprodutos de dois objetos A,B são isômorfos («unicidade» de coprodutos)
- Tente definir categorias onde os objetos são:
- as categorias(!)
- as setas de uma data categoria ℂ
2023-06-19 (CATS) (3) – (CFR2) (6) & (IEA) (14)
- Escreva sozinho as definições categoriais que conhecemos até agora.
- Fixe duas categorias ℂ,𝔻. Considere cada functor ℂ → 𝔻 como um objeto em uma nova categoria. Como definarias as setas nessa nova categoria?
- Traduza os conceitos categoriais que temos definido até agora nas novas categorias que conhecemos.
- Entre na 𝐀𝐛𝐞𝐥. Sejam 𝒜,ℬ objetos desse mundo. Mostre que o grupo abeliano 𝒜×ℬ definido usando as operações component-wise é um produto dos 𝒜,ℬ mesmo (com quais setas?). Mostre que o mesmo grupo abeliano é um coproduto dos 𝒜,ℬ (com quais setas?).
- O 𝐑𝐢𝐧𝐠 tem inicial? Terminal?
- Suponha que a $\mathbb C$ tem (co)produtos. A $\mathbb C^{\to}$ tem (co)produtos?
- Investiga a existência de (co)produtos e (co)terminais nas categorias “comma” ℂ/C e C/ℂ (slice ou over; e coslice ou under).
- Na aula encontramos maneiras de (re)definir os conceitos de monóide e de grúpo. No mesmo estilo como (re)definarias os conceitos de «homomorfismo entre monóides» e «homomorfismo entre grupos»?
- Defina functors:
- De 𝐆𝐫𝐨𝐮𝐩 para 𝐌𝐨𝐧𝐨𝐢𝐝
- De 𝐑𝐢𝐧𝐠 para 𝐀𝐛𝐞𝐥
- De 𝐑𝐢𝐧𝐠 para 𝐌𝐨𝐧𝐨𝐢𝐝
- De 𝐌𝐨𝐧𝐨𝐢𝐝 para 𝐒𝐞𝐭
- De 𝐒𝐞𝐭 para 𝐌𝐨𝐧𝐨𝐢𝐝
- De ℂ[ℳ] para 𝐒𝐞𝐭, para uns monóides ℳ que tu gosta
- De ℂ[𝒢] para 𝐒𝐞𝐭, para uns grupos 𝒢 que tu gosta
2023-06-21 (CFR2) (7)
- Demonstre que o quadrado tem o tamanho do seu lado: [0,1]² = [0,1]
- Será que o cubo tem o tamanho de uma aresta?
- Investigue as cardinalidades dos:
- (ℕ→ℕ)
- (ℕ→ℝ)
- (ℝ→ℕ)
- (ℝ→ℝ)
- Demonstre a Q-Daví: A ≤c B & B ≤c A ⇒ A =c B
- Demonstre a Q-Isaac: A ≤c B ou B ≤c A
2023-06-26 (CFR2) (8)
- Capítulo «O paraíso de Cantor»: até §«Os números transfinitos»
- (A×B)→C =c A → (B→C)
- Demonstre nossa afirmação que a união dos ℕ, ℘ℕ, ℘℘ℕ, … tem cardinalidade maior que a cardinalidade de cada um desses conjuntos.
- Compare as cardinalidades dos (A→B) e ℘(A×B)
- Problemas: Π12.3; Π12.4; Π12.5; Π12.6; Π12.7; Π12.10
- Para quem estudou reais bem:
- Demonstre que o conjunto C[0,1] de todas as funções continuas no ([0,1] → ℝ) é equinúmero com o ℝ
- Demonstre que o conjunto de todas as funções monótonas no ([0,1] → ℝ) é equinúmero com o ℝ
- Chute qual parece ser o peso (length) do conjunto 𝐂 de cantor
- Capítulo «Relações»: até o primeiro intervalo de problemas
- Problemas: Π9.1; Π9.2; Π9.3; Π9.4; Π9.5; Π9.6; Π9.7; Π9.8; Π9.9; Π9.10; Π9.11; Π9.12; Π9.13
- Como definarias a categoria 𝐑𝐞𝐥 de conjuntos e relações entre eles?
2023-06-28 (CFR2) (9)
- Capítulo «Relações»: §«Partições» e §«Conjunto quociente»
- Problemas: Π.15; Π9.16; Π9.17; Π9.18; Π9.19; Π9.20; Π9.22; Π9.23; Π9.24; Π9.25
2023-07-01 (IEA) (15)
- Um anel é chamado anel booleano sse todos seus membros são idempotentes: (∀x)[x = x²]. Demonstre que em qualquer anel booleano:
- (∀x)[x = -x]
- (∀x,y)[xy = -yx]
- Seja R anel comutativo. Demonstre: R é DI ⇔ R é DC.
- Todo anel booleano é comutativo.
- Demonstre que todo domínio de integridade finito é um corpo.
- Seja φ homomorfismo entre corpos. A φ precisa respeitar os (·)-inversos?
- Capítulo «Estruturas algébricas»: todo.
- Problemas: Π10.24; Π10.25; Π10.26; Π11.1
2023-07-04 (CFR2) (10)
- Capítulo «O paraíso de Cantor» (todo).
- Π12.8; Π12.9; Π12.11
2023-07-04 (IEA) (16)
- Demonstre o teorema de Cayley: todo grupo é isomorfo àlgum subgrupo de algum grupo simétrico.
- Demonstre o teorema de Cauchy para os grupos abelianos: para todo grupo abeliano 𝒜 de ordem n, e todo primo p que divide o n, existe a∈A com o(a)=p.
- Verifique: em qualquer espaço vetorial:
- $0\mathbf v = \mathbf 0$;
- $r\mathbf 0 = \mathbf 0$;
- $(-r)\mathbf v = \ominus (r\mathbf v)$;
- $r\mathbf v = \mathbf 0 \implies r=0~~\text{ou}~~\mathbf v = \mathbf 0$;
- $\ominus \mathbf v = (-1)\mathbf v$;
- Mostre que anel booleano e álgebra booleana são estruturas equivalentes no sentido seguinte:
- a partir de qualqeur anel booleano R podemos definir uma algrebra booleana BA(R);
- a partir de qualqeur álgebra booleana A podemos definir um anel booleano BR(A);
- os
BR
eBA
são inversos entre si; - os conceitos de morfismos concordam nas duas interpretações.
2023-07-06 (IEA) (17)
- Mostre como o R/I pode virar um anel, tendo I um ideal do anel R.
- Um homomorfismo de grupos reflete os subgrupos normais?
- Verifique que os units dum anel formam um grupo com a multiplicação.
2023-07-08 (CFR2) (11)
- Mostre que com a implementação de 2-tupla de Kuratowski o produto cartesiano a×b de dois conjuntos a,b, é de fato um conjunto.
- Capítulo «Teoria axiomática dos conjuntos»: até o primeiro intervalo, sem as partes que falam sobre classes
- Π15.1; Π15.2; Π15.3; Π15.6; Π15.7
2023-07-10 (CFR2) (12)
- Capítulo «Teoria axiomática dos conjuntos»: até o primeiro intervalo
- Verifiquem o claim de Matias: um functor de ℂ[𝒫] para ℂ[𝒬] é uma função monótona de 𝒫 para 𝒬
- Vendo um poset como categoria, traduza a definição categorial de produto e de coproduto.
- Capítulo «Posets; Reticulados»: §«Conceito, notação, propriedades»
2023-07-12 (CFR2) (13)
- Capítulo «Teoria axiomática dos conjuntos»: até §«Teoremas de recursão»
2023-07-14 (CFR2) (14)
- Capítulo «Teoria axiomática dos conjuntos»: até §«Mais axiomas»
- Π15.10; Π15.11; Π15.12; Π15.13
- Sejam 𝒫, 𝒬 posets. Mostre como definir ordens para tornar posets também os:
- P⊎Q (ache umas 2 aqui)
- P×Q (ache umas 3 aqui)
- (P→Q) [o que tu precisa mesmo aqui?]
- Ache um critério para estabelecer qual seria a definição certa para o P×Q, e elabore também sobre o P⊎Q.
- Capítulo «Posets; reticulados»: estude a §«Mapeametos» e resolva seus exercícios.
2023-07-17 (CFR2) (15) & IEA (18)
- Estabeleça a equivalência entre reticulados como posets e reticulados como álgebras.
- Demonstre a monotonicidade das
(a ∧)
,(a ∨)
,(∧ a)
, e(∨ a)
- Demonstre a distributividade fraca para qualquer reticulado:
(x ∧ y) ∨ (x ∧ z) ≤ x ∧ (y ∨ z)
- …e sua dual?
- Demonstre a modularidade fraca para qualquer reticulado:
x ≤ z ⇒ x ∨ (y ∧ z) ≤ (x ∨ y) ∧ z
- …e sua dual?
- Sejam
L
um reticulado,a ∈ L
. Chamamos de complemento dea
qualquerc ∈ L
tal quea ∧ c = ⊥
ea ∨ c = ⊤
.- Demonstre a unicidade de complementos (mesmo quando não há existência) para reticulados distributivos.
- Def. Seja
L
reticulado. ChamamosL
de reticulado booleano sse: (i)L
é distributivo; (ii) L possui ⊥ e ⊤; (iii) Todo membroa
deL
possui complemento (que necessariamente é único pelo hw anterior). Denotamos o complemento dea
pora'
. Demonstre que em qualquer reticulado booleano temos:- (a ∨ b)’ = a’ ∧ b’
- (a ∧ b)’ = a’ ∨ b’
- a ∧ b’ = ⊥ ⇔ a ≤ b
- Sejam $B, C$ algebras booleanas, e $f : B → C$ homomorfismo de reticulados.
- O.s.s.e.:
- (i) f ⊥ = ⊥ e f ⊤ = ⊤
- (ii) (∀b∈B)[f(b’) = (f b)’ ]
- Suponha que $f$ preserve o complemento
'
. Logo: $f$ preserve (∨) sse $f$ preserve os (∧).
- O.s.s.e.:
- Estabeleça a equivalência entre reticulados booleanos e aneis booleanos.
- Pensando num reticulado L como algebra, defina o que significa subreticulado e o que subreticulado gerado por A ⊆ L.
- Pensando num reticulado L como um poset, qualquer A ⊆ L herda uma ordem, assim virando um poset 𝒜 também.
- Investigue: 𝒜 é um reticulado ⇔ A é um subreticulado de L?
2023-07-18 (CFR2) (16) & IEA (19)
- Θ. Se um proset possui todos os joins, então ele possui todos os meets (e vice versa).
- Θ. Sejam L, K reticulados, e f : L → K um mapa. O.s.s.e.:
- (i) f é monótona (preserva a ordem)
- (ii) f “adia” joins:
f(a∨b) ≥ fa ∨ fb
- (iii) f “adianta” meets:
f(a∧b) ≤ fa ∧ fb
- Considere a proposição (∗):
«se nenhum dos
(∨t)
e(∧t)
distingua entreu
ev
, entãou = v
».- (i) Entenda o que (∗) significa e o traduza para uma proposição sem gírias;
- (ii) Demonstre a (∗) para reticulados distributivos.
Histórico
2023-03-06: Aula cancelada pela UFRN
2023-03-08: Pré e Introdução [video]
- Introdução meta
- Revisão: type errors, linguagem de demonstrações matemáticas
- Exemplos: teoremas sobre a transitividade da (|)
2023-03-10: IEA (1): Introdução [video]
- Os inteiros e sua estrutura
- Propriedades de operações
- Aridades, nulária, unária, e constantes
- Os strings com concatenação
- Associatividade e como a definir
- Parseamento e árvore sintáctica
- A idéia da abstração algébrica
- Trade-off entre axiomas e modelos
- O papel dum exemplo-guia para uma estrutura algébrica
- Comutatividade
- Permutações, sua notação, e o S₃
- Enter Álgebra: a operação (∘)
- Do exemplo-guia S₃ para a definição de grupo
- inversos e um problema de escopo
- «Existe único …» e como expressá-lo
- Θ. (id-uniq)
2023-03-13: CFR1 (1): Introdução [video]
- Set: tipos de conjuntos
- Funções: Inferência
- Set como um type constructor
- Como introduzir um novo tipo: interface (como usar), como formar, igualdade
- Interface de conjunto
- buracos e funções de ordem superior
- Sobre conjuntos heterogêneo
- Prop vs Bool
- Set(Set(Int)), etc.
- uma mentira: subconjuntos vs embutimentos
- o que significa «saber o A»
- Igualdade, extensão, black boxes e suas conseqüências
- duas maneiras de errar, dando uma definição
Aulas canceladas pela UFRN: (4×CFR1) + (2×IEA)
2023-03-29: CFR1 (2): Conjuntos [video]
- Operações entre conjuntos e como defini-las
- Complemento relativo (∖)
- Comutatividade de operações
- Diferença simétrica (∆)
- Parseamento e precedência sintáctica
- Diferença simétrica (2)
- Os habitantes duma diferença simétrica
- Complemento de conjunto
- Powerset (℘)
- Empty, Singleton, Universal, Inhabited
- LEM e dupla negação
- conjuntos finitos e o powerset-finito
- união grande
- interseção grande
- sem medo
- versões de set builder
2023-03-31: IEA (2): Grupos [video]
- Definição de grupo
- grupos aditivos vs multiplicativos
- teoria dos grupos e as primeiras conseqüências
- (canL) cancelamento pela esquerda
- detalhamento das justificativas
- aplicando a mesma função nos dois lados
- como demonstrar com apenas um cálculo
- (id-!) unicidade da identidade
- (resR) resoluções únicas
- (inv-id), (inv-inv), (inv-op)
- igualdade não é exatamente simétrica
- uns exemplos e nãoexemplos
- como definir operações
- tabelas Cayley e Grupoku™
2023-04-03: CFR1 (3): Conjuntos; Tuplas [video]
- Sobre o LEM
- Habitado vs Não-vazio
- Brouwer vs Hilbert
- Θ. 𝒜∩ℬ hab ⇒ ⋂𝒜 ⊆ ⋃ℬ
- Um primeiro papo sobre especificação
- Interface das tuplas
- Equações fundamentais das tuplas
- Igualdade entre tuplas
- Criando tipos mais complexos usando Set e Pair
- Q: Podemos definir um novo «pertence» para tuplas?
- Podemos inferir Ø∈A? Ø⊆A?
2023-04-05: IEA (3) [video]
- Mais sobre Grupoku
- umas primeiras potências em grupo
- associatividade sintáctica e precedência sintáctica
- duas definições de potências para n ≥ 0 e sua equivalência
- potências negativas
- diagramas comutativos
- ordem de grupo e de membro de grupo
- o ℘A munido com qual das (∪),(∩),(),(∆), vira um grupo?
2023-04-10: CFR1 (4) [video]
- 3-tuplas como tipo primitivo
- especificação vs implementação
- como implementar 3-tuplas usando 2-tuplas
- a importância de ser implementação-agnóstico
- n-tuplas para outros n
- desafio: implementar 2-tuplas (a implementação de Kuratowski)
- o que seria uma 1-tupla?
- sobre 0-tuplas
- existência e unicidade da 0-tupla
- o muito mal-nomeado void
- teaser: tuplas de tamanho infinito e seqüências
- teaser: sacolas
- o que podemos concluir sobre a cardinalidade do conjunto
{f(x,y) ∣ x,y∈{u,v}}
?
2023-04-12: CFR1 (5) [video]
- Conjunto indexado por I
- Família indexada por I (I-tupla)
- família indexada vs conjunto indexado
- Como solicitar um membro arbitrário dum conjunto indexado
- Usando um produto I×J como conjunto de índices
- Seqüências
- Famílias indexadas para implementar outros tipos
- 2-tuplas como conjuntos e um roubo “definindo” funções
- produto generalizado (de famílias indexadas)
- nível-coração: escolhedores
2023-04-14: Prova CFR1.1 & Prova IEA.1
2023-04-17: CFR1 (6) [video]
- De operacões binárias para operações generalizadas
- definições recursivas de operações que operam em seqüências
- Somatórios sem órdem/agrupamento especificados
- Funções: black box, descrição, especificação, igualdade, notação
- Q: sobre funções parciais
- Espaço de funçoẽs (A→B) ou Bᴬ
- Vazio como domínio ou codomínio
- Tipo vazio e tipo unit: discussão sobre o mentiroso void
- Definindo funções com buracos
2023-04-19: CFR1 (7) [video]
- graph : (A→B) → Set(A×B)
- o espaço de funções (A→B)
- diagramas internos vs externos
- setas: → vs ↦
- igualdade extensional vs intensional
- «aquele x tal que»
- definição por casos
- abstração com buracos
- funções de ordem superior
- currificação e descurrificação
- aplicação parcial
- $∣B^A∣=∣B∣^{∣A∣}$
2023-04-24: CFR1 (8) [video]
- recap: currificação e associatividades sintácticas
- de buracos para lambdas
- como funciona um cálculo
- funções anônimas e compração com set builder
- semântica vs sintaxe, nomes de símbolos vs nomes de noções
- a notação lambda
- metáforas com almas e corpos
- Q: funções anônimas de aridades maiores?
- Q: buracos vs lambdas e ordem dos parametros
- parenteses implícitas e convenções
- sobre binding e ocorrências de variáveis livres
- dois exemplos de abstrações e inferência de tipos polimórfica
- o açúcar sintáctico λ(x,y).coisa
- como cálcular: β-redex, β-redução
- chegando à idéia do α-renomeamento
- introdução de lambdas em linguagens de programação “populares”
- plicker: calcule a expressão-λ
- sobre a η-conversão
2023-04-26: IEA (4) [video]
- proposições disfarçadas como igualdades
- Θ. o(a) = n ⇔ existem exatamente n potências distintas de a
- Θ. aᵐ = e ⇔ o(a) | m
- Subgrupos: duas idéias para chegar na sua definição
- um grupo de ordem infinita, pode ter subgrupos de ordem finita?
2023-04-28: CFR1 (9) [video]
- recap: curry & uncurry
- operações de números vs operações de conjuntos
- igualdade-entre-aspas de conjuntos
- mais leis e mais conceitos para investigar
- sobre a idéia de «usar conjuntos para fundamentar a matemática»?
- Funções de graça
- função identidade
- função inclusão
- Podemos considerar, sendo conjuntistas, que ℕ⊆ℤ?
- não é ousadia usar o nome identidade?
- plicker: calcule uma expressão-λ
2023-04-28: IEA (5) [video]
- subgrupos triviais e não-triviais
- podemos usar o termo subgrupo mesmo?
- é a mesma operação mesmo?
- Q: podemos definir uma nova operação num subgrupo?
- O plano complexo e sua interpretação geométrica
- uns (sub)grupos de complexos
- Q: conclusões sobre (⊆) e (≤)
- Critéria de ser subgrupo e o que significa critério
- primeiro critério
- segundo critério e uma dica sobre como demonstrar
- terceiro critério
- o que acontece se apagar um dado do contexto dum teorema
2023-05-03: CFR1 (10) [video]
- recap: λ, β, η, α
- η-conversão
- Como interpretar uma função aplicada nela mesmo
- Manifestações dos β,η para outros tipos: conjuntos e 2-tuplas
- função-imagem
- função-pré-imagem
- sobre composição
- Plicker: a função-imagem respeita uniões e interseções?
2023-05-05: IEA (6) [video]
- Qual o tipo mesmo da (≤)?
- Interseção de subgrupos é subgrupo
- (Como) podemos estender o teorema sobre interseção de subgrupos?
- Tentativa de estender para união
- O que precisamos demonstrar para estendar sobre interseções arbitrárias?
- Q: podemos só demonstrar o teorema sobre as interseções arbitrárias?
- Duas relações que acabam sendo de equivalência: $\mathrm R_H$ e conjugação
- Subgrupo gerado por membro de grupo: ⟨a⟩
- Subgrupo gerado por subconjunto de grupo: ⟨A⟩ (bottom-up)
2023-05-08: IEA (7) [video]
- recap: subgrupo gerado por A: bottom-up
- subgrupo gerado por A: top-down
- conjuntos convexos: bottom-up e top-down do convex hull
- mais recap: as relações de equivalência de conjugados e do $\mathrm R_H$
- investigando a $\mathrm R_H$
- Caso ambos no $H$
- Caso um dentro um fora do $H$
- Caso ambos fora do $H$
- A partição induzida pela $\mathrm R_H$
2023-05-08: CFR1 (11) [video]
- inversão de função
- injetividade, sobrejetividade, bijetividade
- funções de graça: f×g
- um desafio parecido: duas funções com o mesmo domínio
- tentando definir uma f∪g, em forma parecida
- o que podemos inferir sobre duas funções, sabendo que sua composição é bijetiva?
2023-05-10: IEA (8) [video]
- Coclasses de subgrupo
- Partição do grupo 𝒢 pelas coclasses de H
- Demonstração do teorema de Lagrange
- indice de subgrupo
- Corolário de Lagrange: subgrupos de G com o(G) primo
- a notação Hab²Kb⁻¹KKcaH…etc
- Q: $\mathcal L_H ≟ \mathcal R_H$
2023-05-10: CFR1 (12) [video]
- função constante vs função invariável
- iterações de endomapas
- associatividade de composição
- composição respeita as -jetividades
- definições e demonstrações com pontos
- botando na mesa as definições recursivas
2023-05-12: CFR1 (13) [video]
- Partições e coberturas de conjuntos
- Diagramas comutativos
- Leis da composição (assoc. e ident.)
- [tacit-programming][Estilo tácito] (aka: point-free, pointless)
- a função const : β → α → β e um desafio
- Uma das leis de identidade descrita como diagrama comutativo
- id é uma identidade para a composição
- recap: funções e diagramas relacionados ao produto (×)
- única função que faz um diagrama comutar
- união disjunta: no caminho de achar a soma de conjuntos
- Plicker: a ℘f respeita as uniões e as interseções?
2023-05-15: CFR1 (14) [video]
- Fixpoints
- Definindo iterações melhor (sem pontos)
- Mais funções de graça: pointwise, diagonal, pareamento, produto
- Uma vantagem de usar funções descurrificadas
- conjuntista-vs-tipista sobre funções (e pouco em geral)
- implementações usando funções
- funções parciais e não-deterministas
- união-disjunta: especificação-vs-implementação, copareamento, coproduto
2023-05-17: CFR1 (15) [video]
- equações recursivas como sistemas de incógnitos
- mais funções de graça: função caraterística
2023-05-19: IEA (9) [video]
- Sobre a top-down e bottom-up abordagem do subgrupo gerado por um subconjunto
- demonstração que as duas abordagens definam o mesmo subgrupo
- improve e seus fixpoints
- Uns grupos de inteiros (aditivos e multiplicativos)
- Mais (corolários de) Lagrange
- partições feitas por coclasses e as relações módulo subgrupo
- o teorema de Euler (FMC1-IDMa) como corolário de Lagrange
- HK ≤ G? KH ≤ G?
- Um exemplo onde $\mathcal L_H \neq \mathcal R_H$
- Uma primeira definição de subgrupo normal e umas equivalentes
2023-05-22: IEA (10) [video]
- Conjunto quociente
- Congruências
- Grupo quociente
- Entendendo melhor os grupos aditivos ℤ/mℤ
- Definições equivalentes para subgrupo normal
- Significado de igualdade para 3 tipos diferentes
- Relação de equivalência sobre uma partição
- Aviso sobre um erro comum usando gN=Ng ou HK=KH
- {e,ψ,ψ²} ⊴ S₃?
2023-05-24: IEA (11) [video]
- Θ. HK = KH ⇔ HK ≤ G
- O grupo das simetrias de um triangulo equilátero
- Quão “novo” é realmente esse grupo?
- “tem a cara” de S₃ e como formalizar isso
- Desenhando os (N)Sub(S₃) e (N)Sub(ℤ/6ℤ)
- Homomorfismo
- Isomorfismo
- Um homomorfismo trivial
- Critério de homomorfismo
2023-05-26: Prova CFR1.2
2023-05-29: IEA (12) [video]
- possíveis conflitos sobre a definição de homomorfismo
- Critérion de homomorfismo de grupos
- kernel (núcleo) e imagem
- Θ. φ injetiva ⇔ kerφ = {⋆}
- Qual a mais forte afirmação sobre kerφ?
- Θ. kerφ ⊴ A
- Θ. G/kerφ ≅ imφ
- kernel ⇒ normal & kernel ⇐ normal ??
2023-05-31: CFR2 (1) [video]
- retrações e secções
- funções (L/R)-invertíveis
- funções (L/R)-canceláveis
- como dizer Seja a ∈ A. sem pontos
- confundindo aplicações com composições
2023-06-02: CFR2 (2) [video]
- especificações sem pontos
- procurando uma especificação para produto
- ganhando gratuitamente uma especificação para soma (coproduto)
- pairing, copairing, projeções, coprojeções
2023-06-05: Prova IEA.2
2023-06-07: IEA (13) [video]
- As idéias principais até agora, vistas no mundo dos grupos
- Teoremas vs Modelos
- As simetrias dum quadrado
- Classes de conjugações
- Hom, End, Aut, Inn, e prefixos de morfismos
- Cuidados sobre teoremas de outras teorias
- Como considerar leis como parte da estrutura
- Teaser FMC3: álgebra universal
- Magma, Semigrupo, Monóide, Grupo, Abel
- Galois e Abel
- potências e generalização para operar em listas
- Tentando aproveitar critéria
- Anéis
- Convenções sintácticas sobre anéis
- Anéis comutativos, Rngs, e Rigs
- Homomorfismo de anéis
- Subanéis
2023-06-12: CFR2 (3): Enter Cantor [video]
- minisermão
- sobre Cantor
- comparação de cardinalidades
- cardinalidade de conjuntos finitos recursivamente
- definição de equinumerosidade e outras comparações de cardinalidades
- conjuntos contáveis/(d)enumeráveis
- setup do jogo imortal de adivinhar
- uns conjuntos contáveis: ℕ, ℤ, ℕ×ℕ, ℚ, ℘f ℕ, A*, ℕ*, ℘f℘f ℕ
- (=c) é relação de equivalência
- lemma sobre ℘f
- a dupla abstração de Cantor
- primeiro argumento diagonal de Cantor
- cuidado sobre intuições sobre conjuntos finitos
- o conjunto dos algébricos é contável
- o segundo argumento diagonal de Cantor
- um conjunto incontável
- Plicker: para quantas dessas operações a (=c) é uma congruência?: ℘f,⋃,⋂
2023-06-14: CFR2 (4) & IEA (14): CATS 🐱 (1) [video]
- O que é uma categoria: dados (interface) e leis
- Exemplos de categorias
- Categoria a partir dum monóide
- Categoria a partir duma estrutura algébrica (𝐌𝐚𝐠𝐦𝐚, 𝐒𝐞𝐦𝐢𝐠𝐫𝐨𝐮𝐩, 𝐌𝐨𝐧𝐨𝐢𝐝, 𝐆𝐫𝐨𝐮𝐩, 𝐀𝐛𝐞𝐥, 𝐑𝐢𝐧𝐠, …)
- As categorias 𝟘, 𝟙, 𝟚
- Categoria a partir duma preordem
- Definições categoriais
- Objeto terminal
- Objeto inicial
2023-06-16: CFR2 (5) & IEA (15): CATS 🐱 (2) [video]
- Definição de categoria (recap)
- Exemplos (antigos e novos)
- categorias magras (thin)
- categorias discretas
- categorias a partir de linguagens de programação
- categorias a partir de sistemas de lógica
- objetos: terminal; inicial; zero
- setas: (split) mono; (split) epi; iso
- objetos isômorfos
- Θ. os terminais são isômorfos
- categoria oposta e o princípio da dualidade
- conceitos «self-dual»
- presente da dualidade: Θ (gratuito). os iniciais são isômorfos
- produto e coproduto de dois objetos
- traduzindo e procurando produtos e coprodutos em umas categorias
- abuso do artigo definido
- diagram chasing
- Plicker: tem produtos e coprodutos na categoria 𝐆𝐫𝐨𝐮𝐩?
2023-06-19: CFR2 (6) & IEA (16): CATS 🐱 (3) [video]
- Propriedades universais
- (≅) é uma relação de equivalência
- Uma categoria com setas matrizes
- (Re)definindo monóides, grupos, grupóides
- A categoria das setas de ℂ
- As categorias “comma”: slice ou over (ℂ/C); coslice ou under (C/ℂ)
- Functors e a categoria 𝐂𝐚𝐭
- Functors em programação funcional
- O que seriam setas entre functors?
- Plicker: A × 1 ≅ A? A × 0 ≅ 0?
2023-06-21: CFR2 (7): Cantor [video]
- recap sobre o mundo a.C.-vs-d.C.
- duas questões sobre a (≤c):
- Q. (∀A,B:Set)[ A ≤c B & B ≤ A ⇒ A =c B ]
- Q. (∀A,B:Set)[ A ≤c B ou B ≤c A ]
- enumeração; ser finito; ser infinito
- mais recap: conjuntos contáveis
- ℘ℕ =c (ℕ→{0,1})
- mais recap: o 2o argumento diagonal de Cantor
- ℝ é incontável
- algébricos vs transcendentais; racionais vs irracionais
- Θ. A ≨c ℘A
- ℝ =c ℝ×ℝ ?
- Plicker: votação sobre as duas questões sobre o (≤c)
2023-06-23: CFR2 (8): Cantor [video]
- A primeira demonstração de Cantor sobre a incontabilidade do ℝ (1874)
- Θ. (Bernstein, aka CBS) (casamentos)
- Θ. (Bernstein, aka CBS) (sem amor)
- Injeções vistas como codificações
- Θ. (Cantor, aka diagonal) (com depressão)
- Continuum Hypothesis e sua generalização
- Uma carta de Cantor para Dedekind
2023-06-26: CFR2 (9): Cantor; Relações [video]
- O conjunto de Cantor
- Comparando intervalos sem e com CBS
- Numeros transfinitos: cardinais e ordinais
- alephs (ℵ) e beths (ℶ)
- Relações
- Composição de relações
- Usando relações para implementar funções
- Adjectivos (propriedades) sobre relações
- Préordens e ordens
- Partições e relações de equivalência
- Mais adjectivos: irreflexividade; assimetria; …
- Diagramas internos de relações binárias
- Teaser sobre fechos de relações a partir de propriedades
- Fechos: a ordem de aplicá-los importa?
2023-06-28: CFR2 (10): Relações; Russell; Zermelo [video]
- Relações de equivalência; partições; o conjunto quociente
- o conjunto quociente vs um conjunto quociente
- Fechos: bottom-up e top down
- Sobre a implementação de funções usando relações
- Q: podemos misturar relações de A para A e de A para B?
- Q: o que significa que RelEq’s e Partitions é a mesma coisa?
- O parádoxo de Russell
- Resoluções e Fundamentos de Matemática
- Uns minutos para a palavra de Zermelo
- Uma outra maneira de entender os axiomas duma teoria dos conjuntos
- Q: sobre o princípio da comprehensão geral
- Q: como que surgiu o Ø no ZF3 do nada?
- esquema axiomático vs axioma (Plicker)
2023-06-30: IEA (17): Estruturas Algébricas e mais [video]
- Recap: Noether, kernel, normal
- Recap: estruturas e axiomatizações usando apenas equações
- Ring, Rig, Rng, Distributividade (binária e nulária)
- Domínios de integridade e de cancelamento
- Corpos
- Corpos ordenados
- Corpos ordenados completos
- A unicidade do corpo ordenado completo (esboço)
- Q: outras estruturas? Reticulados, álgebras booleanas, …
2023-06-30: CFR2 (11): Computabilidade [video]
- Άριστος vs Βλαμμένος
2023-07-03: CFR2 (12): Medida e Integração; Cantor [video]
- Uma teaser sobre teoria das medidas
- Integrais: Riemann vs Lebesgue e Borel
- Devil’s staircase (função de Cantor)
- o Hypergame de Zwicker
2023-07-03: IEA (18): Teoremas de Representação; Módulos e espaços vetoriais [video]
- kernel ⇔ normal
- Teoremas de representação
- Um teorema de Cayley e um teorema de Cauchy
- Esboço da demonstração do teorema de Cayley
- Algebras Booleanas e o teorema de representação de Stone
- Aneis e Módulos; Corpos e Espaços Vetoriais
- Plicker: prontos pra provas?
2023-07-05: Prova CFR2.1 & Prova IEA.3
2023-07-07: CFR2 (13): ZF [video]
- Sobre ZF e fundamentos em geral
- Sobre FOL
- ZF2. Emptyset
- Predicados primitivos
- Como assim só tem conjuntos no universo?
- Refletindo sobre o culpado do paradoxo do Russell
- ZF3. Pairset
- Θ. Singleton
- ZF4${}_\varphi$. Separação (esquema)
- Russell: de paradoxo para teorema
- Outras abordagens por outras teorias de conjuntos
- ZFC, polêmicas, hipocrisia
- Conceitos definidos vs primitivos
- ZF5. Powerset
- Nossos conjuntos não são necessariamente coleções de objetos
- ZF6. Unionset
- Θ. bin-union (∪)
- Arvores de construções
- Θ. bin-inter (∩)
- fundamentos: implementações em termos de conjuntos
- tuplas, produto cartesiano, especifiação, o operador de Kuratowski
- Justificando a definição do ⟨,⟩ de Kuratowski
- Teaser: infinidade
2023-07-10: CFR2 (14): ZF; Ordens [video]
- A não-gratuidade do operator Kuratowski
- Relações e funções
- Mais operações binárias
- o desafio do (×)
- Classes (próprias) e operadores function-like (ou class functions)
- Conjuntos estruturados
- P(r)osets: préordens e ordens (parciais)
- preservação de relação e a categoria 𝐏𝐨𝐬𝐞𝐭
- ordem linear, diagramas de Hasse, e «covered-by»
- a categoria dos posets 𝐏𝐨𝐬𝐞𝐭
- um p(r)oset 𝒫 visto como categoria ℂ[𝒫]
- downset, upset
- upper bounds, lower bounds, mínimo, máximo, ⊥, ⊤
- investigando o poset visto como categoria
- iniciais e terminais num poset visto como uma categoria.
- melhor upper bound e melhor lower bound: lub/glb, join/meet, sup/inf, ∨/∧
2023-07-12: CFR2 (15): ZF [video]
- Tentando vender ZF(C) como fundamentos
- Dedekind-infinito
- Sucessor de conjunto (Zermelo, von Neumann)
- ZF7. Infinidade
- Interseção de famílias vazias
- Possível lixo no I e como jogá-lo fora
- Θ. Existência dos naturais
- Θ. Unicidade dos naturais
- Θ. Teorema da recursão
- funções parciais; aproximações; compatibilidade
2023-07-14: CFR2 (16): ZF; Ordens [video]
- Naturais, recursão, indução
- Construindo os inteiros
- Construindo os racionais
- Construindo os reais (à la Cantor)
- Construindo os reais (à la Dedekind)
- ZF8. Replacement (scheme)
- ZF9. Foundation
- Antifoundation axioms
- P(r)osets gratuitos e construções
- poset oposto, discreto, flat
- lift de poset
- desafio: união disjunta, produto, espaço de funções, etc.
2023-07-17: CFR2 (17) & IEA (19): Reticulados [video]
- joins e meets (gerais e binários)
- Reticulados como posets
- Reticulados como algebras
- Misturando algebra e ordem em demonstrações
- Reticulados cotados
- Reticulados booleanos (álgebras booleanas) e aneis booleanos
2023-07-19: IEA (20): Livres e livremente gerados; Anel quociente [video]
- lembrete: subgrupo gerado por um subconjunto
- subreticulado gerado por um subconjunto
- reticulado livremente gerado por um conjunto
- monóide livremente gerado por um conjunto
- grupo livremente gerado por um conjunto
- teaser FMC3: álgebra universal
- teaser FMC3: álgebra de termos
- categorias to the rescue! (coiso livremente gerado)
- Aneis, ideais, anel quociente
Futuro (fluido)
Medley CFR2 em um universo paralelo
- relações bem fundadas e indução
- noções de computabilidade
- números computáveis
- ordinais e sua aritmética
- cardinais e sua aritmética
- álgebras booleanas e álgebras Heyting
- conjuntos estruturados interessantes (topologia, espaços métricos, normados, grafos, σ-algebras, espaços de medida …)
- axiomas de escolha
- comparabilidade de cardinalidades
- a hipótese do continuum
- fundamentos baseados em categorias e teorias dos tipos
- programação relacional (logic programming)
- bancos de dados relacionais