2020.2 FMC1, turmas de Thanos

Horários sincronizados: (quando tiver) será dentro dos 246T34 [14h55–16h35] 246N12 [18h45–20h25]
Contato:thanos@imd.ufrn.br
Playlists: FMC1 2019.2 (aulas gravadas)
TeX / LaTeX / ConTeXt (minicurso e sermões)
Monitoria/TA: fmc.imd.ufrn.br
Turmas anteriores: ..

Info

Pré-requisitos

É pré-requisito ter aprendido bem o conteudo das disciplinas de matemática do primeiro semestre., e (obviamente) do ensino médio também:

  • A Matemática do Ensino Médio, vol I de Lima, Carvalho, Wagner, Morgado (para esta disciplina os mais relevantes pré-requisitos são os Cap. 1–4)

(Obs.: aprenderpassar.)

Alem disso, é pré-requisito que os alunos matriculados tem tempo e vontade para estudar, fazer os trabalhos atribuídos, etc.

(Obs.: estudarler.)

ANTES de começar—é bom ler os:

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

Disclaimer. Eu suponho que os alunos desta turma verificaram os pré-requisitos da disciplina e assumam responsabilidade sobre o seu conhecimento. Lembrete:

pré-requisito

substantivo masculino

  1. condição prévia indispensável para se alcançar algo, seguir uma formação, fazer um curso, ocupar uma função etc.
  2. *(pedagogia)* num currículo, disciplina cursada obrigatoriamente antes de outra, por envolver conhecimentos prévios necessários ao estudo da segunda.

Conteúdo

Conteúdo transversal (durante todas as unidades)
Lógica proposicional e de predicados (linguagem; sintaxe e semântica). Definições e demonstrações. Demonstrações diretas e indiretas, refutações. Definições por recursão – provas por indução. Os números. A linguagem de funções.
Linguagem; Típos; (U0)
Crash course!
Logica, Demonstrações; Naturais, Recursão, Indução; (U1)
Teoria dos números; Análise combinatória (U2)
Teoria dos números (U3)

Bibliografia

(Conhece o libgen.rs?)

Principal

Auxiliar

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

Links

Dicas

Tecnologias e ferramentas necessárias

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. TeX / LaTeX / ConTeXt. (Online editor/compilador: Overleaf.)
  3. Um aparelho com câmera e uma ferramenta para escanear teu caderno
  4. Zulip: leia as instruções
  5. Google Meet
  6. O proof assistant Coq para algumas atividades. (Coq à la pastebin: CollaCoq.)
  7. Git e uma conta no github.
  8. Recomendado mas não necessário: um sistema Unix (Minicurso Unix 2019.2)

(Instalem e criem uma conta para usar onde necessário.)

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 é 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 via videochamada, em modo privado ou aberto. Se um aluno não consegue explicar o que ele mesmo escreveu numa resolução, será considerado plágio e o aluno será reprovado imediatamente por nota e por faltas.
  3. Participando, nunca dê uma resposta que tu não pensou sozinho.
  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 no cada homework. O único recurso aceitável para procurar ajuda é o nosso Zulip, especificamente seus canáis públicos (não DM).
  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.)

Avaliação e faltas

Disclaimer. Eu suponho que os alunos desta turma escolheram se matricular por interesse em aprender seu conteudo. 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 orais com videochamada em modo privado e/ou aberto; (ii) sua participação (que inclue correação de trabalhos de outros alunos); (iii) suas resoluções de problem sets escritas e submetidas em TeX/LaTeX/ConTeXt; (iv) caderno escaneado com resoluções de homeworks; (v) resoluções em algum proof assistant, possivelmente publicadas em repositório git

Note que:

  • Os problem sets / homeworks podem envolver simular uma prova escrita em tempo real.
  • 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 / Faltas

As presenças/faltas serão cadastradas baseadas na participação, na entrega dos trabalhos, e na entrega de caderno. Nenhuma dessas coisas é opcional, logo aluno que não as faz com a devida freqüência será reprovado por faltas.

FAQs

Dynamic content

Pontos

Pontos de participação

Problem Sets (PS)

Nenhum PS por enquanto.

Homework (HW)

Homeworks são atribuidos também: durante as aulas gravadas e no Slack.

Obs.:

  • Estudar um assunto dum livro obviamente inclui resolver todos os exercícios e problemas.
  • «Até» é sempre inclusivo.
  • Homeworks marcados assim são opcionais; considero o resto obrigatório.
  • Depois de cada aula, um homework é sempre válido, obrigatório, e essencial: sem olhar para teu caderno, defina todas as noções e demonstre TODOS os teoremas da aula;
    while (não conseguiu) {
      estude o assunto;
      tente novamente;
    }
    
  • Exceto quando é explicitamente pedido, faça os homework sem consultar nenhum livro/texto/etc. auxiliar
  • Para os trabalhos de SF1 precisarás o arquivo lf-20210117.tgz. Baixe e abra o arquivo no teu computador; cria um repositorio git nele, e fique trabalhando aí. Se precisar ajuda, use o #tech.

18/01/2021

  1. Capítulo 1: todo

19/01/2021

  1. [SF1]: Basics.v

20/01/2021

  1. Capítulo 2: até o primeiro intervalo de problemas.
  2. Capítulo 3: até a «atacando a estrutura lógica duma proposição»

