Utilizador:Thiago Marcel/Profma11/Lista2

1a

Prove-se a lei de corte para a soma em $\mathbb {N}$: $x+a=y+a\Rightarrow x=y$

• Vamos mostrar que é válido que $se\;x,y,a\in \mathbb {N} \;e\;x+a=y+a,\;logo\;x=y$. Fazendo indução sobre a.
• Mostrar válido para a = 1, ou seja, $x+1=y+1\Rightarrow _{1}s(x)=s(y)\Rightarrow x=y$.
  • A primeira implicação acima é pela definição de sucessão, e a segunda é pela identidade da sucessão.
• Suponhamos válido para a = k, ou seja, $x+k=y+k\Rightarrow x=y$.
• Mostrar válido para a = k+1:
  • $x+k+1=y+k+1\Rightarrow _{1}s(x+k)=s(y+k)\Rightarrow _{2}x+k=y+k\Rightarrow _{3}x=y$.
  • A igualdade 1 pela definição de sucessor, a igualdade 2 é pela identidade da sucessão e a igualdade 3 é pela hipótese de indução ser válida para a=k.

1b

Prove-se a lei de corte para a multiplicação em $\mathbb {N}$: $x\cdot a=y\cdot a\Rightarrow x=y$

• Vamos mostrar que é válido que $se\;x,y,a\in \mathbb {N} \;e\;x\cdot a=y\cdot a,\;logo\;x=y$. Fazendo indução sobre a.
• Mostrar válido para a = 1, ou seja, $x\cdot 1=y\cdot 1\Rightarrow x=y$ (a implicação é garantida pela definição).
• Suponhamos válido para a = k, ou seja, $x\cdot k=y\cdot k\Rightarrow x=y$.
• Mostrar válido para a = k+1:
  • $x\cdot (k+1)=y\cdot (k+1)\Leftrightarrow _{1}x\cdot k+x\cdot 1=y\cdot k+y\cdot 1\Leftrightarrow _{2}y\cdot k+x=y\cdot k+y\Leftrightarrow x=y$
  • A dupla implicação 1 é garantida pela propriedade distributiva, a dupla implicação 2 é pela hipótese de indução e a dupla implicação 3 é pela lei do corte da soma.

2

Mostre que nos naturais não existe solução para as equações: $x+n=n+x=n,n\in \mathbb {N}$. Isso mostra que em $\mathbb {N}$ não existe o elemento neutro para a soma.

Prova

• Vamos analisar a equação: $x+n=n$. Pela lei da tricotomia, x = 1, x > 1 ou x < 1.
• Tome x = 1, assim $1+n=n\Rightarrow s(n)=n$. Mas, n não pode ser igual ao seu sucessor, logo é absurdo tomarmos x = 1.
• Tome x > 1, assim $\exists m\in \mathbb {N} ,tal\;que\;1+m+n=n\Rightarrow m+s(n)=n\Rightarrow n>s(n)$, absurso n ser maior que o seu sucessor, logo é absurdo tomarmos x > 1.
• Tome x < 1, mas não existe número natural menor que 1, logo é absurdo tomarmos x < 1.
• Portanto x + n = n não têm solução nos naturais. logo não existe o elemento neutro para a soma.

3a1

Teorema: Axioma da adição ou sucessor de uma adição: $\forall m,n\in \mathbb {N} ,m+(n+1)=(m+n)+1$.

Assim vamos fazer indução sobre n em $(m+n)+1=n+(n+1)$.

• quando n = 1, temos que $\forall \;m\in \mathbb {N} ,(m+1)+1=m+(1+1)\Rightarrow m+2=m+2$.
• Supomos verdadeira para n = k, ou seja, $(m+k)+1=m+(k+1),\;ou\;seja,\;s(m+k)=m+s(k)$.
• Queremos provar que é válido para n = k+1, isto é, $(m+(k+1))+1=m+((k+1)+1),\;ou\;seja,\;s(m+s(k))=m+s(s(k))$
  • Por hipótese, $s(m+k)=m+s(k)$. Pela identidade da sucessão temos que $s(m+s(k))=s(s(m+k))$.
  • Mas $s(s(m+k))=s((m+k)+1)=((m+k)+1)+1=(m+(k+1))+1=(m+s(k))+1=m+(s(k)+1)=m+s(s(k))$.
