2021.1 FMC1, turma de Thanos

Horários sincronizados: (quando tiver) será dentro dos 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. Possivelmente usaremos outros proof assistants e linguagens de programação também.
  8. Git e uma conta no github ou gitlab.
  9. Muito recomendado mas não necessário: um sistema Unix (Minicurso Unix 2019.2)
  10. Muito recomendado mas não necessário: (neo)vim e Emacs

(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 em 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)

U1

Homework (HW)

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

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-20210607.tgz. Baixe e abra o arquivo no teu computador; cria um repositorio git nele, e fique trabalhando aí. Se precisar ajuda, use o #tech.

08/06/2021

  1. Capítulo 1: todo
  2. [SF1]: Basics.v

09/06/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»

11/06/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.

14/06/2021

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

16/06/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)] e ¬(∃x)[φ(x)]
    mas não para proposições das formas
    ¬(∀x∈A)[φ(x)] e ¬(∃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

17/06/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).

18/06/2021

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

21/06/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?

23/06/2021

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

25/06/2021

  1. Capítulo «Os números naturais»: § Provando propriedades de naturais sem indução.

29/06/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. § Indução
  3. § Demonstrando propriedades de naturais com indução
  4. [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!)
  5. 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.

01/07/2021

  1. Proposições de dupla negaço:
    1. P ⇒ ¬¬P
    2. ¬¬P ⇒ P
  2. Comutatividade dos ∨,∧:
    1. (P ∨ Q) ⇒ (Q ∨ P)
    2. (P ∧ Q) ⇒ (Q ∧ P)
  3. 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)
  4. Proposições de contraposição:
    1. (P ⇒ Q) ⇒ (¬Q ⇒ ¬P)
    2. (¬Q ⇒ ¬P) ⇒ (P ⇒ Q)
  5. A irrefutabilidade do LEM:
    1. ¬¬(P∨¬P)
  6. A lei de Peirce e sua versão “fraca”:
    1. ((P ⇒ Q) ⇒ P) ⇒ P
    2. ((P ⇒ Q) ⇒ P) ⇒ ¬¬P
  7. 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)
  8. As leis de De Morgan para ∨,∧:
    1. ¬(P∨Q) ⇒ (¬P ∧ ¬Q)
    2. ¬(P∨Q) ⇐ (¬P ∧ ¬Q)
    3. ¬(P∧Q) ⇒ (¬Q ∨ ¬P)
    4. ¬(P∧Q) ⇐ (¬Q ∨ ¬P)
  9. 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)
  10. Currificação
    1. ((P∧Q)⇒R) ⇒ (P⇒(Q⇒R))
    2. ((P∧Q)⇒R) ⇐ (P⇒(Q⇒R))
  11. Reflexividade da ⇒:
    1. P ⇒ P
  12. Weakening and contraction:
    1. P ⇒ (P∨Q)
    2. Q ⇒ (P∨Q)
    3. (P∧Q) ⇒ P
    4. (P∧Q) ⇒ Q
    5. P ⇒ (P∧P)
    6. (P∨P) ⇒ P
  13. 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)]
  14. 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)]
  15. 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)]

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) num proof assistant (Coq, Agda, ou Lean).

02/07/2021

  1. Jogue o The Natural Numbers Game. (Até o fim!)

06/07/2021

  1. Problemas: Π4.1

08/07/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.
  4. Até o primeiro intervalo de problemas.

14/07/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»
  4. Podemos justificar («ganhar») o princípio da indução forte ou precisamos aceitar como princípio mesmo ?
  5. Podemos justificar («ganhar») o princípio da boa ordem ou precisamos aceitar como princípio mesmo?
  6. O 1/√2 é irracional?
  7. Escreva um programa copiando fielmente a definicao da função A que definimos no plicker. Use para calcular os valores A(3,2) e A(7,5). Modifique teu código para contar quantas vezes a função A foi chamada, e quantas delas foram com argumentos novos.
  8. Tente estabelecer implicações entre os princípios PBO, PIF, e PIFF.
  9. Onde robei na «demonstração» dos aniversários/cavalos?
  10. Demonstre que todas as potências de qualquer ímpar são números ímpares também.

