\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    {}

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

\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

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

\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$.}

\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$.}

\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

\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.}

\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$.}

\bye