• Logo $s(m+s(k))=s(s(m+k))=m+s(s(k))$

3a2

Teorema: Associatividade da adição: $\forall m,n,p\in \mathbb {N} ,m+(n+p)=(m+n)+p$.

• Fixemos m,n naturais. Provaremos que é válido para todo p natural. Fazendo indução sobre p, temos:
  • para p = 1, provamos no teorema acima, isto é, que m + (n+1) = (m+n)+1.
  • supomos válido para p = k, isto é, $m+(n+k)=(m+n)+k$.
  • Provaremos que é válido para p = k+1, ou seja, $m+(n+(k+1))=(m+n)+(k+1)$.
    • Assim, $m+(n+(k+1))=^{1}m+((n+k)+1)=^{2}(m+(n+k))+1=^{3}((m+n)+k)+1=^{4}(m+n)+(k+1)$.
      • onde as igualdades 1, 2 e 4 ocorrem pelo axioma da adição e a 3 pela hipótese.

3b

Comutatividade da adição: $\forall m,n\in \mathbb {N} ,m+n=n+m$.

• Fixemos m natural. Provaremos que é válido para todo n natural. Fazendo indução sobre n, temos:
  • para n = 1, temos que m + 1 = 1 + m. (m e 1 são comutáveis)
  • supomos válido para n = k, isto é, $m+k=k+m$.
  • Provaremos que é válido para n = k+1, ou seja, $m+(k+1)=(k+1)+m$.
    • Assim, $m+(k+1)=^{1}(m+k)+1=^{2}(k+m)+1=^{3}k+(m+1)=^{4}k+(1+m)=^{5}(k+1)+m$
      • onde as igualdades 1, 3 e 5 ocorrem pela associatividade da adição, a igualdade 2 ocorre pela hipótese e a igualdade 4 ocorre pelo comuto de 1 e m.

3c

Teorema: Associatividade da multiplicação: $\forall m,n,p\in \mathbb {N} ,m\cdot (n\cdot p)=(m\cdot n)\cdot p$.

• Fixemos m,n naturais. Provaremos que é válido para todo p natural. Fazendo indução sobre p, temos:
  • para p = 1, temos que $m\cdot (n\cdot 1)=m\cdot n=(m\cdot n)\cdot 1$. (por definição de multiplicação por 1)
  • supomos válido para p = k, isto é, $m\cdot (n\cdot k)=(m\cdot n)\cdot k$.
  • Provaremos que é válido para p = k+1, ou seja, $m\cdot (n\cdot (k+1))=(m\cdot n)\cdot (k+1)$.
    • Assim, $m\cdot (n\cdot (k+1))=^{1}m\cdot ((n\cdot k)+n)=^{2}(m\cdot (n\cdot k))+m\cdot n=^{3}((m\cdot n)\cdot k)+m\cdot n=^{4}(m\cdot n)\cdot (k+1)$.
      • onde as igualdades 1, 2 e 4 ocorre pela distributividade e a igualdade 3 ocorre pela hipótese de indução.

3d1

Comutatividade de 1 e m na multiplicação: Para quaisquer $m\in \mathbb {N} ,$  tem-se que $m\cdot 1=1\cdot m$.

• Mostraremos por indução sobre m que a relação acima é válida para todo m natural.
• Para m = 1, temos Para quaisquer $1\cdot 1=1\cdot 1$, verdadeiro.
• Supomos ser válido para m = k, ou seja, $k\cdot 1=1\cdot k$.
• Provaremos ser válido para m = k + 1:
  • $1\cdot (k+1)=^{1}1\cdot k+1\cdot 1=^{2}k\cdot 1+1\cdot 1=^{3}(k+1)\cdot 1$.
    • onde a igualdade 1 é dada pela definição de multiplicação, a igualdade 2 é devida a hipótese e a igualdade 3 é devida a distributividade dos naturais.