22/01/2021

  1. Capítulo 2: dê uma lida no resto do capítulo sem se preocupar com os detalhes, mas resolva mesmo os exercícios do «2.62: Não-limitações».
  2. Π2.7; Π2.8; Π2.9.
  3. Capítulo 3: até § «real-life exemplos: divisibilidade» (use no teu rascunho o tabuleiro de Dados/Alvos, mas escreva separadamente o texto mesmo (o código) das suas demonstrações.

25/01/2021

  1. Capítulo 3: até o primeiro intervalo de problemas

28/01/2021

  1. Se convença que os ataques e os usos que encontramos até agora fazem todos sentido.
  2. Θ. O √2 é irracional
  3. Discutimos como «passar a negação por dentro» para proposições das formas
    ¬(∀x)[φ(x)]
    ¬(∃x)[φ(x)]
    mas não para proposições das formas
    ¬(∀x∈A)[φ(x)]
    ¬(∃x∈A)[φ(x)]
    Trate essas também em duas maneiras: (i) malandramente, reduzindo em outros casos que já tratamos; (ii) coraçãomente, argumentando diretamente com o que cada proposição dessas afirma mesmo.
  4. Suponha que A denota uma proposição que tu não tens o direito de saber qual é. Mesmo assim tente demonstrar cada uma das direções, com as «regras do jogo» que temos encontrado até agora. Lembre-se que seguimos a idéia de considerar qualquer ¬P como sinônimo de (P⇒⊥)
    • A ⇒ ¬¬A
    • ¬¬A ⇒ A

29/01/2021

  1. Demonstre sem olhar em nada que √2 é irracional
  2. √6 é irracional?
  3. ³√2 é irracional?
  4. Existem irracionais a,b tal que, aᵇ é racional?
  5. Sem pensar sobre nenhuma idéia nova, enuncie e demonstre uma generalização dos teoremas que demonstramos (sobre o √2 e o √3).

02/02/2021

  1. Capítulo 3: até o fim.

03/02/2021

  1. Investigue (demonstre ou refute): Cada número bonito tem raiz irracional.
  2. E o contrário? Cada número que tem raiz irracional é bonito?
  3. Tente demonstrar as duas conjecturas que encontramos na aula.
  4. para todo n natural, demonstre que existe número real √n construindo um segmento no plano cujo comprimento é √n.
  5. podes construir um segmento cujo comprimento é ³√2?

05/02/2021

  1. Capítulo «Os números naturais»: §47–48
  2. Podemos trocar o «S(n+m)» da (a2) por «Sn+m»?

06/02/2021

  1. Proposições de dupla negaço:
    1. P ⇒ ¬¬P
    2. ¬¬P ⇒ P
  2. A irrefutabilidade do LEM:
    1. ¬¬(P∨¬P)
  3. A lei de Peirce e sua versão “fraca”:
    1. ((P ⇒ Q) ⇒ P) ⇒ P
    2. ((P ⇒ Q) ⇒ P) ⇒ ¬¬P
  4. Proposições de interdefinabilidade dos ⇒,∨:
    1. (P ⇒ Q) ⇒ (¬P ∨ Q)
    2. (P ⇒ Q) ⇐ (¬P ∨ Q)
    3. (P ∨ Q) ⇒ (¬P ⇒ Q)
    4. (P ∨ Q) ⇐ (¬P ⇒ Q)
  5. Proposições de interdefinabilidade dos ∨,∧:
    1. P∨Q ⇒ ¬(¬P∧¬Q)
    2. P∨Q ⇐ ¬(¬P∧¬Q)
    3. P∧Q ⇒ ¬(¬P∨¬Q)
    4. P∧Q ⇐ ¬(¬P∨¬Q)
  6. As leis de De Morgan:
    1. ¬(P∨Q) ⇒ (¬P ∧ ¬Q)
    2. ¬(P∨Q) ⇐ (¬P ∧ ¬Q)
    3. ¬(P∧Q) ⇒ (¬Q ∨ ¬P)
    4. ¬(P∧Q) ⇐ (¬Q ∨ ¬P)
  7. Proposições de distributividade dos ∨,∧:
    1. P∧(Q∨R) ⇒ (P∧Q)∨(P∧R)
    2. P∧(Q∨R) ⇐ (P∧Q)∨(P∧R)
    3. P∨(Q∧R) ⇒ (P∨Q)∧(P∨R)
    4. P∨(Q∧R) ⇐ (P∨Q)∧(P∨R)
  8. As leis de De Morgan para ∃,∀:
    1. ¬(∀x)[φ(x)] ⇒ (∃x)[¬φ(x)]
    2. ¬(∀x)[φ(x)] ⇐ (∃x)[¬φ(x)]
    3. ¬(∃x)[φ(x)] ⇒ (∀x)[¬φ(x)]
    4. ¬(∃x)[φ(x)] ⇐ (∀x)[¬φ(x)]
  9. Proposições de interdefinabilidade dos ∃,∀:
    1. (∃x)[φ(x)] ⇒ ¬(∀x)[¬φ(x)]
    2. (∃x)[φ(x)] ⇐ ¬(∀x)[¬φ(x)]
    3. (∀x)[φ(x)] ⇒ ¬(∃x)[¬φ(x)]
    4. (∀x)[φ(x)] ⇐ ¬(∃x)[¬φ(x)]
  10. Proposições de distributividade de quantificadores:
    1. (∃x)[φ(x) ∧ ψ(x)] ⇒ (∃x)[φ(x)] ∧ (∃x)[ψ(x)]
    2. (∃x)[φ(x) ∧ ψ(x)] ⇐ (∃x)[φ(x)] ∧ (∃x)[ψ(x)]
    3. (∃x)[φ(x) ∨ ψ(x)] ⇒ (∃x)[φ(x)] ∨ (∃x)[ψ(x)]
    4. (∃x)[φ(x) ∨ ψ(x)] ⇐ (∃x)[φ(x)] ∨ (∃x)[ψ(x)]
    5. (∀x)[φ(x) ∧ ψ(x)] ⇒ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
    6. (∀x)[φ(x) ∧ ψ(x)] ⇐ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
    7. (∀x)[φ(x) ∨ ψ(x)] ⇒ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]
    8. (∀x)[φ(x) ∨ ψ(x)] ⇐ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]
    9. (∀x)[φ(x) ∧ ψ(x)] ⇒ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
    10. (∀x)[φ(x) ∧ ψ(x)] ⇐ (∀x)[φ(x)] ∧ (∀x)[ψ(x)]
    11. (∀x)[φ(x) ∨ ψ(x)] ⇒ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]
    12. (∀x)[φ(x) ∨ ψ(x)] ⇐ (∀x)[φ(x)] ∨ (∀x)[ψ(x)]

