2021.2 FMC1, turma de Thanos

Pontos

Pontos de participação

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.

18/10/2021

1. Capítulo 1: todo

20/10/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/10/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.

24/10/2021

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

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

29/10/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).
6. Capítulo 3: até o fim.

03/11/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/11/2021

1. Jogue (até completar!) o jogo Natural Number Game
2. [SF1]: Basics.v
3. Capítulo «Os números naturais»: até §«Demonstrando propriedades de naturais sem indução».
4. Podemos trocar o «S(n+m)» da (a2) por «Sn+m»?
5. Proposições de dupla negaço:
   1. P ⇒ ¬¬P
   2. ¬¬P ⇒ P
6. Comutatividade dos ∨,∧:
   1. (P ∨ Q) ⇒ (Q ∨ P)
   2. (P ∧ Q) ⇒ (Q ∧ 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. Proposições de contraposição:
   1. (P ⇒ Q) ⇒ (¬Q ⇒ ¬P)
   2. (¬Q ⇒ ¬P) ⇒ (P ⇒ Q)
9. A irrefutabilidade do LEM:
   1. ¬¬(P∨¬P)
10. A lei de Peirce e sua versão “fraca”:
    1. ((P ⇒ Q) ⇒ P) ⇒ P
    2. ((P ⇒ Q) ⇒ P) ⇒ ¬¬P
11. 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)
12. 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)
13. 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)
14. Currificação
    1. ((P∧Q)⇒R) ⇒ (P⇒(Q⇒R))
    2. ((P∧Q)⇒R) ⇐ (P⇒(Q⇒R))
15. Reflexividade da ⇒:
    1. P ⇒ P
16. 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
17. 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)]
18. 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)]
19. 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.

Sugestão: verifiquem os (i) e (ii) num proof assistant (Coq, Agda, ou Lean).

08/11/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»

17/11/2021

1. Problemas: Π4.1
2. §«Ordem nos naturais»
3. Problemas: Π4.11

18/11/2021

1. Siga a sugestão do hw do dia 05/11/2021: (i) instale o Lean no teu computador; (ii) configure teu editor para ativar o modo Lean; (iii) numa pasta no teu computador use o comando leanpkg new fmclean; (iv) baixe o arquivo logic.lean que tem os enunciados prontos, e o coloca na pasta fmclean/src; (v) substitua todos os sorry, do arquivo com código que compila para demonstrar tudo. Dúvidas nos #proofassistants e #tech, obviamente!

19/11/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 segundo intervalo de problemas pulando a §53. «Somatórios e produtórios formalmente» (para este assunto consulte a aula #14).

23/11/2021

1. 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.
2. Resolva o resto (que não conseguiu resolver dentro do tempo em modo simulação-de-prova).

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

29/11/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

01/12/2021

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

03/12/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.

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

10/01/2022

1. (para depois da Aula 26b) Θ: 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∈ℤ}.
2. (para depois da Aula 26b) Q: no Θ acima precisamos mesmo ambas as hipoteses sobre o S?
3. Resolva a Prova 2.X do 2019.2.

11/01/2022

• nat-rec-ind
  1. Implemente (defina) os Ints e suas operações (adição, multiplicação).
  2. Mostre que modemos inferir o princípio da indução que encontramos nos inteiros a partir dos princípio da indução original.
• pre-aula 29
  1. Capítulo 6: até a § «O máximo divisor comum»
  2. 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.
  3. 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).
  4. 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?
  5. Resolva o plicker: d|ab ⇐?⇒ (d|a ou d|b)

12/01/2022

1. Demonstre ou refute: para quaisquer inteiros a,b, os seguintes são todos iguais: (a,b), (-a,b), (a,-b), (-a,-b), (b,a)
2. (a,b) =?= (a,a+b)
3. (a,b) =?= (a,ax+b)
4. (a,b) =?= (a,ax+by)
5. Para quaisquer inteiros a,b, e qualquer primo p:
   p|ab ⇒ (p|a ou p|b)
6. a|m & b|m ⇐?⇒ ab|m
7. d|a+b ⇒?⇒ d|a ou d|b
8. Podes afirmar algo sobre o (a,p)?

13/01/2022

