[MCTB019-17] § 2 — Demonstrações: técnicas

Publicado em por

Índide das técnicas

2.1. Demonstração direta de implicação

2.2. Demonstração indireta de implicação

2.3. Demonstração de equivalências

2.4. Demonstração por casos

2.5. Demonstração de sentenças existenciais

2.6. Mais demonstrações por contradição

O objetivo de uma demonstrações é convencer outras pessoas, ou a si mesmo, de que uma sentença é verdadeira. Toda demonstração parte de algumas definições e/ou de algumas sentenças primordiais chamadas axiomas os quais são, convencionalmente, considerados verdadeiros. Uma demonstração somente pode usar sentenças e regras de dedução válidas. Em geral, também usamos equivalências e implicações lógicas vistas anteriormente e as sentenças que já foram provadas serem verdadeiras. Uma sentença devidamente demonstrada é chamada de teorema (palavra derivada de uma expressão grega que significa “verdade dos Deuses”). Assim, essencialmente, temos dois tipos de sentenças verdadeiras na matemática: os axiomas e os teoremas.

Uma demonstração também pode usar definições que tenham sido feitas previamente. Uma definição é uma explicação exata e não ambígua de um conceito, deve especificar todas as propriedades que identificam exatamente o conceito definido. Por exemplo, a definição de um número inteiro par é dada a seguir.

Definição (par) Um inteiro {n} é par se, e somente se, {n} é da forma {2k} para algum inteiro {k}.

Definição (ímpar) Um inteiro {n} é ímpar se, e somente se, {n} é da forma {2k+1} para algum inteiro {k}.

Observe que esta definição não deixa dúvida de quando um inteiro é par. A definição pode ser usada em demonstrações como se fosse uma equivalência lógica, para qualquer que seja o inteiro {n}