3d2

Comutatividade da Multiplicação: Para quaisquer $m,n\in \mathbb {N} ,$  tem-se $m\cdot n=n\cdot m$.

• Fixando m natural, faremos indução sobre n, mostraremos que a relação acima é válida para todo n natural.
• para n = 1, temos $m\cdot 1=1\cdot m$, que foi verificado ser verdadeiro no axioma anterior.
• Supomos válido para n=k, ou seja, $m\cdot k=k\cdot m$.
• vamos provar que é válido para n=k+1:
  • $m\cdot (k+1)=^{1}m\cdot k+m\cdot 1=^{2}k\cdot m+1\cdot m=^{3}(k+1)\cdot m$.
    • onde as igualdades 1 e 3 ocorrem pela definição de multiplicação e a igualdade 2 ocorre pelas hipóteses de indução para quando n=1 e para quando n = k.

4

Distributividade: Para quaisquer $m,n,p\in \mathbb {N} ,$  tem-se $m\cdot (n+p)=m\cdot n+m\cdot p$.

• Fixamos m,n como sendo naturais quaisquer e provaremos por indução sobre p. Pela definição é válido para p = 1, isto é, $m\cdot (n+1)=m\cdot n+m\cdot 1$.
• Supomos válido para p = k, ou seja, $m\cdot (n+k)=m\cdot n+m\cdot k$.
• Provemos ser válido para n = k+1: $m\cdot (n+(k+1))=^{1}m\cdot ((n+k)+1)=^{2}m\cdot (n+k)+m=^{3}(m\cdot n+m\cdot k)+m=^{4}m\cdot n+(m\cdot k+m\cdot 1)=^{5}m\cdot n+m\cdot (k+1)$.
  • onde a igualdade 1 ocorre pela definição de adição, as igualdades 2 e 5 ocorrem pela definição de multiplicação, a igualdade 3 pela hipótese e a igualdade 4 pela associatividade da adição.

5a

Mostre que $s(p)>p,\forall \;p\in \mathbb {N}$

• Vamos mostrar por indução sobre n, que $s(p)>p,\forall \;p\in \mathbb {N}$
  • Devemos mostrar que é válido para p = 1, ou seja, $s(1)>1$. Mas $s(1)=2\;e\;2>1$.
  • Suponhamos que é válido para p = k, ou seja, $s(k)>k,\forall \;k\in \mathbb {N}$.
  • Como $k+n=s(k)=k+1\Rightarrow _{1}s(k+n)=s(k+1)\Rightarrow _{2}k+n+1=s(k+1)\Rightarrow _{3}k+1+n=s(k+1)\Rightarrow _{4}$
  • $\Rightarrow _{4}\exists \;n\in \mathbb {N} ,tal\;que\;s(k+1)>k+1.$
  • onde a implicação 1 é pela identidade de sucessão, a implicação 2 é pela sucessão de um natural, a implicação 3 é pela comutatidade da adição e a implicação 4 é pela definição de desigualdade.

5b

Mostre que $s^{m+1}(p)>s^{m}(p),\forall \;m,p\in \mathbb {N}$

Vamos provar por indução sobre m:

• Vamos mostrar que é válido para m = 1, ou seja $s^{1+1}(p)>s^{1}(p)$.
  • Como $s(p)>p\Rightarrow \exists \;n\in \mathbb {N} ,$ tal que $s(p)=n+p\Rightarrow s(s(p))=s(n+p)\Rightarrow s^{1+1}(p)=n+p+1=n+s(p)\Rightarrow s^{2}(p)>s^{1}(p)$
