Ir ao conteúdo principal

Matemática Discreta: notas de aula

Ricardo Machado

Seção 1.1 Números Ordinais

Subseção 1.1.1 Introdução

A primeira experiência que a maior parte de nós tem com a Matemática é por meio do processo de contagem. É importante observar que aprender a contar tem duas etapas bem distintas, com graus de complexidade também distintos:
  • Na primeira etapa, aprendemos a enunciar uma sequência de palavras (um, dois, três, ...), sem atribuir significado a elas;
  • Algum tempo depois, aprendemos a usar esta sequência para contar os elementos de um conjunto, ou seja, estabelecer uma correspondência entre os elementos do conjunto e estas palavras que chamamos de números. Algo notável, que não custamos a observar, é que, não importa como façamos a correspondência, o número final é sempre o mesmo -a ele, denominamos o número de elementos do conjunto.
A mesma tarefa em duas etapas deve ser empreendida ao se estabelecer a fundamentação matemática apropriada para os números naturais. Ao olhar os números naturais como uma simples sequência, estamos diante do que chamamos de números ordinais, examinados a seguir, enquanto seu uso como instrumento de contagem remete à noção de número cardinal, estudada no fim deste capítulo.

Subseção 1.1.2 Números Ordinais

Como descrever matematicamente a estrutura do conjunto dos números naturais, no sentido de números ordinais? Isto é feito por meio de uma lista de propriedades essenciais, chamadas de axiomas, que caracterizam a estrutura da sequência, sem ambiguidades ou propriedades supérfluas. Giuseppe Peano (1858-1932) propôs uma lista de axiomas, baseado na noção de sucessor de um número natural. A construção de Peano caracteriza o conjunto dos números naturais \(\mathbb{N}\) por meio dos seguintes \(4\) axiomas:
  1. Todo número natural tem um único sucessor, que também é um número natural.
  2. Números naturais diferentes tem sucessores diferentes.
  3. Existe um único número natural, designado por \(1\text{,}\) que não é sucessor de nenhum outro.
  4. Seja \(X\) um conjunto de números naturais (isto é \(X\subset \mathbb{N}\)). Se \(1\in X\) e se, além disso, o sucessor de cada elemento de \(X\) ainda pertence a \(X\text{,}\) então \(X=\mathbb{N}\text{.}\)
A noção de sucessor de um número natural está intimamente relacionada à ideia de adição: tomar o sucessor é equivalente a somar uma unidade, como discutido em mais detalhes na Subseção 1.1.3. Os axiomas de Peano podem ser reescritos como se segue, representando como \(n+1\) o sucessor de \(n\text{:}\)
  1. Todo número natural \(n\) tem um sucessor, representado por \(n+1\text{.}\)
  2. Se \(m+1=n+1\text{,}\) então \(m=n\text{.}\)
  3. Existe um único número natural, designado por \(1\text{,}\) tal que \(n+1\neq 1\text{,}\) para todo \(n\in \mathbb{N}\text{.}\)
  4. Seja \(X\) um conjunto de números naturais (isto é, \(X\subset \mathbb{N}\)). Se \(1\in X\) e se, além disso, \(n+1\in X\text{,}\) para cada \(n\in X\text{,}\) então \(X=\mathbb{N}\text{.}\)

Nota 1.1.1.

O terceiro axioma estabelece \(1\) como sendo o único número natural que não é o sucessor de nenhum outro e que, portanto, representa o "ponto de partida" no conjunto \(\mathbb{N}=\{1, 2, 3, \ldots\}\) dos números naturais. É comum, também adotar-se o \(0\) como ponto de partida, levando a \(\mathbb{N}=\{0, 1, 2, 3, \ldots\}\text{.}\) A opção por uma ou outra alternativa é uma questão de gosto ou de conveniência.
Embora todos os quatro axiomas sejam fundamentais para a caracterização dos números naturais, o último, chamado de Axioma de Indução, se destaca. Ele fornece um mecanismo para garantir que um dado subconjunto \(X\) de \(\mathbb{N}\) inclui, na verdade, todos os elementos de \(\mathbb{N}\text{.}\) Por esta razão, é um instrumento fundamental para construir definições e demonstrar teoremas relativos a números naturais.
O Axioma de Indução, que também pode ser chamado de Princípio de Indução Finita ou da Indução Matemática, pode ser reescrito como abaixo
4'. Seja \(P(n)\) uma propriedade relativa ao número natural \(n\text{.}\) Suponhamos que
  1. \(P(1)\) seja válida.
  2. Para todo \(n\in \mathbb{N}\text{,}\) a validez de \(P(n)\) implica na validez de \(P(n+1)\text{.}\)