\displaystyle n \text{ \'e par} \Leftrightarrow \exists k\in{\mathbb Z},\,n=2k

porque ela nos garante que a sentença {\forall n,\, (n \text{ \'e par} \leftrightarrow \exists k,\,n=2k) } é verdadeira, como um axioma.

Observemos o uso do conectivo lógico se e somente se. Este conectivo permite-nos decidir se uma entidade qualquer do domínio se enquadra ou não na definição. Em textos matemáticos é comum encontrar definições que usam apenas a palavra se, uma condicional, que deve ser entendido como se e somente se. Por exemplo: um inteiro {n} é par se ele é múltiplo de {2}. Esta definição deve ser entendida como enunciada na definição dada acima. Eventualmente, definições não usam nem se nem se e somente se. Por exemplo: um número inteiro que não é da forma {2k}, para algum inteiro {k}, é chamado de ímpar. O leitor deve certificar-se de que está claro qual é a equivalência nesse caso.

Os axiomas, ou postulados, são sentenças que aceitamos como verdadeiras sem prova, ou demostração. Por exemplo, os axiomas de Peano “definem o que significa ser um número natural” e a partir deles podemos construir mais definições — adição, multiplicação, subtração, divisão, números primos, e assim por diante — e os teoremas da aritmética. Outros exemplos são os axiomas de Zermelo e Fraenkel para a teoria dos conjuntos e os axiomas de Euclides, ou os de Hilbert, para a geometria euclidiana. Os teoremas são sentenças cuja veracidade é atestada por uma demonstração. Na maioria dos casos, a lista de axiomas é pequena e provar qualquer resultado significativo a partir desses axiomas requer uma quantidade enorme de trabalho. Tais conjuntos de axiomas são mais adequados para um curso de lógica do que um curso sobre estruturas discretas. Nosso foco é em técnicas de prova e suas aplicações para estruturas discretas, assim consideraremos verdadeiros fatos familiares de matemática que aprendemos no ensino médio, por exemplo. Assim, podemos assumir verdadeiras (como axiomas da aritmética sobre os inteiros ao invés de teoremas, o que de fato são) as seguintes sentenças:

  • Associativa: {\forall a,b,c\in {\mathbb Z}}

    \displaystyle a+(b+c)=(a+b)+c

  • Comutativa: {\forall a,b\in {\mathbb Z}}

    \displaystyle a+b=b+a

  • Elemento neutro: {\forall a\in {\mathbb Z}},

    \displaystyle a+0=a

    e {0} é o único inteiro que satisfaz essa sentença.

  • Elemento inverso: {\forall a\in {\mathbb Z},~\exists b\in {\mathbb Z}}

    \displaystyle a+b=0

    {b} é denotado por {-a}.

  • Lei cancelativa da soma: {\forall a,b,c\in {\mathbb Z}}

    \displaystyle a+ b= a+ c \leftrightarrow b=c

  • Associativa: {\forall a,b,c\in {\mathbb Z}}

    \displaystyle a\cdot (b\cdot c)=(a\cdot b)\cdot c

  • Comutativa: {\forall a,b\in {\mathbb Z}}

    \displaystyle a\cdot b=b\cdot a

  • Elemento neutro: {\forall a\in {\mathbb Z}}

    \displaystyle a\cdot 1=a

    e {1} é o único inteiro que satisfaz essa sentença.

  • Distributiva: {\forall a,b,c\in {\mathbb Z}}

    \displaystyle a\cdot (b+c)=a\cdot b+a\cdot c

  • Lei cancelativa do produto: {\forall a,b,c\in {\mathbb Z}}

    \displaystyle b=c \rightarrow a\cdot b= a\cdot c

    \displaystyle a\neq 0 \text{ e }a\cdot b= a\cdot c \rightarrow b=c

  • Tricotomia: {\forall a,b\in {\mathbb Z}} vale só um de

    \displaystyle a<b \textrm{ ou }a=b\textrm{ ou }b<a.

  • Compatibilidade de {\leq} com as operações aritméticas: {\forall a,b\in {\mathbb Z}}
    1. {\forall c\in{\mathbb Z}}, { a\leq b \leftrightarrow a+c\leq b+c}
    2. {\forall c\in{\mathbb N}}, {a\leq b \leftrightarrow a\cdot c\leq b\cdot c}.
  • Transitividade de {<}: {\forall a,b,c\in {\mathbb Z}}

    \displaystyle a< b \text{ e }b< c \rightarrow a<c

    Decorre disso, por exemplo, o teorema da divisão cuja demonstração adiamos.

    Teorema 1 (Teorema da Divisão) Para todo inteiro {a} e todo inteiro positivo {b} existe um único inteiro {q} e existe um único inteiro {r} tal que

    \displaystyle a=bq+r \;\text{ e }\;\, 0\leq r< b . \ \ \ \ \ (1)

    Um corolário de um teorema é outro teorema que é consequência do primeiro, e cuja demonstração é relativamente simples. Por exemplo, pelo Teorema da Divisão, todo inteiro {n} deixa resto {0} ou {1} quando dividido por {2}, portanto todo número que não é da forma {2k} deve ser da forma {2k+1} para algum inteiro {k}. Isso, levando em conta as definições 1 e 2, demonstra a seguinte sentença.

    Corolário 2 Para todo inteiro {n}, {n} é par ou {n} é ímpar.

    Os teoremas também são apresentados como lema — um “teorema auxiliar”, i.e., uma sentença verdadeira que é usada na demonstração de sentenças mais complexas — e como proposição — é um teorema de menor importância.

    Uma demonstração encerra um argumento válido e correto, emprega os elementos da lógica mas é expressa em linguagem natural, estabelece a veracidade de uma sentença matemática usando axiomas e teoremas previamente comprovados, juntamente com as regras de inferência. Em geral mais de uma regra de inferência pode ser usada em cada passo, alguns passos são omitidos e axiomas e regras de inferência utilizados não são explicitamente mencionadas. O objetivo é convencer um público da verdade de uma sentença de modo que o nível de detalhamento é, em geral, calibrado de acordo com a audiência a que se destina a demonstração. Para convencer outras pessoas, entretanto, devemos cuidar para que a demonstração seja, além de correta, também simples, clara e objetiva, tanto quanto possível.

    Teorema Se {x\in {\mathbb Z}} é par e {y\in {\mathbb Z}} é par, então {x+y} é par.

    Essa sentença tem a forma lógica {A\land B \rightarrow C} e essa implicação é falsa somente quando {A\land B} é verdadeiro e {C} falso. Assim, o que precisamos demonstrar que se {A\land B} é verdadeiro então, obrigatoriamente, {C} é verdadeiro. Pra isso, assumimos {A\land B} como um premissa verdadeira e construímos um argumento que conclui {C}.

    Demonstração: Suponha {x\in {\mathbb Z}} é par e {y\in {\mathbb Z}} é par. Então existem inteiros {k_1} e {k_2} tais que {x=2k_1} e {y=2k_2} pela definição de número par, logo {x+y= 2(k_1+k_2)} que é inteiro e é par. \Box

    A demonstração está estruturada da seguinte forma:

    1) {x} é par (premissa)
    2) {x=2k_1} para algum inteiro {k_1} (1 e a definição de número par)
    3) {y} é par (premissa)
    4) {y=2k_2} para algum inteiro {k_2} (3 e a definição de número par)
    5) {x+y = 2(k_1+k_2)} (propriedade igualdade)
    6) {x+y} é inteiro e par (5 e a definição de número par)

    Essa demonstração mais detalhada e que explicita todo esquema lógico desse argumento segue abaixo.

    1) {x} é par. (premissa)
    2) {y} é par. (premissa)
    3) Se {x} é par então {x=2k_1} para algum inteiro {k_1} (da definição de número par)
    4) {x=2k_1} (1, 3 e Modus Ponens e instanciação existencial)
    5) Se {y} é par então {y=2k_2} para algum inteiro {k_2} (da definição de número par)
    6) {y=2k_2} (2, 5 e Modus Ponens e instanciação existencial)
    7) {x=2k_1} e {y=2k_2} (4, 6 e a regra da conjunção)
    8) Se {x=2k_1} e {y=2k_2}, então {x+y = 2(k_1+k_2)} (compatibilidade do = com +)
    9) {x+y = 2(k_1+k_2)} (8, 7 e Modus Ponens)
    10) Se {x+y = 2(k_1+k_2)} então existe {c\in{\mathbb Z}} tal que {x+y=2c} (generalização universal)
    11) Existe {c\in{\mathbb Z}} tal que {x+y=2c} (9, 10 e Modus Ponens)
    12) Se existe {c\in{\mathbb Z}} tal que {x+y=2c} então {x+y} é inteiro e par (def. de número par)
    13) {x+y} é inteiro e par (11, 12 e Modus Ponens).

    Notemos que, a partir das premissas, uma linha qualquer é uma sentença
    verdadeira sempre a linhas anteriores a ela são verdadeiras.

    Esse tipo de argumento que para demonstrar que {P\rightarrow Q} assume {P} verdadeiro e conclui que {Q} é verdadeiro é chamado de prova direta da implicação.

    Um termo recorrente em textos matemáticos é conjetura que é uma sentença que está sendo proposta como uma sentença verdadeira.

    Conjetura de Goldbach Todo inteiro maior que 2 e par pode ser escrito como a soma de dois números primos.

    Se posteriormente demonstrada verdadeira essa sentença torna-se um teorema, entretanto se for encontrado um contraexemplo, isto é, inteiro que não é escrito como a soma de dois números primos, então essa será uma sentença falsa, e não será um teorema.


    2.1. Demonstração direta de implicação

    Teorema Sejam {a} e {b} números reais tais que {0<a<b}. Então {a^2 < b^2}.

    Demonstração: Devemos provar que, no domínio dos números reais, se {0<a<b} então {a^2 < b^2}. Suponha que {0<a} e {a<b}. Então {0<b} e, multiplicando por {a} ambos os lados da desigualdade {a<b}, temos {a^2 < ab} e, multiplicando por {b}, temos {ab < b^2}. De {a^2 < ab} e {ab < b^2} concluímos {a^2 < b^2}. \Box

    A estrutura lógica do argumento fica mais explicita se destrinchamos a dedução em passos menores e justificamos cada passo como a seguir.

    1) {0<a} (premissa)
    2) {a<b} (premissa)
    3) {0<a} e {a<b} (regra da conjunção)
    4) se {0<a} e {a<b} então {0<b} (transitividade do {<})
    5) {0<b} (3, 4 e modus ponens)
    6) se {a>0} e {a< b} então, multiplicando por {a} ambos os lado da desigualdade, {a^2 < ab} (compatibilidade do {<} com {\cdot})
    7) {a^2 < ab} (3, 6 e modus ponens)
    8) {b>0} e {a< b} (2, 8 e regra da conjunção)
    9) se {b>0} e {a< b} então, multiplicando por {b} ambos os lado da desigualdade, {ab < b^2} compatibilidade do {<} com {\cdot})
    10) {ab < b^2} (8, 9 e modus ponens)
    11) {a^2 < ab} e {ab < b^2} (7, 10 e regra da conjunção)
    12) se {a^2 < ab} e {ab < b^2} então {a^2 < b^2} (transitividade do {<})
    13) {a^2 < b^2} (7, 8 e modus ponens)

    Definição (inclusão de conjuntos) Se {A} e {B} são conjuntos então a inclusão {A\subset B} é caracterizado pela sentença

    \displaystyle \forall x \, (x\in A \rightarrow x\in B).

    Definição (interseção de conjuntos) Se {A} e {B} são conjuntos então a interseção {A\cap B} é caracterizado pela sentença

    \displaystyle \forall x \, (x\in A\cap B \leftrightarrow x\in A \land x\in B).

    Definição (diferença de conjuntos) Se {A} e {B} são conjuntos então a diferença {A\setminus B} é caracterizado pela sentença

    \displaystyle \forall x \, (x\in A\setminus B \leftrightarrow x\in A \land x\not\in B).

    Teorema Sejam {A,B,C} conjuntos não vazios. Se {A\cap C \subset B} e {a \in C} então {a\not\in A\setminus B}.

    De acordo com a estratégia acima, devemos supor {A\cap C \subset B} e {a \in C} e provar {a\not\in A\setminus B}. Pela definição de diferença de conjuntos {a \not\in A\setminus B \leftrightarrow \neg (a\in A \land a\not\in B)} mas {\neg (a\in A \land a\not\in B)} é logicamente equivalente a {a\not\in A \lor a\in B} que, por sua vez, é logicamente equivalente a {a\in A \rightarrow a\in B}. Assim

    \displaystyle (A\cap C \subset B \land a \in C ) \rightarrow a\not\in A\setminus B

    é logicamente equivalente a

    \displaystyle (A\cap C \subset B \land a \in C ) \rightarrow (a\in A \rightarrow a\in B) \ \ \ \ \ (2)

    de modo que basta demonstrarmos que essa sentença é verdadeira para concluirmos o teorema. Para demonstrar (2)

    assumimos: {A\cap C \subset B} e {a \in C}

    provamos: {a\in A \rightarrow a\in B}

    mas {a\in A \rightarrow a\in B} é uma implicação e para demonstrá-la assumimos {a\in A} e provamos {a\in B}. Assim para demonstrar (2)

    assumimos: {A\cap C \subset B} e {a \in C} e {a\in A}

    provamos: {a\in B}.

    Demonstração: Suponhamos que {A\cap C \subset B} e {a \in C} e {a\in A}.

    Se {a \in C} e {a\in A} então {a\in A\cap C} por definição de interseção. < Se {a\in A\cap C} e {A\cap C \subset B} então {a\in B} por definição de inclusão. \Box

    A estrutura lógica do argumento fica mais explicita em

    1) suponhamos que {A\cap C \subset B} e {a \in C} e {a\in A} (premissa)
    2) se {A\cap C \subset B} e {a \in C} e {a\in A} então {A\cap C \subset B} e {a\in A\cap C} (definição de interseção)
    3) se {A\cap C \subset B} e {a\in A\cap C} então {a\in B} (definição de inclusão)
    4) se {A\cap C \subset B} e {a \in C} e {a\in A} então {a\in B} (2, 3 e silogismo hipotético)
    5) {a\in B} (1, 4 e Modus Ponens)

    Exercício Escreva uma demonstração para: se {P\rightarrow (Q\rightarrow R)} então {\neg R\ \rightarrow (P \rightarrow \neg Q)}.

    (Solução.)

    Vejamos alguns esclarecimentos a respeito da escrita de enunciados e demostrações. Muitos teoremas afirmam propriedades para todos os elementos de um domínio sem que o quantificado seja explicitamente mencionado, por exemplo,

    1. Seja n um inteiro. Se 3 divide {n} então 9 divide {n^2}.
    2. Seja n um inteiro. Se {n} é ímpar, então {n^2} é ímpar.
    3. Seja n,\,m inteiros. Se {m} é par e {n} é par, então {m+n} é par.

    Essas sentenças significam, no domínio dos números inteiros

    1. Para todo {n}, se 3 divide {n} então 9 divide {n^2}.
    2. Para todo {n}, se {n} é ímpar, então {n^2} é ímpar.
    3. Para todo {n}, para todo {m}, se {m} é par e {n} é par, então {m+n} é par.

    Em parte, esse comportamento é explicado pelo seguinte. Uma demonstração para uma sentença na forma lógica {\forall x(P(x)\rightarrow Q(x))} tem os passos:

    A parte principal dessa estratégia é a implicação {P(c)\rightarrow Q(c)}, todo o trabalho de demonstrar “Para todo {n}, se 3 divide {n} então 9 divide {n^2}” está concentrado na parte “se 3 divide {n} então 9 divide {n^2}” para um {n} arbitrário.

    Numa prova direta, para demonstrar {P\rightarrow Q} assumimos {P} verdadeiro e usamos regras de inferência, definições, axiomas e equivalências lógicas para concluir que {Q} é verdadeiro. Isso feito sabemos que {P\rightarrow Q} é verdadeiro o que estabelece o passo 2 descrito acima.

    Por exemplo, se {n} é um número inteiro arbitrário então a condicional

    \displaystyle \text{se }3\text{ divide } n \text{ ent\~{a}o } 9 \text{ divide } n^2 \ \ \ \ \ (23)

    é verdadeira.

    Definição (divide) o inteiro {k} divide o inteiro {n} se, e somente se, existe {q\in{\mathbb Z}} tal que {kq=n}.

    Nesse caso escrevemos {k|n}.

    Que a implicação (23) é verdadeira:

    1) Suponha que {3} divide {n} (premissa)
    2) Se {3} divide {n}, então existe {q\in{\mathbb N}} tal que {n=3q} (definição de divide)
    3) {n=3q} (1, 2 e Modus Ponens e instanciação existencial)
    4) Se {n=3q}, então {n^2= 9q^2} (compatibilidade do = com \cdot)
    5) Se {n^2=9q^2} então existe {k\in {\mathbb Z}} tal que {n^2 = 9k} (generalização existencial)
    6) Se existe {k\in {\mathbb Z}} tal que {n^2 = 9k} então {9} divide {n^2} (definição de divide)
    7) Se {n=3q} então {9} divide {n^2} (silogismo hipotético com 4 e 5 e do resultado disso com 6)
    8) {9} divide {n^2} (modus ponens com as linhas 3 e 7)

    Como a variável {n} acima pode assumir qualquer valor natural, ou seja, {n} é um elemento genérico de {{\mathbb Z}}, o que provamos de fato foi a seqguinte sentença.

    Teorema 3 Para todo {n\in {\mathbb Z}}, se {3} divide {n} então {9} divide {n^2}.

    Em geral, quando escrevemos uma demonstração, não enumeramos nem justificamos os passos como foi feito no exemplo acima. Para a próximo exemplo escrevemos uma demonstração mais resumida.

    Teorema 4 Para todo {n\in{\mathbb Z}}, se {n} é ímpar, então {n^2} é ímpar.

    Demonstração: Seja {n} um número natural arbitrário. Vamos provar que se {n} é ímpar então {n^2} é ímpar.

    Suponha {n} ímpar.

    Então existe {k\in{\mathbb Z}} tal que {n=2k+1}.

    Se {n=2k+1} então {n^2=(2k+1)^2= 2(2k^2+2k)+1}.

    Portanto {n^2} é ímpar. \Box

    Exercício: Reescreva a demonstração acima exibindo todos os detalhes das deduções, numerando as linhas e justificando cada passo.

    Usualmente, pulamos passos elementares, mais fáceis e os passos ubíquos como a conclusão através da generalização universal. Também se temos a premissa {A} e a definição {A\leftrightarrow B}, então não escrevemos a dedução: de {A} e {A\rightarrow B}, temos {B}; nesse caso, vamos direto para a conclusão {B}. Ainda, é usual usarmos a mesma variável do enunciado para representar o elemento arbitrário do domínio. Finalmente, embora
    tenhamos usados símbolos lógicos para explicitar formas e argumentos,
    não usamos símbolos de conectivos e quantificadores para
    escrever uma demonstração na redação final, é uma questão de estilo de
    boa escrita.

    Retomemos a prova de

    {\forall x,y\in {\mathbb Z}}, se {x} e {y} são pares então {x+y} é par.

    1) {x} é par. (premissa)
    2) {y} é par. (premissa)
    3) Se {x} é par então {x=2k_1} para algum inteiro {k_1} (da definição de número par)
    4) {x=2k_1} (1, 3 e Modus Ponens e instanciação existencial)
    5) Se {y} é par então {y=2k_2} para algum inteiro {k_2} (da definição de número par)
    6) {y=2k_2} (2, 5 e Modus Ponens e instanciação existencial)
    7) {x=2k_1} e {y=2k_2} (4, 6 e a regra da conjunção)
    8) Se {x=2k_1} e {y=2k_2}, então {x+y = 2(k_1+k_2)} (compatibilidade do = com +)
    9) {x+y = 2(k_1+k_2)} (8, 7 e Modus Ponens)
    10) Se {x+y = 2(k_1+k_2)} então existe {c\in{\mathbb Z}} tal que {x+y=2c} (generalização universal)
    11) Existe {c\in{\mathbb Z}} tal que {x+y=2c} (9, 10 e Modus Ponens)
    12) Se existe {c\in{\mathbb Z}} tal que {x+y=2c} então {x+y} é inteiro e par (def. de número par)
    13) {x+y} é inteiro e par (11, 12 e Modus Ponens).

    Pulando as inferências decorrentes de definição e de propriedades certamente conhecidas, a demonstração resume-se em

    1) {x} é par.
    2) {y} é par.
    portanto
    4) {x=2k_1} para algum inteiro {k_1}
    6) {y=2k_2} para algum inteiro {k_2}
    portanto
    9) {x+y = 2(k_1+k_2)}
    portanto
    11) {x+y} é inteiro e par.

    Reescrevendo de modo a torná-la mais apresentável resulta na seguinte demonstração.

    Demonstração: Sejam {x} e {y} números inteiros. Suponha que {x} e {y} são pares, então existem {k_1,k_2\in{\mathbb Z}} tais que {x=2k_1} e {y=2k_2}. Logo {x+y = 2(k_1 + k_2)}, portanto, {x+y} é par por definição. \Box

    Exercício 7 Escreva uma demonstração para: para todo {x\in {\mathbb N}^*} (os naturais menos o zero), para todo {y\in{\mathbb N}}, se {x} divide {y} então {x^2} divide {y^2}.

    (Solução)


    2.2. Demonstração indireta de implicação

    Nesse tipo de prova, demonstramos que uma proposição logicamente equivalente a {P\rightarrow Q} é verdadeira, como a contrapositiva, por exemplo.

    • Prova da contrapositiva: Provamos que {\neg(Q)\rightarrow \neg(P)} é verdadeira donde concluímos que {P\rightarrow Q} é verdadeira pela equivalência lógica da contrapositiva. Por exemplo, para um número natural {n} arbitrário, a implicação

      \displaystyle n^2 \mathrm{~par} \rightarrow n \mathrm{~par} \ \ \ \ \ (24)

      é verdadeira (tente uma prova direta). Vamos provar a contrapositiva de (24)

      \displaystyle n \mathrm{~impar}\rightarrow n^2 \mathrm{~impar}

      1. Suponha {n} ímpar.
      2. Se {n} é ímpar, então pelo teorema 4 acima {n^2} é ímpar.
      3. Portanto, {n^2} é ímpar.

      Esse argumento é a regra Modus Ponens, assim temos (24) verdadeira.

      Definição (mdc) Vamos definir mdc (maior divisor comum) de quaisquer dois inteiros {a} e {b}. Primeiro, observamos que se {a>0} e {d} é um natural que divide {a} então {d\leq a}, portanto o conjunto de todos os divisores de {a} tem um maior elemento. Se {a=0} então todo inteiro é divisor de {a}, portanto o conjunto de todos os divisores de {a} não tem um maior elemento. Analogamente, o conjunto de todos os divisores de {b\neq 0} tem um maior elemento. Disso, está bem definido o

      \displaystyle \mathrm{mdc}(a,b) := \begin{cases} 0, &\text{ se }a=b=0,\\ \max \big\{ d\in{\mathbb N} \colon d|a \text{ e } d|b\big\}, &\text{ caso contr\'ario}. \end{cases} \ \ \ \ \ (1)

      Agora, para quaisquer inteiros {a} e {b}

      \displaystyle \mathrm{mdc}(a,b) := \mathrm{mdc}(|a|,|b|)

      em que {|a|} denota o valor absoluto de {a}.

      Definição (coprimo) {a} e {b} inteiros positivos são coprimos se, e só se, {\mathrm{mdc}(a,b)=1}.

      Teorema 6 Se {a} e {b} são números inteiros coprimos, então não são ambos par.

      Vamos demonstrar que se {a} e {b} são coprimos então não são ambos par pela contrapositiva. Isso significa provar a sentença

      \displaystyle \begin{array}{rcl} \text{para todos }a,b\in{\mathbb Z}, \, \big(a \text{ \'e par e } b \text{ \'e par}\big) \rightarrow \big(\mathrm{mdc}(a,b)\neq 1\big). \end{array}

      passo 1 Sejam {a} e {b} números inteiros arbitrários.

      passo 2

      1) {a} é par e {b} é par (premissa)
      2) Se {a} é par e {b} é par então {2|a} e {2|b} (definição de número par)
      3) se {2|a} e {2|b} então {\mathrm{mdc}(a,b)\geq 2} (definição de mdc)
      4) se {\mathrm{mdc}(a,b)\geq 2} então {\mathrm{mdc}(a,b)\neq 1} (pois {1\not\geq 2})
      5) se {a} é par e {b} é par então {\mathrm{mdc}(a,b)\neq 1} (silogismos com 2, 3 e 4)
      6) Portanto {\mathrm{mdc}(a,b)\neq 1}. (1, 5 e Modus Ponens)

      A implicação “ se {a} e {b} são números inteiros positivos coprimos, então não são ambos par” é verdadeira.

      passo 3 Concluindo pela generalização universal, pois {a} e {b} são inteiros arbitrários: para todo {a\in {\mathbb Z}} e todo {b\in{\mathbb Z}}, se {a} e {b} são coprimos, então não são ambos par.

      Demonstração: Sejam {a} e {b} números inteiros quaisquer. Vamos provar o teorema 6 pela contrapositiva. Suponhamos que {a} é par e que {b} é par. Então {2} divide {a} e divide {b}, logo o {\mathrm{mdc}(a,b)} é pelo menos {2}. Portanto, se {a} e {b} são inteiros pares então {\mathrm{mdc}(a,b)\neq 1}. \Box

    • Prova por vacuidade e prova trivial: A sentença {P\rightarrow Q} é verdadeira se conseguimos provar que {P} é falso. Por exemplo, considere o predicado {P(n):}

      se {n>1} então {n^2>n}.

      A sentença condicional {P(0)} é verdadeira por vacuidade.

      Assim, {\forall x (P(x) \rightarrow Q(x))} é verdadeiro porque para nenhum elemento do domínio da variável {x} o predicado {P} é verdadeiro. Para {R(n):}

      se {n + \frac 1n <2} então {n^2 + \frac 1n^2 <2}

      a sentença {\forall n\in {\mathbb N}^*,\, R(n)} é verdadeira por vacuidade.

      Observação: {\forall x\in D, P(x)} tem o mesmo significado que {\forall x\, (x\in D \rightarrow P(x))}.

      Teorema 7 Para todo {x\in{\mathbb R}}, se {x^2+1 <0} então {x^5\geq 4}.

      Demonstração: Seja {x} um real arbitrário. Sabemos que {x^2 \geq 0}, logo {x^2+1 > 0}. Portanto, por vacuidade, se {x^2+1 <0} então {x^5\geq 4}. \Box

      Notemos que a contrapositiva do teorema acima afirma que se {x^5 < 4} então {x^2+1 \geq 0}. Como a conclusão é sempre verdadeira a implicação também será, isto é,

      se {x^5 < 4} então {x^2+1 \geq 0}

      é verdadeiro porque {x^2+1 \geq 0} é verdadeiro. Esse argumento para uma mplicação é chamado de prova trivial.

      Teorema 8 Para qualquer conjunto {A}, {\emptyset \subseteq A}.

      Lembremos que, por definição,

      {\emptyset \subseteq A} se, e somente se {\forall x\, (x\in \emptyset \rightarrow x\in A)}.

      Demonstração por vacuidade: Como {x\in \emptyset} é falso, para qualquer {x}, a implicação {x\in \emptyset \rightarrow x\in A} é verdadeira. Portanto, {\forall x\, (x\in \emptyset \rightarrow x\in A)}. \Box

      Agora, a contrapositiva da sentença aberta {x\in \emptyset \rightarrow x\in A} é a sentença aberta {x\notin A \rightarrow x\notin \emptyset} cujo consequente, {x\notin \emptyset} é verdadeiro, portanto a condicional é verdadeira qualquer que seja o {x}.

      Demonstração trivial: Dado o conjunto {A}, {\emptyset \subseteq A} se, e só se, para todo {x}, se {x\notin A} então {x\notin \emptyset}, que vale trivialmente. \Box

    • Prova por contradição: Numa demonstração por contradição assumimos que a negação da sentença a ser provada é verdadeira e derivamos disso uma contradição, ou seja, uma sentença falsa.

      Mais especificamente, para demonstrar {P\rightarrow Q} usamos a equivalência lógica {(P\rightarrow Q) \Leftrightarrow (P\land \neg Q)\rightarrow \mathbf{F}} e demonstramos, de fato {(P\land \neg Q)\rightarrow \mathbf{F}}. Em geral, a estratégia é

      1) {P} (premissa)
      2) {\neg Q} (premissa)
      3) {\neg P} (demonstração)
      4) {P \land \neg P} (regra da conjunção com 1 e 3)
      5) portanto contradição (conclusão)

      Eventualmente, na linha 3 provamos {Q} e chegamos na contradição {Q\land \neg Q}. De fato, na linha 3 deduzimos alguma sentença que junto com as premissas formam uma sentença lógica falsa. Abreviemos por {P} o predicado “é par”. Vamos provar por contradição o terorema 6:

      {\forall a\in{\mathbb Z},~\forall b\in{\mathbb Z},~\big( (\mathrm{mdc}(a,b)=1) \rightarrow \neg (P(a) \land P(b)) \big).}

      Sejam {a} e {b} números inteiros arbitrários. Vamos provar { \big(\mathrm{mdc}(a,b)=1\big) \land \neg\neg( P(a)\land P(b)) \rightarrow \mathbf{F}}.

      1) {\mathrm{mdc}(a,b)=1}. (premissa)
      2) {\neg\neg(P(a) \land P(b))}. (premissa)
      3) {P(a) \land P(b)}. (pela dupla negação)
      4) Se {P(a) \land P(b)} então {\mathrm{mdc}(a,b)\geq 2}. (da definição de mdc)
      5) {\mathrm{mdc}(a,b)\geq 2}. (modus ponens)
      6) {\mathrm{mdc}(a,b)=1 \land \mathrm{mdc}(a,b)\geq 2} (conjunção de 1 e 4)

      Portanto, temos uma contradição.

      Demonstração: Sejam {a} e {b} números inteiros arbitrários. Suponha que {\mathrm{mdc}(a,b)=1}. Se {a} é par e {b} é par então {\mathrm{mdc}(a,b)\geq2}, uma contradição. Portanto, {a} e {b} não são ambos números pares. \Box


      2.3. Demonstração de equivalências

      Para demonstrar uma sentença da forma {P\leftrightarrow Q} usamos que {(P\leftrightarrow Q) \Leftrightarrow ( P\leftarrow Q)\land (P\rightarrow Q)} e, de fato, escrevemos duas demonstrações para
      condicionais, provamos {P\rightarrow Q} e a sua recíproca { Q\rightarrow P}. Cada uma dessas duas implicações pode ser demonstrada com alguma das técnicas para demonstrar uma implicação.

      Teorema 7 Para todo {n\in {\mathbb Z}}, {n} é ímpar se, e somente se, {n^2} é ímpar.

      Demonstração: Seja {n\in{\mathbb Z}} arbitrário. Vamos provar que {n^2} ímpar {\leftrightarrow} {n} ímpar.

      • {n^2} ímpar {\rightarrow} {n} ímpar: Essa implicação pode ser provada na contrapositiva: {n} par {\rightarrow} {n^2} par. Suponha {n} par. Se {n} é par então {n=2k} para algum {k\in{\mathbb Z}}. Se {n=2k} então {n^2=4k^2}. Se {n^2=4k^2} então {n^2} é par.
      • {n} ímpar {\rightarrow} {n^2} ímpar: Essa implicação é o teorema 4.

       

      Portanto a equivalência é verdadeira. \Box


      2.4. Demonstração por casos

      O argumento é baseado na equivalência lógica

      \displaystyle ((P_1 \lor P_2 \lor \cdots \lor P_n) \rightarrow Q) \Leftrightarrow ((P_1\rightarrow Q) \land (P_2\rightarrow Q) \land \cdots \land (P_n\rightarrow Q))

      as implicações {P_i\rightarrow Q} são os casos. Essa equivalência justifica o argumento válido

      {P_1\rightarrow Q}
      {P_2\rightarrow Q}
      {\vdots}
      {P_n\rightarrow Q}
      {P_1 \lor P_2 \lor \cdots \lor P_n}
      {\therefore Q}

      Por exemplo,

      para todo inteiro {n}, {n^ 2\geq n}.

      Seja {n} um inteiro qualquer. Então {n\leq -1} ou {n=0} ou {n\geq 1}.

      1. Caso {n=0}: se {n=0} então {n^2=0^2=0=n}, portanto {n^2 \geq n}.
      2. Caso {n \geq 1}: se {n \geq 1} então {n^2 \geq n}, multiplicando os dois lados da desigualdade por {n}, portanto {n^2 \geq n}.
      3. Caso {n \leq -1}: se {n \leq -1} então {n^2 \geq n}.

        Suponha {n \leq -1}, então {n<0}. Se {n<0} e {0 \leq n^2} então {n\leq n^2}.

      Portanto, {n^2 \geq n}. {\Box}

      Teorema 11 Para todo {n\in{\mathbb Z}}, {n^2 + 3n + 5} é ímpar.

      Demonstração: Seja {n} um inteiro arbitrário. Então {n} é divisível por {2} ou {n} não é divisível por {2}.

      Caso 1: Assuma {2|n}. Se {n} é divisível por {2} então {n=2k} para algum inteiro {k} e

      \displaystyle \begin{array}{rcl} n^2 + 3n + 5 = (2k)^2 + 3(2k) + 5 = 2(2k^2+3k+2)+1 \end{array}

      logo {n^2 + 3n + 5} é ímpar

      Caso 2: Assuma {2\not|n}. Se {n} não é divisível por {2} então {n=2k+1} para algum inteiro {k} e

      \displaystyle \begin{array}{rcl} n^2 + 3n + 5 = (2k+1)^2 + 3(2k+1) + 5 = 2(2k^2+5k+4)+1. \end{array}

      logo {n^2 + 3n + 5} é ímpar.

      Portanto, se {n} é inteiros então {n^2 + 3n + 5} é ímpar. \Box

      Exercício Escreva detalhadamente, passo-a-passo, a demonstração dos dois casos no exemplo acima. Em seguida, reúna suas deduções numa única dedução para a sentença do teorema 11.

      Teorema 12 Seja {n} um número inteiro. Se {1\leq n\leq 40} então {n^2 - n + 41} é primo.

      Demonstração: Defina {f(n) = n^2 - n + 41}.

      { f( 1 ) = 41} é primo, { f( 2 ) = 43} é primo, { f( 3 ) = 47} é primo, { f( 4 ) = 53} é primo, { f( 5 ) = 61} é primo, { f( 6 ) = 71} é primo, { f( 7 ) = 83} é primo, { f( 8 ) = 97} é primo, { f( 9 ) = 113} é primo, { f( 10 ) = 131} é primo, { f( 11 ) = 151} é primo, { f( 12 ) = 173} é primo, { f( 13 ) = 197} é primo, { f( 14 ) = 223} é primo, { f( 15 ) = 251} é primo, { f( 16 ) = 281} é primo, { f( 17 ) = 313} é primo, { f( 18 ) = 347} é primo, { f( 19 ) = 383} é primo, { f( 20 ) = 421} é primo, { f( 21 ) = 461} é primo, { f( 22 ) = 503} é primo, { f( 23 ) = 547} é primo, { f( 24 ) = 593} é primo, { f( 25 ) = 641} é primo, { f( 26 ) = 691} é primo, { f( 27 ) = 743} é primo, { f( 28 ) = 797} é primo, { f( 29 ) = 853} é primo, { f( 30 ) = 911} é primo, { f( 31 ) = 971} é primo, {f( 32 ) = 1033} é primo, {f( 33 ) = 1097} é primo, {f( 34 ) = 1163} é primo, {f( 35 ) = 1231} é primo, {f( 36 ) = 1301} é primo, {f( 37 ) = 1373} é primo, {f( 38 ) = 1447} é primo, {f( 39 ) = 1523} é primo, {f( 40 ) = 1601} é primo. \Box

      É possível conferir a lista dos 1000 primeiros números primos aqui.

      Exercicio 2 A demonstração por casos em geral é útil para provar propriedades do valor absoluto, porque esse é definido por casos. Sejam {a} e {b\neq 0} números reais. Demonstre que {\left| \frac ab \right| = \frac {|a|}{|b|}.}


      2.5. Demonstração de sentenças existenciais

      Para demonstrar uma proposição da forma lógica {\exists x,~P(x)}, usualmente, adotamos uma das seguintes estratégias.

      • Prova construtiva: exibimos um elemento {c} do universo tal que {P(c)} seja verdade.
      • Prova não-construtiva: inferimos indiretamente a existência desse objeto que torna {P} verdadeira, por exemplo, através de uma prova por contradição: assumimos que tal objeto não existe e derivamos uma contradição.

      Teorema 13 Existe um inteiro positivo {n} que pode ser escrito como a soma de dois cubos de duas maneiras diferentes.

      Demonstração: (construtiva) Faça {n=1729} e verifique que {1729 = 10^3 + 9^3 = 12^3 + 1^3}. \Box

      Teorema 14 Existem {x}, {y} irracionais tais que {x^y} é racional.

      Demonstração: (não-construtiva) Sabemos que {\sqrt{2}} é irracional.

      Se {\sqrt{2}^{\sqrt{2}}} é racional então faça {x=y=\sqrt 2}.

      Se {\sqrt{2}^{\sqrt{2}}} é irracional então faça {x=\sqrt{2}^{\sqrt{2}}} e {y=\sqrt{2}} e temos

      \displaystyle x^y = {\sqrt{2}^{\sqrt{2}}}^{\sqrt{2}} = \sqrt{2}^2 =2

      que é racional. \Box

      Na demonstração acima usamos a regra de inferência de prova por casos. Note-se que não sabemos exatamente pra quais valores de x e y a sentença vale, mesmo assim concluímos a existência deles.

      Teorema 15 Se {y} é racional então existe um inteiro {x} tal que {y < x}.

      Esse enunciado está (implicitamente) dizendo que

      \displaystyle \mathrm{para~todo~} y \in {\mathbb Q}, \mathrm{existe~} x\in{\mathbb Z}, y < x.

      Então, consideramos um racional arbitrário e demonstramos a sentença existencial {\mathrm{existe~} x\in{\mathbb Z}, \frac pq < x.}

      Demonstração: (construtiva) Seja {\frac pq} um racional arbitrário. Vamos exibir um inteiro n com a propriedade {\frac pq < n}.

      Faça {n=|p|+1}. Temos da definição de valor absoluto que{\frac pq \leq |\frac pq |}. Ademais {|\frac pq| \leq |p|} e {|p|< |p|+1}. Portanto {\frac pq < |p|+1}. \Box

      Teorema 17 O polinômio {p(x)=x^3+x-1} tem exatamente uma raiz real.

      Nesse enunciado temos duas afirmações a serem demonstradas. A primeira é que o polinômio tem raiz. A segunda é que a raiz “mostrada” no passo anterior é única.

      Demonstração (não-construtiva): Seja {p(x)=x^3+x-1}. Então {p} é uma função real e contínua em todo intervalo da reta real. Pelo Teorema do Valor Intermediário, para todo {b\in [p(0),p(1)]}, existe {a\in [0,1]} tal que {p(a)=b}. Como {p(0)=-1} e {p(1)=1} temos {0\in[p(0),p(1)]} assim fazendo {b=0} concluímos, pelo enunciado acima, que existe {a\in [0,1]} tal que {p(a)=0}. Portanto {a} é raiz de {p}.

      Agora, vamos demonstrar que essa raiz é única. A prova é por contradição. Suponha que {p} tenha pelo menos duas raízes. Sejam {r_1} e {r_2} raízes distintas de {p(x)} de modo que {r_1 < r_2}.

      Como {p(x)} é contínua em {[r_1,r_2]} e derivável em {(r_1,r_2)}, pelo Teorema do Valor Médio existe um ponto {c\in [r_1,r_2]} tal que

      \displaystyle p'(c) = \frac{p(r_2)-p(r_1)}{r_2-r_1}

      mas {p(r_2)-p(r_1)=0}, portanto {p'(c)=0} que é uma contradição pois {p'(x) = 3x^2 +1 >0} qualquer que seja {x}. Portanto, não pode haver duas raízes de {p}. \Box

      Na segunda parte da demonstração acima usamos a seguinte regra de inferência da demonstração por absurdo na forma:

      {\neg P\rightarrow \mathbf{F}}
      {\therefore P}

      assumimos a negação de “{p} tem uma única raiz” derivamos uma contradição {\mathbf{F}} e concluímos, com essa regra, que “{p} tem uma única raiz”.

      Exercício 10 Prove que para qualquer natural {n>1}, existe uma sequência formada por {n} números naturais consecutivos tal que nenhum deles é primo.

      (Solução)

      Exercício 11 Prove que no domínio dos números reais a seguinte sentença é verdadeira:

      \displaystyle \forall \epsilon >0, ~\exists \delta > 0, \forall x\in {\mathbb R},~ \left(|x-3|< \delta \rightarrow \left|\frac{2x^2-5x-3}{x-3}\right|<\epsilon\right).


      2.6. Mais demonstrações por contradição

      Os próximos exemplos são de demonstrações por contradição mas os enunciados não envolvem explicitamente uma condicional.

      Teorema 8 Para todo {d\in{\mathbb N}^*} e todo {e\in{\mathbb N}^*}

      \displaystyle \mathrm{mdc} \left( \frac d{\mathrm{mdc}(d,e)}, \frac e{\mathrm{mdc}(d,e)} \right)=1.

      Nesse casos, vamos provar que

      \displaystyle \begin{array}{rcl} \mathrm{mdc} \left( \frac d{\mathrm{mdc}(d,e)}, \frac e{\mathrm{mdc}(d,e)} \right) > 1 \rightarrow \mathbf{F}. \end{array}

      para {d} e {e} não nulos quaisquer. Disso inferimos que {\mathrm{mdc} \left( \frac d{\mathrm{mdc}(d,e)}, \frac e{\mathrm{mdc}(d,e)} \right) \leq 1}. Como não são ambos os números iguais a {0} temos {\mathrm{mdc} \left( \frac d{\mathrm{mdc}(d,e)}, \frac e{\mathrm{mdc}(d,e)} \right) \geq 1} da definição de mdc. Portanto concluímos que vale a igualdade, {\mathrm{mdc} \left( \frac d{\mathrm{mdc}(d,e)}, \frac e{\mathrm{mdc}(d,e)} \right) =1}.

      Demonstração: Sejam {d} e {e} números naturais arbitrários e não nulos. Façamos, para fins de simplificação, {m=\mathrm{mdc}(d,e)} e {k= \mathrm{mdc}(\frac dm, \frac em)}. Suponha {k>1}. Pela definição de mdc, {k} divide {\frac dm} e {k} divide {\frac em}.

      Se {k} divide {\frac dm} então {k m} divide {d}. (verifique) Logo {k m} divide {d}.

      Analogamente, {k m} divide {e}.

      Se {k>1} então {k m > m}. Logo {k m > m}.

      Se {k m | d} e {k m | e} então {km \leq m}, pois {m} é o maior divisor de {d} e {e}. Logo {km \leq m}.

      Portanto {k m > m} e {km \leq m}, uma contradição. \Box

      Corolário 9 Todo número racional pode ser escrito como {\frac ab} com {a} e {b} coprimos.

      Demonstração: Seja {q} um racional arbitrário. Por definição, existem inteiros {d} e {e} tais que {q=\frac de}.

      Faça {a=\frac d{\mathrm{mdc}(d,e)}} e {b=\frac e{\mathrm{mdc}(d,e)}} que temos, pelo teorema anterior, {\mathrm{mdc}(a,b)=1}.

      Portanto {q=\frac de = \frac ab}. \Box

      Teorema 10 {\sqrt{2}} é irracional.

      A prova desse teorema é por absurdo. Provamos que { \sqrt{2} \in {\mathbb Q} \rightarrow \mathbf{F}} donde inferimos {\neg( \sqrt{2} \in {\mathbb Q})}.

      Demonstração: Bases Matemáticas Faremos a demonstração pelo método de redução ao absurdo. Ou seja, supomos que {\sqrt 2} é um número racional, i.e., que existem números inteiros positivos a e b tais que: {\frac a b = \sqrt 2} ou, equivalentemente: {\left(\frac a b \right)^2}.

      Podemos supor que {a} e {b} não são ambos números pares, pois se fossem, poderíamos simplificar a fração até termos que pelo menos um dos termos da fração seja ímpar.

      Agora, escrevemos: {\left(\frac a b \right)^2 = \frac{a^2}{b^2} = 2}, então:

      \displaystyle qa^2 = 2b^2 \ \ \ \ \ (1)

      Concluímos então que {a^2} é um número par, pois é dobro de {b^2}. Logo {a} também deve ser par, pois se a fosse ímpar o seu quadrado também seria ímpar.

      Temos então que {a} é um número par e, portanto, é o dobro de algum número inteiro, digamos {k}: {a = 2k}. em (1) temos: {(2k)^2= 2b^2} implica {4k^2 = 2b^2} implica { 2k^2 = b^2}. De modo análogo, temos que {b} deve ser um número par. O que é absurdo pois {a} e {b} não são ambos números pares. Portanto, {\sqrt 2} tem que ser um número irracional. Como queríamos demonstrar. \Box

      Façamos um escrutínio:

      1) {\sqrt{2} \in {\mathbb Q} } (premissa)
      2) Se {\sqrt{2} \in {\mathbb Q} } então existem naturais positivos e coprimos {a} e {b} tais que {\sqrt{2}=\frac{a}{b}}. (corolário 9)
      3) Existem naturais positivos tais que {\sqrt{2}=\frac{a}{b}} e coprimos {a} e {b} . (modus ponens)
      4) {\sqrt{2}=\frac{a}{b}} e {a} e {b} são coprimos. (instanciação existencial)
      5) {a} e {b} são coprimos. (4 e regra da simplificação)
      6) {\sqrt{2}=\frac{a}{b}}. (4 e regra da simplificação)
      7) Se {\sqrt{2} =\frac ab} então {2 = \left(\frac a b\right)^2}. (compatibilidade do = com o {\cdot})
      7{\frac 12}) Se {2 = \left( \frac a b\right)^2} então {2 = \frac {a^2}{b^2}}. (propriedade aritmética da potência)
      8) Se {2 = \frac {a^2}{b^2}} então {a^2=2 b^2}. (compatibilidade do = com o {\cdot})
      9) Se {\sqrt{2} =\frac ab} então {a^2=2 b^2} . (silogismo de 7, 7{\frac 12} e 8)
      10) {a^2=2 b^2} . (6, 9 e modus ponens)
      11) Se {a^2=2 b^2} então {a^2} é par. (definição de par)
      12) Se {a^2} é par então {a} é par (contrapositiva do teorema 4)
      13) Se {a^2=2 b^2} então {a} é par (silogismo de 11 e 12)
      14) {a} é par (10, 13 e modus ponens)
      15) Se {a} é par então existe {k\in{\mathbb N}}, {a=2k}. (definição de par)
      16) Existe {k\in{\mathbb N}}, {a=2k}. (14, 15 e modus ponens)
      17) {a=2k}. (instanciação universal)
      18) {a=2k} e {a^2=2 b^2} . (conjunção de 10 e 17)
      19) Se {a=2k} e {a^2=2 b^2} então {4k^2 = 2b^2}. (compatibilidade do = com o {\cdot})
      19) Se {4k^2 = 2b^2} então {2k^2 = b^2}. (compatibilidade do = com o {\div} )
      20) Se {b^2 = 2k^2} então {b^2} é par. (definição de par)
      21) Se {b^2} é par então {b} é par. (contrapositiva do teorema 4)
      22) Se {a=2k} e {a^2=2 b^2} então {b} é par. (silogismos de 19, 20 e 21)
      23) {b} é par. (18, 22 e modus ponens)
      24) {a} é par e {b} é par. (conjunção de 14 e 23)
      25) {a} e {b} coprimos e {a} é par e {b} é par. (contradição)

      Exercício 12 Prove que não há uma quantidade finita de números primos.

      Exercício 13 Prove que não há um “menor racional positivo”.

      Exercícios

    • 4 respostas em “[MCTB019-17] § 2 — Demonstrações: técnicas”

    1. Professor, na demonstração do teorema 14 parece que tem algo errado. Você divide em casos. Na parte (a) você assume que é racional e, até aí, sem problemas. Mas na parte (b), você assume que não é (afinal, ou é racional ou não é) e durante a demonstração algébrica você assume a parte (a) [quando você faz sqrt(2)^sqrt(2)=2, que é racional], contrariando o que você tinha assumido para a parte (b). Pode ser que tenha entendido errado também, mas fiquei com essa dúvida. Além do mais, eu chequei no Wolfram Alpha e sqrt(2)^sqrt(2)^sqrt(2) não é igual a 2.

      Comentar ↓

    Deixe um comentário