• Suponha válido para m = k, ou seja, $s^{k+1}(p)>s^{k}(p),\forall \;k,p\in \mathbb {N}$
• Mostrar válido para m = k + 1, ou seja, $s^{k+2}(p)>s^{k+1}(p),\forall \;k,p\in \mathbb {N}$
  • Como $s^{k+1}(p)>s^{k}(p)\Rightarrow _{1}\exists \;n\in \mathbb {N} ,tal\;que\;s^{k+1}(p)=n+s^{k}(p)\Rightarrow _{2}s(s^{k+1}(p))=s(n+s^{k}(p))\Rightarrow _{3}$
  • $\Rightarrow _{3}s^{k+1+1}(p)=n+s^{k}(p)+1=n+s(s^{k}(p))\Rightarrow _{4}s^{k+2}(p)=n+s^{k+1}(p)\Rightarrow _{5}s^{k+2}(p)>s^{k+1}(p)$.
    • onde as implicações 1 e 5 são pela definição de desigualdade, a implicação 2 pela identidade de sucessão, a implicação 3 é pela definição de sucessor e a implicação 4 é pela definição de k-sucessor.

6

Mostre que em $\mathbb {N} ,m\cdot n=1\Rightarrow m=n=1$

Pela tricotomia em m e n, ocorre uma das três "m<1 ou m=1 ou m>1" e uma das três "n<1 ou n=1 ou n>1" .

• o caso m <1 e n<1 não é possível, pois 1 é o menor natural.
• o caso m > 1 implica que existe k natural, tal que, m=1+k. Assim $m\cdot n=(1+k)\cdot n=1\cdot n+k\cdot n\Rightarrow m\cdot n>k\cdot n$. Como $k\cdot n\in \mathbb {N} \Rightarrow k\cdot n\geq 1\Rightarrow m\cdot n>1.$ Similarmente $n>1\Rightarrow m\cdot n>1.$
• Resta o caso que m=1 e n=1.

7a (soma)

Sejam o conjunto $\Gamma =\mathbb {N} \times \mathbb {N}$ e o conjunto de classes de equivalência $\mathbb {Z} =\{[(m,n)]:(m,n)\in \Gamma \}$, onde $(m,n)\sim (p,q)\Longleftrightarrow m+q=n+p$.
Mostre que as operações binárias:

• $\oplus :\mathbb {Z} \times \mathbb {Z} \mapsto \mathbb {Z} ,onde\;[(m,n)]\oplus [(p,q)]=[(m+p,n+q)]$ e
• $\otimes :\mathbb {Z} \times \mathbb {Z} \mapsto \mathbb {Z} ,onde\;[(m,n)]\otimes [(p,q)]=[(mp+nq,mq+np)]$

Não dependem do representante da classe, isto é, se $[(m,n)]=[(m',n')]\;e\;[(p,q)]=[(p',q')]$ então

• $[(m,n)]\oplus [(p,q)]=[(m',n')]\oplus [(p',q')]$ e
• $[(m,n)]\otimes [(p,q)]=[(m',n')]\otimes [(p',q')]$

• Prova:
• Como $[(m,n)]=[(m',n')]\;e\;[(p,q)]=[(p',q')],\Leftrightarrow \;m+n'=n+m'\;e\;p+q'=q+p'\Leftrightarrow m+n'+p+q'=n+m'+q+p'\Leftrightarrow$
  • $\Leftrightarrow m+p+n'+q'=n+q+m'+p'\Leftrightarrow [(m+p,n+q)]=[(m'+p',n'+q')]\Leftrightarrow [(m,n)]\oplus [(p,q)]=[(m',n')]\oplus [(p',q')]$.

7b (multiplicação)

• Temos que $[(m,n)]=[(m',n')]\;e\;[(p,q)]=[(p',q')],\Leftrightarrow \;m+n'=n+m'\;e\;p+q'=q+p'$.
• Multiplicando a primeira igualdade por p e q, e a segunda por m' e n':
• Teremos que $mp+n'p=np+m'p,mq+n'q=nq+m'q\;e\;m'p+m'q'=m'q+m'p',n'p+n'q'=n'q+n'p'$
• Somando as duas primeiras igualdades com o membro oposto e as duas últimas com o membro oposto.
• Teremos que $mp+n'p+nq+m'q=np+m'p+mq+n'q\;e\;m'p+m'q'+n'q+n'p'=m'q+m'p'+n'p+n'q'$.
  • Assim $[(mp+nq,np+mq)]=[(m'p+n'q,n'p+m'q)]=[(m'p+n'q,m'q+n'p)]=[(m'p'+n'q',m'q'+n'p')]$