Então, \(P(n)\) é válido para todo \(n\in \mathbb{N}\text{.}\)

Exemplo 1.1.2.

Obtenha uma expressão para a soma
\begin{equation*} 1+3+5+\cdots+(2n-1). \end{equation*}
Solução.
Calculando a soma para os primeiros valores naturais de \(n\text{,}\) obtemos:
\begin{align*} 1 =\amp~ 1\\ 1+3 =\amp~ 4\\ 1+3+5 =\amp~ 9\\ 1+3+5+7 =\amp~ 16\\ \cdots \end{align*}
O exame das igualdades acima sugere que a soma seja sempre igual ao quadrado do número de parcelas, ou seja, que a afirmativa
\begin{equation*} P(n): 1+3+5+\cdots+(2n-1)=n^2 \end{equation*}
é válida para todo \(n\in \mathbb{N}\text{.}\)
O Princípio da Indução permite demonstrar este fato. O primeiro passo é:
  1. verificar a validez de \(P(n)\) para \(n=1\text{.}\) Isto já foi feito acima.
  2. verificar a validez de \(P(n)\text{,}\) para um valor arbitrário de \(n\text{,}\) implica a validez de \(P(n+1)\text{.}\) Ou seja, admitindo que
    \begin{equation} 1+3+5+\cdots+(2n-1)=n^2\tag{1.1.1} \end{equation}
    para um certo valor de \(n\text{,}\) devemos mostrar que
    \begin{equation*} 1+3+5+\cdots+(2n-1)+(2(n+1)-1)=(n+1)^2. \end{equation*}
    Para tal, somamos o novo termo \(2(n+1)-1\) a ambos os membros da Equação (1.1.1), obtemos:
    \begin{align*} 1+3+5+\cdots+(2n-1)+(2(n+1)-1) =\amp~ n^2+2(n+1)-1\\ =\amp~n^2+2n+1\\ =\amp~(n+1)^2. \end{align*}
    Portanto, a validez de \(P(n)\) para um valor arbitrário de \(n\) implica sua validez para \(n+1\text{.}\)
Logo, pelo Princípio da Indução, \(P(n)\) é válida para todo \(n\in \mathbb{N}\text{.}\)

Nota 1.1.3.

A verificação de que \(P(1)\) é válida costuma ser chamada de caso base de uma demonstração por indução, enquanto a demonstração de que a validez de \(P(n)\) implica a validez de \(P(n+1)\) é chamada de passo de indução.

Nota 1.1.4.

Considere a igualdade
\begin{equation*} P(n): 1+3+5+\cdots+(2n-1)=n^2+1. \end{equation*}
Suponha que \(P(n)\) é verdadeira para algum \(n\text{,}\) temos
\begin{align*} 1+3+5+\cdots+2n-1+2(n+1)-1 =\amp~ n^2+1+2n+1\\ =\amp~(n+1)^2+1. \end{align*}
Portanto, a implicação \(P(n)\Rightarrow P(n+1)\) é verdadeira para todo \(n\in \mathbb{N}\text{,}\) embora \(P(n)\) seja falsa para todo \(n\) (já que, no exemplo anterior, mostramos que a soma é igual a \(n^2\) e não \(n^2+1\)). Isto ilustra o fato de que o passo em que provamos a implicação \(P(n)\Rightarrow P(n+1)\) não estamos usando o resultado que desejamos demonstrar. Naturalmente, a prova por indução falha por não ser possível mostrar o caso base, pois \(P(1)\) é falsa.

Subseção 1.1.3 Adição, multiplicação e Ordem

