[fmcmon]: https://fmc.imd.ufrn.br/
[aulabooks]: https://fmc.imd.ufrn.br/aulabook/
[fmcbook]: https://tsouanas.org/fmcbook
# AulaBook 2023.1
Desenvolvido pelo projeto [Monitoría FMCn][fmcmon].
Veja mais detalhes no site do projeto: fmc.imd.ufrn.br.
Veja também os outros [AulaBook™][aulabooks].
## 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 $(\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](https://gist.github.com/isaacmsl/c6d808d6283d5e0253e5b992ec6e387d)
- Addition World (NNG)
- (Extra) Multiplication World (NNG)
## 2023-04-03 (IG)
(IDMa)
Demonstre que $(\forall p_{\geq 1})[p \text{ primo} \land p \text{ ímpar} \implies (\exists !x, y, _{\geq 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.
- $(\forall f: A \to B)[1_B \circ f = f \land 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 } \iff g \text{ injetora }$$
???
## 2023-04-24 (IG)
(IEA)
- Definição de subgrupo
- $(\forall m)[m\mathbb{Z} \leq \mathbb{Z}]$
## 2023-04-26 (IG)
(IEA)
Critérion *one-test*
$$\emptyset \neq H \subseteq G \land (\forall a, b \in H)[ab^{-1} \in H] \implies H \leq G$$
## 2023-04-28 (IL)
(IDMa) Rumo à criptografia!
*unit* e *invertível* são sinônimos:
$$(\forall x)[x \text{ unit} \iff x \text{ invertível}]$$
## 2023-05-03 (IG)
(CFR)
Seja $f: A \to B$, demonstraremos:
$$ f \text{ possui inverso } \iff f \text{ bijetiva } $$
## 2023-05-05 (IL)
(IDMa) Rumo à criptografia!
Sejam a, m inteiros. $a$ tem inverso módulo m $\iff (a, m) = 1$.
*Disclaimers*:
- O detalhe de que a $(a,m) \in \mathbb{Z}_{\geq 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}_{\geq 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 } \iff f^{-1}[ \_ ] \text{ injetiva }$$
???
## 2023-05-10 (IL)
(IDMa) Finalmente, RSA.
- Sejam $e, M ∈ \mathbb{Z}$ com $(e, \phi(M)) = 1$, e seja $d$ um inverso de $e$ módulo $\phi(M)$. Para cada $m$ com $(m, M) = 1$,
$$(m^e)^d ≡_m m\text{.}$$
- A ideia do RSA
## 2023-05-15 (IG)
(CFR)
Seja $f: A \to B$
$$f \text{ bijetiva } \iff (\forall b \in B)[f^{-1}[\{b\}] \text{ é um conjunto unitario }$$
## 2023-05-17 (IG)
(CFR)
Seja $f$ endomapa.
$$(\forall x \in A)[x \text{ é um fixpoint da } f \iff (\forall n)[x \text{ é um fixpoint da } f^n]]$$
## 2023-05-18 (IL)
(IEA) Homomorfismo!
Sejam $\mathcal{A}, \mathcal{B}$ grupos e $\phi : \mathcal{A} \to \mathcal{B}$. Suponha que $\phi$ respeita a operação binária do $\mathcal{A}$. Demonstre que $\phi$ é 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
$$\phi: A \to B \text{ respeita operação } \implies \phi \text{ é homomorfismo }$$
## 2023-05-25 (IL)
(IEA)
O <ins>centro do grupo</ins> G é o conjunto de todos os elementos de G que comutam com todos os elementos do G:
$$Z(G) \stackrel{def}{=} \{z \in G | (\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 $\phi: \mathcal{A} \to \mathcal{B}$
$$ker \; \phi ⊴ 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 $φ: P \to Q$. Dizemos que $φ$ é order-embbeding sse ela é injetora e preserva as ordens. Em símbolos matemáticos: $$φ\ \text{order-embbeding} \stackrel{def}{\iff} φ\ \text{injetora & }\ (x \leq y \iff φ\ x \leq φ\ y).$$ Demonstre que $\phi$ preserva as ordens $\stackrel{?}{\iff} φ$ injetiva.
## 2023-06-05 (IG)
Investigando relações doidas
Sejam $f,g: \mathbb{Z} \to \mathbb{Z}$
Definimos: $$f \sim g \stackrel{def}{\iff} (\exists u : \mathbb{Z})(\forall x : \mathbb{Z})[f(x) = g(x+u)]$$
$$f \; R \; g \stackrel{def}{\iff} (\exists v: \mathbb{N})(\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}{\iff} R$ reflexiva, transitiva e simétrica
- $R$ é circular $\stackrel{def}{\iff} (\forall x,y,z)[x\ R\ y$ & $y\ R\ z \implies z\ R\ x]$
## 2023-06-14 (IG)
Seja $(G, *, e, ^{-1})$ um grupo cíclico infinito. Mostre que $G$ é contável.
## 2023-06-15 (IL)
**🐱 Cat*egorias*!** Sejam $e : E \to A,f,g : A \to B$. Dizemos que $e$ é um <ins>equalizer</ins> das $f,g$ sse o seguinte diagrama comuta:
<!-- https://q.uiver.app/#q=WzAsNCxbMCwwLCJFIl0sWzEsMCwiQSJdLFsyLDAsIkIiXSxbMCwxLCJIIl0sWzAsMSwiZSJdLFsxLDIsImYiLDAseyJvZmZzZXQiOi0xfV0sWzEsMiwiZyIsMix7Im9mZnNldCI6MX1dLFszLDEsImgiLDJdLFszLDAsIiEiLDIseyJzdHlsZSI6eyJib2R5Ijp7Im5hbWUiOiJkYXNoZWQifX19XV0= -->
<iframe class="quiver-embed" src="https://q.uiver.app/#q=WzAsNCxbMCwwLCJFIl0sWzEsMCwiQSJdLFsyLDAsIkIiXSxbMCwxLCJIIl0sWzAsMSwiZSJdLFsxLDIsImYiLDAseyJvZmZzZXQiOi0xfV0sWzEsMiwiZyIsMix7Im9mZnNldCI6MX1dLFszLDEsImgiLDJdLFszLDAsIiEiLDIseyJzdHlsZSI6eyJib2R5Ijp7Im5hbWUiOiJkYXNoZWQifX19XV0=&embed" width="432" height="304" style="border-radius: 8px; border: none;"></iframe>
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)](https://leanprover.github.io/), [Agda](https://agda.readthedocs.io/en/v2.6.3/index.html), [Coq](https://coq.inria.fr/)
## 2023-06-28 (IG)
Introdução às álgebras booleanas.
$$(B, 0, 1, \vee, \wedge, ')$$
- Unicidade dos complementos
- $(a')' = a$
- Leis de demorgan.
## 2023-07-06 (IL)
*Essa aula foi gravada: [assista no youtube](https://youtu.be/dVw_mVzGTok).*
**🐱🖥️ 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) \leq 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'= \{x'\ |\ x \in X\}$ é ideal.