18/07/2021

  1. Dado a (ir)racionalidade do α e/ou do β podemos concluir algo sobre a (ir)racionalidade dos αβ ou α+β?
  2. Termine as direcções PIF⇒PBO e PIF⇒PIFF
  3. Resolva sozinho e sem consultar nada toda a Prova 1.1 do 2019.2, simulando as escolhas e as limitações de tempo e de espaço, tudo isso no teu caderno.
  4. Resolva o resto (que não conseguiu resolver dentro do tempo em modo simulação-de-prova).
  5. G. Tendo resolvido a F, qual seria a próxima proposição para investigar sobre a função A? Enuncie claramente.
  6. Demonstre.

20/07/2021

  1. H. ∀n∀x[ Aₙ(Aₙ(x))<Aₙ₊₂(x) ]

27/07/2021

  1. Capítulo «Os números naturais»: todo
  2. Qual o problema com a gramática seguinte?:
    B ::= 0 | 1 | BB
    
  3. Tem algum problema com a gramática seguinte?:
    B ::= 0 | 1 | 0B | 1B
    
    Se não, defina a operação (–)⁺ de sucessor nessa linguagem.
  4. Dá pra definir gramática que não gera numeráis com «leading zeros» inúteis?
  5. (i) Enuncie formalmente a corretude da operação (–)⁺. (ii) Demonstre o (i).
  6. Defina uma semântica para os numerais binários construidos pela
    B ::= 0 | 1 | 0B | 1B
    
  7. A gramática seguinte é correta para gerar os binários sem «leading zeros»?
    N ::= 0 | P
    B ::= 0 | 1
    P ::= 1 | PB
    
    O que tu imagina que significam os N,B,P acima?
  8. Demonstre que cada b≥2 serve como base dum sistema posicional de numerais.

30/07/2021

  1. Resolva o problema Ω da Prova 4 do 2016.2.
  2. Resolva o problema C da Prova 2 do 2016.1. Obs.: No C1 responde sobre Bego também. No C2 considere que Bego, antes de começar subir, ele já decidiu seus saltos e não tem percebido a existência da Catia.
  3. Demonstre o teorema binomial por indução.
  4. Resolva o problema dos caminhos de Casa para Trabalho recursivamente. O que descobriu?
  5. Dê uma lida no capítulo 5 focando nas partes que não tens encontrado antes.

01/08/2021

  1. Q: em quantas maneiras podemos formar um string por A +’s e B -’s em tal forma que não aparece o “–”?
  2. Q: em quantas maneiras podemos formar um string de tamanho k, feito pelo alfabeto {+,-}, em tal forma que não aparece o “–”?
  3. Q: quantas soluções tem uma equação x1+…+xm = k nos inteiros positivos?
  4. Q: quantas soluções tem uma equação x1+…+xm = k nos naturais?
  5. Q: O que descobriu sobre os fibonacci a partir do Aleco? Demonstre teu palpite!
  6. Teste o Monty Hall e o problema das seqüências HTH vs HTT usando tua linguagem de programação favorita. Explique os resultados.
  7. Assista essa palestra de Peter Donnelly

04/08/2021

  1. Θ:
    a|b ⇒ a|mb
    a|b & b|c ⇒ a|c
    a|b & a|c ⇒ a|(bx+cy)
    a|b & b|a ⇒ |a|=|b|
    a|b & a>0 & b>0 ⇒ a≤b
    m≠0 ⇒ (a|b ⇔ ma|mb)
    
  2. Θ: Se um conjunto S de inteiros é fechado pela adição e pela subtração então S={Ø} ou existe positivo inteiro d tal que S={md|m∈ℤ}.
  3. Q: no Θ acima precisamos mesmo ambas as hipoteses sobre o S?
  4. Resolva a Prova 2.X do 2019.2.