Nesta Seção vamos será definido apropriadamente a adição e a multiplicação. Iremos recorrer novamente ao mecanismo de indução.

Nota 1.1.5.

Seja \(a(n)\) um atributo relativo ao número natural \(n\text{.}\) Se definirmos \(a(1)\) e estabelecemos como \(a(n+1)\) pode ser obtido a partir de \(a(n)\text{,}\) para \(n\in \mathbb{N}\) arbitrário, o Axioma da Indução garante que o atributo \(a(n)\) estará definido para cada \(n\in \mathbb{N}\text{.}\) Definições construídas desta forma são chamadas de definições por indução ou recorrência.
Por exemplo, a soma \(m+n\) de dois números naturais pode ser definida por recorrência do seguinte modo:

Definição 1.1.6.

  1. \(m+1\) é definido, como fizemos antes, como o sucessor de \(m\text{.}\)
  2. \(m+(n+1)\) é definido como o sucessor de \(m+n\text{,}\) ou seja, como \((m+n)+1\text{.}\)
A definição acima corresponde a ideia intuitiva de que o valor de \(m+n\) é obtido acrescentando-se \(n\) vezes uma unidade a \(m\text{.}\)
Para a multiplicação, podemos definir:

Definição 1.1.7.

  1. \(\displaystyle m\cdot 1 = m.\)
  2. \(\displaystyle m\cdot(n+1)=m\cdot n+m.\)
A partir dessas definições, podem ser demonstradas as propriedades usuais da adição e multiplicação. Ilustramos este fato com a demonstração da propriedade distributiva da multiplicação em relação a adição.
Vamos utilizar indução em \(p\text{.}\)
  1. A propriedade é válida para \(p=1\text{,}\) já que
    \begin{equation*} (m+n)\cdot 1=m+n \end{equation*}
    e
    \begin{equation*} m\cdot 1+n\cdot 1=m+n. \end{equation*}
  2. Suponhamos que a propriedade seja válida para um certo \(p\text{,}\) ou seja, \((m+n)\cdot p = m\cdot p+n\cdot p\text{.}\) Temos, pela definição indutiva da multiplicação (Definição 1.1.7):
    \begin{equation*} (m+n)\cdot(p+1)=(m+n)\cdot p+(m+n)\text{.} \end{equation*}
    Mas, pela hipótese de indução, \((m+n)\cdot p=m\cdot p+n\cdot p\text{.}\) Portanto
    \begin{equation*} (m+n)\cdot(p+1) = m\cdot p+m + n\cdot p+n \end{equation*}
    (aqui, usamos as propriedades comutativa e associativa da adição, que deveriam ter sido provadas previamente). Mas, pela definição de multiplicação (Definição 1.1.7), temos \(m\cdot p+m = m\cdot (p+1)\) e \(n\cdot p+n = n\cdot (p+1)\text{.}\) Logo,
    \begin{equation*} (m+n)\cdot (p+1) = m\cdot (p+1)+n\cdot (p+1). \end{equation*}
    Assim, a afirmativa é válida também para \(p+1\text{.}\)
Portanto, pelo Princípio da Indução, a propriedade é válida para quaisquer \(m, n\) e \(p\) naturais.
A introdução das operações aritméticas permite tornar precisa uma outra noção fundamental para números naturais: a de ordem.

Definição 1.1.9.

Sejam \(m\) e \(n\) números naturais. Dizemos que \(m\lt n\) quando existe um número natural \(p\) tal que \(m+p=n\text{.}\)
Desta definição, podem ser obtidas as propriedades usuais da ordem.
Além dessas propriedades, a ordem nos números naturais tem uma propriedade característica, conhecida como a Propriedade da Boa Ordenação:

Nota 1.1.12.

A Propriedade da Boa Ordenação não vale para a ordem definida em outros conjuntos numéricos; por exemplo, o conjunto dos números reais e o dos números reais positivos são não vazios, mas não possuem um menor elemento.

Nota 1.1.13.

A demonstração da Propriedade da Boa Ordenação é feita por indução, mas a demonstração será feita no próximo capítulo.
<Anterior^TopPróximo>
Feito com PreTeXt
Powered by Runestone