[fmcmon]: https://fmc.imd.ufrn.br/
[fmcbook]: https://tsouanas.org/fmcbook
[aulabook-2022.1]: https://hackmd.io/ropuoEHdRJWGwRTtVaJwCg?view

# AulaBook 2022.2

Desenvolvido pelo projeto [Monitoría FMCn][fmcmon].
Veja mais detalhes no site do projeto: fmc.imd.ufrn.br.
Veja também o [AulaBook 2022.1][aulabook-2022.1].

## 2022-07-04
Definimos recursivamente as potências naturais dos racionais, onde $a \in \mathbb Q$ e $n \in \mathbb N$:
$$ a^0 = 1 $$
$$ a^{n+1} = a a^n $$
Demonstre, para quaisquer $a \in \mathbb Q$ e $n, m \in \mathbb N$:
- $a^n a^m = a^{n+m}$
- $(a^n)^m = a^{nm}$

## 2022-07-18
Definimos o _valor absoluto_ de um real $x$:
$$ |x| = x, x\geq 0$$
$$ |x| = -x, x\le 0$$
Demonstre:
- $|x| \geq 0$
- $|x| = 0 \iff x = 0$
- $z<0 \wedge x<y \Rightarrow xz > yz$

## 2022-08-25
Sejam $a$, $b$, e $c$ naturais. Encontre contraexemplos para as seguintes proposições:
- Se $ab$ divide $c$, então $a$ divide $c$ ou $b$ divide $c$.
- $a$ divide $b$ ou $b$ divide $a$.
- Se $3$ não divide $a$, então $3$ divide $a+1$.

Ainda para $a$, $b$, e $c$ naturais, demonstre:
- $a$ divide $a$.
- Se $a$ divide $b$ e $b$ divide $a$, então $a=b$.
- $a$ divide $0$.
- $1$ divide $a$.
- Se $a$ divide $b$, então $a$ divide $bc$.

## 2022-08-29

Demonstre que para quaisquer conjuntos $A,B,C$, se $A \not= \emptyset$ e $A \subseteq B \setminus C$, então $B \not\subseteq C$.

## 2022-08-30

Demonstre que para todo $n$ natural maior ou igual à $1$, $3^n - 2$ é ímpar.

## 2022-09-02

Seja $f: A \to A$ e $x \in A$, demonstre que um $x$ é um fixpoint da $f$ sse para todo $n \in \mathbb{N}$, $x$ é um fixpoint da $f^n$.

## 2022-09-05

Seja $\mathcal {C}$ uma $\subseteq$-chain e seja $T=\bigcup\mathcal {C}$. Demonstre que $\mathcal {C} \cup \{T\}$ é uma chain.

Definição:
- Seja $\mathcal {A}$ uma família de conjuntos. Chamados $\mathcal {A}$ de $\subseteq$-chain sse para quaisquer conjuntos $A,B \in \mathcal {A}$, temos $A \subseteq B$ ou $B \subseteq A$

## 2022-09-06

É possível expressar a ideia de que existem exatamente dois objetos com uma propriedade $P$ da seguinte forma: $(\exists x,y)[Px \wedge Py \wedge x \not= y \wedge (\forall z)[Pz \implies z=x \vee z=y]]$. Tente expressar a mesma ideia como uma conjunção e mostre que as duas formas são equivalentes.

## 2022-09-09

Demonstre que para todo natural $n$ temos $(F_{n+1},F_{n})=1$.
- Definições:
- $F_0 = 1$
- $F_1 = 1$
- $F_{n + 2} = F_{n + 1} + F_n$
- $d = (a, b) \iff d \mid a \ \And \ d \mid b \ \And \ d \in \mathbb N \ \And \ (\forall c)[c \mid a \And c \mid b \implies c \mid d]$

## 2022-09-13

Seja $(A_n)_n$ uma sequência de conjuntos. Definimos os conjuntos
- $A_* = \bigcup_{i=0}^\infty\bigcap_{j=i}^\infty A_j$
- $A^* = \bigcap_{i=0}^\infty \bigcup_{j=i}^\infty A_j$

Demonstre que $A_* \subseteq A^*$.

## 2022-09-14
Seja $S$ um conjunto e $P(S)$ seu conjunto potência. Demonstre que $P(S)$ é um grupo abeliano sob a diferença simétrica. Isto é, para quaisquer $A,B,C \in P(S)$:
- Associatividade: $(A \triangle B) \triangle C = A \triangle (B \triangle C)$
- Identidade: existe $I \in P(S)$ tal que $A \triangle I = I \triangle A = A$
- Inverso: existe $A' \in P(S)$ tal que $A' \triangle A = A \triangle A' = I$, onde $I$ é a identidade descrita acima.
- Comutatividade: $A \triangle B = B \triangle A$

## 2022-09-16

### Exercício

Sejam $(A_n)_n$ e $(B_n)_n$ sequências de conjuntos tais que para todo $m$ par temos $A_m \subseteq B_{m/2}$. Prove que $\bigcap_{n=0}^\infty A_n \subseteq \bigcap_{n=0}^\infty B_n$.

### Exercício

Definimos a relação de ordem $\leq$ nos naturais pela:
- $n \leq m \iff (\exists k ∈ N)[ n + k = m ]$

Demonstre que $(\forall n,m)[n \leq Sm \iff n\leq m$ ou $n=Sm ].$

## 2022-09-15
Demonstre o princípio da descida infinita nos naturais:
Não existe sequência de naturais $a_1, a_2, a_3, \ldots$ tal que $a_i < a_{i+1}$ para todo $i \in \mathbb N$.

## 2022-09-20

