\documentclass[12pt, a4paper]{article}

\addtolength{\topmargin}{-2cm}
\addtolength{\textheight}{4cm}

\pagestyle{empty}

\newcounter{conta}
\begin{document}

\noindent Bacharelado em Matem\'atica Computacional
\hfill UFMG \\
{\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002 \\
Professor: Newton Jos\'{e} Vieira  \\
{\bf Segunda Prova/Solu\c c\~ao do professor}

\begin{enumerate}
 \item {\em Sejam $A$, $B$ e $C$ conjuntos quaisquer. Prove que
       \[\mbox{se } A\subseteq B \mbox{ ent\~ao } A\cap C\subseteq B\cap C\mbox{.}\]}

       {\em Solu\c c\~ao\/}: Suponha que $A\subseteq B$. Seja $x$ um elemento
       arbitr\'ario de $A\cap C$; segue-se que $x\in A$ e $x\in C$. Como
       $x\in A$ e $A\subseteq B$, deduz-se que $x\in B$. Desta \'ultima e
       $x\in C$ conclui-se que $x\in B\cap C$. Como $x$ \'e um elemento
       arbitr\'ario de $A\cap C$, segue-se que $A\cap C\subseteq B\cap C$.
       Portanto, se $A\subseteq B$, ent\~ao $A\cap C\subseteq B\cap C$.

 \item {\em Sejam $A$, $B$, $C$ e $D$ conjuntos tais que $D$ n\~ao \'e vazio, $B$ e
       $C$ s\~ao disjuntos, e $D\subseteq C\backslash A$. Prove que
       $D\not\subseteq A\cup B$.}

       {\em Solu\c c\~ao\/}: Como $D$ n\~ao \'e vazio, seja $d\in D$.
       Como $D\subseteq C\backslash A$,
       tem-se que $d\in C$ e $d\not\in A$; e como $B$ e $C$ s\~ao disjuntos,
       o fato de que $d\in C$ implica que $d\not\in B$. Assim, $d\not\in A$ e
       $d\not\in B$, ou seja, $d\not\in A\cup B$. Como $d$ \'e um elemento de $D$
       que n\~ao est\'a em $A\cup B$, conclui-se que $D\not\subseteq A\cup B$.

 \item {\em Suponha que $\{A_i\,\,|\,\,i\in I\}$ \'e uma fam\'{\i}lia indexada de conjuntos.
       Prove que $\cup_{i\in I}{\cal P}(A_i)\subseteq {\cal P}(\cup_{i\in I}A_i)$.}

       {\em Solu\c c\~ao\/}: Seja $X$ um elemento arbitr\'ario de
       $\cup_{i\in I}{\cal P}(A_i)$. Ent\~ao $\exists i\in I(X\in {\cal P}(A_i))$.
       Seja, ent\~ao, $i_0\in I$ tal que $X\in {\cal P}(A_{i_0})$, ou seja,
       $X\subseteq A_{i_0}$. Como $X\subseteq A_{i_0}$ e $i_0\in I$, segue-se que
       $X\subseteq\cup_{i\in I}A_i$, ou ainda, $X\in {\cal P}(\cup_{i\in I}A_i)$.
       Como $X$ \'e um elemento arbitr\'ario de $\cup_{i\in I}{\cal P}(A_i)$,
       conclui-se que $\cup_{i\in I}{\cal P}(A_i)\subseteq {\cal P}(\cup_{i\in I}A_i)$.

 \item {\em Prove que para todo n\'umero natural $n$, $n^3$ \'e par se, e somente se,
       $n$ \'e par.}

       {\em Solu\c c\~ao\/}:

       $(\leftarrow)$ Suponha que $n$ \'e par, ou seja, que $n=2k$ para um n\'umero
       natural $k$. Ent\~ao: $n^3=(2k)^3=8k^3=2(4k^3)$. Como $4k^3$ \'e um n\'umero
       natural, conclui-se que $n^3$ \'e par.

       $(\rightarrow)$ Ser\'a provada a contrapositiva. Suponha que $n$ \'e \'{\i}mpar,
       ou seja, que $n=2k+1$ para um n\'umero natural $k$. Ent\~ao: $n^3=(2k+1)^3=
       8k^3+12k^2+6k+1=2(4k^3+6k^2+3k)+1$. Como $4k^3+6k^2+3k$ \'e um n\'umero
       natural, conclui-se que $n^3$ \'e \'{\i}mpar.

 \item {\em Seja $P(x)$ uma afirmativa com uma vari\'avel livre $x$. A seguinte f\'ormula
       expressa o fato ``{\em existem exatamente dois valores de $x$ para os quais
       $P(x)$ \'e verdadeira}'':
       \[\exists x\exists y[P(x)\wedge P(y)\wedge x\not= y\wedge\forall z(P(z)\rightarrow
         (z=x\vee z=y))]\mbox{.}\]}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\em Explique como seria uma estrat\'egia, baseada nesta f\'ormula, para
              provar uma afirmativa da forma ``{\em existem exatamente dois
              valores de $x$ para os quais $P(x)$ \'e verdadeira}''.}

              {\em Solu\c c\~ao\/}: Uma estrat\'egia constando de 3 passos:
              \begin{list}{\arabic{conta}.}{\usecounter{conta}}
               \item Exibir elementos $x_0$ e $y_0$ diferentes tais que
                     $P(x_0)$ e $P(y_0)$.
               \item Supor $P(z)$ para um elemento $z$ arbitr\'ario.
               \item Provar que $z=x_0\vee z=y_0$.
              \end{list}

        \item {\em Prove que existem exatamente duas solu\c c\~oes para a equa\c c\~ao
              $x^3=x^2$.}

              {\em Solu\c c\~ao\/}: A equa\c c\~ao se verifica para os valores $0$ e
              $1$: $0^3=0^2$ e $1^3=1^2$. Seja $z$ um n\'umero arbitr\'ario e
              suponha que $z^3=z^2$. Basta, ent\~ao, provar que $z=0$ ou $z=1$. Se
              $z=0$, nada resta a provar. Suponha, ent\~ao, que $z\not=0$. Neste
              caso, pode-se dividir ambos os lados de $z^3=z^2$ por $z$, o que
              resulta em $z^2=z$. Novamente, dividindo-se ambos os lados por $z$,
              obt\'em-se $z=1$. Portanto, $z=0$ ou $z=1$.

       \end{list}
\end{enumerate}

\end{document}