Axioma da Indução
editar
Ao querermos provar alguma sentença matemática P(n), se é verdadeira, tendo seus elementos nos naturais, usamos a indução, onde:
Provamos que a propriedade é válida para n = 1.
Supomos válida para n = k e mostramos ser válida para n = k+1, usando a equação advinda da propriedade ser válida em n = k. Um número Natural
editar
Definição de um número natural:
n
=
1
+
1
+
.
.
.
+
1
⏟
n
v
e
z
e
s
{\displaystyle n={\begin{matrix}\underbrace {1+1+...+1} \\n\;vezes\end{matrix}}}
Adição dos Naturais
editar
Somar dois números n e p:
n
+
p
=
1
+
1
+
.
.
.
+
1
⏟
n
v
e
z
e
s
+
1
+
1
+
.
.
.
+
1
⏟
p
v
e
z
e
s
=
1
+
1
+
.
.
.
+
1
⏟
n
+
p
v
e
z
e
s
{\displaystyle n+p={\begin{matrix}\underbrace {1+1+...+1} \\n\;vezes\end{matrix}}+{\begin{matrix}\underbrace {1+1+...+1} \\p\;vezes\end{matrix}}={\begin{matrix}\underbrace {1+1+...+1} \\n+p\;vezes\end{matrix}}}
sucessor de um número natural
editar
Um número natural n tem o seu sucessor como sendo s(n) = n + 1.
propriedade identidade de sucessão
editar
Sejam a,b naturais, assim se a=b então s(a) = s(b)
Vamos fixar a natural e provar por indução sobre b. assim:
mostrar que é válido para b = 1: a=1, então s(a) = 1+1 e s(1) = 1+1, logo s(a) = s(1)
supor que seja válido para b = k, ou seja, a=k implica que s(a) = s(k), ou seja, a+1 = k+1.
Provar que seja válido para b = k+1:
s
(
a
+
1
)
=
1
(
a
+
1
)
+
1
=
2
(
k
+
1
)
+
1
=
3
s
(
k
+
1
)
{\displaystyle s(a+1)=^{1}(a+1)+1=^{2}(k+1)+1=^{3}s(k+1)}
onde as igualdades 1 e 3 ocorrem por definição de sucessão e a igualdade 2 ocorre por hipótese de indução. o sucessor do k-ésimo sucessor
editar
Vamos definir
s
k
(
s
(
n
)
)
=
s
k
+
1
(
n
)
{\displaystyle s_{k}(s(n))=s_{k+1}(n)}
p-sucessor de n será definido como
s
p
(
n
)
=
n
+
p
{\displaystyle s_{p}(n)=n+p}
p
=
1
+
1
+
.
.
.
+
1
⏟
p
v
e
z
e
s
{\displaystyle p={\begin{matrix}\underbrace {1+1+...+1} \\p\;vezes\end{matrix}}}
Exemplos:
s
(
n
)
=
n
+
1
,
s
2
(
n
)
=
(
n
+
1
)
+
1
=
n
+
2
,
s
3
(
n
)
=
(
n
+
2
)
+
1
=
n
+
3
,
.
.
.
,
e
s
p
(
n
)
=
(
n
+
p
−
1
)
+
1
=
n
+
p
.
{\displaystyle s(n)=n+1,s_{2}(n)=(n+1)+1=n+2,s_{3}(n)=(n+2)+1=n+3,...,\;e\;s_{p}(n)=(n+p-1)+1=n+p.}
Provaremos por indução que essa propriedade é válida.
Quando p=1, temos que
s
1
(
n
)
=
n
+
1
=
s
(
n
)
{\displaystyle s_{1}(n)=n+1=s(n)}
Suponhamos ser válida para p = k, ou seja,
s
k
(
n
)
=
n
+
k
{\displaystyle s_{k}(n)=n+k}
provaremos que é válida para p=k+1, ou seja, que
s
k
+
1
(
n
)
=
n
+
(
k
+
1
)
{\displaystyle s_{k+1}(n)=n+(k+1)}
Pela hipótese temos que
s
k
(
n
)
=
n
+
k
{\displaystyle s_{k}(n)=n+k}
Pela identidade da sucessão é implicado que
s
(
s
k
(
n
)
)
=
s
(
n
+
k
)
{\displaystyle s(s_{k}(n))=s(n+k)}
Pela definição de sucessão ocorre que
s
k
(
n
)
+
1
=
(
n
+
k
)
+
1
{\displaystyle s_{k}(n)+1=(n+k)+1}
Pela definição de sucessão ocorre que
s
k
+
1
(
n
)
=
n
+
(
k
+
1
)
{\displaystyle s_{k+1}(n)=n+(k+1)}
Faltando apenas mostrar o porque que para todo n,k naturais, é válido que
(
n
+
k
)
+
1
=
n
+
(
k
+
1
)
{\displaystyle (n+k)+1=n+(k+1)}
O sucessor de uma adição n + p
editar
Na última prova é bem aceitável aceitar como verdadeira a igualdade
(
n
+
k
)
+
1
=
n
+
(
k
+
1
)
{\displaystyle (n+k)+1=n+(k+1)}
Assim vamos fazer indução sobre p em
(
n
+
p
)
+
1
=
n
+
(
p
+
1
)
{\displaystyle (n+p)+1=n+(p+1)}
quando p = 1, temos que
∀
n
∈
N
,
(
n
+
1
)
+
1
=
n
+
(
1
+
1
)
⇒
s
(
s
(
n
)
)
=
n
+
s
(
1
)
=
n
+
2
{\displaystyle \forall \;n\in \mathbb {N} ,(n+1)+1=n+(1+1)\Rightarrow s(s(n))=n+s(1)=n+2}
Supomos verdadeira para p = k, ou seja,
(
n
+
k
)
+
1
=
n
+
(
k
+
1
)
,
o
u
s
e
j
a
,
s
(
n
+
k
)
=
n
+
s
(
k
)
{\displaystyle (n+k)+1=n+(k+1),\;ou\;seja,\;s(n+k)=n+s(k)}
Queremos provar que é válido para p = k+1, isto é,
(
n
+
(
k
+
1
)
)
+
1
=
n
+
(
(
k
+
1
)
+
1
)
,
o
u
s
e
j
a
,
s
(
n
+
s
(
k
)
)
=
n
+
s
(
s
(
k
)
)
{\displaystyle (n+(k+1))+1=n+((k+1)+1),\;ou\;seja,\;s(n+s(k))=n+s(s(k))}
Por hipótese,
s
(
n
+
k
)
=
n
+
s
(
k
)
{\displaystyle s(n+k)=n+s(k)}
Pela identidade da sucessão temos que
s
(
n
+
s
(
k
)
)
=
s
(
s
(
n
+
k
)
)
{\displaystyle s(n+s(k))=s(s(n+k))}
Mas
s
(
s
(
n
+
k
)
)
=
(
n
+
k
)
+
2
=
(
n
+
k
)
+
1
+
1
=
n
+
(
k
+
1
)
+
1
=
n
+
s
(
k
)
+
1
=
n
+
s
(
s
(
k
)
)
{\displaystyle s(s(n+k))=(n+k)+2=(n+k)+1+1=n+(k+1)+1=n+s(k)+1=n+s(s(k))}
ou
(
n
+
p
)
+
1
=
1
+
1
+
.
.
.
+
1
⏟
n
+
p
v
e
z
e
s
+
1
=
1
+
1
+
.
.
.
+
1
⏟
n
+
p
+
1
v
e
z
e
s
=
1
+
1
+
.
.
.
+
1
⏟
n
v
e
z
e
s
+
1
+
1
+
.
.
.
+
1
⏟
p
+
1
v
e
z
e
s
=
n
+
(
p
+
1
)
{\displaystyle (n+p)+1={\begin{matrix}\underbrace {1+1+...+1} \\n+p\;vezes\end{matrix}}+1={\begin{matrix}\underbrace {1+1+...+1} \\n+p+1\;vezes\end{matrix}}={\begin{matrix}\underbrace {1+1+...+1} \\n\;vezes\end{matrix}}+{\begin{matrix}\underbrace {1+1+...+1} \\p+1\;vezes\end{matrix}}=n+(p+1)}
Definição do "Axioma da adição":
(
n
+
p
)
+
1
=
n
+
(
p
+
1
)
{\displaystyle (n+p)+1=n+(p+1)}
Teorema: Associatividade da adição
editar
∀
m
,
n
,
p
∈
N
,
m
+
(
n
+
p
)
=
(
m
+
n
)
+
p
{\displaystyle \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
{\displaystyle m+(n+k)=(m+n)+k}
Provaremos que é válido para p = k+1, ou seja,
m
+
(
n
+
(
k
+
1
)
)
=
(
m
+
n
)
+
(
k
+
1
)
{\displaystyle 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
)
{\displaystyle 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. Axioma: Comuto de m e 1 na adição
editar
Provar por indução que
∀
m
∈
N
,
m
+
1
=
1
+
m
{\displaystyle \forall \;m\in \mathbb {N} ,m+1=1+m}
Para m = 1, temos que 1+1=1+1 (verdade)
Supomos válido para m = k, isto é, k+1 = 1+k e provar ser verdadeiro para k+1, ou seja,
(
k
+
1
)
+
1
=
1
+
(
k
+
1
)
{\displaystyle (k+1)+1=1+(k+1)}
(
k
+
1
)
+
1
=
1
(
1
+
k
)
+
1
=
2
1
+
(
k
+
1
)
{\displaystyle (k+1)+1=^{1}(1+k)+1=^{2}1+(k+1)}
onde a igualdade 1 ocorre pela hipótese e a igualdade 2 ocorre pelo axioma da adição. Comutatividade da adição
editar
∀
m
,
n
∈
N
,
m
+
n
=
n
+
m
{\displaystyle \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
{\displaystyle m+k=k+m}
Provaremos que é válido para n = k+1, ou seja,
m
+
(
k
+
1
)
=
(
k
+
1
)
+
m
{\displaystyle 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
{\displaystyle 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. Multiplicação dos naturais
editar
Multiplicação de dois números naturais, m e n
editar
m
⋅
n
=
m
+
m
+
.
.
.
+
m
⏟
n
v
e
z
e
s
{\displaystyle m\cdot n={\begin{matrix}\underbrace {m+m+...+m} \\n\;vezes\end{matrix}}}
Definição: multiplicação de m por (n+1)
editar
m
⋅
(
n
+
1
)
=
m
+
m
+
.
.
.
+
m
⏟
n
+
1
v
e
z
e
s
=
m
+
m
+
.
.
.
+
m
⏟
n
v
e
z
e
s
+
m
=
m
n
+
m
{\displaystyle m\cdot (n+1)={\begin{matrix}\underbrace {m+m+...+m} \\n+1\;vezes\end{matrix}}={\begin{matrix}\underbrace {m+m+...+m} \\n\;vezes\end{matrix}}+m=mn+m}
Distributividade
editar
Para quaisquer
m
,
n
,
p
∈
N
,
{\displaystyle m,n,p\in \mathbb {N} ,}
m
⋅
(
n
+
p
)
=
m
⋅
n
+
m
⋅
p
{\displaystyle 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
⋅
(
n
+
1
)
=
m
⋅
n
+
m
⋅
1
{\displaystyle m\cdot (n+1)=m\cdot n+m\cdot 1}
Supomos válido para p = k, ou seja,
m
⋅
(
n
+
k
)
=
m
⋅
n
+
m
⋅
k
{\displaystyle m\cdot (n+k)=m\cdot n+m\cdot k}
Provemos ser válido para n = k+1:
m
⋅
(
n
+
(
k
+
1
)
)
=
1
m
⋅
(
(
n
+
k
)
+
1
)
=
2
m
⋅
(
n
+
k
)
+
m
=
3
(
m
⋅
n
+
m
⋅
k
)
+
m
=
4
m
⋅
n
+
(
m
⋅
k
+
m
⋅
1
)
=
5
m
⋅
n
+
m
⋅
(
k
+
1
)
{\displaystyle 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. Comuto de 1 e m na multiplicação
editar
Para quaisquer
m
∈
N
,
{\displaystyle m\in \mathbb {N} ,}
m
⋅
1
=
1
⋅
m
{\displaystyle 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
⋅
1
=
1
⋅
1
{\displaystyle 1\cdot 1=1\cdot 1}
Supomos ser válido para m = k, ou seja,
k
⋅
1
=
1
⋅
k
{\displaystyle k\cdot 1=1\cdot k}
Provaremos ser válido para m = k + 1:
1
⋅
(
k
+
1
)
=
1
1
⋅
k
+
1
⋅
1
=
2
k
⋅
1
+
1
⋅
1
=
3
(
k
+
1
)
⋅
1
{\displaystyle 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. Comutatividade da Multiplicação
editar
Para quaisquer
m
,
n
∈
N
,
{\displaystyle m,n\in \mathbb {N} ,}
m
⋅
n
=
n
⋅
m
{\displaystyle 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
⋅
1
=
1
⋅
m
{\displaystyle m\cdot 1=1\cdot m}
Supomos válido para n=k, ou seja,
m
⋅
k
=
k
⋅
m
{\displaystyle m\cdot k=k\cdot m}
vamos provar que é válido para n=k+1:
m
⋅
(
k
+
1
)
=
1
m
⋅
k
+
m
⋅
1
=
2
k
⋅
m
+
1
⋅
m
=
3
(
k
+
1
)
⋅
m
{\displaystyle 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. Associatividade da multiplicação
editar
∀
m
,
n
,
p
∈
N
,
m
⋅
(
n
⋅
p
)
=
(
m
⋅
n
)
⋅
p
{\displaystyle \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
⋅
(
n
⋅
1
)
=
m
⋅
n
=
(
m
⋅
n
)
⋅
1
{\displaystyle m\cdot (n\cdot 1)=m\cdot n=(m\cdot n)\cdot 1}
supomos válido para p = k, isto é,
m
⋅
(
n
⋅
k
)
=
(
m
⋅
n
)
⋅
k
{\displaystyle m\cdot (n\cdot k)=(m\cdot n)\cdot k}
Provaremos que é válido para p = k+1, ou seja,
m
⋅
(
n
⋅
(
k
+
1
)
)
=
(
m
⋅
n
)
⋅
(
k
+
1
)
{\displaystyle m\cdot (n\cdot (k+1))=(m\cdot n)\cdot (k+1)}
Assim,
m
⋅
(
n
⋅
(
k
+
1
)
)
=
1
m
⋅
(
(
n
⋅
k
)
+
n
)
=
2
(
m
⋅
(
n
⋅
k
)
)
+
m
⋅
n
=
3
(
(
m
⋅
n
)
⋅
k
)
+
m
⋅
n
=
4
(
m
⋅
n
)
⋅
(
k
+
1
)
{\displaystyle 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. outras propriedades
editar
Lei de corte para adição
editar
S
e
m
,
n
,
p
∈
N
e
m
+
p
=
n
+
p
,
l
o
g
o
m
=
n
{\displaystyle Se\;m,n,p\in \mathbb {N} \;e\;m+p=n+p,\;logo\;m=n}
Vamos fazer indução sobre p.
Mostrar válido para p = 1, ou seja,
m
+
1
=
n
+
1
⇒
m
=
n
{\displaystyle m+1=n+1\Rightarrow m=n}
Temos que s(m) = m + 1, mas pela hipótese s(m) = n + 1. Mas s(n) = n+1, assim m e n têm os mesmo sucessores. Pela identidade da sucessão, m = n.
Supor válido para p = k, ou seja,
m
+
k
=
n
+
k
⇒
m
=
n
{\displaystyle m+k=n+k\Rightarrow m=n}
Mostrar válido para p = k+1:
m
+
k
+
1
=
n
+
k
+
1
{\displaystyle m+k+1=n+k+1}
Recíproca da Lei de corte para adição
editar
S
e
m
,
n
,
p
∈
N
e
m
=
n
,
l
o
g
o
m
+
p
=
n
+
p
{\displaystyle Se\;m,n,p\in \mathbb {N} \;e\;m=n,\;logo\;m+p=n+p}
Vamos fazer indução sobre p.
Mostrar válido para p = 1, ou seja,
m
=
n
⇒
m
+
1
=
n
+
1
{\displaystyle m=n\Rightarrow m+1=n+1}
como m = n, logo s(m) = s(n), ou seja, m + 1 = n + 1.
Supor válido para p = k, ou seja,
m
=
n
⇒
m
+
k
=
n
+
k
{\displaystyle m=n\Rightarrow m+k=n+k}
Mostrar válido para p = k+1:
m
+
(
k
+
1
)
=
1
(
m
+
k
)
+
1
=
2
(
n
+
k
)
+
1
=
3
n
+
(
k
+
1
)
{\displaystyle m+(k+1)=^{1}(m+k)+1=^{2}(n+k)+1=^{3}n+(k+1)}
onde as igualdades 1 e 3 ocorrem por associatividade da adição e a igualdade 2 ocorre pela hipótese da indução quando p=k. Lei de corte para multiplicação
editar
S
e
m
,
n
,
p
∈
N
e
m
⋅
p
=
n
⋅
p
,
l
o
g
o
m
=
n
{\displaystyle Se\;m,n,p\in \mathbb {N} \;e\;m\cdot p=n\cdot p,\;logo\;m=n}
Vamos fazer indução sobre p.
Mostrar válido para p = 1, ou seja,
m
⋅
1
=
n
⋅
1
⇒
m
=
n
{\displaystyle m\cdot 1=n\cdot 1\Rightarrow m=n}
Supor válido para p = k, ou seja,
m
⋅
k
=
n
⋅
k
⇒
m
=
n
{\displaystyle m\cdot k=n\cdot k\Rightarrow m=n}
Mostrar válido para p = k + 1:
m
⋅
(
k
+
1
)
=
1
m
⋅
k
+
m
⋅
1
=
2
n
⋅
k
+
n
⋅
1
=
3
n
⋅
(
k
+
1
)
⇒
4
m
=
n
{\displaystyle m\cdot (k+1)=^{1}m\cdot k+m\cdot 1=^{2}n\cdot k+n\cdot 1=^{3}n\cdot (k+1)\Rightarrow _{4}m=n}
onde as igualdades 1 e 3 ocorrem pela lei da distributividade, a igualdade 2 ocorre pela hipótese da indução quando p=k e a implicação 4 ocorre pela hipótese de indução de p = k. 