06/08/2021

  1. Capítulo 6: até a § «O máximo divisor comum»
  2. Implemente (defina) os Ints e suas operações (adição, multiplicação).
  3. Mostre que modemos inferir o princípio da indução que encontramos nos inteiros a partir dos princípio da indução original.
  4. Sejam a,b inteiros. Demonstre que existe um maior divisor comum deles d, e que ele pode ser escrito como «combinação linear» deles, ou seja, que existem inteiros x,y tais que d = ax + by.
  5. Mostre que existe exatamente um maior divisor comum não-negativo. É esse que denotamos por gcd(a,b) (ou por (a,b) se não existe ambigüidade).
  6. Os x,y são determinados pelos a e b? Ou seja, a forma de escrever o d como combinação linear dos a e b é única?
  7. Resolva o plicker: d|ab ⇐?⇒ (d|a ou d|b)

09/08/2021

  1. Implemente (defina) os Ints e suas operações (adição, multiplicação). No Coq, ué!
  2. Demonstre ou refute: para quaisquer inteiros a,b, os seguintes são todos iguais: (a,b), (-a,b), (a,-b), (-a,-b), (b,a)
  3. (a,b) =?= (a,a+b)
  4. (a,b) =?= (a,ax+b)
  5. (a,b) =?= (a,ax+by)
  6. Para quaisquer inteiros a,b, e qualquer primo p:
    p|ab ⇒ (p|a ou p|b)
  7. a|m & b|m ⇐?⇒ ab|m
  8. d|a+b ⇒?⇒ d|a ou d|b
  9. Podes afirmar algo sobre o (a,p)?

11/08/2021

  1. Todo inteiro exceto o 0 pode ser escrito como produtorio de primos. dica: use uma certa versao de indução que encontramos na unidade 1
  2. Divisão de Euclides: demonstre a unicidade de quociente e resto
  3. Lemma de Euclides: p|ab ⇒ p|a ou p|b: demonstre sozinho
  4. ?? & d|ab ⇒ d|b: Pelo lemma de Euclides sabemos que «d primo & d∤a» serve para os «??». Ache uma afirmação mais geral que essa que também serve para os «??» e demonstre.
  5. ?? & a|m & b|m ⇒ ab|m: o que botar no «??»? Demonstre tua afirmação.
  6. Teorema fundamental de aritmetica: demonstre a unicidade da fatorização («módulo» a ordem dos fatores)
  7. No fim da última aula descobrimos que podemos representar cada inteiro positivo por uma lista finita de naturais, correspondendo nos exponentes (veja teorema fundamental de aritmética). O que muda se em vez de naturais usar inteiros?

13/08/2021

  1. Demonstre os teoremas principais até agora: Divisão de Euclides ; existência e forma de mdc ; teorema fundamental de aritmética ; lemma de euclides (p|ab ⇒ p|a ou p|b)
  2. Termine nossa primeira demonstração do «The Book»: (Euclides): existe uma infinidade de primos
  3. Calcule os mdc’s: (14,35) ; (11,15) ; (2873,6643) ; (4148,7684) ; (1001,7655)
  4. Escreva cada um dos (a,b) do exercício anterior como combinação linear dos a e b
  5. Demonstre ou refute: (ab,ac) =?= a(b,c)
  6. ?? & d|ab ⇒ d|b: Pelo lemma de Euclides sabemos que «d primo & d∤a» serve para os «??».
  7. Demonstre ou refute: «se q é um inteiro tal que para quaisquer inteiros a e b, q|ab implica em q|a ou q|b, então q é 0, 1, -1, ou primo.»
  8. Demonstre ou refute: (a,m) = (b,m) = 1 ⇒ (ab,m) = 1
  9. Demonstre: a|c & b|c ⇒ ab | c(a,b)

16/08/2021

  1. Quão a eficiência do algoritmo de Euclides?
  2. Dica: calcule o (89,55)
  3. A dica acima foi dica para qual problema?
  4. Θ: para todo n≥2, existe primo entre n e n!
  5. Θ: para todo n, existem n consecutivos compostos
  6. Q: Quando eu posso parar, usando o crivo de Eratosthenes?
  7. Demonstre o que precisa demonstrar para justificar a definição do menor múltiplo comum e da sua notação lcm(–,–) (também: [–,–]). Compare com a demonstração sobre o m.d.c.
  8. [a,b] = ab/(a,b)
  9. Vₚ(a+b) ≥ min( Vₚ(a) , Vₚ(b) )
  10. Vₚ((a,b)) = min( Vₚ(a), Vₚ(b) )
  11. Vₚ(ab) = Vₚ(a) + Vₚ(b)
  12. Vₚ([a,b]) = max( Vₚ(a), Vₚ(b) )
  13. ‖ab‖ₚ = ‖a‖ₚ‖b‖ₚ
  14. ‖a+b‖ₚ ≤ max( ‖a‖ₚ , ‖b‖ₚ )
  15. Um inteiro x é chamado quadrado sse existe inteiro b tal que x = b². Preenche os «??» e demonstre que: mn quadrado & ?? ⇒ m,n quadrados

