AulaBook 2023.1

Desenvolvido pelo projeto Monitoría FMCn.
Veja mais detalhes no site do projeto: fmc.imd.ufrn.br.
Veja também os outros AulaBook™.

2023-03-27 (IG)

• Demonstre que para quaisquer
  $a,b$ e
  $c$, Se
  $a|b+c$ e
  $a|b$ então
  $a|c$.
• Demonstre que para qualquer
  $p$, se
  $2|p^2$ então
  $2|p$.

2023-03-28 (IL)

Enquanto isso, no mundo do reais…

• Demonstre a lei do cancelamento multiplicativo
• (Extra) Demonstre que não há zero divisores

(Aqui iremos refletir um pouco sobre o uso da Lei do Terceiro Excluído (LEM))

2023-03-29 (IG)

Foco em IRI

• Definir os Nats
• Definir algumas operações (soma e multiplicação)

Exercício

• Demonstre que
  $(\mathrm{\forall }a,b:Nats)[Sa+b=a+Sb]$

2023-03-30 (IL)

Com a maior naturalidade…

• Revisão sobre naturais e a soma
• A (+) é associativa nos naturais (sem/com indução)

2023-03-31 (IL)

(IRI) Jogatina matemática…

• O que é a L∃∀N?
• Exercício para iniciantes L∃∀N
• Addition World (NNG)
• (Extra) Multiplication World (NNG)

2023-04-03 (IG)

(IDMa)
Demonstre que

$(\mathrm{\forall }{p}_{\ge 1})[p\text{ primo}\wedge p\text{ ímpar}⟹(\mathrm{\exists }!x,y{,}_{\ge 1})[x^2-y^2=p]]$

2023-04-05 (IG)

(IRI)

• Revisão dos tipos básicos
• Listas de naturais
• Como generalizar a indução para qualquer tipo
• (Se der tempo) Demonstrar associatividade da concatenação (++) de listas.

2023-04-10 (IG)

(IDMa)

Introdução à aritmética modular.

• Duas definições para a congruência módulo
  $m$.
• Demonstraremos a (quase) equivalência entre as duas.
• ${\equiv }_m$ é uma relação de equivalência.

2023-04-14 (IL)

(CRF1)

Seja

$I$ um conjunto de indices. Para todo

$i\in I$, seja

$A_i$ um conjunto. Demonstre:

$\cup \{I,{\cap }_{i\in I}{A}_i\}={\cap }_{i\in I}\cup \{I,A_i\}$.

2023-04-16 (IG)

(CRF)

• Associatividade da composição de funções.
• $(\mathrm{\forall }f:A\to B)[1_B\circ f=f\wedge f=f\circ 1_A]$

2023-04-18 (IG)

(CRF)

Sejam

$f:A\to B$ e

$g:B\to C$ t.q

$g\circ f$ é bijetora, podemos demonstrar que

$$f\text{ sobrejetora }⟺g\text{ injetora }$$
???

2023-04-24 (IG)

(IEA)

• Definição de subgrupo
• $(\mathrm{\forall }m)[m\mathbb{Z}\le \mathbb{Z}]$

2023-04-26 (IG)

(IEA)
Critérion one-test

$$\mathrm{\varnothing }\ne H\subseteq G\wedge (\mathrm{\forall }a,b\in H)[a{b}^{-1}\in H]⟹H\le G$$

2023-04-28 (IL)

(IDMa) Rumo à criptografia!

unit e invertível são sinônimos:

$$(\mathrm{\forall }x)[x\text{ unit}⟺x\text{ invertível}]$$

2023-05-03 (IG)

(CFR)
Seja

$f:A\to B$, demonstraremos:

$$f\text{ possui inverso }⟺f\text{ bijetiva }$$

2023-05-05 (IL)

(IDMa) Rumo à criptografia!

Sejam a, m inteiros.

$a$ tem inverso módulo m

$⟺(a,m)=1$.

Disclaimers:

