Artigos

1.1: O Princípio de Ordenação e Indução Matemática - Matemática


Dado um conjunto (S ) de números (de qualquer tipo), dizemos que ( ell in S ) é um menos elemento de (S ) if ( forall x in S ), seja (x = ell ) ou ( ell

Cada conjunto não vazio de números naturais tem um elemento mínimo.

Este princípio é freqüentemente considerado um axioma.

O Princípio Pigeonhole

[thm: escaninho] O Princípio Pigeonhole: Deixe (s, k in NN ) satisfazer (s> k ). Se os objetos (s ) forem colocados em caixas (k ), então pelo menos uma caixa contém mais de um objeto.

Suponha que nenhuma das caixas contenha mais de um objeto. Então, há no máximo (k ) objetos. Isso leva a uma contradição com o fato de que existem objetos (s ) para (s> k ).

O Princípio da Indução Matemática

Agora apresentamos uma ferramenta valiosa para provar resultados sobre números inteiros. Esta ferramenta é o princípio da indução matemática.

O primeiro princípio da indução matemática: Seja (S subset NN ) um conjunto que satisfaça as duas propriedades a seguir:

  1. (1 em S ); e
  2. ( forall k in NN, k in S Rightarrow k + 1 in S ).

Então (S = NN ). De forma mais geral, se ( Pp (n) ) é uma propriedade dos números naturais que pode ou não ser verdadeira para qualquer particular (n em NN ), satisfazendo

  1. ( Pp (1) ) é verdadeiro; e
  2. ( forall k in NN, Pp (k) Rightarrow Pp (k + 1) )

então ( forall n in NN, Pp (n) ) é verdadeiro.

Usamos o princípio da boa ordenação para provar este primeiro princípio de indução matemática.

Seja (S ) o conjunto da primeira parte do teorema e seja (T ) o conjunto de números naturais que não estão em (S ). Usaremos uma prova por contradição, então suponha que (T ) não seja vazio.

Então, pelo princípio da boa ordenação, (T ) contém um elemento mínimo ( ell ).

Observe que (1 em S ), então (1 notin T ) e, portanto, ( ell> 1 ). Portanto, ( ell-1 ) é um número natural. Como ( ell ) é o menor elemento de (T ), ( ell-1 ) não está em (T ), portanto, está em (S ).

Mas pelas propriedades definidoras de (S ), uma vez que ( ell-1 in S ), ( ell = ell-1 + 1 in S ), o que contradiz o fato de que ( ell ) é um elemento mínimo de (T ), portanto, em (T ), portanto, não em (S ).

Esta contradição implica que a suposição de que (T ) não é vazio é falsa, portanto (S = NN ).

Para a segunda parte do teorema, deixe (S = {n in NN mid Pp (n) text { is true} } ) e aplique a primeira parte.

[por exemplo: induçãov1a] Usamos indução matemática para mostrar que ( forall n in mathbb {N} ) [ sum_ {j = 1} ^ nj = frac {n (n + 1)} {2 }. ] Primeiro observe que [ sum_ {j = 1} ^ 1j = 1 = frac {1 cdot 2} {2} ] e, portanto, a afirmação é verdadeira para (n = 1 ). Para a etapa indutiva restante, suponha que a fórmula seja válida para algum (n in NN ) particular, ou seja, ( sum_ {j = 1} ^ nj = frac {n (n + 1)} {2 } ). Mostramos que [ sum_ {j = 1} ^ {n + 1} j = frac {(n + 1) (n + 2)} {2}. ] Para completar a prova por indução. De fato [ sum_ {j = 1} ^ {n + 1} j = sum_ {j = 1} ^ nj + (n + 1) = frac {n (n + 1)} {2} + (n + 1) = frac {(n + 1) (n + 2)} {2}, ] e o resultado segue.

[por exemplo: induçãov1b] Agora usamos a indução matemática para provar que (n! leq n ^ n ) ( forall n in NN ).

Observe que (1! = 1 leq 1 ^ 1 = 1 ). Agora apresentamos a etapa indutiva. Suponha que [n! Leq n ^ n ] para algum (n in NN ), provamos que ((n + 1)! Leq (n + 1) ^ {n + 1} ) Observe que [(n + 1)! = (N + 1) n! Leq (n + 1) .n ^ n <(n + 1) (n + 1) ^ {n} = (n + 1) ^ {n + 1}. ] Isso completa a prova.

O Segundo Princípio de Indução Matemática: Seja (S subset NN ) um conjunto que satisfaça as duas propriedades a seguir:

  1. (1 em S ); e
  2. ( forall k in NN, 1, dots, k in S Rightarrow k + 1 in S ).

Então (S = NN ). De forma mais geral, se ( Pp (n) ) é uma propriedade dos números naturais que pode ou não ser verdadeira para qualquer particular (n em NN ), satisfazendo

  1. ( Pp (1) ) é verdadeiro; e
  2. ( forall k in NN, ) se ( Pp (1), dots, Pp (k) ) forem todos verdadeiros, então ( Pp (k + 1) ) também é verdade

então ( forall n in NN, Pp (n) ) é verdadeiro.

Para provar o segundo princípio de indução, usamos o primeiro princípio de indução.

Seja (S ) um conjunto de inteiros como na primeira parte do teorema. Para (n em NN ), seja ( Pp (n) ) a propriedade matemática “ (1, pontos, n em S )”. Então, podemos aplicar o Primeiro Princípio da Indução Matemática para provar que ( forall n in NN Pp (n) ) é verdadeiro, o que significa (S = NN ). [Detalhes deixados para o leitor.]

A segunda parte do teorema segue da primeira exatamente da mesma maneira que a segunda parte do Primeiro Princípio de Indução Matemática seguiu do primeiro.

Exercícios

Prove usando indução matemática que (n <3 ^ n ) para todos os inteiros positivos (n ).

Mostre que ( sum_ {j = 1} ^ nj ^ 2 = frac {n (n + 1) (2n + 1)} {6} ).

Use a indução matemática para provar que ( sum_ {j = 1} ^ n (-1) ^ {j-1} j ^ 2 = (- 1) ^ {n-1} n (n + 1) / 2 )

Use a indução matemática para provar que ( sum_ {j = 1} ^ nj ^ 3 = [n (n + 1) / 2] ^ 2 ) para cada número inteiro positivo (n ).

Use a indução matemática para provar que ( sum_ {j = 1} ^ n (2j-1) = n ^ 2 ).

Use a indução matemática para provar que (2 ^ n

Use a indução matemática para provar que (n ^ 2


  1. Um matemático fictício e autor de muitos (não fictícios - eles realmente existem) textos de matemática finos, como ↩
  2. Bisbilhoteiro aparentemente vem do inglês antigo yfesdrype, significando literalmente aquele que fica na escuta [terreno onde a água goteja do beiral do telhado] para ouvir conversas dentro de uma casa.
  3. Outra sinédoque! ↩
  4. Al-Kindi é uma figura muito interessante do início da história intelectual muçulmana: por exemplo., ele parece ter trazido os números hindus, com sua notação de valor posicional, para o mundo muçulmano.
  5. Com um clássico computador - há um algoritmo eficiente conhecido para fatorar em um computador quântico, veja e .↩
  6. Embora, de fato, alguma criptografia de chave pública viável tenha sido inventada anteriormente na comunidade de inteligência dos EUA / Reino Unido e não compartilhada com o público. Desde o início da Guerra Fria, existem teoremas matemáticos e provas mantidas em segredo por grandes governos.↩
  7. Como é o caso da fatoração, existe um algoritmo conhecido para um computador quântico que resolve o DHP de forma eficiente, consulte .↩

O princípio de boa ordem

O princípio de boa ordem diz que os inteiros positivos são bem ordenado. A conjunto ordenado é dito ser bem ordenado se cada subconjunto não vazio tiver um elemento menor ou menor. Portanto, o princípio de boa ordenação é a seguinte declaração:

Observe que essa propriedade não é verdadeira para subconjuntos de inteiros (nos quais existem números negativos arbitrariamente pequenos) ou para os números reais positivos (nos quais existem elementos arbitrariamente próximos de zero).

Uma declaração equivalente ao princípio de boa ordenação é a seguinte:

O conjunto de inteiros positivos não contém nenhuma sequência infinita estritamente decrescente.

A prova de que este princípio é equivalente ao princípio da indução matemática está abaixo.


Quando você perguntou sobre indução forte outro dia, me perguntei se o princípio da boa ordem estava a caminho e aqui estamos.

não estamos realmente provando que a indução fraca implica a existência de um ordenamento parcial particular ≤ em N tal que é um ordenamento bom com $ x leq y Rightarrow x leq S (y) $?

Isso seria uma coisa sensata a fazer, mas provavelmente não é o que está acontecendo aqui.

Acho que você está estudando sozinho, já que disse antes que estava trabalhando dentro de sua própria estrutura para os números naturais e que está trabalhando com um texto que prova que indução fraca, indução forte e boa ordenação são equivalentes.

Um texto que faça isso pode começar com um conjunto relativamente grande de axiomas de números naturais, os axiomas de Peano, excluindo a indução, digamos, algumas leis de ordem e algumas leis de adição. Ou pode derivar ordem da adição, como parece as anotações de aula de Mauro Allegranza. Pode nem mesmo indicar um conjunto de axiomas, mas apenas prosseguir com o conhecimento informal preexistente: & quotVocê já sabe muito sobre os números naturais, mas agora vamos lhe contar três coisas novas, mas descobriremos que eles são realmente apenas uma coisa nova. & quot

De qualquer forma, isso está em um nível teórico inferior do que começar com os axiomas de Peano, construindo as relações de ordem e operações aritméticas, e provando forte indução e boa ordenação. Talvez seja por isso que você decidiu desenvolver sua própria estrutura.

Resumindo: a pergunta que você formula provavelmente não é a mesma que o seu texto está perguntando, mas é uma pergunta melhor.


Álgebra abstrata: APENAS AMOSTRA DE PRETEXTO XML

para qualquer número natural (n text <.> ) Esta fórmula é facilmente verificada para números pequenos, como (n = 1 text <,> ) 2, 3 ou 4, mas é impossível verificar para todos os números naturais, caso a caso. Para provar que a fórmula é verdadeira em geral, é necessário um método mais genérico.

Suponha que tenhamos verificado a equação para os primeiros (n ) casos. Tentaremos mostrar que podemos gerar a fórmula para o ((n + 1) ) o caso a partir deste conhecimento. A fórmula é verdadeira para (n = 1 ), uma vez que

Se tivermos verificado os primeiros (n ) casos, então

Esta é exatamente a fórmula para o ((n + 1) ) o caso.

Este método de prova é conhecido como. Em vez de tentar verificar uma afirmação sobre algum subconjunto (S ) dos inteiros positivos (< mathbb N> ) caso a caso, uma tarefa impossível se (S ) for um conjunto infinito , damos uma prova específica para o menor inteiro sendo considerado, seguida por um argumento genérico mostrando que se a instrução vale para um determinado caso, então também deve valer para o próximo caso na sequência. Resumimos a indução matemática no seguinte axioma.

Princípio 2.1.1. Primeiro Princípio de Indução Matemática.

Seja (S (n) ) uma declaração sobre números inteiros para (n in < mathbb N> ) e suponha que (S (n_0) ) seja verdadeiro para algum número inteiro (n_0 texto <.> ) Se para todos os inteiros (k ) com (k geq n_0 text <,> ) (S (k) ) implica que (S (k + 1) ) é verdadeiro, então (S (n) ) é verdadeiro para todos os inteiros (n ) maiores ou iguais a (n_0 text <.> )

Exemplo 2.1.2. Uma desigualdade para poderes de (2 ).

Para todos os inteiros (n geq 3 text <,> ) (2 ^ n gt n + 4 text <.> ) Desde

a afirmação é verdadeira para (n_0 = 3 text <.> ) Suponha que (2 ^ k gt k + 4 ) para (k geq 3 text <.> ) Então (2 ^ = 2 cdot 2 ^ gt 2 (k + 4) text <.> ) Mas

uma vez que (k ) é positivo. Portanto, por indução, a declaração vale para todos os inteiros (n geq 3 text <.> )

Exemplo 2.1.3. Alguns inteiros divisíveis por (9 ).

Cada inteiro (10 ​​^ + 3 cdot 10 ^ n + 5 ) é divisível por 9 para (n in < mathbb N> text <.> ) Para (n = 1 text <,> )

é divisível por 9. Suponha que (10 ​​^ + 3 cdot 10 ^ k + 5 ) é divisível por 9 para (k geq 1 text <.> ) Então

Exemplo 2.1.4. O Teorema Binomial.

Vamos provar o teorema binomial usando indução matemática, ou seja,

onde (a ) e (b ) são números reais, (n in mathbb text <,> ) e

é o coeficiente binomial. Nós primeiro mostramos isso

Se (n = 1 text <,> ) o teorema binomial é fácil de verificar. Agora suponha que o resultado seja verdadeiro para (n ) maior ou igual a 1. Então

Temos uma declaração equivalente do Princípio da Indução Matemática que geralmente é muito útil.

Princípio 2.1.5. Segundo Princípio de Indução Matemática.

Seja (S (n) ) uma declaração sobre números inteiros para (n in < mathbb N> ) e suponha que (S (n_0) ) seja verdadeiro para algum número inteiro (n_0 texto <.> ) If (S (n_0), S (n_0 + 1), ldots, S (k) ) implica que (S (k + 1) ) para (k geq n_0 text <,> ) então a declaração (S (n) ) é verdadeira para todos os inteiros (n geq n_0 text <.> )

Um subconjunto não vazio (S ) de (< mathbb Z> ) é se (S ) contém um elemento mínimo. Observe que o conjunto (< mathbb Z> ) não está bem ordenado, pois não contém o menor elemento. No entanto, os números naturais são bem ordenados.

Princípio 2.1.6. Princípio da boa ordem.

Cada subconjunto não vazio dos números naturais é bem ordenado.

O princípio da boa ordenação é equivalente ao princípio da indução matemática.

Lema 2.1.7.

O Princípio da Indução Matemática implica que (1 ) é o menor número natural positivo.

Prova .

Vamos (S = : n geq 1 > text <.> ) Então (1 in S text <.> ) Agora suponha que (n em S text <> ) ou seja, (n geq 1 text <.> ) Desde (n + 1 geq 1 text <,> ) (n + 1 in S text < > ) portanto, por indução, todo número natural é maior ou igual a 1.

Teorema 2.1.8.

O Princípio da Indução Matemática implica o Princípio da Boa Ordenação. Ou seja, cada subconjunto não vazio de ( mathbb N ) contém um elemento mínimo.

Prova .

Devemos mostrar que se (S ) é um subconjunto não vazio dos números naturais, então (S ) contém um elemento mínimo. Se (S ) contém 1, então o teorema é verdadeiro pelo Lema 2.1.7. Suponha que se (S ) contém um inteiro (k ) tal que (1 leq k leq n text <,> ) então (S ) contém um mínimo de elemento. Mostraremos que se um conjunto (S ) contém um número inteiro menor ou igual a (n + 1 text <,> ) então (S ) tem um mínimo de elemento. Se (S ) não contém um número inteiro menor que (n + 1 texto <,> ) então (n + 1 ) é o menor inteiro em (S texto <.> ) Caso contrário, uma vez que (S ) não é vazio, (S ) deve conter um número inteiro menor ou igual a (n text <.> ) Neste caso, por indução, (S ) contém um elemento mínimo.

A indução também pode ser muito útil na formulação de definições. Por exemplo, existem duas maneiras de definir (n! Text <,> ) o fatorial de um número inteiro positivo (n text <.> )

O explícito definição: (n! = 1 cdot 2 cdot 3 cdots (n - 1) cdot n texto <.> )

O indutivo ou recursivo definição: (1! = 1 ) e (n! = n (n - 1)! ) para (n gt 1 text <.> )

Todo bom matemático ou cientista da computação sabe que olhar para os problemas recursivamente, em vez de explicitamente, geralmente resulta em uma melhor compreensão de questões complexas.


1.3 Princípio de Ordenação de Poços

Este é um dos mais de 2.400 cursos do OCW. Explore os materiais para este curso nas páginas com links à esquerda.

MIT OpenCourseWare é uma publicação gratuita e aberta de material de milhares de cursos do MIT, cobrindo todo o currículo do MIT.

Sem inscrição ou registro. Navegue livremente e use materiais OCW em seu próprio ritmo. Não há inscrição nem datas de início ou término.

O conhecimento é a sua recompensa. Use o OCW para orientar sua própria aprendizagem ao longo da vida ou para ensinar outras pessoas. Não oferecemos crédito ou certificação para usar OCW.

Feito para compartilhar. Baixe os arquivos para mais tarde. Envie para amigos e colegas. Modifique, remixe e reutilize (lembre-se de citar o OCW como a fonte).

Sobre o MIT OpenCourseWare

MIT OpenCourseWare é uma publicação online de materiais de mais de 2.500 cursos do MIT, compartilhando conhecimento gratuitamente com alunos e educadores em todo o mundo. Saiba mais & raquo

& copy 2001 & ndash2018
Instituto de Tecnologia de Massachusetts

O uso do site e dos materiais do MIT OpenCourseWare está sujeito à nossa Licença Creative Commons e outros termos de uso.


2. Indução estrutural & # x7ED3 & # x6784 & # x5F52 & # x7EB3 & # x6CD5

Para provar resultados sobre conjuntos definidos recursivamente, podemos usar Indução Estrutural

  • Etapa de base: Mostre que o resultado é válido para todos os elementos especificados na etapa de base da definição recursiva para estar no conjunto.
  • Etapa recursiva: mostre que se a afirmação for verdadeira para cada um dos elementos usados ​​para construir novos elementos na etapa recursiva da definição, o resultado é válido para esses novos elementos.

Seção 6 Indução Matemática

para qualquer número natural (n text <.> ) Esta fórmula é facilmente verificada para números pequenos, como (n = 1 text <,> ) (2 text <,> ) (3 text <,> ) ou (4 text <,> ), mas é impossível verificar todos os números naturais caso a caso. Para provar que a fórmula é verdadeira em geral, é necessário um método mais genérico.

Suponha que tenhamos verificado a equação para os primeiros (n ) casos. Tentaremos mostrar que podemos gerar a fórmula para o ((n + 1) ) o caso a partir deste conhecimento. A fórmula é verdadeira para (n = 1 ) uma vez que

Se tivermos verificado os primeiros (n ) casos, então

Esta é exatamente a fórmula para o ((n + 1) ) o caso.

Este método de prova é conhecido como indução matemática. Em vez de tentar verificar uma afirmação sobre algum subconjunto (S ) dos inteiros positivos (< mathbb N> ) caso a caso, uma tarefa impossível se (S ) for um conjunto infinito , damos uma prova específica para o menor inteiro sendo considerado, seguida por um argumento genérico mostrando que se a instrução vale para um determinado caso, então também deve valer para o próximo caso na sequência. Resumimos a indução matemática no seguinte axioma.

Princípio 6.31 Primeiro Princípio de Indução Matemática

Seja (S (n) ) uma declaração sobre números inteiros para (n in < mathbb N> ) e suponha que (S (n_0) ) seja verdadeiro para algum número inteiro (n_0 texto <.> ) Se para todos os inteiros (k ) com (k geq n_0 text <,> ) (S (k) ) implica que (S (k + 1) ) é verdadeiro, então (S (n) ) é verdadeiro para todos os inteiros (n ) maiores ou iguais a (n_0 text <.> )

Exemplo 6.32

Para todos os inteiros (n geq 3 text <,> ) (2 ^ n gt n + 4 text <.> ) Desde

começar 8 = 2 ^ 3 gt 3 + 4 = 7, fim

a afirmação é verdadeira para (n_0 = 3 text <.> ) Suponha que (2 ^ k gt k + 4 ) para (k geq 3 text <.> ) Então (2 ^ = 2 cdot 2 ^ gt 2 (k + 4) text <.> ) Mas

começar 2 (k + 4) = 2k + 8 gt k + 5 = (k + 1) + 4 fim

uma vez que (k ) é positivo. Portanto, por indução, a declaração vale para todos os inteiros (n geq 3 text <.> )

Exemplo 6.33

Cada inteiro (10 ​​^ + 3 cdot 10 ^ n + 5 ) é divisível por (9 ) para (n in < mathbb N> text <.> ) Para (n = 1 text <,> )

começar 10 ^ <1 + 1> + 3 cdot 10 + 5 = 135 = 9 cdot 15 end

é divisível por (9 text <.> ) Suponha que (10 ​​^ + 3 cdot 10 ^ k + 5 ) é divisível por (9 ) para (k geq 1 text <.> ) Então

começar 10 ^ <(k + 1) + 1> + 3 cdot 10 ^ + 5 & amp = 10 ^ + 3 cdot 10 ^ + 50 - 45 & amp = 10 (10 ^ + 3 cdot 10 ^ + 5) - 45 fim

Exemplo 6.34

Vamos provar o teorema binomial usando indução matemática, ou seja,

onde (a ) e (b ) são números reais, (n in mathbb text <,> ) e

é o coeficiente binomial. Nós primeiro mostramos isso

Se (n = 1 text <,> ) o teorema binomial é fácil de verificar. Agora suponha que o resultado seja verdadeiro para (n ) maior ou igual a (1 text <.> ) Então

Temos uma declaração equivalente do Princípio da Indução Matemática que geralmente é muito útil.

Princípio 6.35 Segundo Princípio de Indução Matemática

Seja (S (n) ) uma declaração sobre números inteiros para (n in < mathbb N> ) e suponha que (S (n_0) ) seja verdadeiro para algum número inteiro (n_0 texto <.> ) If (S (n_0), S (n_0 + 1), ldots, S (k) ) implica que (S (k + 1) ) para (k geq n_0 text <,> ) então a declaração (S (n) ) é verdadeira para todos os inteiros (n geq n_0 text <.> )

Um subconjunto não vazio (S ) de (< mathbb Z> ) é bem ordenado if (S ) contém um elemento mínimo. Observe que o conjunto (< mathbb Z> ) não está bem ordenado, pois não contém o menor elemento. No entanto, os números naturais são bem ordenados.

Princípio 6.36 Princípio de boa ordem

Cada subconjunto não vazio dos números naturais é bem ordenado.

O princípio da boa ordenação é equivalente ao princípio da indução matemática.

Lema 6.37

O Princípio da Indução Matemática implica que (1 ) é o menor número natural positivo.

Prova

Vamos (S = : n geq 1 > text <.> ) Então (1 in S text <.> ) Suponha que (n in S text <.> ) Uma vez que (0 lt 1 text <,> ) deve ser o caso de (n = n + 0 lt n + 1 text <.> ) Portanto, (1 leq n lt n + 1 text <.> ) Consequentemente, se (n em S text <,> ) então (n + 1 ) também deve estar em (S text <,> ) e pelo Princípio da Indução Matemática, e (S = mathbb N text <.> )

Teorema 6.38

O Princípio da Indução Matemática implica o Princípio da Boa Ordenação. Ou seja, cada subconjunto não vazio de ( mathbb N ) contém um elemento mínimo.

Prova

Devemos mostrar que se (S ) é um subconjunto não vazio dos números naturais, então (S ) contém um elemento mínimo. Se (S ) contém 1, então o teorema é verdadeiro pelo Lema 6.37. Suponha que se (S ) contém um inteiro (k ) tal que (1 leq k leq n text <,> ) então (S ) contém um mínimo de elemento. Mostraremos que se um conjunto (S ) contém um número inteiro menor ou igual a (n + 1 text <,> ) então (S ) tem um mínimo de elemento. Se (S ) não contém um número inteiro menor que (n + 1 texto <,> ) então (n + 1 ) é o menor inteiro em (S texto <.> ) Caso contrário, uma vez que (S ) não é vazio, (S ) deve conter um número inteiro menor ou igual a (n text <.> ) Neste caso, por indução, (S ) contém um elemento mínimo.

A indução também pode ser muito útil na formulação de definições. Por exemplo, existem duas maneiras de definir (n! Text <,> ) o fatorial de um número inteiro positivo (n text <.> )

O explícito definição: (n! = 1 cdot 2 cdot 3 cdots (n - 1) cdot n texto <.> )

O indutivo ou recursivo definição: (1! = 1 ) e (n! = n (n - 1)! ) para (n gt 1 text <.> )

Todo bom matemático ou cientista da computação sabe que olhar para os problemas recursivamente, em vez de explicitamente, geralmente resulta em uma melhor compreensão de questões complexas.


SOLUÇÃO: MATH 109 University of California San Diego Math Problems Questions

Math 109 SS1 2020
Lição de casa 3
Lec A Prof. Chow
Vencimento na terça-feira, 25 de agosto às 23h59 (nova data de vencimento) por envio online para
escopo de grau.
Todos os exercícios, problemas e número da página referem-se ao livro de Eccles.
# 1. Faça o Exercício 11.1 na pág. 143 de Eccles: Suponha que Nn → X seja uma sobreposição. Provar,
por indução em n, que X é um conjunto finito e que | X | ≤ n.
# 2. Faça o # 9 em Problemas III na pág. 184: Prove a proposição 11.1.4: se X → Nn é um
injeção, então X é finito e | X | ≤ n.
# 3. Faça o Exercício 11.4 na pág. 143 de Eccles: Prove que, se aeb são números inteiros diferentes de zero
com mdc (a, b) = d, então os inteiros a / d e b / d são coprimos.
# 4. Prove: Se A é um conjunto finito não vazio de números reais, então A tem um mínimo
elemento. (Este é o # 5 nos Problemas III na p. 183, que é "metade" da Proposição 11.2.3.)
# 5. Dados inteiros diferentes de zero a1,. . . , um, deixe
D (a1,..., An) = .
Prove por indução que max D (a1,..., An) ≤ min <| a1 |,. . . , | an |>.
# 6. Faça o Exercício 11.6 na pág. 143: Prove por indução em n que se A é um conjunto de
inteiros sem um mínimo de elemento, então Nn ⊆ Z + - A para cada n, de modo que A é o conjunto vazio.
Deduza o princípio de boa ordenação: todo conjunto não vazio de inteiros positivos tem pelo menos
elemento.
# 7. Faça o # 11 em Problemas III na pág. 184. Use o princípio do escaninho e prova por
contradição para provar o Teorema 11.1.7: Conjuntos finitos não vazios dados X e Y com | X | = | Y |,
uma função f: X → Y é uma injeção se e somente se f for uma sobreposição.
# 8. Faça o # 12 em Problemas III na pág. 184: Suponha que haja uma injeção f: Z + → X.
Prove por contradição que X é um conjunto infinito.
# 9. Faça o # 15 em Problemas III na pág. 184: Prove o princípio de indução a partir do princípio de ordenação (ver Exemplo 11.2.2 (c)).
[Prove o princípio de indução na forma do Axioma 7.5.1 por contradição.]
Dica: o Axiom 5.4.1 é equivalente ao Axiom 5.1.1. Supondo que o princípio de boa ordem
é falso, existe um subconjunto B & # 8230, considere o complemento de B e aplique o forte
princípio de indução.
Math 109 SS1 2020
Lição de casa 3
Lec A Prof. Chow
# 10. Seja X1,. . . , Xk são conjuntos finitos, onde k é um número inteiro positivo. Dado um conjunto de j distinto
índices I = ⊆ Nk = <1, 2,. . . , k>, onde 1 ≤ j ≤ k, define
XI =

Xi = Xi1 ∩ Xi2 ∩ · · · ∩ Xij.
eu
(a) Para cada subconjunto não vazio I ⊆ N3 escreva o conjunto XI. Por exemplo, se I = <1, 3>,
então XI = X1 ∩ X3.
(b) Escreva a soma
X
(−1) | I | −1 | XI |.
∅6 = I⊆N3
Faça isso para que a primeira linha tenha os termos com | I | = 1, a segunda linha tem os termos com
| I | = 2, e a terceira linha tem os termos com | I | = 3. Por exemplo, se você estiver listando o
termos em "ordem lexigráfica", então o primeiro termo da primeira linha seria | X1 |, uma vez que este
é igual a (−1) | <1> | −1 | X <1> |.
(c) Fato: A soma no item (b) é igual a | X1 ∪ X2 ∪ X3 |. Isso é,
X
| X1 ∪ X2 ∪ X3 | =
(−1) | I | −1 | XI |.
∅6 = I⊆N3
Verifique se de fato esta é a afirmação (não prova) da Proposição 10.3.2.
# 11. Suponha que k seja um número inteiro positivo para o qual conhecemos qualquer conjunto finito Y1,. . . , Yk,
que (princípio de inclusão-exclusão para k conjuntos)
| Y1 ∪ · · · ∪ Yk | =
X
(−1) | I | −1 | YI |.
∅6 = I⊆Nk
Seja X1,. . . , Xk + 1 são conjuntos finitos. Claro,
X1 ∪ · · · ∪ Xk + 1 = (X1 ∪ · · · ∪ Xk) ∪ Xk + 1.
(a) Prove por indução que para quaisquer n + 1 conjuntos A0, A1,. . . , A
(A1 ∪ · · · ∪ An) ∩ A0 = (A1 ∩ A0) ∪ · · · ∪ (An ∩ A0).
(1)
(b) Mostre que (lembre-se da suposição em k)
| X1 ∪ · · · ∪ Xk + 1 | =
X
∅6 = I⊆Nk
(−1) | I | −1 | XI | + | Xk + 1 | - | (X1 ∩ Xk + 1) ∪ · · · ∪ (Xk ∩ Xk + 1) | .
Math 109 SS1 2020
Lição de casa 3
Lec A Prof. Chow
# 12. Continuação do problema anterior.
(a) Para 0 ≤ i ≤ k, seja Zi = Xi ∩ Xk + 1. Explique por que se J ⊆ Nk, então
ZJ = XJ ∩ Xk + 1 = XJ∪ .
(b) Prove que se ∅ =
6 I ⊆ Nk + 1, então exatamente um dos seguintes se mantém:
(i) ∅ =
6 I ⊆ Nk,
(ii) I = ,
(iii) I = J ∪ , onde ∅ =
6 J ⊆ Nk.
(c) Explique por que
X
(−1) | I | −1 | XI | =
∅6 = I⊆Nk + 1
X
X
(−1) | I | −1 | XI | + | Xk + 1 | +
∅6 = I⊆Nk
(−1) | J | | XJ∪ |.
∅6 = J⊆Nk
(d) Prove que a soma da parte (b) do problema anterior é igual à soma da parte
(c) deste problema, isto é,
X
| X1 ∪ · · · ∪ Xk + 1 | =
(−1) | I | −1 | XI |.
∅6 = I⊆Nk + 1
# 13. Faça o # 4 em Problems III nas páginas 182–183. Este é o princípio de inclusão-exclusão.
Isso não deve ser muito trabalho, dado todo o trabalho que você fez nos problemas anteriores # 8
e # 9.
# 14. Prove, por indução em n, que para quaisquer conjuntos X1,. . . , Xn, a seguinte igualdade para
funções características:
χX1 ∪ ··· ∪Xn =
X
(−1) | I | −1 χXI.
∅6 = I⊆Nn
[A prova desse problema está relacionada aos problemas # 11– # 13. Mas é muito mais curto.]

Compre a resposta para ver completo
acessório


1.1: O Princípio de Ordenação e Indução Matemática - Matemática

A suposição básica que se faz sobre a ordem dos inteiros é a seguinte:

Princípio de boa ordem. Cada conjunto não vazio de inteiros positivos tem pelo menos um elemento.

A partir dessa suposição, é fácil provar o seguinte teorema, que fundamenta o método de prova por indução:

Teorema 1: Princípio da indução matemática Deixe A representar um conjunto de inteiros positivos. Considere as duas condições a seguir:

(ii)Para qualquer número inteiro positivo k, se k está em A, então k + 1 está em A.

Se A for qualquer conjunto de inteiros positivos que satisfaçam essas duas condições, então A consiste em todos os inteiros positivos.

PROVA: Se UMA não contém todos os inteiros positivos, então pelo princípio de boa ordenação (acima), o conjunto de todos os inteiros positivos que são não dentro UMA tem pelo menos elemento chamá-lo b. Da condição (i), b & ne 1, portanto b > 1.

Desse modo, b & menos 1> 0, e b & mdash 1 & isin UMA Porque b é o ao menos inteiro positivo não dentro UMA. Mas então, da Condição (ii), b &é em UMA, o que é impossível. ■

Aqui está um exemplo de como o princípio da indução matemática é usado: Devemos provar a identidade

ou seja, a soma do primeiro n inteiros positivos são iguais a n(n + 1)/2.

Deixar UMA consistem em todos os inteiros positivos n para qual Equação (1) é verdade. Então 1 está dentro UMA Porque

Em seguida, suponha que k é qualquer número inteiro positivo em UMA devemos mostrar que, nesse caso, k + 1 também está em UMA. Para dizer aquilo k é em UMA significa que

Adicionando k + 1 para ambos os lados desta equação, obtemos

A partir desta última equação, k + 1 & isin UMA.

Nós mostramos que 1 & isin UMAe, além disso, se k &é em UMA, então k + 1 & isin UMA. Então, pelo princípio da indução matemática, todos os inteiros positivos estão em UMA. Isso significa que Equação (1) é verdadeiro para todo número inteiro positivo, conforme afirmado.

Use a indução matemática para provar o seguinte:

1 1 + 3 + 5 + ⋯ + (2n & menos 1) = n 2

(Ou seja, a soma do primeiro n inteiros ímpares são iguais a n 2 .)

2 1 3 + 2 3 + ⋯ + n 3 = (1 + 2 + ⋯ + n) 2

3 1 2 + 2 2 + ⋯ + n 2 = n(n + 1)(2n + 1)

4 1 3 + 2 3 + ⋯ + n 3 = n(n + 1) 2

5

6 1 2 + 2 2 + ⋯ + (n e menos 1) 2 2 + 2 2 + ⋯ + n 2

Se você é o detentor dos direitos autorais de qualquer material contido em nosso site e pretende removê-lo, entre em contato com o administrador do site para aprovação.


Teoria dos Números: em contexto e interativa

Antes de prosseguir, precisamos fazer uma pequena revisão. Os três tópicos a seguir podem ser considerados pré-requisitos para o curso.

Subseção 1.2.1 Ordem de Bem

O primeiro princípio é simples e profundo. É uma propriedade profunda dos inteiros positivos, mas damos a ela seu nome usual.

Axiom 1.2.1. Princípio de boa ordem.

Qualquer conjunto não vazio de inteiros positivos tem um elemento mínimo / menor.

Este princípio realmente se aplica a qualquer subconjunto de ( mathbb) que é delimitado abaixo, como ( mathbb) (lembre-se da Definição 1.0.1).

Vamos usá-lo como um exemplo para provar o seguinte fato, do qual você provavelmente não sabia a prova necessária.

Fato 1.2.2. Inteiros consecutivos.

Não há números inteiros entre 0 e 1.

Prova .

Esta prova procede por contradição. Suponha que existam alguns desses inteiros, e deixe

Este conjunto deve ter um elemento mínimo (a text <,> ) e (0 & lta & lt1 text <.> ) Se multiplicarmos por (a ) (que é positivo), então obtemos (0 & lta ^ 2 & lta text <.> )

Assim, (a ^ 2 ) é outro inteiro tal que (0 & lta ^ 2 & lt1 text <,> ) então (a in S text <,> ) mas também sabemos que (a ^ 2 & lta text <.> ) Então (a ^ 2 ) é um elemento de (S ) que é menor do que o menor elemento de (S text <.> ) Isso é uma contradição, então nossa suposição original estava errado e não existem tais números inteiros (ou seja, (S ) está vazio).

Observação 1.2.3.

Para revisar, as provas de e ambos começam assumindo a negação da conclusão. Uma prova por contraposição usa essa suposição para provar a negação da suposição original. Uma prova por contradição, por outro lado, leva a algum absurdo, mas não necessariamente apenas negando as suposições originais. Na prova acima do Fato 1.2.2, a contradição é que você não pode ter dois menores elementos diferentes de um conjunto.

Subseção 1.2.2 Indução

Às vezes, precisamos de uma maneira de provar uma declaração para todos os inteiros (n ) após um certo ponto, por exemplo, inteiros maiores ou iguais a (n = 1 text <.> ) Isso geralmente é chamado. Normalmente, existem duas etapas em uma indução "simples" típica.

Primeiro, provamos o “caso base” (frequentemente (n = 1 ) ou (n = 0 )).

Em seguida, provamos a "etapa de indução", que o caso (n = k ) implica o caso (n = k + 1 text <.> )

Estes se combinam para provar um fato para tudo casos (n geq 1 text <.> )

Exemplo 1.2.4. Arquétipo de indução.

O caso básico é verificar se (1 = frac <1 (1 + 1)> <2> text <,> ), o que é fácil.

A etapa de indução começa com a suposição de que

e então continua mostrando que a fórmula ainda é verdadeira quando (k ) é substituído por (k + 1 text <.> ) Para esta prova, para adicionar apenas mais um inteiro (k + 1 ) para a soma significa

(que podemos ver reescrevendo a soma). Então podemos apenas conectar a indução suposição obter

que é exatamente o que é necessário para terminar a etapa de indução, a saber

Em relação a alguns outros axiomas básicos, pode-se realmente tomar a legitimidade da indução como um axioma final e usá-lo para provar que a boa ordem (Axioma 1.2.1) é verdadeira. Os instrutores devem observar que o inverso é falso 4 Não incluiremos tais provas (ou uma coleção de axiomas relevantes, como o de Peano) aqui, mas observe a exposição útil em [E.7.33].

Subseção 1.2.3 Divisibilidade

Definição 1.2.5.

Se um inteiro (n ) pode ser escrito como um produto (kd = n ) de dois inteiros (k ) e (d text <,> ), então dizemos que (d ) (n text <,> ) ou que (n ) é por (d text <,> ) ou que (d ) é um de (n text <.> ) Nós escrevemos (d mid n ) para denotar que (d ) divide (n text <.> )

Exemplo 1.2.6.

Por exemplo, o conceito de que (n ) é par é exatamente a mesma coisa que (2 mid n text <.> )

O divisores de (n = 8 ) são… ( pm 1, pm 2, pm 4, pm 8 text <.> ) (Não se esqueça dos divisores negativos.)

Muitas vezes podemos escrever isso genericamente, então por exemplo (n mid x + 1 ) significa que (x + 1 ) pode ser escrito como o produto de (n ) e algum outro inteiro (m texto <.> )

Ocasionalmente, usamos o termo para denotar um divisor positivo de (n ) que não é (n text <> ) no exemplo com (n = 8 text <,> ) (1 text < ,> ) (2 text <,> ) e (4 ) são todos divisores apropriados.

Há muitas coisas interessantes a dizer sobre a divisibilidade. Vamos provar uma afirmação um tanto inesperada usando indução e apenas o que já sabemos.

Exemplo 1.2.7.

Mostre que (4 mid 5 ^ n-1 ) para (n geq 0 text <.> )

Esta prova será feita por indução. Desta vez, o caso básico será (n = 0 text <.> ) Tentaremos deixar as etapas claras com marcadores separados.

Etapa básica: Se (n = 0 ) a fórmula diz que 4 divide (5 ^ 0-1 = 1-1 = 0 texto <,> ), o que é definitivamente verdadeiro.

Suponha que (4 mid 5 ^ k-1 text <.> ) Então, pela Definição 1.2.5, (5 ^ k-1 = 4x ) para algum inteiro (x text <.> )

Portanto, (5 ^ k = 1 + 4x ) é um fato que poderíamos usar mais tarde.

Nosso objetivo nesta etapa é mostrar (4 mid 5 ^-1 text <.> )

Uma vez que precisamos de algo verdadeiro sobre (5 ^-1 text <,> ) vamos considerar (5 ^) primeiro. A observação principal será que (5 ^= 5 ^ k cdot 5 text <.> )

Using the fact we obtained from the induction assumption we can write this as (5^kcdot 5=(1+4x)cdot 5 ext<>) this means that

Certainly (20x+4) is divisible by 4.

Thus we have shown that (4mid 5^-1 ext<,>) so we have finished the induction step, and our proof by induction is complete.

There are lots of other propositions about divisibility you are probably familiar with from previous courses. Here is a sampler.

Proposition 1.2.8 . Divisibility Facts.

If (amid b) and (bmid c) then (amid c ext<.>)

If (amid b) then (camid cb ext<.>)

If (cmid a) and (cmid b) then (cmid au+bv) for any integers (u,v ext<.>)

If (n>0) then all divisors of (n) are less than or equal to (n ext<.>)

These are not hard to prove (see Exercise 1.4.1). For instance, the second one can be proved by simply noting (b=ka) for some (kinmathbb ext<,>) so that (cb=c(ka)=c(ak)=(ca)k ext<.>) The others are similar, and are good practice with using basic algebraic manipulation in proofs.


Assista o vídeo: Indução Matemática - Aula 1 - Princípio de Indução Matemática (Dezembro 2021).