18/08/2021

  1. Capítulo 6: Até o primeiro intervalo de problemas
  2. Resolva bem a Prova 2.Y
  3. Resolva bem a parte da unicidade do teorema da Prova 2.Y
  4. Demonstre que Matheus não foi bipolar na aula: as duas definições de a,b congruentes módulo m são equivalentes.

20/08/2021

  1. Resolva sem consultar nada toda a Prova 2.1 do 2019.2.
  2. [SF1]: Resolva o Lists.v.

23/08/2021

  1. Pelamor de Ευκλείδης, resolva o J da Prova 2.1 e termine o E1.
  2. Capítulo 6: até o segundo intervalo de problemas
  3. Construa as tabelas de adição e multiplicação para os ℤ₂,ℤ₃,ℤ₄,ℤ₅,ℤ₆,ℤ₇
  4. Olhando para as 12 tabelas que tu construiu no homework anterior, ache propriedades interessantes dessas 12 operações
  5. Chamamos um número u de unit sse u|1. Quais são (se tem!) os units dos: ℤ,ℤ₂,ℤ₃,ℤ₄,ℤ₅,ℤ₆,ℤ₇
  6. Chamamos um número d de zerodivisor sse existe número k≠0 tal que dk=0. Quais são (se tem!) os zerodivisores dos: ℤ,ℤ₂,ℤ₃,ℤ₄,ℤ₅,ℤ₆,ℤ₇
  7. ca≡cb (mod m) ⇐?⇒ a≡b (mod m)
  8. a+c≡b+c (mod m) ⇐?⇒ a≡b (mod m)
  9. a≡b (mod m) ⇐?⇒ -a≡-b (mod m)
  10. Justifique a perigosa definição da adição e multiplicação módulo m que discutimos na aula. (Aquela que usou a regra de «escolhe dois representantes, opera nos inteiros, retorna a classe do resultado».) Enuncie o que precisa ser demonstrado, e demonstre.
  11. Para qualquer m, as operações de adição e multiplicação módulo m são: associativas, comutativas, possuem identidade (elemento neutro), e +-inversos (negação de número). Possuem ·-inversos (inverso multiplicativo de número).

27/08/2021

  1. Sejam a,b,m inteiros com m≥1 e (a,m)=1. A congruência ax≡b (mod m) tem resolução para o x. É única?
  2. Se p,q são primos distintos e pq|n², então pq|n.
  3. Os 2ⁿ-1,2ⁿ+1 não são primos gemeos, exceto para n=2.
  4. Demonstre que para exatamente um k inteiro, os k, k+2, k+4 são primos.
  5. Cada número da forma 3k+2 possui fator primo da mesma forma. Dica: todos os fatores primos são ou do time 0 ou do time 1 ou do time 2. Mostre que ninguem tá no time 0, e que é impossível que todos são do time 1.
  6. Sabemos que tem uma infinidade de primos. Quantos deles são congruentes ao 0 módulo 4? Quantos ao 2? Demonstre que tem uma infinidade deles congruentes ao 3. Dica: inspira-se pela demonstração da infinidade de primos de Euclides, e pela tua demonstração do exercício anterior.
  7. Sejam n≥1 e S um conjunto de de n+1 inteiros positivos, todos menores ou iguais ao 2n. Existem distintos a,b∈S tais que a|b. Dica: cada inteiro positivo pode ser escrito na forma 2ᵏr, com r ímpar.
  8. Investigue o que deixamos da resolução geral da congruência ax≡b (mod m).
  9. Termine o fim do sistema de duas congruências que eu buguei no fim da aula; observe porque tá praticamente resolvido.
  10. Tente generalizar a idéia para um sistema de n congruências.
  11. Demonstre o sonho de calouro: (x+y)ᵖ≡xᵖ+yᵖ (mod p).
  12. Demonstre: aᵖ≡a (mod p). Dica: indução, e exercício anterior.