• O detalhe de que a

  $(a,m)\in {\mathbb{Z}}_{\ge 0}$ vem do teorema da unicidade dos m.d.c a menos de sócios, isto é, conseguimos demonstrar que existe único
  $d\in {\mathbb{Z}}_{\ge 0}$ t.q.
  $d=(a,m)$.

• A partir de

  $(a,m)=1$, conseguimos escrever
  $1$ como combinação linear dos
  $a$,
  $b$ (Lemma de Bézout). Além disso, podemos encontrar esses coeficientes também por meio do algoritmo estendido de Euclides.

2023-05-10 (IG)

(CFR)
Seja

$f:A\to B$.
Podemos demonstrar que

$$f\text{ sobrejetiva }⟺f^{-1}[\mathrm{\_}]\text{ injetiva }$$

???

2023-05-10 (IL)

(IDMa) Finalmente, RSA.

• Sejam
  $e,M\in \mathbb{Z}$ com
  $(e,\varphi (M))=1$, e seja
  $d$ um inverso de
  $e$ módulo
  $\varphi (M)$. Para cada
  $m$ com
  $(m,M)=1$,
  
  $$(m^e{)}^d{\equiv }_{m}m\text{.}$$
• A ideia do RSA

2023-05-15 (IG)

(CFR)
Seja

$f:A\to B$

