Exercício 1. Mostre que:
A operação soma/adição em
é comutativa.
A operação soma/adição em
Passo 1
Queremos provar que, para todos
,
O que usamos: a definição recursiva da soma em
(axiomas de Peano) e o princípio da indução finita.
Passo 2
Definição recursiva da soma em
:
onde
é o sucessor de
.
Passo 3
Lema 1: Para todo
vale
Prova por indução em
:
— Base ( ):
— Base (
por definição.
— Passo indutivo: suponha . Então
— Passo indutivo: suponha
Logo o lema vale para
.
Passo 4
Lema 2: Para todos
vale
Prova por indução em
:
— Base ( ):
— Base (
por definição, e
logo coincide.
— Passo indutivo: suponha . Então
— Passo indutivo: suponha
e por definição de soma em segundo termo
Assim o lema estende-se a
.
Passo 5
Prova principal (indução em
): queremos
.
— Base ( ):
— Base (
e, pelo Lema 1,
Logo
.
— Passo indutivo: suponha que para um qualquer se tenha
— Passo indutivo: suponha que para um
para todo
. Então
pela definição,
pelo Lema 2,
e pela hipótese indutiva segue
e pela hipótese indutiva
Com isso concluímos
Resposta
Para todos
vale
ou seja, a adição em
é comutativa.