AulaBook 2022.2

Desenvolvido pelo projeto Monitoría FMCn.
Veja mais detalhes no site do projeto: fmc.imd.ufrn.br.
Veja também o 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\ge 0$$

$$|x|=-x,x\le 0$$
Demonstre:

• $|x|\ge 0$
• $|x|=0⟺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\ne \mathrm{\varnothing }$ e

$A\subseteq B\setminus C$, então

$B⊈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:

$(\mathrm{\exists }x,y)[Px\wedge Py\wedge x\ne y\wedge (\mathrm{\forall }z)[Pz⟹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)⟺d\mid a\mathrm{\&}d\mid b\mathrm{\&}d\in \mathbb{N}\mathrm{\&}(\mathrm{\forall }c)[c\mid a\mathrm{\&}c\mid b⟹c\mid d]$

2022-09-13

Seja

$(A_n{)}_n$ uma sequência de conjuntos. Definimos os conjuntos

• $A_{\ast }=\bigcup _{i=0}^{\mathrm{\infty }}\bigcap _{j=i}^{\mathrm{\infty }}{A}_j$
• $A^{\ast }=\bigcap _{i=0}^{\mathrm{\infty }}\bigcup _{j=i}^{\mathrm{\infty }}{A}_j$

Demonstre que

$A_{\ast }\subseteq A^{\ast }$.

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\mathrm{△}B)\mathrm{△}C=A\mathrm{△}(B\mathrm{△}C)$
• Identidade: existe
  $I\in P(S)$ tal que
  $A\mathrm{△}I=I\mathrm{△}A=A$
• Inverso: existe
  $A^{\prime }\in P(S)$ tal que
  $A^{\prime }\mathrm{△}A=A\mathrm{△}{A}^{\prime }=I$, onde
  $I$ é a identidade descrita acima.
• Comutatividade:
  $A\mathrm{△}B=B\mathrm{△}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}^{\mathrm{\infty }}{A}_n\subseteq \bigcap _{n=0}^{\mathrm{\infty }}{B}_n$.

Exercício

Definimos a relação de ordem

$\le$ nos naturais pela:

• $n\le m⟺(\mathrm{\exists }k\in N)[n+k=m]$

Demonstre que

$(\mathrm{\forall }n,m)[n\le Sm⟺n\le 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,\dots$ tal que

$a_i<a_{i+1}$ para todo

$i\in \mathbb{N}$.

2022-09-20

Definimos a relação de ordem

$\le$ nos naturais pela:

• $n\le m⟺(\mathrm{\exists }k\in N)[n+k=m]$

Demonstre que (?)

2022-09-23

Fixe um

$m$ inteiro. Demonstre que para todos

$a,b,c$ inteiros, temos:

• (1)
  $a\equiv a$ (mod
  $m$) (reflexividade)
• (2)
  $a\equiv b$ (mod
  $m$) &
  $b\equiv c$ (mod
  $m$)
  $⟹a\equiv c$ (mod
  $m$) (transitividade)
• (3)
  $a\equiv b$ (mod
  $m$)
  $⟹b\equiv 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⟹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{\equiv }_{m}b$. Demonstre que para todo

$x$ inteiro:

• $a+x{\equiv }_{m}b+x$
• $ax{\equiv }_{m}bx$
• $-a{\equiv }_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⟹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⟺(\mathrm{\exists }f:A\to B)[fbijetora].$

2022-10-05

Demonstre a unicidade do mínimo múltiplo comum de dois inteiros. Isto é: se

$a,b,d,d^{\prime }$ são inteiros tais que

$d$ e

$d^{\prime }$ são menor múltiplo comum de

$a$ e

$b$ então

$d=d^{\prime }$.

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=ϵ$
(L2)

$s^n=s^{n-1}++s$

(R1)

$s_0=ϵ$ 
(R2)

$s_n=s++s_{n-1}$

onde 

$ϵ$ representa o string vazio tal que

$(\mathrm{\forall }s)[ϵ++s=s=s++ϵ]$.

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⟺a+1=b$

Demonstre que

$(\mathrm{\forall }n\in \mathbb{N})[a{\to }^{n}b⟹a+n=b]$.

Definições:

• $x(R\diamond S)y⟺(\mathrm{\exists }w)[xRw\mathrm{\&}wSy]$
• 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⟺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\ast b)\ast c=a\ast (b\ast c)$.

c) Demonstre que para todos

$a,x,y\in Nats$ temos

$a^{(x+y)}=a^x\ast 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.