$$f\text{ bijetiva }⟺(\mathrm{\forall }b\in B)[f^{-1}[\{b\}]\text{ é um conjunto unitario }$$

2023-05-17 (IG)

(CFR)
Seja

$f$ endomapa.

$$(\mathrm{\forall }x\in A)[x\text{ é um fixpoint da }f⟺(\mathrm{\forall }n)[x\text{ é um fixpoint da }{f}^n]]$$

2023-05-18 (IL)

(IEA) Homomorfismo!

Sejam

$\mathcal{A},\mathcal{B}$ grupos e

$\varphi :\mathcal{A}\to \mathcal{B}$. Suponha que

$\varphi$ respeita a operação binária do

$\mathcal{A}$. Demonstre que

$\varphi$ é um homomorfismo.

Disclaimer: demonstramos um critérion de homomorfismo.

2023-05-22 (IG)

(IEA) Conjugados!

Sejam

$a,b\in G$ tal que

$a$ e

$b$ são conjugados.
Demonstre que para qualquer

$n\in \mathbb{N},a^n$ e

$b^n$ são conjugados.

2023-05-24 (IG)

(IEA)

• Simetrias e o grupo
  $D_3$
• Homomorfismos

$$\varphi :A\to B\text{ respeita operação }⟹\varphi \text{ é homomorfismo }$$

2023-05-25 (IL)

(IEA)

O centro do grupo G é o conjunto de todos os elementos de G que comutam com todos os elementos do G:

$$Z(G)\stackrel{def}{=}\{z\in G|(\mathrm{\forall }g\in G)[zg=gz]\}.$$Demonstre

$Z(G)⊴G$, isto é,

$Z(G)$ é subgrupo normal do

$G$.

2023-05-29 (IG)

(IEA)
O conjunto

$Kernel$ e suas propriedades.

Sejam

$\mathcal{A},\mathcal{B}$ grupos e

$\varphi :\mathcal{A}\to \mathcal{B}$

$$ker\varphi ⊴A$$

2023-05-31 (IG)

(CFR)

• Composição de relações
• (
  $\diamond$) é associativa
• "Potências" de relações

2023-06-01 (IL)

Início de São João! 🧑‍🌾🌽

Relações. Para todo

$P,Q$ posets, e

$\phi :P\to Q$. Dizemos que

$\phi$ é order-embbeding sse ela é injetora e preserva as ordens. Em símbolos matemáticos:

$$\phi \text{order-embbeding}\stackrel{def}{⟺}\phi \text{injetora \& }(x\le y⟺\phi x\le \phi y).$$ Demonstre que

$\varphi$ preserva as ordens

$\stackrel{?}{⟺}\phi$ injetiva.

2023-06-05 (IG)

Investigando relações doidas
Sejam

$f,g:\mathbb{Z}\to \mathbb{Z}$
Definimos:

$$f\sim g\stackrel{def}{⟺}(\mathrm{\exists }u:\mathbb{Z})(\mathrm{\forall }x:\mathbb{Z})[f(x)=g(x+u)]$$

$$fRg\stackrel{def}{⟺}(\mathrm{\exists }v:\mathbb{N})(\mathrm{\forall }x:\mathbb{Z})[f(x)=g(x)+v]$$

2023-06-07 (IG)

Joins e meets nos posets. Introdução aos reticulados.

2023-06-13 (IL)

Relações. Sejam

$A$ conjunto e

$R$ uma relação binária sobre

$A$. Demonstre ou refute:

$R$ é uma relação de equivalência sse

$R$ é reflexiva e circular.

Definições:

• $R$ é uma relação de equivalência
  $\stackrel{def}{⟺}R$ reflexiva, transitiva e simétrica
• $R$ é circular
  $\stackrel{def}{⟺}(\mathrm{\forall }x,y,z)[xRy$ &
  $yRz⟹zRx]$

2023-06-14 (IG)

Seja

$(G,\ast ,e{,}^{-1})$ um grupo cíclico infinito. Mostre que

$G$ é contável.

2023-06-15 (IL)

🐱 Categorias! Sejam

$e:E\to A,f,g:A\to B$. Dizemos que

$e$ é um equalizer das

$f,g$ sse o seguinte diagrama comuta:

ou se o link morreu (tentei):

       f    
  e   ———>
E———>A———>B
^    ^ g
. = /  
.! / 
. / 
 H

Demonstre que equalizadores são monos.

2023-06-21 (IG)

Sejam

$A,B$: Set e

$f:A\to B$
Sabemos o que é

$\mathcal{P}A$. O que seria

$\mathcal{P}f$ ?
Demonstre que

$\mathcal{P}:\mathbb{Set}\to \mathbb{Set}$ é um functor

2023-06-27 (IL)

Zero-Knowledge Proof (ZPK).

Alice possui um segredo que Bob não pode saber. OO desafio para Alice é encontrar uma maneira de mostrar que possui tal conhecimento sem o revelar para Bob.

Encontre uma forma convincente¹ de convencer alguém que um teorema é válido sem revelar como ele pode ser demonstrado.

¹ convincente: por meio de algum proof assistant, como: L∃∀N (Lean), Agda, Coq

2023-06-28 (IG)

Introdução às álgebras booleanas.

$$(B,0,1,\vee ,\wedge {,}^{\prime })$$

• Unicidade dos complementos
• $(a^{\prime }{)}^{\prime }=a$
• Leis de demorgan.

2023-07-06 (IL)

Essa aula foi gravada: assista no youtube.

🐱🖥️ Categorias na computação.

• Stacks
• Type stack-of-X
• O
  $\mathbb{N}$ é stack-of- de algum conjunto?

2023-07-13 (DT)

Seja

$P$ poset chain-completo e

$\pi :P\to P$ monótona e contávelmente contínua. Logo

$\pi$ possui exatamente um strongly least fixpoint

$p$.

2023-07-14 (DT)

• Seja
  $L$ um lattice (reticulado). Demonstre que para todo
  $x,y,z\in L$, vale:
  $(x\vee y)\wedge (x\vee z)\le x\vee (y\wedge z)$.
• Seja
  $P$ um poset habitado. Mostre que as seguintes são equivalentes:
  • $P$ é um reticulado completo
  • $\bigvee S$ existem para todo
    $S\subseteq P$
  • $P$ tem
    $T$ e
    $\bigwedge S$ existem para todos conjuntos habitados
    $S\subseteq P$

2023-07-18 (IM)

Demonstre que para todo

$P$ poset chain-completo,

$P$ possui bottom.

2023-07-18 (DT)

Mostre que

$X$ é filtro sse

$X^{\prime }=\{x^{\prime }|x\in X\}$ é ideal.