Para cada uma das proposições acima: (i) demonstre se for possível sem feitíços (lógica intuicionista); (ii) caso contrário demonstre se for possível com feitícos (lógica clássica); (iii) caso contrário refute dando um contraexemplo.

Os (i) e (ii) das 1–7, no Coq!

07/02/2021

  1. (cont.) Proposições de contraposição:
    1. (P ⇒ Q) ⇒ (¬Q ⇒ ¬P)
    2. (¬Q ⇒ ¬P) ⇒ (P ⇒ Q)

08/02/2021

  1. Capítulo «Os números naturais»: §49

10/02/2021

  1. Na aula a primeira tentativa de descrever a indução foi reduzindo nosso alvo para a Base (φ(0)) e para o (∃n)[φ(n)⇒φ(Sn)]. Mostrei um exemplo para argumentar que seria errado permitir essa regra no jogo, pois assim a gente poderia demonstrar a proposição «todo número natural é menor ou igual a 1». A gente poderia demonstrar também a proposição «todo número natural é igual a 0»?
  2. Capítulo «Os números naturais»: §§50–51
  3. [SF1]: Induction.v Estude a parte inicial do [SF1] mostrando apenas o uso de indução. Define as operações como temos nas aulas e no fmcbook, e demonstre os exercícios/problemas do cap.4 tanto no papel (texto humano) quanto no Coq. (Continuaremos o próprio Induction.v depois!)

12/02/2021

  1. Numa pasta diferente do SF1, crie uma nova pasta fmc1-coq. Nela crie o NatRecInd.v, e nele: implemente os nats e suas operações na maneira que temos definido no fmcbook/aulas, junto com as demonstrações das suas propriedades e os demais hw do capítulo.

13/02/2021

  1. Problemas: Π4.1

20/02/2021

  1. Na aula definimos somatório (e produtório) para seqüências finitas de números x₁,…,xₙ em tal forma que a expressão x₁+x₂+x₃+x₄ acabou sendo definida como a (((x₁+x₂)+x₃)+x₄). Redefina somatório e produtório em tal forma que x₁+x₂+x₃+x₄ acabará sendo definida como a (x₁+(x₂+(x₃+x₄))).
  2. Na indução «alternativa» de Andreon/Erickson que aceitamos, parece que nem precisamos demonstrar a base. No outro lado, na nossa primeira idéia, pareceu necessário demonstrar a base φ(8). Cadê a base agora?
  3. Mostre que não podemos supor que k>0 no passo indutivo, escolhendo uma proposição absurda que vira demonstrável com essa regra de indução que nos permite considerar que k>0 no passo indutivo. Ou seja: precisa definir uma afirmação φ(–) que é obviamente errada, e escrever uma demonstração que para todo n, φ(n), usando essa regra.

21/02/2021

  1. Até o primeiro intervalo de problemas.

23/02/2021

  1. Na aula descobrimos que a regra de indução «a partir dum número b» não é algo que precisamos aceitar como princípio (axioma) mas podemos inferir a partir do princípio da indução «original e oficial». Faça a mesma coisa para justificar a indução com mais que uma base. Primeiramente enuncie formalmente esse princípio, e depois mostre como reduzí-lo para o princípio de indução.
  2. Novamente: existem irracionais a,b tal que, aᵇ é racional?
  3. Ache uma outra maneira para justificar o princípio de indução de «a partir dum número b»

25/02/2021

  1. Podemos justificar («ganhar») o princípio da indução forte ou precisamos aceitar como princípio mesmo ?
  2. Podemos justificar («ganhar») o princípio da boa ordem ou precisamos aceitar como princípio mesmo?
  3. O 1/√2 é irracional?

Histórico

Vamos acompanhar as aulas gravadas de FMC1, e discutir no Slack.

18/01/2021: Aula 1: Introdução [video]

  • Apresentação dos assuntos principais
  • Os típos principais: proposições (tbm: afirmações); objetos (tbm: individuais)
  • Erros comuns
  • Type error
  • Erro de semântica
  • Diferença entre as duas frases:
    • «Se A, (então) B
    • «Como A, (logo) B
  • O significado da palavra «equivalente» em matemática
  • Noções primitivas – Definições
  • Axiomas – Teoremas
  • Sinônimos de «teorema» e seus usos: lema, corolário
  • Hipótese; tese
  • Programando programas vs. provando teoremas
  • Lemmata como funções e bibliotecas de programação
  • Árvores de derivação

20/01/2021: Aula 2: Introdução; Demonstrações [video]

  • Decepção e recap
  • implicação em matemática
  • «se» vs «somente se»
  • «necessário» vs «suficiente»
  • Erro: afirmação do conseqüente
  • Conjunção: como atacar e como usar
  • Um exemplo de demonstração e seu tabuleiro
  • Definições
  • contexto de definição
  • variáveis livres e ligadas
  • duas maneiras que uma definição pode ser errada
  • igualdade vs equivalência, com e sem «def»
  • declarar vs definir
  • Um exemplo de demonstração (cont.)
  • notação de conjuntos
  • Existência: como atacar e como usar

22/01/2021: Aula 3: Demonstrações [video]

  • Recap: açúcares sintácticos que já encontramos
  • (∃x∈A)[φ(x)] e (∀x∈A)[φ(x)] como açúcar sintáctico
  • Θ: todos os quadrados de ímpares são ímpares
  • «para algum» e CUIDADO: não use a «vírgula mágica», nem um «para» seco
  • propriedades de igualdade
  • «Calculamos»
  • D: divide
  • Θ: O 1 divide todos os inteiros
  • Θ: Cada inteiro divide ele mesmo

