Seja o conjunto S=\{m \in \omega ; m+0=0+m\}. Prove que S=\omega.

Passo 1

O enunciado define \displaystyle S=\{m\in\omega\mid m+0=0+m\}
e pede que provemos S=\omega. Vamos usar o princípio da indução em \omega e a definição recursiva da adição em \omega:
m+0 = m
m+\mathsf{succ}(n)=\mathsf{succ}(m+n)

Passo 2

(Base da indução)
Para m=0 devemos verificar que 0+0=0+0. Mas pela primeira cláusula da definição recursiva,
0+0 = 0
e também 0+0=0. Logo
0+0 = 0+0,
ou seja, 0\in S.

Passo 3

(Passo indutivo)
Suponha como hipótese de indução que algum k\in\omega satisfaz
k+0 = 0 + k.
Precisamos mostrar que \mathsf{succ}(k)\in S, ou seja,
\mathsf{succ}(k)+0 = 0 + \mathsf{succ}(k).
Pela definição recursiva da adição no segundo termo, temos
\mathsf{succ}(k)+0 = \mathsf{succ}\bigl(k+0\bigr).
Pela hipótese de indução k+0=0+k, então
\mathsf{succ}(k)+0 = \mathsf{succ}(0+k).
Novamente pela definição recursiva, agora aplicada a 0+\mathsf{succ}(k), obtemos
0+\mathsf{succ}(k)=\mathsf{succ}(0+k).
Portanto
\mathsf{succ}(k)+0 = 0+\mathsf{succ}(k),
mostrando que \mathsf{succ}(k)\in S.
Pelo princípio da indução em \omega, concluímos S=\omega.

Resposta

S=\omega

Exercícios relacionados