Prove que na presença dos axiomas P1 e P2, o axioma (A) abaixo é equivalente a P3.
(A) Para todo subconjunto não-vazio
A
⊂
N
{\displaystyle A\subset \mathbb {N} }
, tem-se
A
−
s
(
A
)
≠
∅
{\displaystyle A-s(A)\not =\emptyset }
P1
S
:
N
→
N
{\displaystyle S:\mathbb {N} \rightarrow \mathbb {N} }
é injetiva, isto é, dados
m
,
n
∈
N
,
s
(
m
)
=
s
(
n
)
⇒
m
=
n
{\displaystyle m,n\in \mathbb {N} ,s(m)=s(n)\Rightarrow m=n}
P2 1 não é sucessor de nenhum natural, e se existe um n natural que é diferente de 1, existe um único m natural tal que s(m)=n.
P3 Se
X
⊂
N
;
1
X
∈
X
,
∀
n
∈
X
⇒
s
(
n
)
∈
X
{\displaystyle X\subset \mathbb {N} ;1_{X}\in X,\forall n\in X\Rightarrow s(n)\in X}
, então
X
=
N
{\displaystyle X=\mathbb {N} }
O axioma A na presença do axioma P2: Temos que
1
A
∈
A
{\displaystyle 1_{A}\in A}
não é sucessor de nenhum elemento de A, logo
A
−
s
(
A
)
=
{
1
A
}
{\displaystyle A-s(A)=\{1_{A}\}}
.
Se existe um
n
∈
A
−
{
1
A
}
{\displaystyle n\in A-\{1_{A}\}\;}
. Pela prop 2,
∃
m
∈
A
;
s
(
m
)
=
n
∈
s
(
A
)
{\displaystyle \exists \;m\in A;s(m)=n\in s(A)}
, onde n é diferente de m pela propriedade 1.
⇒
s
(
A
)
⊂
A
.
{\displaystyle \Rightarrow s(A)\subset A.}
Logo o axioma A na presença dos axiomas P1 e P2 é equivalente a P3.
Dados
a
,
b
∈
N
{\displaystyle a,b\in \mathbb {N} }
, prove que
∃
m
∈
N
;
m
⋅
a
>
b
{\displaystyle \exists \;m\in \mathbb {N} ;m\cdot a>b}
Pela lei da tricotomia,
a
<
b
ou
a
=
b
ou
a
>
b
,
{\displaystyle a<b{\mbox{ ou }}a=b{\mbox{ ou }}a>b,}
logo:
Se
a
<
b
∈
N
⇒
∃
q
,
r
∈
N
;
b
=
a
⋅
q
+
r
,
r
<
a
⇒
(
q
+
1
)
⋅
a
>
b
⇒
m
=
q
+
1
{\displaystyle a<b\in \mathbb {N} \Rightarrow \exists q,r\in \mathbb {N} ;b=a\cdot q+r,r<a\Rightarrow (q+1)\cdot a>b\Rightarrow m=q+1}
Se
a
=
b
∈
N
⇒
a
+
a
>
b
⇒
2
⋅
a
>
b
⇒
m
=
2
{\displaystyle a=b\in \mathbb {N} \Rightarrow a+a>b\Rightarrow 2\cdot a>b\Rightarrow m=2}
Se
a
>
b
∈
N
⇒
∀
q
∈
N
,
q
⋅
a
>
b
⇒
m
=
q
{\displaystyle a>b\in \mathbb {N} \Rightarrow \forall q\in \mathbb {N} ,q\cdot a>b\Rightarrow m=q}
Um elemento
a
∈
N
{\displaystyle a\in \mathbb {N} }
chama-se antecessor de
b
∈
N
{\displaystyle b\in \mathbb {N} }
quando se tem
a
<
b
{\displaystyle a<b\;}
mas não existe
c
∈
N
{\displaystyle c\in \mathbb {N} }
tal que
a
<
c
<
b
{\displaystyle a<c<b\;}
. Prove que, exceto 1, todo número natural possui um antecessor.
1 é o menor natural, logo não existe um natural menor que ele, logo 1 não tem antecessor.
Queremos mostrar que, qualquer que seja
t
>
1
,
temos
t
>
t
−
1
≥
1
,
onde
t
>
c
>
t
−
1
⇒
c
∉
N
.
{\displaystyle t>1,{\mbox{ temos }}t>t-1\geq 1,{\mbox{ onde }}t>c>t-1\Rightarrow c\not \in \mathbb {N} .}
Temos que
2
>
1
≥
1
,
{\displaystyle 2>1\geq 1,}
onde não existe nenhum natural entre 1 e 2.
Suponha que
t
>
t
−
1
≥
1
;
t
>
c
>
t
−
1
,
c
∉
N
.
{\displaystyle t>t-1\geq 1;t>c>t-1,c\not \in \mathbb {N} .}
Como
t
>
t
−
1
≥
1
,
logo
t
+
1
>
(
t
−
1
)
+
1
≥
2
>
1
⇒
(
t
+
1
)
>
(
t
+
1
)
−
1
=
t
≥
1.
{\displaystyle t>t-1\geq 1,{\mbox{ logo }}t+1>(t-1)+1\geq 2>1\Rightarrow (t+1)>(t+1)-1=t\geq 1.}
onde
t
+
1
>
c
⇒
t
+
1
−
t
>
c
−
t
⇒
1
>
c
−
t
⇒
c
∉
N
{\displaystyle {\mbox{ onde }}t+1>c\Rightarrow t+1-t>c-t\Rightarrow 1>c-t\Rightarrow c\not \in \mathbb {N} }
Use o segundo principio da indução para demonstrar a unicidade da decomposição de um número natural em fatores primos
Não está pronta a Resolução
editar
Seja X um conjunto com n elementos. Use indução para provar que o conjunto das bijeções( ou permutações)
f
:
X
→
X
{\displaystyle f:X\rightarrow X}
tem n! elementos.
Vamos provar usando indução sobre n:
Vamos mostrar que é válido para n=1:
X
=
{
x
1
}
⇒
{
f
(
x
1
)
=
x
1
}
⇒
{\displaystyle X=\{x_{1}\}\Rightarrow \{f(x_{1})=x_{1}\}\Rightarrow }
o conjuntos das bijeções sobre f tem 1 elemento = 1!
(desnecessário) Vamos mostrar que é válido para n=2:
X
=
{
x
1
,
x
2
}
⇒
{
(
x
1
,
x
1
)
,
(
x
2
,
x
2
)
}
ou
{
(
x
1
,
x
2
)
,
(
x
2
,
x
1
)
}
⇒
{\displaystyle X=\{x_{1},x_{2}\}\Rightarrow \{(x_{1},x_{1}),(x_{2},x_{2})\}{\mbox{ ou }}\{(x_{1},x_{2}),(x_{2},x_{1})\}\Rightarrow }
o conjuntos das bijeções sobre f tem 2 elementos = 2!. Percebe-se que permutamos
x
1
e
x
2
{\displaystyle x_{1}{\mbox{ e }}x_{2}}
na imagem
(desnecessário) Vamos mostrar que é válido para n=3:
X
=
{
x
1
,
x
2
,
x
3
}
⇒
{
(
x
1
,
x
1
)
,
(
x
2
,
x
2
)
,
(
x
3
,
x
3
)
}
ou
{\displaystyle X=\{x_{1},x_{2},x_{3}\}\Rightarrow \{(x_{1},x_{1}),(x_{2},x_{2}),(x_{3},x_{3})\}{\mbox{ ou }}}
ou
{
(
x
1
,
x
1
)
,
(
x
2
,
x
3
)
,
(
x
3
,
x
2
)
}
ou
{
(
x
1
,
x
2
)
,
(
x
2
,
x
1
)
,
(
x
3
,
x
3
)
}
ou
{
(
x
1
,
x
2
)
,
(
x
2
,
x
3
)
,
(
x
3
,
x
1
)
}
ou
{\displaystyle {\mbox{ ou }}\{(x_{1},x_{1}),(x_{2},x_{3}),(x_{3},x_{2})\}{\mbox{ ou }}\{(x_{1},x_{2}),(x_{2},x_{1}),(x_{3},x_{3})\}{\mbox{ ou }}\{(x_{1},x_{2}),(x_{2},x_{3}),(x_{3},x_{1})\}{\mbox{ ou }}}
ou
{
(
x
1
,
x
3
)
,
(
x
2
,
x
2
)
,
(
x
3
,
x
1
)
}
ou
{
(
x
1
,
x
3
)
,
(
x
2
,
x
1
)
,
(
x
3
,
x
2
)
}
⇒
{\displaystyle {\mbox{ ou }}\{(x_{1},x_{3}),(x_{2},x_{2}),(x_{3},x_{1})\}{\mbox{ ou }}\{(x_{1},x_{3}),(x_{2},x_{1}),(x_{3},x_{2})\}\Rightarrow }
o conjuntos das bijeções sobre f tem 6 elementos = 3!. Percebe-se que permutamos
x
1
,
x
2
e
x
3
{\displaystyle x_{1},x_{2}{\mbox{ e }}x_{3}}
na imagem
Vamos supor ser válido para n=t: Tome
X
=
{
x
1
,
x
2
,
.
.
.
,
x
t
}
e
f
:
X
→
X
{\displaystyle X=\{x_{1},x_{2},...,x_{t}\}{\mbox{ e }}f:X\rightarrow X}
. O conjuntos das bijeções sobre f tem
t
!
{\displaystyle t!\;}
elementos, pois permutamos
x
1
,
x
2
,
.
.
.
e
x
t
{\displaystyle x_{1},x_{2},...{\mbox{ e }}x_{t}}
na imagem
Vamos provar que é válido para n=t+1: Tome
X
∪
{
x
t
+
1
}
=
{
x
1
,
x
2
,
.
.
.
,
x
t
,
x
t
+
1
}
.
{\displaystyle X\cup \{x_{t+1}\}=\{x_{1},x_{2},...,x_{t},x_{t+1}\}.}
Fixemos
f
(
x
1
)
=
x
t
+
1
{\displaystyle f(x_{1})=x_{t+1}}
e permutemos os t elementos restantes, assim temos que o conjunto das bijeções de t elementos tem
t
!
{\displaystyle t!}
elementos. Fixemos
f
(
x
i
)
=
x
t
+
1
,
i
=
1
,
.
.
.
,
n
+
1
{\displaystyle f(x_{i})=x_{t+1},i=1,...,n+1}
. Assim o conjuntos das bijeções sobre
f
:
X
∪
{
x
t
+
1
}
→
X
∪
{
x
t
+
1
}
{\displaystyle f:X\cup \{x_{t+1}\}\rightarrow X\cup \{x_{t+1}\}}
tem
(
t
+
1
)
⋅
t
!
=
(
t
+
1
)
!
{\displaystyle (t+1)\cdot t!=(t+1)!}
elementos.