\input thatexhandout

\def\PROFESSOR  {Θάνος}
\def\COURSE     {FMC1}
\def\SEMESTER   {2021.2}
\def\HANDOUT    {Problem Set 1}
\def\DEADLINE   {15/12/2021, 23h59}
\def\POINTS     {52}
\def\STUDENT    {Θάνος \bf (gabarito)}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\explodes{\doublemidrel}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mktitle

\rules Regras.
\rule: Escolha {\bf até dois} problemas para resolver.
\rule: Podes citar como lemma (sem demonstrar) \emph{apenas}
       resultados que são \emph{demonstrados} no fmcbook.
\rule: Nenhuma outra consulta ou colaboração é permitida.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\definition Definição.
Sejam $a,b$ racionais.
Dizemos que $a$ \dterm{explode} $b$ ($a \explodes b$) sse
existe inteiro $k$ tal que $a^k = b$.

\definition Definição.
Sejam $+$ e $\ntimes$ as operações definidas recursivamente pelas:
$$
\mathnoted {
\ltext {(a1)}  n + 0  &= n  \\
\ltext {(a2)}  n + Sm &= S(n+m)
} \qqqquad
\mathnoted {
\ltext {(m1)}  n \ntimes 0  &= 0  \\
\ltext {(m2)}  n \ntimes Sm &= (n \ntimes m) + n.
}
$$

\definition Definição.
Definimos as $\leq$ e $<$ nos naturais pelas
\mathcol
n \leq m &\defiff \text{existe natural $w$ tal que $n +  w = m$} \\
n <    m &\defiff \text{existe natural $w$ tal que $n + Sw = m$}.
\endmathcol

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\Question Problema 0. [8 pts]
Demonstre ou refute:
\statement{para quaisquer $a,x,y\in\rats$,
se $a \explodes x$ e $a \explodes y$, então para quaisquer
inteiros $u,v$, $a \explodes x^u y^v$.}

\answer Demonstração.
Sejam $a,x,y$ racionais tais que $a \explodes x$ e $a \explodes y$, e
logo sejam $i, j$ tais que $a^i = x$\fact{1} e $a^j = y$\fact{2}.
Sejam $u,v$ inteiros.
Pelas \byfact{1},\byfact{2} temos
$
x^u y^v
= (a^i)^u (a^j)^v
= a^{iu} a^{jv}
= a^{iu+jv}
$
e como $iu+jv \in \ints$, logo $a \explodes x^u y^v$.
\qed

\newpage

\Question Problema 1. [12 pts]
Demonstre ou refute:
\statement{para quaisquer naturais $a,b,c$,
se $a \leq b$ e $b < c$ então $a < c$.}

\answer Demonstração.
Sejam $a,b,c$ naturais tais que $a \leq b$ e $b < c$.
Logo sejam $u, v$ naturais tais que $a + u = b$ e $b + Sv = c$.
Calculamos:
\compute
c &= b + Sv         \by {pela escolha de $v$} \\
  &= (a + u) + Sv   \by {pela escolha de $u$} \\
  &= a + (u + Sv)   \by {associatividade da $+$} \\
  &= a + S(u + v)   \by {pela (a2)} \\
\endcompute
e logo $a < c$ (pois $u + v \in \nats$).
\qed

\newpage

\Question Problema 2. [18 pts]
Demonstre as leis de cancelamento para a adição:
\mathcol
&\lforall {t,a,b \in \nats} {t+a = t+b \implies a = b} \\
&\lforall {t,a,b \in \nats} {a+t = b+t \implies a = b}.
\endmathcol

\answer Demonstração.
Demonstrarei primeiramente o cancelamento à direita.
Sejam $a,b \in \nats$.
Por indução no $t$.
\crproofpart{Base.}
Suponha $a + 0 = b + 0$.
Calculando temos $a + 0 = a$ e $b + 0 = b$ e logo $a = b$.
\crproofpart{Passo indutivo.}
Seja $k$ tal que $a + k = b + k$ implica $a = b$.
Preciso demonstrar que $a + Sk = b + Sk$ também implica $a = b$.
Suponha $a + Sk = b + Sk$.
Logo $S(a + k) = S(b + k)$ (pela (a2)), e já que $S$ é injectiva temos
$a + k = b + k$, e pela H.I.~segue $a = b$.
\eop
Agora o cancelamento à esquerda é um corolário imediato
graças a comutatividade da adição, pois para quaisquer $t,a,b$ naturais temos:
\compute
          t + a = t + b
&\implies a + t = b + t \by{comutatividade da $+$} \\
&\implies a     = b.    \by{cancelando os $t$} \\
\endcompute
\qed

\newpage

