Utilizador:Thiago Marcel/Mestrado/Análise/Conjuntos Finitos, Enumeráveis e não-enumeráveis/1-8

1

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\subset \mathbb {N}$, tem-se $A-s(A)\not =\emptyset$
• P1 $S:\mathbb {N} \rightarrow \mathbb {N}$ é injetiva, isto é, dados $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\subset \mathbb {N} ;1_{X}\in X,\forall n\in X\Rightarrow s(n)\in X$, então $X=\mathbb {N}$

Resolução:

• O axioma A na presença do axioma P2: Temos que $1_{A}\in A$ não é sucessor de nenhum elemento de A, logo $A-s(A)=\{1_{A}\}$.
• Se existe um $n\in A-\{1_{A}\}\;$. Pela prop 2, $\exists \;m\in A;s(m)=n\in s(A)$, onde n é diferente de m pela propriedade 1. $\Rightarrow s(A)\subset A.$
• Logo o axioma A na presença dos axiomas P1 e P2 é equivalente a P3.

2

Dados $a,b\in \mathbb {N}$, prove que $\exists \;m\in \mathbb {N} ;m\cdot a>b$

Resolução

• Pela lei da tricotomia, $a<b{\mbox{ ou }}a=b{\mbox{ ou }}a>b,$ logo:
  • Se $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\in \mathbb {N} \Rightarrow a+a>b\Rightarrow 2\cdot a>b\Rightarrow m=2$
  • Se $a>b\in \mathbb {N} \Rightarrow \forall q\in \mathbb {N} ,q\cdot a>b\Rightarrow m=q$

3

Seja $a\in \mathbb {N} .$ Se um conjunto X é tal que $a\in X$ e, além disso, $n\in X\Rightarrow n+1\in X,$ então $X\supset \{n\in \mathbb {N} ;n\geq a\}$

Resolução

• Como $a\in X\Rightarrow a+1\in X.{\mbox{ Suponha que }}a+n\in X.{\mbox{ Devemos mostrar que }}a+(n+1)\in X.{\mbox{ Como }}a+n\in X\Rightarrow$ $\Rightarrow (a+n)+1\in X\Rightarrow a+(n+1)\in X.{\mbox{ Logo }}a+n\in X,\forall n\in \mathbb {N} .$
• Tome $t>a;t\in \mathbb {N} \Rightarrow t=a+n,n\in \mathbb {N} \Rightarrow t\in X.{\mbox{ Portanto }}X\supset \{t\in \mathbb {N} ;t>a\}\cup \{a\}$

5

Um elemento $a\in \mathbb {N}$ chama-se antecessor de $b\in \mathbb {N}$ quando se tem $a<b\;$ mas não existe $c\in \mathbb {N}$ tal que $a<c<b\;$. Prove que, exceto 1, todo número natural possui um antecessor.

Resolução

• 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,{\mbox{ temos }}t>t-1\geq 1,{\mbox{ onde }}t>c>t-1\Rightarrow c\not \in \mathbb {N} .$
  • Temos que $2>1\geq 1,$ onde não existe nenhum natural entre 1 e 2.
  • Suponha que $t>t-1\geq 1;t>c>t-1,c\not \in \mathbb {N} .$
  • Como $t>t-1\geq 1,{\mbox{ logo }}t+1>(t-1)+1\geq 2>1\Rightarrow (t+1)>(t+1)-1=t\geq 1.$
    • ${\mbox{ onde }}t+1>c\Rightarrow t+1-t>c-t\Rightarrow 1>c-t\Rightarrow c\not \in \mathbb {N}$

6

Use indução para demonstrar os seguintes fatos:

6a

$2(1+2+...+n)=n(n+1)$

Resolução

Vamos provar por indução sobre n:

• Mostrar ser válido para n=1: $2(1)=1(1+1)$
• Supor ser válido para n=t: $2(1+2+...+t)=t(t+1)$
• Provar ser válido para n=t+1: $2(1+2+...+t)+2(t+1)=t(t+1)+2(t+1)\Rightarrow 2(1+2+...+t+t+1)=(t+1)((t+1)+1)$.

6b

$1+3+5+...+(2n+1)=(n+1)^{2}$

Resolução

Vamos provar por indução sobre n:

• Mostrar ser válido para n = 1: $1+(2.1+1)=(1+1)^{2}\Rightarrow 1+3=2^{2}$
• Supor ser válido para n = t: $1+3+5+...+(2t+1)=(t+1)^{2}$.
• Provar ser válido para n = t+1: Como é válido para n=t, logo $1+3+5+...+(2t+1)+(2(t+1)+1)=(t+1)^{2}+(2(t+1)+1)=$ $=t^{2}+2t+1+(2(t+1)+1)=t^{2}+4t+4=(t+2)^{2}=((t+1)+1)^{2}$.

6c

$(a-1)(1+a+...+a^{n})=a^{n+1}-1$

Resolução

Vamos provar por indução sobre n:

• Mostrar ser válido para n=1: $(a-1)(1+a)=a^{1+1}-1$
• Supor ser válido para n=t: $(a-1)(1+a+...+a^{t})=a^{t+1}-1$
• Provar ser válido para n = t+1: $(a-1)(1+a+...+a^{n})+(a-1)a^{n+1}=a^{n+1}-1+(a-1)a^{n+1}=a^{n+1}-1+a^{n+1+1}-a^{n+1}=a^{n+2}-1$.

6d

$n\geq 4\Rightarrow n!>2^{n}$

Resolução

Vamos mostrar por indução sobre n:

• Mostrar ser válido para n=4: $4!>2^{4}\Rightarrow 4.3.2.1>2.2.2.2(/8)\Rightarrow 3>2$
• Supor válido para n=t: $t!>2^{t}$
• Provar ser válido para n = t+1: $(t+1).t!>(t+1).2^{t},{\mbox{ como }}(t+1)>2\Rightarrow (t+1)!>(t+1).2^{t}>2^{t+1}$

7

Use o segundo principio da indução para demonstrar a unicidade da decomposição de um número natural em fatores primos

8

Seja X um conjunto com n elementos. Use indução para provar que o conjunto das bijeções( ou permutações) $f:X\rightarrow X$ tem n! elementos.

Resolução

Vamos provar usando indução sobre n:

• Vamos mostrar que é válido para n=1: $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}\}\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}{\mbox{ e }}x_{2}$ na imagem

• (desnecessário) Vamos mostrar que é válido para n=3: $X=\{x_{1},x_{2},x_{3}\}\Rightarrow \{(x_{1},x_{1}),(x_{2},x_{2}),(x_{3},x_{3})\}{\mbox{ ou }}$${\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 }}$${\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}{\mbox{ e }}x_{3}$ na imagem

• Vamos supor ser válido para n=t: Tome $X=\{x_{1},x_{2},...,x_{t}\}{\mbox{ e }}f:X\rightarrow X$. O conjuntos das bijeções sobre f tem $t!\;$ elementos, pois permutamos $x_{1},x_{2},...{\mbox{ e }}x_{t}$ na imagem

• Vamos provar que é válido para n=t+1: Tome $X\cup \{x_{t+1}\}=\{x_{1},x_{2},...,x_{t},x_{t+1}\}.$ Fixemos $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!$ elementos. Fixemos $f(x_{i})=x_{t+1},i=1,...,n+1$. Assim o conjuntos das bijeções sobre $f:X\cup \{x_{t+1}\}\rightarrow X\cup \{x_{t+1}\}$ tem $(t+1)\cdot t!=(t+1)!$ elementos.