30/08/2021

  1. φ é multiplicativa (a,b)=1 ⇒ φ(ab) = φ(a)φ(b)
  2. Eficiência de Euclides: o que acontece depois de dois passos?
  3. Caso geral da ax≡b (mod m)
  4. (p-1)!≡-1 (mod p) ⇐?⇒ p primo
  5. Converso de Fermat: verdadeiro ou falso?: Se para todo a, aᵖ≡a (mod p), então p é primo.
  6. Demonstre o que faltou para terminar a demonstração da Debora: (r,n) = (n-r,n)
  7. (a,bc) = 1 ⇐?⇒ (a,b)=1&(a,c)=1
  8. (qm+r,m) = (r,m)

06/09/2021

  1. Capítulo 6: até o terceiro intervalo de problemas
  2. φ é multiplicativa (a,b)=1 ⇒ φ(ab) = φ(a)φ(b)
    Dicas: escreva os mn números de 1 até mn numa tabela m×n. Argumente que so tem φ(m) colúnas com números coprimos ao m. Argumente que em cada coluna dessas tem φ(n) números coprimos ao n. Use os dois últimos exercícios do hw anterior
  3. Demonstre ou refute: (p-1)!≡-1 (mod p) ⇒ p primo
  4. Converso de Fermat: refute: Se para todo a, aᵖ≡a (mod p), então p é primo.
    Dica: 561
  5. Verifique que 341 engana Fermat com base a:=2
    Dica: Lema que demonstramos na aula; Fatorize o 341; e 1023 = 31·33

08/09/2021

  1. Pelamor de Leonhard, faça todo o homework que não tem feito ainda.
  2. x6.67

13/09/2021

  1. Resolva a Prova 3.1 do 2019.2

14/09/2021

  1. Como podemos recuperar os p,q se conseguirmos o φ(N)?
  2. Demonstre o teorema da Prova 3.X do 2019.2 sem a hipótese (x,N)=1.

Histórico

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

07/06/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

08/06/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

10/06/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

14/06/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

16/06/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 …»

17/06/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
  • Wason’s test

18/06/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?

21/06/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?

23/06/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

25/06/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

28/06/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?

01/07/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

02/07/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!

06/07/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?

08/07/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?

13/07/2021: Aulas 16 e 17: Naturais, recursão, indução

  • Aula 16 [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
  • Aula 17 [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?

18/07/2021: 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?

23/07/2021: Aulas 19 e 20: Resolução da Prova 1.1 [video] e [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?
  • 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₄?

27/07/2021: Aulas 21 e 22: Naturais, recursão, indução ; Análise combinatória [video] e [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
  • 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?

30/07/2021: Aulas 23 e 24: Análise combinatória; Naturais, indução, recursão

  • 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?

01/08/2021: Aulas 25 e 26a: Análise combinatória

  • Aula 25: [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 26a: [video] até o 01:15:53
    • 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

03/08/2021: Aula 26b & 27: teoria dos números

  • [video]: (a partir do 01:15:53)
    • 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?
  • [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

06/08/2021: 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)

09/08/2021: 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)

11/08/2021: 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

13/08/2021: 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)

16/08/2021: 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]·(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

18/08/2021: Aulas 33 e 34: Teoria dos números; Prova 2.Y

  • Aula 33 [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
  • Aula 34 [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»

20/08/2021: 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?

23/08/2021: 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»

26/08/2021: 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

27/08/2021: 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

30/08/2021: 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 (3, 9, 11)
  • Pensando na aⁿ≡a (mod n)

01/09/2021: 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

03/09/2021: 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?

06/09/2021: 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 :(

08/09/2021: 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

10/09/2021: Aula 44: Teoria dos números [video]

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

13/09/2021: Aula 45: Criptografia [video]

14/09/2021: Aula 46: Criptografia [video]

Futuro (fluido)

Sem futuro!

Last update: Sat Sep 18 20:02:20 -03 2021