1. Capítulo 6: até o primeiro intervalo de problemas
2. 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, ou o PBO
3. Divisão de Euclides: demonstre a unicidade de quociente e resto
4. Lemma de Euclides: p|ab ⇒ p|a ou p|b: demonstre sozinho
5. ?? & 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.
6. ?? & a|m & b|m ⇒ ab|m: o que botar no «??»? Demonstre tua afirmação.
7. Teorema fundamental de aritmetica: demonstre a unicidade da fatorização («módulo» a ordem dos fatores)
8. 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?
9. 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)
10. Termine nossa primeira demonstração do «The Book»: (Euclides): existe uma infinidade de primos
11. Calcule os mdc’s: (14,35) ; (11,15) ; (2873,6643) ; (4148,7684) ; (1001,7655)
12. Escreva cada um dos (a,b) do exercício anterior como combinação linear dos a e b
13. Demonstre ou refute: (ab,ac) =?= a(b,c)
14. 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.»
15. Demonstre ou refute: (a,m) = (b,m) = 1 ⇒ (ab,m) = 1
16. Demonstre: a|c & b|c ⇒ ab | c(a,b)
17. Resolva a Prova 2.Y do 2019.2.
18. Resolva a Prova 2.Z do 2019.2.
19. Resolva a Prova 2.1 do 2019.2.

24/01/2022

1. Demonstre que Matheus não foi bipolar na aula: as duas definições de a,b congruentes módulo m são equivalentes.
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).

26/01/2022

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 gêmeos, 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.

28/01/2022

1. Demonstramos 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.
2. 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.
3. Investigue o que deixamos da resolução geral da congruência ax≡b (mod m).
4. Termine o fim do sistema de duas congruências que eu buguei no fim da aula; observe porque tá praticamente resolvido.
5. Tente generalizar a idéia para um sistema de n congruências.
6. Demonstre o sonho de calouro: (x+y)ᵖ≡xᵖ+yᵖ (mod p).
7. Demonstre: aᵖ≡a (mod p). Dica: indução, e exercício anterior.

02/02/2022

1. Capítulo 6: até o terceiro intervalo de problemas

04/02/2022

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 Débora: (r,n) = (n-r,n)
7. (a,bc) = 1 ⇐?⇒ (a,b)=1&(a,c)=1
8. (qm+r,m) = (r,m)

07/02/2022

1. φ é 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.)
2. Demonstre ou refute: (p-1)!≡-1 (mod p) ⇒ p primo
3. Converso de Fermat: refute: Se para todo a, aᵖ≡a (mod p), então p é primo. (Dica: 561)
4. Verifique que 341 engana Fermat com base a:=2 (Dica: Lema que demonstramos na aula; Fatorize o 341; e 1023 = 31·33)

09/02/2022

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

11/02/2022

1. Resolva a Prova 3.1 do 2019.2

14/02/2022

1. Pelamor de Ευκλείδης, resolva o J da Prova 2.1 do 2019.2 e termine o E1.
2. Como podemos recuperar os p,q se conseguirmos o φ(N)?

15/02/2022

1. 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.

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

01/11/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/11/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/11/2021: Aulas 9b & 10: naturais; recursão; indução

• Aula 9b: [video] (a partir do 00:37:00)
  • 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
• Aula 10: [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

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

10/11/2021: Aula 12 [2019-08-19]: 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

12/11/2021: Aula 13 [2019-08-21]: 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!

19/11/2021: Aula 14 [2019-08-26]: 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/11/2021: Aula 15 [2019-08-28]: 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?

24/11/2021: Aulas 16 [2019-08-30]: 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

26/11/2021: Aula 17 [2019-09-02]: 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?

29/11/2021: Aula 18 [2019-09-04]: Naturais, recursão, indução [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?

01/12/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₄?

03/12/2021: Aulas 21 e 22: Naturais, recursão, indução; Análise combinatória

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

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

13/12/2021: Aulas 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?

15/12/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

17/12/2021: Brigas sobre PS1

10/01/2022: Aulas 26b & 27: teoria dos números

• Aula 26b [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 não vazio 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 [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 S é legal
  • Plicker: o paradoxo da surpresa
  • Prova (surpresa) 2.X

11/01/2022: Aulas 28 & 29: teoria dos números

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

12/01/2022: Aulas 30 & 31: teoria dos números

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

13/01/2022: Aulas 32 & 33 & 34a: teoria dos números

• 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
• 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 34a [video]: (até o 00:49:46)
  • 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

15/01/2022: Aula 35a: teoria dos números

• Aula 35a: Correção da Prova 2.1 [video]: (até o 00:50:00)
  • 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

24/01/2022: Aula 34b & 35b: teoria dos números II

• Aula 34b [video]: (a partir do 00:49:46)
  • 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»
• Aula 35b: Teoria dos números [video]: (a partir do 00:50:00)
  • 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?

26/01/2022: Aula 36

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

28/01/2022: 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

31/01/2022: 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

02/02/2022: 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)

04/02/2022: 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

07/02/2022: 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?

09/02/2022: 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 :(

11/02/2022: 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

12/02/2022: Aula 44: Teoria dos números [video]

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

14/02/2022: Aulas 45: Criptografia

• Aula 45: Criptografia [video]

15/02/2022: Aulas 45: Criptografia

• Aula 46: Criptografia [video]

Futuro (fluido)