25/01/2021: Aula 4: Demonstrações [video]

  • Dois enunciados dum teorema: mesma coisa ou não?
  • Θ: (∀a∈ℤ)[a|0]
  • Demonstração errada: podemos inferir algo?
  • Θ: (∀a,b,x∈ℤ)[a|b ⇒ a|bx]
  • Como justificar uma coisa «obvia» de igualdade
  • Quantificadores consecutivos
  • Θ: (∀a,b∈ℤ)[a|b ⇒ (a|-b e -a|b)]
  • atacando conjunções
  • Utilizando teoremas demonstrados como lemmata
  • usando afirmações universais
  • Θ: (∀a,b,c∈ℤ)[(a|b e a|c) ⇒ a|b+c)]
  • mais uma justificação de algo «óbvio»
  • Θ: (∀a,b,c,x,y∈ℤ)[a|b e a|c ⇒ a|bx+cy]
  • usando implicações: modus ponens

27/01/2021: Aula 5: Demonstrações [video]

  • Θ: (∀a,b,c∈ℤ)[a|b e b|c ⇒ a|c]
  • Stocktaking/bookkeeping
  • Disjunção: como atacar
  • Separação em casos
  • LEM (Law of Excluded Middle)
  • Resumindo numa maneira mais humana
  • Disjunção: como usar
  • Uma resposta malandra
  • Uma resposta direta
  • Tratando negação
  • A ⇐?⇒ ¬¬A
  • Como usar
  • Θ: O √2 é irracional
  • D: (ir)racional
  • D: √2
  • «aquele … que …»

29/01/2021: Aula 6: irracionalidade [video]

  • Θ: O √2 é irracional
  • «aquele … tal …»
  • existência e unicidade
  • um enunciado errado de lemma
  • um enunciado dum lemma que não nos ajuda
  • um enunciado dum lemma que nos ajuda sim
  • implicação: outra maneira para atacar
  • a contrapositiva de implicação
  • uma demonstração com erros
  • não confunda «tal que» com «e»
  • a importância enorme do que demonstramos
  • Plicker: Wason’s test

01/02/2021: Aula 7: irracionalidade [video]

  • Recap: Θ: O √2 é irracional
  • perguntando nossas próprias perguntas
  • Θ? O √3 é irracional
  • tentando copiar «mutatis mutandis» uma demonstração
  • dois teoremas fortes que não demonstramos ainda
  • dificuldade: demonstrar ou refutar?
  • demonstrado o lema que queremos
  • o que ganhamos brincando com o 4
  • separando números em «times» a partir dum número-guia
  • separando em casos
  • cadê o problema com o lemma sobre o 4?
  • esse √3 é um número mesmo?
  • para quais números x o √x é racional?
  • umas questões sobre primos e raizes racionais
  • Plicker: o √6 é irracional?

03/02/2021: Aulas 8 & 9a: demonstrações; linguagens

  • Aula 8 [video]
    • Demonstrações
      • perguntando nossas próprias perguntas
      • generalizando um teorema
      • generalizando uma definição
      • perguntando o contrário
      • Plicker: as conjecturas da aula passada são verdadeiras?
      • sobre a redução ao absurdo
    • Linguagens
      • sintaxe vs semântica
      • definindo linguagens
      • gramáticas e notação BNF
      • erro de ética: escolhe nomes bons e honestos
      • dígito vs numeral vs número
      • convenções e açúcar sintáctico
      • linguagens com variáveis
      • «arbitrariamente grande»
      • metalinguagem e metavariáveis
  • Aula 9a [video] (até o 00:36:59)
    • Demonstrações
      • Dupla negação
      • Como demonstrar que √n é definido para cada n natural
      • Plicker: o ³√2 é irracional?

05/02/2021: Aula 9b: Demonstrações; Naturais, recursão, indução [video]

  • Nat(urais): uma definição humana
  • um acordo sobre afirmações com (meta)variáveis não declaradas
  • voltando: variável vs metavariável
  • Nat(urais): uma definição com gramática
  • Nat(urais): uma definição com regras de inferência
  • Um açúcar sintáctico
  • os valores canônicos de Nats
  • função vs construtor
  • Numerais diferentes
  • Spoiler/trailer: seqüências, funções, FMC2
  • Igualdade
  • cuidado: os «para todo» e «existe»
  • Recursão
  • 2+3=5
  • Resumo: o que aconteceu

08/02/2021: Aula 10: Naturais, recursão, indução [video]

  • Recap: Nat(urais)
  • Recursão vs tijolo
  • Calculando a soma com recursão
  • onde focar para reduzir?
  • Multiplicação
  • 2 · 3 = 6
  • qual resultado incompleto é melhor?
  • precedência e associatividade de operadores
  • Θ. Associatividade da +
  • Plicker: tem como continuar a demonstração?
  • escolhendo variáveis com «linhas»: x’, x’’, etc.
  • o problema que temos demonstrando esse teorema

10/02/2021: Aula 11: Naturais, recursão, indução [video]

  • Recap: tentativa de demonstrar
  • a recursão foi no segundo argumento, então…
  • «para ALGUM»
  • Recursão – Indução
  • Indução
  • quando podemos usar indução
  • indução informalmente
  • indução expressa com conjunto
  • «conjunto fechado por…»
  • Esqueçam a receitinha de 3 passos!
  • Indução como regra de inferência
  • «Base» e «Passo indutivo»
  • a regra de indução na verdade é um esquema
  • indução para demonstrar nosso teorema atual
  • «hipótese indutiva»
  • Como podemos continuar agora?
  • Briga: poluição do estado com novos nomes novos «para abreviar»
  • Podemos continuar assim também!
  • continuando a demonstração
  • presente da recursão vs presente da indução
  • continuando a demonstração
  • Algo que NÃO é supor o próprio alvo!
  • Donde chegou essa paréntese?
  • continuando o cálculo
  • donde chegou essa paréntese?
  • propriedades de igualdade
  • o que aconteceu
  • E se eu nem precisei usar a hipótese indutiva?
  • Plicker: Faz diferença se escolher usar indução mais cedo?