Definimos a relação de ordem $\leq$ nos naturais pela:
- $n \leq m \iff (\exists k ∈ N)[ n + k = m ]$

Demonstre que $(\forall n,m)[n\leq m$ ou $n=Sm ].$

## 2022-09-23

Fixe um $m$ inteiro. Demonstre que para todos $a,b,c$ inteiros, temos:

- (1) $a ≡ a$ (mod $m$) (reflexividade)
- (2) $a ≡ b$ (mod $m$) & $b ≡ c$ (mod $m$) $\implies a ≡ c$ (mod $m$) (transitividade)
- (3) $a ≡ b$ (mod $m$) $\implies b ≡ a$ (mod $m$) (simetria)

## 2022-09-27

### Exercício 1

Seja $f: A \to B$ . A $f$ é sobrejetora sse ela é $\circ$-cancelável pela direita:
- $g \circ f = h \circ f \implies g = h$

para todas as $g, h$ tais que as composições acima são definidas (ou seja, com domínio $B$).

## 2022-09-30

### Exercício 1

Fixe um $m$ inteiro. Sejam $a,b$ inteiros tais que $a ≡_m b$. Demonstre que para todo $x$ inteiro:
- $a + x ≡_m b +x$
- $ax ≡_m bx$
- $-a ≡_m -b$

### Exercício 2

Propriedade de máximo divisor comum: demonstre que para todos $a,b$ inteiros, $(a,a+b)=(a,b).$

## 2022-10-04

### Exercício 1

Seja $f: A \to B$ . A $f$ é injetora sse ela é $\circ$-cancelável pela esqueda:
- $f \circ g = f \circ h \implies g = h$

para todas as $g, h$ tais que as composições acima são definidas (ou seja, com codomínio $A$).

### Exercício 2

Demonstre que $=_c$ é uma relação de equivalência.

Definição:

$A =_c B \iff (\exists f:A \to B)[f \ bijetora].$

## 2022-10-05
Demonstre a unicidade do mínimo múltiplo comum de dois inteiros. Isto é: se $a,b, d, d'$ são inteiros tais que $d$ e $d'$ são menor múltiplo comum de $a$ e $b$ então $d=d'$.

## 2022-10-07

Sejam $a,m$ inteiros. Demonstre que $a$ tem inverso módulo $m$ se, e somente se, $(a,m)=1$.

## 2022-10-10

### Exercício 1

Denotamos a operação de concatenação de strings por $+\!+$. Assim é possível definir a "exponenciação" de duas maneiras:

(L1) $s^0 = \epsilon$
(L2) $s^n = s^{n-1} +\!+ s$

(R1) $s_0 = \epsilon$ 
(R2) $s_n = s +\!+ s_{n-1}$

onde  $\epsilon$ representa o string vazio tal que $(\forall s)[\epsilon +\!+ s = s = s +\!+ \epsilon]$.

Considerando que a operação $+\!+$ é associativa mas não comutativa, demonstre que para todo string $s$ e para todo $n$ natural, $s^n=s_n$.

### Exercício 2

Demonstre que para todos $a, x, y \in Nats$ temos $a^{xy} = (a^{x})^y$.

## 2022-10-11

### Exercício 1

Seja $\to$ uma relação no conjunto $\mathbb N$ definida pela:

- $a \to b \iff a + 1 = b$

Demonstre que $(\forall n \in \mathbb N)[a \to^n b \implies a + n = b]$.

**Definições**:
- $x(R \diamond S)y \iff (\exists w)[x \mathrel R w \mathbin\& w \mathrel S y]$
- Definimos a relação $R^n$ recursivamente pelas:
- $R^0 = (=)$
- $R^{n + 1} = R \diamond R^n$

### Exercício 2

Seja $R$ uma preordem num conjunto $A$. Demonstre que $R=R \diamond R$.

### Exercício 3

Defina no $\mathbb{Q}$ a relação $r$ ~ $s \Longleftrightarrow r-s \in \mathbb{Z}$. Demonstre então que ~ é uma relação de equivalência.

## 2022-10-14

a) Demonstre que para todos $a, b, c \in Nats$ temos $(a+b)+c = a+(b+c)$.

b) Demonstre que para todos $a, b, c \in Nats$ temos $(a*b)*c = a*(b*c)$.

c) Demonstre que para todos $a, x, y \in Nats$ temos $a^{(x+y)}=a^x * a^y$.

## 2022-10-19
Aula sobre Lean4. O arquivo usado nesta aula está em https://github.com/matheusanmo/lean4-fmc/blob/master/Quartafeira.lean
- Os comandos `#check` e `#eval`
- Definindo funções com `def`
- Pattern matching usando `match ... with`
- Funções que recebem e retornam funções

## 2022-10-26
Aula sobre Lean4. O arquivo usada nesta aula está em https://github.com/matheusanmo/lean4-fmc/blob/master/LambdaSimples.lean
- Termos dependentes de termos: _lambda simplesmente tipado_
- O construtor de tipo `List`
- As funções recursivas `len`, `map`, `filter` e seu uso no lugar de "laços de repetição".
- O tipo `Type`.

# 2022-11-29
Demonstre que os automorfismo de um conjunto são um grupo sob a composição.

Errata: na aula comentei que precisamos de um conjunto habitado para que seus automorfismos sejam um grupo. Não é verdade: um conjunto vazio tem único automorfismo, que é uma função vazia. Esta função serve como elemento neutro e como seu próprio inverso, configurando sim um grupo.
O que não pode "formar" um grupo é um conjunto vazio: precisamos de ao menos um elemento para servir como elemento neutro. Sem elemento neutro não temos um grupo.