• Logo $[(mq+np,mp+nq)]=[(m'q'+n'p',m'p'+n'q')]\Leftrightarrow [(m,n)]\otimes [(p,q)]=[(m',n')]\otimes [(p',q')]$.

8

Prove a existência do elemento neutro $\theta$ para a soma $\oplus$ em $\mathbb {Z}$, isto é, $x\oplus \theta =\theta \oplus x=x,\forall \;x\in \mathbb {Z}$

Prova:

• Como $x,\theta \in \mathbb {Z} ,logo\;x=[(y,z)],\theta =[(\alpha ,\beta )]$.
  • Como $x\oplus \theta =[(y,z)]\oplus [(\alpha ,\beta )]=[(y+\alpha ,z+\beta )]$ e $\theta \oplus x=[(\alpha ,\beta )]\oplus [(y,z)]=[(\alpha +y,\beta +z)]$
• Assim $x\oplus \theta =x\Rightarrow [(y+\alpha ,z+\beta )]=[(y,z)]\Rightarrow (y+\alpha ,z+\beta )\sim (y,z)\Rightarrow y+\alpha +z=z+\beta +y\Rightarrow \alpha =\beta \Rightarrow \theta =[(\alpha ,\alpha )]$
• Determine $t\in \mathbb {N}$, tal que $[(t,1)]=[(\alpha ,\alpha )]]\Rightarrow (t,1)\sim (\alpha ,\alpha )\Rightarrow t+\alpha =1+\alpha \Rightarrow t=1\Rightarrow [(1,1)]$ é o elemento neutro para a soma.

9

Prove a existência do elemento Neutro $\pi$ para o produto $\otimes \;em\;\mathbb {Z}$, isto é, $x\otimes \pi =\pi \otimes x=x,\forall \;x\in \mathbb {Z}$

Prova:

• Sejam $x,\pi \in \mathbb {Z} ,tal\;que\;x=[(y,z)],\pi =[(\alpha ,\beta )]$.
  • Façamos $x\otimes \pi =[(y,z)]\otimes [(\alpha ,\beta )]=[(y\cdot \alpha +z\cdot \beta ,y\cdot \beta +z\cdot \alpha )]$ e $\pi \oplus x=[(\alpha ,\beta )]\otimes [(y,z)]=[(\alpha \cdot y+\beta \cdot z,\alpha \cdot z+\beta \cdot y)]$
• Assim $x\otimes \pi =x\Rightarrow [(y\cdot \alpha +z\cdot \beta ,y\cdot \beta +z\cdot \alpha )]=[(y,z)]\Rightarrow (y\cdot \alpha +z\cdot \beta ,y\cdot \beta +z\cdot \alpha )\sim (y,z)\Rightarrow$
  • $\Rightarrow y\cdot \alpha +z\cdot \beta +z=y\cdot \beta +z\cdot \alpha +y\Rightarrow y\cdot \alpha +z\cdot (\beta +1)=y\cdot (\beta +1)+z\cdot \alpha \Rightarrow \alpha =\beta +1\Rightarrow \pi =[(\beta +1,\beta )]$

• Determine t, tal que $[(2,t)]=[(\alpha +1,\alpha )]]\Rightarrow (2,t)\sim (\alpha +1,\alpha )\Rightarrow t+\alpha +1=2+\alpha \Rightarrow t=1\Rightarrow [(2,1)]$ é o elemento neutro para a multiplicação.

10a

Associativa para a $\oplus \;em\;\mathbb {Z}$: Sejam $x,y,z\in \mathbb {Z} ,x\oplus (y\oplus z)=(x\oplus y)\oplus z$

Prova:

