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

Passo 1

O enunciado define
S = \{\,m\in \omega \mid m+1 = 1 + m\}
e pede para mostrar que S=\omega.
Conteúdo que vamos usar: a definição recursiva da soma em \omega (axiomas de Peano) e o Princípio de Indução sobre \omega.

Passo 2

Base da indução: mostrar que 0\in S.
Pela definição recursiva da soma temos
0 + 1 = 0 + \mathrm{succ}(0) = \mathrm{succ}(0+0) = \mathrm{succ}(0) = 1
e também
1 + 0 = 1
Logo
0 + 1 = 1 + 0,
isto é, 0\in S.

Passo 3

Passo indutivo: suponha m\in S, ou seja,
m+1 = 1 + m.
Preciso mostrar \mathrm{succ}(m)\in S, isto é,
\mathrm{succ}(m) + 1 = 1 + \mathrm{succ}(m).
Usando definição recursiva da soma,
\mathrm{succ}(m) + 1 = \mathrm{succ}(m) + \mathrm{succ}(0) = \mathrm{succ}\bigl(\mathrm{succ}(m) + 0\bigr) = \mathrm{succ}\bigl(\mathrm{succ}(m)\bigr),
enquanto
1 + \mathrm{succ}(m) = \mathrm{succ}\bigl(1 + m\bigr).
Pela hipótese indutiva m+1 = 1 + m, portanto
\mathrm{succ}\bigl(\mathrm{succ}(m)\bigr) = \mathrm{succ}\bigl(m+1\bigr) = \mathrm{succ}\bigl(1 + m\bigr),
e segue
\mathrm{succ}(m) + 1 = 1 + \mathrm{succ}(m).
Assim, \mathrm{succ}(m)\in S.

Passo 4

Pelo Princípio de Indução em \omega, como 0\in S e m\in S\Rightarrow \mathrm{succ}(m)\in S, conclui-se que S=\omega.

Resposta

S=\omega.

Exercícios relacionados