Exercício 1. Mostre que:
A operação soma/adição em N é comutativa.

Passo 1

Queremos provar que, para todos a,binN,
a + b ;=; b + a
O que usamos: a definição recursiva da soma em N (axiomas de Peano) e o princípio da indução finita.

Passo 2

Definição recursiva da soma em N:
a + 0 = a
a + S(b) = Sl(a + br)
onde S(b) é o sucessor de b.

Passo 3

Lema 1: Para todo ninN vale
0 + n = n
Prova por indução em n:
— Base ( n=0):
0 + 0 = 0
por definição.
— Passo indutivo: suponha 0 + n = n. Então
0 + S(n) = Sl(0 + nr) = S(n)
Logo o lema vale para S(n).

Passo 4

Lema 2: Para todos m,ninN vale
S(m) + n = Sl(m + nr)
Prova por indução em n:
— Base ( n=0):
S(m) + 0 = S(m)
por definição, e
Sl(m + 0r) = S(m),
logo coincide.
— Passo indutivo: suponha S(m) + n = S(m + n). Então
S(m) + S(n) = Sl(S(m) + nr) = Sl(S(m + n)r),
e por definição de soma em segundo termo
m + S(n) = S(m + n)Longrightarrow Sl(m + S(n)r)=Sl(S(m + n)r)
Assim o lema estende-se a S(n).

Passo 5

Prova principal (indução em b): queremos forall a:;a+b=b+a.
— Base ( b=0):
a + 0 = a
e, pelo Lema 1,
0 + a = a
Logo a+0 = 0+a.
— Passo indutivo: suponha que para um b qualquer se tenha
a + b = b + a
para todo a. Então
a + S(b) = Sl(a + br)
pela definição,
S(b) + a = Sl(b + ar)
pelo Lema 2,
e pela hipótese indutiva a+b = b+a segue
Sl(a + br) = Sl(b + ar)
Com isso concluímos
a + S(b) = S(b) + a

Resposta

Para todos a,binN vale
a + b = b + a,
ou seja, a adição em N é comutativa.

Exercícios relacionados