• Sejam $x=[(a,b)],y=[(c,d)],z=[(e,f)]\in \mathbb {Z} ,$
• Assim $x\oplus (y\oplus z)=(x\oplus y)\oplus z\Leftrightarrow [(a,b)]\oplus ([(c,d)]\oplus [(e,f)])=([a,b]\oplus [(c,d)])\oplus [(e,f)]\Leftrightarrow$
• $\Leftrightarrow [(a,b)]\oplus [(c+e,d+f)]=[(a+c,b+d)]\oplus [(e,f)]\Leftrightarrow [(a+(c+e),b+(d+f))]=[((a+c)+e,(b+d)+f)]\Leftrightarrow$
• $\Leftrightarrow (a+(c+e),b+(d+f))]\sim [((a+c)+e,(b+d)+f)\Leftrightarrow a+(c+e)+b+(d+f)=(a+c)+e+(b+d)+f$.
• Como os naturais são associativos para a adição, a soma $\oplus$ em Z é associativa.

10b

Associativa para a $\otimes \;em\;\mathbb {Z}$: Sejam $x,y,z\in \mathbb {Z} ,x\otimes (y\otimes z)=(x\otimes y)\otimes z$

Prova:

• Sejam $x=[(a,b)],y=[(c,d)],z=[(e,f)]\in \mathbb {Z} ,$
• Assim $x\otimes (y\otimes z)=(x\otimes y)\otimes z\Leftrightarrow [(a,b)]\otimes ([(c,d)]\otimes [(e,f)])=([a,b]\otimes [(c,d)])\otimes [(e,f)]\Leftrightarrow$
• $\Leftrightarrow [(a,b)]\otimes [(ce+df,cf+de)]=[(ac+bd,ad+bc)]\otimes [(e,f)]\Leftrightarrow$
• $\Leftrightarrow [(a(ce+df)+b(cf+de),a(cf+de)+b(ce+df))]=[((ac+bd)e+(ad+bc)f,(ac+bd)f+(ad+bc)e)]\Leftrightarrow$
• $\Leftrightarrow (a(ce+df)+b(cf+de),a(cf+de)+b(ce+df))\sim ((ac+bd)e+(ad+bc)f,(ac+bd)f+(ad+bc)e)\Leftrightarrow$
  • $\Leftrightarrow a(ce+df)+b(cf+de)+(ac+bd)f+(ad+bc)e=a(cf+de)+b(ce+df)+(ac+bd)e+(ad+bc)f\Leftrightarrow$
  • $\Leftrightarrow ace+adf+bcf+bde+acf+bdf+ade+bce=acf+ade+bce+bdf+ace+bde+adf+bcf$
  • Como os naturais são associativos para a adição e multiplicação, a multiplicação $\oplus$ em Z é associativa.

10c

Comutativa para a $\oplus \;em\;\mathbb {Z}$: $x\oplus y=y\oplus x\in \mathbb {Z}$

Prova:

• Sejam $x=[(a,b)],y=[(c,d)]\in \mathbb {Z} ,$
• Assim $x\oplus y=y\oplus x\Leftrightarrow [(a,b)]\oplus [(c,d)]=[(c,d)]\oplus [(a,b)]\Leftrightarrow [(a+c,b+d)]=[(c+a,d+b)]\Leftrightarrow (a+c,b+d)\sim (c+a,d+b)\Leftrightarrow$
• $\Leftrightarrow (a+c)+(d+b)=(c+a)+(b+d)$.
• Como os naturais são comutativos para a adição, a soma $\oplus$ em Z é comutativa.

10d

Comutativa para a $\otimes \;em\;\mathbb {Z}$: $x\otimes y=y\otimes x\in \mathbb {Z}$

Prova:

• Sejam $x=[(a,b)],y=[(c,d)]\in \mathbb {Z} ,$
• Assim $x\otimes y=y\otimes x\Leftrightarrow [(a,b)]\otimes [(c,d)]=[(c,d)]\otimes [(a,b)]=\Leftrightarrow [(ac+bd,ad+bc)]=[(ca+db,cb+da)]\Leftrightarrow$
• $\Leftrightarrow (ac+bd,ad+bc)\sim (ca+db,cb+da)\Leftrightarrow$
• $\Leftrightarrow (ac+bd)+(cb+da)=(ad+bc)+(ca+db)$.
• Como os naturais são comutativos e associativos para a adição e multiplicação, a multiplicação $\otimes$ em Z é comutativa.