13/02/2021: Aula 12: Naturais, recursão, indução [video]

  • exponenciação
  • recap: associatividade da +
  • tentar começar «por indução»
  • Plicker: melhor, pior, ou mesma coisa?
  • «por indução no z»
  • podemos trocar quantificadores consecutivos da mesma forma
  • discussão: comparação das duas demonstrações
  • comparando as H.I.’s
  • com a regra errada podemos demonstrar que todo natural é igual a 0?
  • drinker’s paradox
  • o que ganhamos
  • Θ: + é comutativa
  • 0 + 0 = 0 + 0 sem nem calcular
  • lemmas em demonstrações
  • comparação com programação
  • subinduções
  • lendo as H.I. «com palavras da rua»
  • escopos e escolhas de variáveis

15/02/2021: Aula 13: Naturais, recursão, indução [video]

  • Θ: + é comutativa: o esqueleto
  • escopos e as várias hipoteses indutivas
  • entender no coração, com palavras da rua
  • passo indutivo da segunda sub-indução
  • matemática é case-sensitive!
  • usando o ` ≟ ’
  • observações
  • adição, multiplicação, exponenciação, e depois?
  • Θ: · é associativa
  • lemmata em demonstrações
  • escolhendo nomes lindos para nossas variáveis
  • um erro no esboço da prova!
  • Plicker: Entendi tudo!

17/02/2021: Aula 14: Naturais, recursão, indução [video]

  • associativa vs associativa-a-esquerda/direita
  • generalizando operação binária para n-ária, com n≥0
  • seqüências finitas e infinitas, convenções com os «…»
  • off-by-one error
  • definição formal (recursiva) de somatório e produtório
  • como definir a «próxima» operação depois da exponenciação
  • indução «a partir dum númer positivo»
  • «vacuamente verdade»
  • Plicker: Posso assumir k>8?
  • Cadê a base?

23/02/2021: Aula 15: Naturais, recursão, indução [video]

  • justificando a regra de «indução a partir de» sem aceitar como princípio
  • o que significa ≤ ?
  • roubando usando língua, etimologia, notação, etc.
  • definindo relações recursivamente
  • programação declarativa: programação funcional e programação lógica
  • um lemma importante sobre a ≤
  • por que não podemos supor k>0 no passo indutivo?
  • descobrindo mais «princípios» relacionados
  • uns cuidados para tomar levantando de low-level para high-level
  • umas maneiras de definir a função fibonacci
  • definição dos números Lucas
  • como calcular valores dessas funções
  • exercício: L = ℓ
  • duas maneiras de organizar o passo indutivo
  • cuidado não escrever objetos não definidos!
  • quando uma base não é suficiente
  • Plicker: survey: tem irracionais a,b tais que aᵇ é racional?

25/02/2021: Aula 16: Naturais, recursão, indução [video]

  • tem irracionais a,b tais que aᵇ é racional?
  • NUNCA dê nenhum espaço desnecessário para teu inimigo!
  • 1/√2 é irracional? (fácil)
  • 2^(1/√2) é irracional? (difícil)
  • uma demonstração clássica
  • de SQL injection para lógica matemática
  • «abusando» o princípio da indução
  • ganhando a «indução a partir de»
  • maneiras diferentes de organizar uma demonstração por indução
  • princípio da indução original
  • princípio da indução com mais bases
  • ganhando a «indução com mais bases»
  • o que aconteceu?
  • dica: como começar sem saber se/qual indução vai precisar
  • indução forte
  • Plicker: tem base?
  • Q: podemos «ganhar» a partir da original?
  • dica de novo: como começar sem saber se/qual indução vai precisar
  • o princípio da boa ordem
  • Todos os naturais a partir de 8 podem ser escritos como somatório de 3s e 5s
  • uma dica seguindo um possível caminho

Futuro (fluido)

Aula 17: Naturais, recursão, indução [video]

  • indução forte
  • princípio da boa ordem (PBO)
  • como usar o PBO na prática
  • exemplo: não existem inteiros entre 0 e 1
  • entendendo o princípio da indução
  • indução e recursão: dois lados da mesma moeda
  • princípio da recursão
  • sobre implicação
  • Wason’s test com psicologia diferente
  • implicação material vs relevante
  • uma demonstração errada: cavalos e aniversários
  • triminôs: de prova por indução para um algoritmo
  • Plicker: uma recursão aninhada: quantas chamadas?

Aula 18: Naturais, recursão, indução; Teoria dos números [video]

  • o 1/√2 é racional?
  • soma e produto de (ir)racionais é (ir)racional?
  • Todas as potências de um ímpar são ímpares
  • escolhendo nomes de variáveis
  • podemos mexer com os quantificadores duma implicação?
  • onde roubei na «demonstração» dos aniversários
  • corolário simples do teorema dos triminôs
  • implicações entre PIF,PIFF,PBO
  • PBO ⇒ PIF
  • PIF ⇒ PIFF (dica)
  • PIF ⇒ PBO (dica)
  • Fortalecendo o enunciando: teorema de pontinhos
  • Plicker: de novo: quantas chamadas precisamos?

Aula 19: Sermão ; Resolução da Prova 1.1 [video]

  • Resolução da Prova 1.1 (A–E)
  • aridade
  • contexto de definição
  • não escreva: «sendo», «para x», «com»
  • português matemático
  • keywords low-level em demonstrações
  • «logo» vs «ou seja»
  • «existe» vs «seja»
  • «procuro …» vs sem nome
  • sobre cálculos e «calculamos»
  • proposição vs declaração
  • «suponha» vs «seja»
  • Reclamação: procurem usar seus recursos (compiladores humanos nesse caso)
  • onde e quando usar indução
  • uma resolução mais econômica
  • qual é a base?
  • somatório vazio
  • cuidado com indução: onde a quando?
  • essa vez o quando importa!
  • descreva tanto formalmente quanto com palavras de rua!
  • Plicker: Survey: ficou surpreso com tua nota?

Aula 20: Resolução da Prova 1.1 [video]

  • F. ∀n[ Aₙ é estritamente crescente ]
  • Plicker: Como começaria a demonstração?
  • Demonstração do F
  • G1. Enuncie a G2 e demonstre.
  • G2. ∀n∀x[ Aₙ(x) é menor que Aₙ₊₁(x) ]
  • E sobre o A₄?

Aula 21: Naturais, recursão, indução [video]

  • Θ. ∀n∀x[ Aₙ(Aₙ(x))<Aₙ₊₂(x) ]
  • Outras linguagens de númerais: Bin
  • Como definir operações no Bin
  • De sintaxe para semântica: um toque de semântica denotacional

Aula 22: Naturais, recursão, indução ; Análise combinatória [video]

  • sistemas posicionais de numerais
  • bin, oct, dec, hex, …
  • Θ. (∀b≥1)[b serve como base dum sistema posicional de numerais]
  • ou seja: (∀b≥1)(∀x)(∃n≥0)(∃c₀,…,cₙ)[x = Σcᵢbⁱ]
  • qual a restrição nos coeficientes?
  • A linguagem Bin dos numerais binários
  • qual o problema com aquela que usa BB ?
  • Enunciando a corretude do sucessor que definimos nos Bins
  • diagrama comutativo: nosso primeiro
  • Como demonstrar a corretude
  • donde que chegou o princípio da indução mesmo?
  • o princípio da indução (e da recursão) no Bin
  • Roubamos usando operações dos naturais?
  • Basta só demonstrar por indução
  • quais são as hipoteses indutivas?
  • o que observamos sobre a gramática que bota os bits no início?
  • como podemos definir (nativamente) a semântica e como o sucessor?
  • Umas gramáticas que não geram numerais com «leading zeros»
  • Como vamos trabalhar estudando teoria dos números
  • Um toque de análise combinatória
  • o que se trata
  • princípio da adição e da multiplicação
  • erros comuns
  • Plicker: temos confiança?

Aula 23: Análise combinatória [video]

  • princípios da adição e multiplicação
  • derivando o princípio da multiplicação a partir o princípio da adição
  • quando (não) podemos adicionar
  • quando (não) podemos multiplicar
  • quantas palavras ordenadas
  • permutações e combinações
  • definição com palavras de contagem
  • chegando em fórmulas (definições equivalentes)
  • Ptot(n)
  • P(n,k)
  • off-by-one!
  • C(n,k): hipercotando via P(n,k); e com recursão
  • demonstrações com argumentos combinatórios
  • Q: como 10 amigos podem viajar com um carro?
  • contando com idéias diferentes
  • Q: como ir de casa para o trabalho?
  • modelando/traduzindo fielmente a pergunta para outra
  • ∀n∀k[ C(n,k) = C(n,n-k) ]
  • Q: e se quiser evitar uma rua?
  • as vezes é mais fácil contar o complemento
  • Q: como sentar num bar?
  • Q: como sentar numa mesa redonda?
  • Q: como sentar num bar, mas agora com brigados
  • Q: permutar as letras da palavra PESSIMISSIMO
  • Plicker: a gente sabia quanto % dessa aula?

Aula 24: Naturais, indução, recursão ; Análise combinatória [video]

  • como definir semântica na gramática dos binários que bota os bits na frente
  • No(ta)ções de conjuntos
  • interface de conjunto
  • operações: união ; intersecção ; diferença
  • subconjunto (próprio)
  • set-builder (comprehensão)
  • igualdade de conjuntos
  • cuidado com os símbolos ‘⊂’ e ‘⊈’
  • Q: quantos subconjuntos?
  • o conjunto vazio
  • usando o princípio da adição
  • usando uma tradução (modelo)
  • a recursão do C(n,k)
  • como calcular
  • (x+y)ⁿ
  • entendendo o teorema binominal
  • contando recursivamente: Aleco e Bego
  • a palavra «respectivamente»
  • Plicker: quais são as bases da recursão?

Aula 25: Análise combinatória [video]

  • contando recursivamente: Aleco e Bego
  • oportunidade de homework!
  • probabilidade elementária
  • de-caso-pro-trampo recursivamente
  • floor e ceiling
  • recursando mais rapido
  • nomear e conquistar
  • o mago Xyzzy e seus lemmings
  • Θ. o teorema binominal
  • quatro perguntas de contagem
  • Monty Hall
  • plicker: avg(HTH) vs avg(HTT)

Aula 26: Análise combinatória ; teoria dos números [video]

  • análise combinatória
    • de Aleco para Fibonacci
    • palavras do {+,-} sem “–”
    • olhando para o triângulo de Pascal
    • resolução de equações com restrições: (i) positivos; (ii) não-negativos
    • Umas aplicações do teorema binominal
    • Torres do Hanoi
    • O problema de Josephus
  • teoria dos números
    • quebrando os números até chegar em tijolos
    • com cimento a adição
    • com cimento a multiplicação
    • Θ (Euclides). existe uma infinidade de primos
    • discussão curta sobre os homeworks da probabilidade
    • lemma da divisão de Euclides
    • D: conjunto fechado por operação
    • Θ: Se um conjunto S de inteiros é fechado pelas + e -, então ou S = {0} ou S = {md | m∈ℤ}
    • Θ: não existe inteiro entre 0 e 1
    • Plicker: Presente?

Aula 27: Teoria dos números ; Prova 2.X [video]

  • discussão: torres de Hanoi
  • presente da recursão no coração
  • Θ: propriedades de divisibilidade
  • D: Conjunto fechado por operação
  • o vazio é fechado por qualquer operação
  • Θ: o lemma da divisão de Euclides
  • importância e como usar
  • dica para demonstrar
  • Θ: S≠Ø e S fechado pelas + e - ⇒ S={0} ou
  • Θ: Se um conjunto S de inteiros é fechado pelas + e -, então ou S = {0} ou S = {md | m∈ℤ}
  • Plicker: o paradoxo da surpresa
  • Prova (surpresa) 2.X

Aula 28: Teoria dos números [video]

  • Θ: conjuntos fechados pelas +,-
  • a idéia da demonstração
  • A1: justificar o uso da PBO
  • como atacar igualdade de conjuntos
  • A2: o S tem todos os múltiplos de d
  • A3: o S não tem lixo: (nada mais exceto múltiplos de d)
  • Um princípio de indução para inteiors
  • Lemma de divisão de Euclides
  • existência
  • como atacar a unicidade
  • relações de ordem
  • mdc (maior divisor comum)
  • Definição de mdc (com erros)
  • 0|x? x|0?
  • a|b vs a/b
  • existência de tal objeto
  • unicidade de tal objeto
  • artigo definido vs artigo indefinido
  • Θ. existe unico m.d.c. não negativo
  • dica para demonstrar
  • Plicker: d|ab ⇐?⇒ (d|a ou d|b)

Aula 29: Teoria dos números [video]

  • d|ab ⇒ (d|a ou d|b)
  • refutação de: «para todo …»
  • refutação de: implicação
  • refutação de: disjunção
  • d|ab ⇐ (d|a ou d|b)
  • «similar»?
  • Palpite: p|ab ⇒ (p|a ou p|b)
  • os números primos
  • D: m.d.c.
  • cuidados com definições
  • artigo «definido» vs «indefinido»
  • obrigações para introduzir notação (de operação)
  • Existência e unicidade
  • Existe um m.d.c.
  • Lemma (da Prova 2.X)
  • Existe um m.d.c [cont.]
  • o conjunto S das combinações lineares dos a,b não é vazio
  • S é fechado pela -
  • o d que ganhamos (graças ao Lemma 2X) é o que procuramos
  • unicidade «módulo módulos»
  • o que ganhamos?
  • os coeficientes não são determinados pelos a,b
  • uma maneira de mostrar que (a,b) = (c,d)
  • a|b ⇒ (a,b) = a
  • (a,0) = a
  • Plicker: os (a,b), (-a,b), (b,a) são todos iguais? (a,b) =?= (a,a+b)

Aula 30: Teoria dos números [video]

  • Recap
  • lemma da divisão de Euclides
  • «sem perda de generalidade»
  • notações: comdiv(–,–) e divs(–)
  • novamente: uma maneira de mostrar que (a,b) = (c,d)
  • (a,b) = (-a,b) = (b,a) [= (a,-b) = (-a,-b)]
  • (a,b) = (a,a+b)
  • (a,b) = (a,ax+b)
  • em geral (a,b) ≠ (a,a+by)
  • D: primo e composto
  • «exatamente»
  • Lemma de Euclides: p|ab ⇒ p|a ou p|b
  • Teorema fundamental de aritmética
  • existência
  • uma demonstração errada da unicidade
  • inteiros positivos como lista finita de naturais
  • o que acontece se trocar os naturais por inteiros?
  • Plicker: a|m e b|m ⇐?⇒ ab|m

Aula 31: Teoria dos números [video]

  • Θ: lemma da divisão de Euclides
  • existência
  • unicidade
  • algoritmo
  • Corolários do lemma de Euclides
  • representação de inteiros como listas finitas de naturais
  • o algoritmo de Euclides
  • corretude
  • eficiência do algoritmo
  • um exemplo: (252,180)
  • metodo da criança brasileira
  • algoritmo de Euclides: ainda mais legal
  • algoritmo de Euclides: terminação
  • Erdős: «The Book»
  • Θ: teorema de Euclides: infinidade de primos
  • Plicker: (ab,ac) =?= a(b,c)

Aula 32: Teoria dos números [video]

  • (ab,ac) = |a|(b,c)
  • sobre a eficiência do algoritmo de Euclides
  • sobre o teorema fundamental da aritmética
  • unicidade
  • Θ (Euclides): tem uma infinidade de primos
  • a distribuição dos primos
  • a conjectura de primos gêmeos
  • entre n e n! tem primo
  • prime gaps
  • para todo n, existem n consecutivos compostos
  • crivo de Eratosthenes
  • quando eu paro?
  • menor múltiplo comum (lcm(–,–) ou [–,–])
  • desenhando os inteiros não-negativos a partir da ordem |
  • ab = a,b
  • o que precisamos demonstrar para justificar a definição?
  • lcm e gcd a partir de fatorização em primos
  • o teorema dos números primos
  • uma viagem sobre tamanhos e distâncias baseadas em primos
  • Plicker: p-valuações dos (a,b) e [a,b] em termos das p-valuações dos a e b[01:35:53]

Aula 33: Teoria dos números; Prova 2.Y [video]

  • Dicas sobre os homeworks
  • Existem ℓ consecutivos compostos
  • Formalizando o enunciado
  • idéias para não seguir e uma dica
  • Existe primo entre n e n!
  • Θ: b-expansão de números
  • enunciado e sua tradução
  • Prova 2.Y: demonstre!
  • dica
  • rascunho de demonstração
  • Plicker: Tô aqui!

Aula 34: Teoria dos números ; Prova 2.Z [video]

  • Existem ℓ consecutivos compostos
  • A conjectura dos primos gêmeos
  • A conjectura de Goldbach
  • fraca ⇐ forte
  • gcd(89,55)
  • (m,n)=1 e mn quadrado ⇒ m,n quadrados
  • entre n e n! tem primo
  • outros homeworks
  • Prova 2.Z: unicidade
  • princípio da boa ordem e indução forte
  • não par vs ímpar
  • congruência módulo m
  • rem(–,–) e quot(–,–)
  • mod binário vs mod de congruência
  • uso da palavra «módulo»
  • Plicker: Tô aqui!

Aula 35: Teoria dos números [video]

  • Correção da Prova 2.1
    • D2. k|n!
    • E1. escolher j de n interios sem nenhum par de consecutivos
    • E2. 5 = 29x + 18y
    • F. consecutivos Fibonacci são coprimos
    • G.
    • I. um critério de gcd
    • Dica: J. o algoritmo de Euclides e Fibonacci
  • Classes e congruência módulo m
  • [a]ₘ
  • três propriedades de congruência módulo m
  • congruência: de ternária para binária
  • reflexividade
  • transitividade
  • simetria
  • os ℤₘ e sua aritmética
  • os nomes dos membros de ℤₘ
  • o que preciso fazer para definir uma operação: tabelas
  • operação «mal-definida»
  • uma outra maneira de pensar sobre a aritmética dos ℤₘ
  • a tabela da adição do ℤ₄
  • um mal-entendido comum
  • a tabela da multiplicação do ℤ₄
  • como inferir comutatividade pela tabela
  • tem x,y com xy = 0 sem nem x=0 nem y=0
  • 2x = 1 tem resolução, ou seja, o 2 tem inverso, ou seja, temos 2⁻¹, ou seja, temos 1/2
  • Plicker: : numa congruência, podemos cancelar na multiplicação?

Aula 36: Teoria dos números [video]

  • Correção da Prova 2.1, J: Euclides e Fibonacci
  • Congruências e aritmética modular
  • Tabelas de adição e multiplicação
  • como denotar os objetos de ℤ₂
  • propriedades de adição e multiplicação modular
  • op-identidade
  • op-inverso de número
  • «oposto» (+-inverso) e «inverso» (·-inverso)
  • «quém é» o (-1)?
  • «quém é» o (-k)?
  • comparando quatro «mundos» de aritmética: ℤ, ℤ₅, ℤ₆, ℤ₇
  • inversos
  • zerodivisores
  • cancelamento
  • lei de cancelamento módulo m
  • treta: não podemos esquecer as ferramentas que já demonstramos!
  • O que ganhamos?
  • Corolário: cancelação nos ℤₚ
  • resolução de «equações» e números invertíveis no ℤₘ
  • inversos ⇒ cancelamento
  • de equação para congruência
  • definição «perigosa» e operação «mal-definida»
  • Plicker: Tô aqui

Aula 37: Teoria dos números [video]

  • p | C(p,r)?
  • definição «perigosa» e operação «mal-definida»
  • adição
  • multiplicação
  • exponenciação??
  • inversos e cancelamento
  • «único módulo m»
  • Resolução da ax≡b (mod m)
  • Todo composto a possui divisor primo p com p≤√a
  • sistemas de congruências
  • Plicker: Tô aqui

Aula 38: Teoria dos números [video]

  • decepção
  • dois exercícios com números consecutivos e módulos
  • qualquer inteiro da forma 3k+2 tem primo divisor da mesma forma
  • «número da forma mk+r»
  • primos da forma 4n+3
  • lembrete: teorema de Euclides
  • teorema de Dirichlet
  • teorema de Fermat
  • o «sonho de calouro»
  • teorema de Fermat: demonstração
  • um sistema de duas congruências
  • como achar inversos
  • únicidade
  • Plicker: Tô aqui

Aula 39: Teoria dos números [video]

  • recap
    • teorema de Fermat
    • sonho de calouro
    • Resolução da ax≡b (mod m)
    • sistema de duas congruências x≡bᵢ (mod mᵢ)
  • exemplo com três congruências
  • «dois-a-dois»
  • teorema chinês dos restos
  • correspondência entre k-tuplas de (bᵢ)ᵢ e resoluções (mod M)
  • Critéria de divisibilidade
  • por 3
  • por 9
  • por 11
  • Pensando na aⁿ≡a (mod n)
  • Plicker: Tô aqui

Aula 40: Teoria dos números [video]

  • sobre n+1 inteiros entre 1 e 2n
  • princípio de casa do pombo
  • lembrete de homework: eficiência de Euclides
  • Θ. Chinês e uns casos mais gerais
  • Fermat e potências positivas de números módulo m
  • A função φ de Euler
  • 4 teoremas sobre φ
  • φ(pᵃ) = pᵃ-pᵃ⁻¹
  • n ≥ 3 ⇒ φ(n) par
  • Plicker: Tô aqui

Aula 41: Teoria dos números [video]

  • eficiência do algoritmo de Euclides
  • Teorema de Fermat e testes de primalidade
  • Um lemma sobre (mod p) e (mod q)
  • x²≡1 (mod p)
  • Θ. Wilson (na vdd Lagrange)
  • Fermat para refutar primalidade
  • exponenciando quadrando repetitivamente
  • Fermat para achar primos
  • φ é multiplicativa: uma dica
  • Plicker: o converso de Wilson é válido?

Aula 42: Teoria dos números [video]

  • hipótese chinesa vs primalidade Fermat
  • pseudoprimos
  • sistemas de resíduos
  • φ é multiplicativa
  • como tomar arbitrario membro dum conjunto indexado
  • cuidado: não vale nada concluir coisas a partir do teu alvo
  • cuidado: contrapositivas e justificativas
  • φ é ainda difícil para calcular: fatorização
  • de Fermat para Euler
  • dum exemplo para a segunda demonstração (também de Euler)
  • o exemplo que nos levará para a terceira demonstração foi cortado no vídeo; vou repetir na próxima aula :(
  • Plicker: Tô aqui

Aula 43: Teoria dos números [video]

  • números Carmichael
  • 561
  • exponenciação módulo m
  • Lemmata sobre sistemas de residuos
  • O ⇐ de Wilson
  • mentalidade de escuridão
  • fofocas
  • demonstração
  • comprando os critérios de primalidade: Fermat vs Wilson
  • Fermat para computar inversos modulo m
  • choque: logaritmos!
  • ax≡b (mod m)
  • Teorema de Euler
  • dica e investigação com uns exemplos com ajuda por Haskell
  • Plicker: Tô aqui

Aula 44: Teoria dos números [video]

  • Correção da Prova 3.1
  • Lema de enganadores de Fermat
  • Teorema de Euler

Aula 45: Criptografia [video]

Aula 46: Criptografia [video]

Last update: Thu Feb 25 22:26:45 -03 2021