\Question Problema 3. [26 pts]
Divulgando o LEM (princípio do terceiro excluído) tentei vender
a idéia que seria essencial para demonstrar mais
proposições do que realmente é!
Com as definições de par e ímpar seguintes
\mathcol
\text{$n$ par}   &\defiff \lexists {k \in \nats} {n = k + k} \\
\text{$n$ ímpar} &\defiff \lexists {k \in \nats} {n = S(k+k)}
\endmathcol
e sem usar nenhum dos feitiços que discutimos
(LEM, Reductio ad Absurdum, Lei da Dupla Negação, etc.)
demonstre por indução a proposição:
\statement{todo número natural é par ou ímpar.}

\answer Demonstração.
Por indução.
\crproofpart{Base.}
Temos que $0$ é par pois $0 = 0 + 0$.
\crproofpart{Passo indutivo.}
Seja $k$ natural tal que $k$ par ou $k$ ímpar.
Separamos em casos.
\crcase{Caso $k$ par.}
Vou demonstrar que $Sk$ é ímpar.
Como $k$ é par, seja $u$ tal que $k = u + u$.
Logo $Sk = S(u + u)$ e como $u\in\nats$, $Sk$ é ímpar.
\crcase{Caso $k$ ímpar.}
Vou demonstrar que $Sk$ é par.
Como $k$ é ímpar, seja $u$ tal que $k = S(u + u)$.
Calculamos
\compute
Sk
&= SS(u + u) \by {pela escolha do $u$}\\
&= S(u + Su) \by {pela \reversed{(a2)}} \\
&= S(Su + u) \by {pelo \reversed{(Λ4.39)}} \\
&= Su + Su   \by {pela \reversed{(a2)} com $n \asseq Su$; $m \asseq u$} \\
\endcompute
e como $Su \in \nats$, $Sk$ é par.
\qed

\newpage

\Question Problema 4. [26 pts]
Demonstre a lei de cancelamento pela esquerda para a multiplicação:
\statement{para qualquer $t \in \nats$ não nulo,
e quaisquer $a,b \in \nats$, se~$ta = tb$ então~$a = b$.}

\answer Demonstração.
Seja $t \neq 0$.
Por indução no $b$.
\crproofpart{Base.}
Seja $a$ natural e suponha $ta = t0$.
Logo $ta = 0$ (pela (m1)).
Vamos demonstrar que $a=0$.
Como $ta = 0$ temos $t = 0$ ou $a = 0$ (pelo Lemma 1).
A primeira alternativa é impossível pois $t\neq 0$, e logo $a = 0$.
\crproofpart{Passo indutivo.}
Seja $k$ tal que
$$
\lforall {x \in \nats} {tx = tk \implies x = k}. \tag{H.I.}
$$
Vou demonstrar que
$$
\lforall {a \in \nats} {ta = tSk \implies a = Sk}.
$$
Seja $a$ natural tal que $ta = tSk$\fact{1}.
Preciso mostrar que $a = Sk$.
Separamos em casos sobre o $a$:
\crcase{Caso $a = 0$.}
Vou mostrar que este caso é impossível.
Temos $tSk = ta = t0 = 0$.
Como $tSk = 0$, pelo Lemma 1 segue que $t = 0$ ou $Sk = 0$:
mas no caso $t = 0$ estamos contradizendo que $t \neq 0$;
e o caso $Sk = 0$ é impossível pela~4.13.
\crcase{Caso $a$ é um sucessor.}
Logo seja $a'$ natural tal que $a = Sa'$.
Basta verificar que $a' = k$ segue pela \byfact{1}:
\compute
          ta      = tSk
&\implies tSa'    = tSk     \by {pela escolha do $a'$} \\
&\implies ta' + t = tk + t  \by {(m2) em cada lado} \\
&\implies ta'     = tk      \by {cancelando os $+\,t$} \\
&\implies a'      = k.      \by {pela H.I.~com $x \asseq a'$} \\
\endcompute
\qed

\lemmaskip

\proposition Lemma 1.
Para quaisquer naturais $a,b$, se $ab=0$ então $a=0$ ou $b=0$.

\answer Demonstração.
Sejam $a,b$ naturais tais que $ab = 0$.
Separamos em casos sobre os $a$ e $b$:
os três casos onde pelo menos um dos $a,b$ é $0$ são imediatos.
Basta demonstrar que o caso onde ambos são sucessores é impossível.
Sejam $a',b'$ tais que $a = Sa'$ e $b = Sb'$.
Vou chegar numa contradição mostrando que
neste caso o $0$ é um sucessor (assim contradizendo o 4.13).
Calculamos:
\compute
0
&= ab           \by {hypótese} \\
&= aSb'         \by {pela escolha do $b'$} \\
&= ab' + a      \by {pela (m2)} \\
&= ab' + Sa'    \by {pela escolha do $a'$} \\
&= S(ab' + a'). \by {pela (a2) com $n \asseq ab'$; $m := a'$}
\endcompute
\qed

\bye
