changed 10 months ago
Published Linked with GitHub

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\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 (?)

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.

Select a repo