Capítulo 1

Elementos de Lógica e Linguagem Matemática

“Quando eu uso uma palavra, disse Humpty Dumpty, em tom bastante desdenhoso, ela significa exatamente o que eu quiser que ela signifique - nem mais nem menos.”
Através do Espelho - Lewis Carroll

A matemática utiliza uma linguagem específica, na qual os termos possuem significados precisos e muitas vezes distintos do usual. Assim é necessário que conheçamos o sentido de alguns termos e expressões matemáticas. Esse é um dos objetivos desse capítulo, ao apresentar de modo sucinto e intuitivo os aspectos fundamentais da linguagem matemática, enfatizando principalmente aqueles termos que são usados em contextos e com significados diversos daqueles em que costumamos empregá-los normalmente.

Mas não é somente o vocabulário e a linguagem que são distintos na matemática. Também a concepção de argumento, de justificativa, e mesmo de explicação. Um argumento matemático, também conhecido como demonstração ou prova, para ser correto, deve seguir princípios estritos de lógica, princípios que garantam a confiabilidade do conhecimento matemático. Alguns desses princípios são apresentados na seção 1.2.

1.1 Proposições

Começaremos definindo as frases mais simples de nossa linguagem: as proposições.

Definição 1.1

Uma proposição é uma sentença declarativa que é verdadeiraou falsa, mas não simultaneamente ambas.

Exemplo 1.1 (Exemplos)

As seguintes frases são exemplos de proposições.

“$2 +5 = 7$”;
“A função $f(x)=-x$ é uma função crescente”. Nesse caso, temos um exemplo de uma proposição falsa.
“$2^{25^{9876}}+3^{4576}$ é primo”; É uma proposição pois apesar de não ser fácil decidir se a proposição é verdadeiraou falsa, claramente só uma dessas opções pode ocorrer.

Exemplo 1.2 (Exemplos)

Nenhuma das frases seguintes é uma proposição, porque ou não são declarações ou não podemos atribuir um único valor verdadeiroou falso.

“Vamos dançar!”
“Como você está?”.
“Esta sentença é falsa”. Essa frase não pode ser verdadeira pois isto implicaria que ela é falsa. E não pode ser falsa pois implicaria que é verdadeira.
“Está quente hoje”. Essa frase pode ser vista como uma proposição desde que especifiquemos precisamente o que significa quente, como por exemplo se definirmos que está quente se a temperatura é maior que 26ºC, pois somente assim podemos atribuir um valor de verdade a frase. Note, porém, que esse não é o uso cotidiano da frase. O uso cotidiano expressa uma impressão, uma sensação e nesse sentido não é uma proposição.

Como ilustrado pelo exemplo anterior, o fato de uma sentença poder ser vista como uma proposição depende do contexto em que essa sentença é enunciada e dentro desse contexto uma proposição deve ser suficientemente clara e objetiva para que possamos atribuir um e somente um valor verdade, i.e, verdadeiroou falso.

Finalmente, a definição de proposição implica que todas as afirmações matemáticas serão necessariamente verdadeiras ou falsas, não havendo outra possibilidade (esse último fato é conhecido como Princípio do Terceiro Excluído).

Notação: No que se segue denotaremos uma proposição qualquer por $p,q,r$, etc.

1.1.1 Proposições Quantificadas

Em diversas situações precisamos que o “sujeito“ das proposições seja uma variável que possa ser substituída por um elemento qualquer dentre uma coleção de objetos $\mathbb {U}$ em consideração. O conjunto $\mathbb {U}$ neste caso será denominado universo do discurso, ou ainda, domínio de discurso . Assim, por exemplo, na sentença “$ x\in \mathbb {R}, x\lt 3$”, $x$ é a variável e $\mathbb {R}$ é o universo do discurso.

Proposições que dependam de uma ou mais variáveis são denominadas proposições abertas. Elas são indicadas por uma letra seguida da variável ou das variáveis entre parênteses, i.e,

\[ p(x), q(x), p(x,y),... \]

O valor verdade de uma proposição aberta depende do valor atribuído às variáveis. Por exemplo, considere a função proposicional $p(x)=$“$x\lt 3$”, neste caso se $x=2$ então $p(2)=$“$2\lt 3$” tem valor verdade $\textsf{verdadeiro}$, por outro lado se considerarmos $x=4$ temos que $p(4)=$“$4\lt 3$ ” tem valor verdade $\textsf{falso}$.

Definição 1.2

O conjunto dos valores de $x$ para os quais a proposição aberta $p(x)$ $\textsf{verdadeira}$ é denominado conjunto verdade de $p(x)$.

Exemplo 1.3 (Exemplos)

O conjunto verdade de $p(x)=$”$x$ é primo e $3\lt x\lt 14$” é $\{ 5,7,11,13\} $
O conjunto verdade de $p(x)=$”$x$ é real e $x^2+1=5$” é $\{ -2,2 \} $

Através de proposições abertas podemos fazer afirmações sobre todos os elementos de um conjunto usando o quantificador universal $\forall $ que é lido como “para todo”ou "qualquer que seja".

Assim a proposição “para todo número natural $n$ temos que $2n+1$ é ímpar” pode ser escrita como

\[ \forall n \in \mathbb {N}, 2n+1 \text{ é ímpar} \]

ou ainda como

\[ \forall n \in \mathbb {N} p(n), \]

sendo que $p(n)$ denota a proposição aberta “$2n+1 \text{ é ímpar}$”.

Também é possível fazer afirmações sobre a existência de um elemento de um conjunto usando o quantificador existencial $\exists $, que é lido como “existe”. Desta forma a proposição “a equação linear $ax+b=0$, com $a \neq 0$, admite solução real” pode ser escrita como :

\[ \text{Se }a \neq 0, \exists x\in \mathbb {R}\, \mid \, ax+b=0. \]

Ou ainda, se denotarmos como $q(x)=``ax+b=0''$ podemos reescrever a afirmação anterior como:

\[ \text{Se }a \neq 0, \exists x \in \mathbb {R}\, \mid \, q(x). \]

Ou de modo mais resumido, deixando subentendido o domínio do discurso e o símbolo de tal que, $\, \mid \, $:

\[ \text{Se }a \neq 0, \exists x q(x) \]

Ressaltamos que $\exists x \, \mid \, p(x)$ significa que existe pelo menos um elemento no domínio de discurso tal que para esse elemento vale $p(x)$. Em diversas situações esse elemento é único, denotaremos esse fato por $\exists ! x \, \mid \, p(x)$, que se lê “existe e é único $x$ tal que $p(x)$”. Assim por exemplo, nos reais, $\exists ! x \in \mathbb {R}\, \mid \, (x-1)=0$.

É importante distinguirmos as variáveis que estão quantificadas das que não estão. Uma variável é dita livre quando não está quantificada e é dita aparente quando está quantificada. Assim, na proposição “$n$ é par”, $n$ é uma variável livre. Já em “ para todo número natural $n$, $2n+1$ é ímpar” $n$ é uma variável aparente.

Em português	símbolo	nome
Para todo, para cada	$\forall$	quantificador universal
Existe, há, para algum	$\exists$	quantificador existencial
Existe único	$\exists !$

Tabela 1.1 Quantificadores

Os quantificadores permitem distinguir duas formas fundamentais de afirmação matemática. Uma afirmação universal diz que uma propriedade vale para todos os elementos do domínio; uma afirmação existencial diz que há pelo menos um elemento para o qual a propriedade vale.

Exemplo 1.4 (Exemplos)

No universo dos números naturais:

“Todo número natural é maior ou igual a $0$” é uma afirmação universal:

\[ \forall n\in \mathbb {N},\quad n\geq 0. \]
“Existe um número natural cujo quadrado é igual a ele mesmo” é uma afirmação existencial:

\[ \exists n\in \mathbb {N}\, \mid \, n^2=n. \]
“Todo número natural é ímpar” é uma afirmação universal falsa.
“Existe um número natural par” é uma afirmação existencial verdadeira.

O tipo de quantificador não determina o valor verdade da afirmação. Há afirmações universais verdadeiras e falsas, assim como afirmações existenciais verdadeiras e falsas.

Exemplos e Contra-exemplos

Quando uma afirmação é universal, um contraexemplo é um elemento do domínio para o qual a propriedade afirmada falha. Um único contraexemplo basta para mostrar que a afirmação universal é falsa.

Exemplo 1.5 (Exemplos)

Na afirmação “todo número natural é ímpar”, o número $5$ satisfaz a propriedade, mas isso não demonstra a afirmação. Já o número $2$ é um contraexemplo e, sozinho, mostra que ela é falsa.
Na afirmação “existe um inteiro $x$ tal que $x^2=9$”, o número $3$ é um exemplo que comprova a existência pedida.

Essas duas formas de afirmação exigem cuidados diferentes:

para provar uma afirmação existencial, basta exibir um elemento que satisfaça a propriedade;
para refutar uma afirmação universal, basta exibir um contraexemplo;
verificar muitos exemplos não demonstra uma afirmação universal;
para provar uma afirmação universal, é necessário um argumento que se aplique a um elemento arbitrário do domínio.

Exercício 1.1

Transcreva as seguintes proposições para a forma simbólica:
Existe um número real $n$ tal que $n^2=2$.
Não existe número racional $x$ tal que $x^2=2$.
Existe $x$ tal que $x^2$ é par e divisível por $3$.
Não existe número inteiro $x$ tal que $x^2$ é primo ou $x^2$ é negativo.
Existe um número inteiro $x$ tal que $x^2$ é par ou $x^2$ é ímpar.
Para cada número real $x$ existe um número real $y$ tal que $x+y=0$.
Todo elemento do conjunto $A$ é elemento do conjunto $B$.

Ver solução

a $\exists n \in \mathbb {R}\, \mid \, n^2=2$ b $\mathop{\mathit{não}}\exists x \in \mathbb {Q}\, \mid \, x^2=2$ c $\exists x \, \mid \, (x^2 \text{ é par} \mathop{\mathit{e}}x^2 \text{ é divisível por } 3)$ d $\mathop{\mathit{não}}\exists x \in \mathbb {Z}\, \mid \, (x^2 \text{ é primo} \mathop{\mathit{ou}}x^2\lt 0)$ e $\exists x \in \mathbb {Z}\, \mid \, (x^2 \text{ é par} \mathop{\mathit{ou}}x^2 \text{ é ímpar})$ f $\forall x \in \mathbb {R}, \exists y \in \mathbb {R}\, \mid \, x+y=0$ g $\forall x, (x \in A \Rightarrow x \in B)$

Exercício 1.2

Seja $A=\{ 1,2,3,4\} $. Determine o valor verdade para cada uma das seguintes proposições:
$\exists x \in A \, \mid \, x+4=9$.
$\exists x \in A \, \mid \, x\lt 7$.
$\forall x \in A, x+3\lt 7$.
$\forall x \in A, x+3\lt 9$.

Ver solução

a $\textsf{falso}$ (o único candidato seria $x=5\notin A$). b $\textsf{verdadeiro}$ c $\textsf{falso}$ (para $x=4$, $4+3=7\not\lt 7$). d $\textsf{verdadeiro}$ (o maior valor de $x+3$ é $7\lt 9$).

Exercício 1.3

Para todas as afirmações a seguir $n$ denota um número natural. Determine o conjunto verdade das seguintes proposições abertas:
$n^2\lt 12$
$3n+1\lt 25$
$3n+1\lt 25$ e$n+1\gt 4$
$n\lt 5$ ou $n\gt 3$
$n$ é primo e não é verdade que $n\gt 17$
$(n-2)(n-3)(n-4)(n-5)=0$

Ver solução

a $\{ 0,1,2,3\} $ b $\{ 0,1,2,3,4,5,6,7\} $ c $\{ 4,5,6,7\} $ d $\mathbb {N}$ (todo natural é menor que $5$ ou maior que $3$). e $\{ 2,3,5,7,11,13,17\} $ f $\{ 2,3,4,5\} $

Exercício 1.4

Dê exemplos ou contraexemplos, se existirem, para as seguintes afirmações:

Para todo $x\in \mathbb {R}$, $x+1\gt 2$.
Todas as letras da palavra “banana” são vogais.
Para todo $x \in \mathbb {R}$, $x^{2}\lt x$.
Para todo $y \in \mathbb {N}$, $y^3\gt 1$

Ver solução

a Exemplos: qualquer número real maior que $1$. Contraexemplos: qualquer número real menor ou igual a $1$. b Exemplo: a letra a. Contraexemplos: as letras b e n. Logo a afirmação é falsa. c Contraexemplos: $x=1$ (pois $1\lt 1$ é falso) ou $x=2$. Exemplos: os reais $x$ com $0\lt x\lt 1$, como $x=\frac{1}{2}$. d Contraexemplos: $y=0$ e $y=1$. Exemplos: qualquer natural $y\geq 2$.

1.1.2 Proposições Compostas: e, ou, não

Podemos expandir nossa linguagem construindo novas proposições através da combinação de proposições mais simples de modo a obter proposições mais elaboradas. Faremos a combinação de proposições através de conectivos, dentre os quais “e”, “ou” e “implica” e do modificador “não”.

Definição 1.3

Dadas duas proposições $p,q$:

a proposição composta $p \mathop{\mathit{ou}}q$ é chamada disjunção de $p$ e $q$. A disjunção $p \mathop{\mathit{ou}}q$ é $\textsf{verdadeira}$ quando pelo menos uma das proposições $p$ ou $q$ forem $\textsf{verdadeiras}$. Caso contrário o valor verdade de $p \mathop{\mathit{ou}}q$ é $\textsf{falso}$.
a proposição composta $p \mathop{\mathit{e}}q$ é chamada conjunção das proposições $p$ e $q$. A conjunção $p \mathop{\mathit{e}}q$ é verdadeirasomente quando as proposições $p$ e $q$ forem ambas verdadeiras. Caso contrário o valor verdade de $p \mathop{\mathit{e}}q$ é falso.

A proposição $p \mathop{\mathit{ou}}q$, pela definição anterior, é falsa somente quando ambas as proposições $p$ e $q$ forem falsas. Desta forma o uso do conectivo ouem matemática não é o mesmo que o uso cotidiano do termo. Assim, por exemplo, o sentido usual da expressão “Pedro estava estudando ou Pedro estava numa festa” não inclui a possibilidade que ele estivesse estudando numa festa, enquanto que o conectivo ouem matemática inclui essa possibilidade. Ou seja, em matemática o conectivo oué sempre usado de modo inclusivo.

Por outro lado o sentido da conjunção ese aproxima do sentido usual do “e” em português, assim a proposição $p \mathop{\mathit{e}}q$ é verdadeira somente quando ambas as proposições $p$ e $q$ forem verdadeiras.

Definição 1.4

Dado uma proposição $p$, a negação de $p$ é uma proposição com valor verdade invertido, chamada de negação de $p$, denotada $\mathop{\mathit{não}}p$ e que pode ser lida como “não $p$” ou “não é verdade $p$”.

Exemplo 1.6 (Exemplos)

A negação da proposição “$x$ é ímpar” é a afirmação “$x$ não é ímpar”, ou equivalentemente “$x$ é par”
A negação da proposição “$\sqrt{2}$ não é racional” é “$\sqrt{2}$ é racional”

Observação

Adotaremos a seguinte convenção relativa a prioridade dos operadores lógicos: o modificador $\mathop{\mathit{não}}$ abrange somente a proposição mais próxima, salvo o caso de parênteses. Assim, por exemplo $\mathop{\mathit{não}}p \mathop{\mathit{ou}}q$, somente a proposição $p$ é negada, isto é, a proposição anterior é uma forma abreviada da proposição $(\mathop{\mathit{não}}p )\mathop{\mathit{ou}}q $.

O seguinte teorema nos diz como negar a conjunção e a disjunção de duas proposições.

Teorema 1.1

Negação da Disjunção e da Conjunção e Dupla Negação
Sejam $p,q$ proposições. Então são válidas as seguintes regras de negação

A negação da proposição $ p \mathop{\mathit{e}}q $ é $(\mathop{\mathit{não}}p ) \mathop{\mathit{ou}}(\mathop{\mathit{não}}q)$;
A negação da proposição $ p \mathop{\mathit{ou}}q$ é $ (\mathop{\mathit{não}}p) \mathop{\mathit{e}}(\mathop{\mathit{não}}q)$;
A negação da proposição $\mathop{\mathit{não}}p$ é $p$.

Exemplo 1.7 (Exemplos)

A negação da proposição “$x$ é divisível por $2$ e $3$” é “$x$ não é divisível por $2$ ou $x$ não é divisível por $3$”.
A negação da proposição “$x$ é divisível por $2$ ou $3$” é “$x$ não é divisível por $2$ e $x$ não é divisível por $3$”.
A negação da proposição “$b$ é soma de quadrados ou $b$ é primo” é a afirmação que “$b$ não é soma de quadrados e $b$ não é primo”.
A negação da proposição “$x$ é maior que $2$ ou$x$ é menor igual que $-1$ ” é a proposição “ $x$ é menor igual a $2$ e$x$ é maior que $-1$.”

Para proposições quantificadas temos ainda as seguintes regras de negação:

Teorema 1.2

Negação do Quantificador
Seja $p(x)$ um proposição aberta. Então são válidas as seguintes regras de negação:

A negação da proposição “para todo $x$ em $D$ é verdade $p(x)$” é a proposição “existe pelo menos um $x$ em D tal que não é verdade $p(x)$”.
A negação da proposição “existe $x$ em $D$ tal que é verdade $p(x)$” é a proposição “para todo $x$ em $D$ não é verdade $p(x)$”.

Exemplo 1.8 (Exercício resolvido)

Converta as seguintes afirmações para a forma simbólica e diga quais são as suas negações:

Todos os números naturais podem ser decompostos como produtos de primos.
Existe inteiro $n$ tal que $n+3=4$.

Solução

Todos os números naturais podem ser decompostos como produtos de primos.

Se denotarmos $m(x)=`` x \text{ pode ser decomposto como produto de números primos}$”, então a proposição acima pode ser reescrita na forma simbólica como:

\[ \forall x \in \mathbb {N}, m(x) \]

ou mais resumidamente $(\forall x ) m(x)$, deixando implícito que o domínio da variável é o conjunto dos números naturais.

A negação da proposição é “ Existe um número natural que não pode ser decomposto em primos” ou simbolicamente

\[ \exists x \in \mathbb {N}\, \mid \, \mathop{\mathit{não}}m(x) \]
Existe inteiro $n$ tal que $n+3=4$.

Se denotarmos por $p(n)=``n+3=4''$ então a proposição pode ser reescrita em forma simbólica como

\[ \exists n \in \mathbb {N} \, \mid \, p(n) \]

Para essa proposição o domínio do discurso são os números naturais. Observe que essa afirmação é verdadeira pois $1$ satisfaz $p(1)$. A negação de “Existe um número inteiro $n$ tal que $n+3=4$” é “para todo inteiro $n$ temos que não é verdade que $n+3=4$”, ou simplificando “para todo número inteiro $n$ temos que $n+3 \neq 4$”

Exercício 1.5

Atribua um valor verdade à cada uma das seguintes proposições:
$5$ é um número primo e $4$ é um número ímpar.
$5$ é um número primo ou $4$ é um número ímpar.
Não é verdade que $\left(5\text{ é um número primo e } 4 \text{ é um número ímpar.}\right)$
$\left( \text{Não é verdade que } 5 \text{ é um número primo}\right)$ ou $4$ é um número ímpar.

Ver solução

a $\textsf{falso}$ b $\textsf{verdadeiro}$ c $\textsf{verdadeiro}$ d $\textsf{falso}$

Exercício 1.6

Negue as seguintes proposições:
$3\gt 4 \mathop{\mathit{e}}2$ é um número par.
$4\gt 2 \mathop{\mathit{ou}}3\gt 5$.
$4\gt 2 \mathop{\mathit{ou}}\left(\exists k)( k\lt 3 \mathop{\mathit{e}}k\gt 5 \right)$.
(Não é verdade que $3$ é um número par) ou que $5$ é um número ímpar.
$2$ é um número par e $3k+1$ é um número ímpar.
$2$ é número par e não é verdade que $3$ é um número ímpar.
Não é verdade que $\left(5\text{ é um número primo e } 4 \text{ é um número ímpar.} \right)$
$\left(\text{Não é verdade que } 5 \text{ é um número primo}\right)$ ou $4$ é um número ímpar.

Ver solução

a $3\leq 4 \mathop{\mathit{ou}}2$ não é par (ou seja, $2$ é ímpar). b $4\leq 2 \mathop{\mathit{e}}3\leq 5$. c $4\leq 2 \mathop{\mathit{e}}\forall k,\ (k\geq 3 \mathop{\mathit{ou}}k\leq 5)$. d $3$ é par e $5$ não é ímpar. e $2$ não é par ou $3k+1$ é par. f $2$ não é par ou $3$ é ímpar. g $5$ é primo e $4$ é ímpar. h $5$ é primo e $4$ não é ímpar.

Exercício 1.7

Nas seguintes proposições abertas o domínio do discurso é o conjunto dos números reais. Para essas proposições determine e esboce na reta real o seu conjunto verdade.
$x\gt 2$ e $x\lt 4$.
$x\gt 2$ ou $x\lt 3$.
$x\gt 2$ ou ( $x\lt 5$ e $x\gt 3$).
não é verdade que ($x\gt 2$ e $x\lt 4$).

Ver solução

a $(2,4)$. b $\mathbb {R}$: todo real é maior que $2$ ou menor que $3$. c $(2,+\infty )$: a condição $x\lt 5$ e $x\gt 3$ define $(3,5)$, que já está contido em $(2,+\infty )$. d $(-\infty ,2]\cup [4,+\infty )$.

Exercício 1.8

Para as seguintes proposições, escreva a negação, em português e simbólica, de cada uma delas.
Existe um número real $x$ tal que $x^2=2$.
Não existe número racional $x$ tal que $x^2=2$.
Existe um número natural $n$ tal que $n^2$ é par e divisível por $3$.
Não existe número inteiro $m$ tal que $m^2$ é um número primo ou $m^2$ é negativo.
Para cada número real $x$ existe um número real $y$ tal que $x+y=0$.
Todo elemento de um conjunto $A$ é elemento do conjunto $B$.

Ver solução

a Para todo real $x$, $x^2\neq 2$. Simbolicamente: $\forall x\in \mathbb {R},\ x^2\neq 2$. b Existe um racional $x$ tal que $x^2=2$. Simbolicamente: $\exists x\in \mathbb {Q}\, \mid \, x^2=2$. c Para todo natural $n$, $n^2$ é ímpar ou não é divisível por $3$. Simbolicamente: $\forall n\in \mathbb {N},\ (n^2 \text{ é ímpar} \mathop{\mathit{ou}}n^2 \text{ não é divisível por } 3)$. d Existe um inteiro $m$ tal que $m^2$ é primo ou $m^2$ é negativo. Simbolicamente: $\exists m\in \mathbb {Z}\, \mid \, (m^2 \text{ é primo} \mathop{\mathit{ou}}m^2\lt 0)$. e Existe um real $x$ tal que, para todo real $y$, $x+y\neq 0$. Simbolicamente: $\exists x\in \mathbb {R}\, \mid \, \forall y\in \mathbb {R},\ x+y\neq 0$. f Existe um elemento de $A$ que não é elemento de $B$. Simbolicamente: $\exists x\in A \, \mid \, x\notin B$.

1.1.3 Implicação

Um dos conectivos de maior importância na matemática é a implicação ou condicional.

Definição 1.5

Dadas duas proposições $p$ e $q$ então podemos construir a proposição “se $p$ então $q$” que também pode ser lida como “$p$ implica $q$”, que denotaremos por

\[ p \Rightarrow q . \]

A implicação $p \Rightarrow q$ é $\textsf{falsa}$ somente no caso que a proposição $p$ é $\textsf{verdadeira}$ e a proposição $q$ é $\textsf{falsa}$.

Numa implicação, $p \Rightarrow q$, a proposição $p$ é denominada hipótese ou premissa e a proposição $q$ é denominada tese, conclusão ou consequente da implicação.

A tabela a seguir apresenta o valor verdade de $p \Rightarrow q$ em função dos valores verdades de $p$ e $ q$.

$p$	$q$	$p \implica q$
$\Vl$	$\Vl$	$\Vl$
$\Vl$	$\Fl$	$\Fl$
$\Fl$	$\Vl$	$\Vl$
$\Fl$	$\Fl$	$\Vl$

Tabela 1.2 Valores verdade da implicação em função dos valores verdades de $p$ e $q$.

E importante observar, que na matemática a implicação $p \Rightarrow q$ não estabelece nenhuma relação de causa-efeito entre a hipótese e a tese. A implicação matemática somente estabelece uma relação entre o valor lógico da implicação e os valores lógicos da premissa e da conclusão.

Assim a implicação “Se $4$ é par, então um triângulo equilátero tem todos os ângulos iguais” é uma implicação verdadeira pois o antecedente (“$4$ é par”) é verdadeiro e o consequente (“um triângulo equilátero tem todos os ângulos iguais”) é também verdadeiro. Apesar disso, nenhuma relação causal parece existir entre esses dois fatos. Mais surpreendente, nesse aspecto é que a implicação “se $2$ é ímpar então $2+5=3$” é verdadeira. Esse exemplo ilustra a última linha da nossa tabela. É fundamental observar que estamos afirmando apenas que a implicação é verdadeira, e não a conclusão da implicação é verdadeira.

Esse comportamento “não-usual” da implicação pode ser melhor entendido através de uma analogia. Imagine uma lei que diz que todos os motoristas de fusca devem usar gravatas vermelhas. Quando um motorista estará desobedecendo a lei? Se ele não estiver dirigindo fusca (ou seja premissa falsa) então não importa se ele está ou não usando gravata vermelha pois nesse caso a lei não se aplica a ele. O único modo de desobedecer a lei é estar dirigindo um fusca (premissa verdadeira) e não estiver usando gravata vermelha (conclusão falsa). Esse é o comportamento da implicação, ela só é falsa se a premissa for verdadeira e o consequente falso.

Exemplo 1.9 (Exemplos)

“Se $2$ é par, então $3$ é ímpar” é verdadeira: hipótese e conclusão são verdadeiras.
“Se $2$ é par, então $4$ é ímpar” é falsa: a hipótese é verdadeira e a conclusão é falsa.
“Se $2$ é ímpar, então $3$ é par” é verdadeira: a hipótese é falsa.
“Se a mãe de Pedro é um trator então Pedro é uma moto-serra.” é uma implicação verdadeira, pois a premissa é falsa (implicitamente estamos assumindo que Pedro é humano, e que humanos não são tratores).

Teorema 1.3

Negação da implicação

A negação da implicação $p \mathop{\mathit{implica}}q$ é a proposição $ p \mathop{\mathit{e}}\mathop{\mathit{não}}q$

Exemplo 1.10 (Exemplos)

A negação de “Se $a$ é par, então $a^2$ é par” é “$a$ é par e $a^2$ é ímpar”.
A negação de “Se $n$ é divisível por $4$, então $n$ é par” é “$n$ é divisível por $4$ e $n$ não é par”.

Dada uma proposição $p \Rightarrow q $ então:

a proposição $q \Rightarrow p$ é chamada de recíproca da proposição;
a proposição $\mathop{\mathit{não}}$ $q \Rightarrow $ $\mathop{\mathit{não}}$ $p$ é chamado de contrapositiva;
a proposição $\mathop{\mathit{não}}$ $p$ $\Rightarrow $ $\mathop{\mathit{não}}$ $q$ é chamado de inversa da proposição.

Destacamos que uma implicação e sua contrapositiva são equivalentes, ou seja, ou ambas são simultaneamente verdadeiras ou ambas são simultaneamente falsas. Como veremos posteriormente (na seção 1.2.2), essa equivalência nos fornece uma técnica de demonstração: no lugar de demonstrarmos uma implicação podemos demonstrar sua contrapositiva.

Também observamos que a contrapositiva da recíproca é a inversa (veja exercício 1.12), e assim pelas razões apresentadas no parágrafo anterior a recíproca e a inversa são equivalentes .

Ressaltamos que um erro lógico muito comum é confundir uma proposição com a sua recíproca. O próximo exemplo ilustra que uma implicação verdadeira pode ter a recíproca falsa.

Exemplo 1.11 (Exemplos)

Considere a seguinte proposição “se $x$ é um número racional então $x^2$ é um número racional”. Essa implicação é verdadeira, como veremos no exercício 1.21.c.

a proposição “se $x^2$ é um número racional então $x$ é um número racional” é a recíproca dessa proposição. Essa recíproca é falsa pois $\sqrt{2}$ não é um número racional, mas o seu quadrado, o número $2$, é racional
a proposição “se $x^2$ não é um número racional, então $x$ não é um número racional” é a contrapositiva da proposição inicial, e assim verdadeira.
a proposição “se $x$ não é um número racional então $x^2$ não é um número racional” é a inversa dessa proposição. Sendo equivalente a recíproca, essa afirmação é falsa.

As seguintes denominações, derivadas da noção de implicação, são usuais:

Definição 1.6

Uma proposição $p$ é dita condição suficiente para uma proposição $q$, se $p \mathop{\mathit{implica}}q$. Uma proposição $p$ é uma condição necessária para uma proposição $q$, se $q \mathop{\mathit{implica}}p$.

Exemplo 1.12 (Exemplos)

Para um número natural, ser par é condição necessária para ser divisível por $4$, mas não suficiente.
Para um número real, ser maior que $2$ é condição suficiente para ser maior que $1$, mas não necessária.
Para um número real, ser distinto de $0$ é condição necessária e suficiente para possuir inverso.

Finalmente, o conectivo $p \Leftrightarrow q$ é chamado de bicondicional ou bi-implicação. A expressão $p \Leftrightarrow q$ é lida como “$p$ se e somente se $q$”. A expressão é equivalente a $(p \Rightarrow q) \mathop{\mathit{e}}(q \Rightarrow p)$. Nesse caso dizemos ainda que $p$ é uma condição necessária e suficiente para $q$.

Exercício 1.9

Ache a contrapositiva, a recíproca e a inversa das seguintes implicações:
$\mathop{\mathit{não}}p \Rightarrow q$.
$p \Rightarrow \mathop{\mathit{não}}q$.
Se chove, então eu não vou trabalhar.
Se $x$ é par, então $2x+1$ é ímpar.
Se $x^2+y^2=0$, então $x=y=0$.

Ver solução

a Contrapositiva: $\mathop{\mathit{não}}q \Rightarrow p$. Recíproca: $q \Rightarrow \mathop{\mathit{não}}p$. Inversa: $p \Rightarrow \mathop{\mathit{não}}q$. b Contrapositiva: $q \Rightarrow \mathop{\mathit{não}}p$. Recíproca: $\mathop{\mathit{não}}q \Rightarrow p$. Inversa: $\mathop{\mathit{não}}p \Rightarrow q$. c Contrapositiva: “Se vou trabalhar, então não chove”. Recíproca: “Se não vou trabalhar, então chove”. Inversa: “Se não chove, então vou trabalhar”. d Contrapositiva: “Se $2x+1$ é par, então $x$ é ímpar”. Recíproca: “Se $2x+1$ é ímpar, então $x$ é par”. Inversa: “Se $x$ é ímpar, então $2x+1$ é par”. e Contrapositiva: “Se $x\neq 0$ ou $y\neq 0$, então $x^2+y^2\neq 0$”. Recíproca: “Se $x=y=0$, então $x^2+y^2=0$”. Inversa: “Se $x^2+y^2\neq 0$, então $x\neq 0$ ou $y\neq 0$”.

Exercício 1.10

Atribua um valor verdade às seguintes proposições:
Se $2$ é par, então $3$ é ímpar.
Se $2$ é par, então $4$ é ímpar.
Se $3$ não é par, então $3$ não é ímpar.

Ver solução

a $\textsf{verdadeiro}$ b $\textsf{falso}$ c $\textsf{falso}$

Exercício 1.11

Para os pares de proposições $p$ e $q$, diga se $p$ é condição necessária, suficiente ou ambas para $q$.
$p=$ “$n\gt 2$”, $q=$ “$n\gt 3$”, com $n\in \mathbb {N}$.
$p=$ “$x\gt 2$”, $q=$ “$x\geq 2$”, com $x\in \mathbb {R}$.
$p=$ “$0\lt n\lt 2$”, $q=$ “$n=1$”, com $n\in \mathbb {N}$.
$p=$ “$\Delta $ é isósceles”, $q=$ “$\Delta $ é equilátero”.

Ver solução

a Condição necessária, mas não suficiente. b Condição suficiente, mas não necessária. c Condição necessária e suficiente. d Condição necessária, mas não suficiente.

Exercício 1.12

Determine:
A contrapositiva da contrapositiva de $p\mathop{\mathit{implica}}q$.
A contrapositiva da recíproca de $p\mathop{\mathit{implica}}q$.
A recíproca de $p\mathop{\mathit{implica}}\mathop{\mathit{não}}q$.

Ver solução

a $p\mathop{\mathit{implica}}q$. b $\mathop{\mathit{não}}p\mathop{\mathit{implica}}\mathop{\mathit{não}}q$ (a inversa de $p\mathop{\mathit{implica}}q$). c $\mathop{\mathit{não}}q\mathop{\mathit{implica}}p$.

Exercício 1.13

Negue a proposição $p \Leftrightarrow q$.

Ver solução

$\mathop{\mathit{não}}(p\Leftrightarrow q)$ equivale a $(p\mathop{\mathit{e}}\mathop{\mathit{não}}q)\mathop{\mathit{ou}}(q\mathop{\mathit{e}}\mathop{\mathit{não}}p)$, pois $p\Leftrightarrow q$ equivale a $(p\mathop{\mathit{implica}}q)\mathop{\mathit{e}}(q\mathop{\mathit{implica}}p)$ e a negação de cada implicação é $p\mathop{\mathit{e}}\mathop{\mathit{não}}q$, $q\mathop{\mathit{e}}\mathop{\mathit{não}}p$. Equivale também a $p\Leftrightarrow \mathop{\mathit{não}}q$.

1.1.4 Múltiplos Quantificadores

Diversas proposições matemáticas envolvem mais que um quantificador. Ao lidarmos com proposições com mais de um quantificador devemos tomar alguns cuidados extras, que exporemos nessa seção. Comecemos com alguns exemplos de proposições matemáticas com múltiplos quantificadores.

Exemplo 1.13 (Exemplos)

Para todo número inteiro par $n$, existe um inteiro $k$ tal que $n=2k$. Essa proposição pode ser escrita simbolicamente como:

\[ \forall n \in \mathbb {Z}\text{ com $n$ par}, \exists k \in \mathbb {Z}\, \mid \, n=2k \]
Para todo número real $x$, e para todo número real $y$, $x+y=y+x$. Essa proposição pode ser escrita simbolicamente como:

\[ \forall x \in \mathbb {R}, \forall y \in \mathbb {R}, x+y=y+x \]
Para todo número real $x\neq 0$, existe um número real $x'$ tal que $x\cdot x' =1$. Essa proposição pode ser escrita simbolicamente como:

\[ \forall x \in \mathbb {R}, \text{com } x \neq 0, \exists x' \in \mathbb {R}\, \mid \, x\cdot x' =1 \]

Um fato a ser observado, é que quando temos dois quantificadores diferentes (um universal e um existencial), a ordem dos quantificadores é importante. Assim por exemplo a proposição

\[ \forall x \in \mathbb {R}, \exists y \in \mathbb {R}\, \mid \, y = x^2 \]

que pode ser reescrita como “para todo $x\in \mathbb {R}$ existe $y \in \mathbb {R}$ tal que $y=x^2$” afirma que para todo número real existe o quadrado desse número, e assim essa é uma proposição verdadeira. Porém se trocarmos a ordem dos quantificadores temos a proposição:

\[ \exists y \in \mathbb {R}\, \mid \, \forall x \in \mathbb {R}, y = x^2 \]

que pode ser reescrita como existe um número real $y$ tal que para todo número real $x$, $y=x^2$, ou seja essa proposição afirma que existe um número real que é o quadrado de qualquer número real ¹ . E desta forma essa proposição é falsa.

Para quantificadores do mesmo tipo (dois existenciais, dois universais, etc.) a ordem dos quantificadores não importa, ou seja, a proposição $\exists x \in S \, \mid \, \exists y \in T p(x,y) $ é equivalente a proposição $\exists y \in T \, \mid \, \exists x \in S p(x,y) $, e a proposição $\forall x \in S, \forall y \in T, p(x,y) $ é equivalente a proposição $ \forall y \in T , \forall x \in S, p(x,y) $.

A negação de proposições com mais de um quantificador pode ser feita utilizando cuidadosamente as regras de negação para quantificadores. Assim por exemplo:

Exemplo 1.14

Usando a negação do quantificador universal, temos que a negação da proposição

\[ \forall y \in T, \exists x \in S \, \mid \, p(x,y) \qquad \text{é :} \]

\[ \exists y \in T \, \mid \, \mathop{\mathit{não}}( \exists x \in S \, \mid \, p(x,y)) \]

Usando a negação do quantificador existencial temos:

\[ \exists y \in T \, \mid \, \forall x \in S, \mathop{\mathit{não}}p(x,y)). \]

Uma forma útil de ler quantificadores sucessivos é respeitar sua ordem. Na afirmação

\[ \forall x\in \mathbb {R},\ \exists y\in \mathbb {R}\, \mid \, x+y=0, \]

o valor de $y$ pode depender do valor escolhido para $x$. Se $x=2$, por exemplo, podemos escolher $y=-2$; em geral, para cada $x$, basta tomar $y=-x$.

A ordem não pode ser trocada livremente. A afirmação

\[ \exists y\in \mathbb {R}\, \mid \, \forall x\in \mathbb {R},\ x+y=0 \]

é falsa: ela exigiria um único número $y$ que fosse simultaneamente igual a $-x$ para todo número real $x$.

Exercício 1.14

Transcreva as seguintes proposições para a forma simbólica:
Para todo número inteiro ímpar $n$, existe um número inteiro $k$ tal que $n=2k+1$.
Para todo $y \in B$ existe um $x \in A$ tal que $f(x)=y$.
Para todo número real $x$ existe $y$ tal que $x+y=0$.
Para todo $\epsilon \gt 0$, existe $N_0 \in \mathbb {N}$ tal que para todo $n\gt N_0$, $\left\lvert a_n-L\right\rvert \leq \epsilon $

Ver solução

a $\forall n\in \mathbb {Z},\ (n \text{ é ímpar} \Rightarrow \exists k\in \mathbb {Z}\, \mid \, n=2k+1)$ b $\forall y\in B,\ \exists x\in A \, \mid \, f(x)=y$ c $\forall x\in \mathbb {R},\ \exists y\in \mathbb {R}\, \mid \, x+y=0$ d $\forall \epsilon \gt 0,\ \exists N_0\in \mathbb {N}\, \mid \, \forall n\in \mathbb {N},\ (n\gt N_0\Rightarrow \left\lvert a_n-L\right\rvert \leq \epsilon )$

Exercício 1.15

Seja a proposição $p(x,y)=$“$x+4\gt y$” com $x,y \in D=\{ 1,2,3,4,5,6\} $. Para as seguintes proposições, reescreva-as em português e atribua um valor verdade
$\forall x \in D, \exists y \in D \, \mid \, p(x,y) $
$\exists y \in D \, \mid \, \forall x \in D, p(x,y) $
$\forall x \in D, \forall y \in D, p(x,y) $
$\exists x \in D, \exists y \in D \, \mid \, p(x,y) $

Ver solução

a Para todo $x\in D$ existe $y\in D$ tal que $x+4\gt y$. $\textsf{verdadeiro}$: basta tomar $y=1$. b Existe $y\in D$ tal que, para todo $x\in D$, $x+4\gt y$. $\textsf{verdadeiro}$: $y=1$ serve, pois $x+4\geq 5\gt 1$. c Para todos $x,y\in D$, $x+4\gt y$. $\textsf{falso}$: com $x=1$ e $y=6$, $5\gt 6$ é falso. d Existem $x,y\in D$ tais que $x+4\gt y$. $\textsf{verdadeiro}$: por exemplo $x=y=1$.

Exercício 1.16

O que as seguintes afirmações significam? Identifique a ordem dos quantificadores, determine se são verdadeiras e dê exemplos ou contraexemplos quando possível. O universo de discurso em todos os casos é o conjunto dos números naturais.
$\forall x, \exists y \, \mid \, (x\lt y)$
$\exists y \, \mid \, \forall x, (x\lt y)$
$\exists x \, \mid \, \forall y, (x\lt y)$
$\forall y, \exists x \, \mid \, (x\lt y)$
$\exists x \, \mid \, \exists y \, \mid \, (x\lt y)$
$\forall x, \forall y, (x\lt y)$

Ver solução

a Para todo número natural $x$ existe um natural $y$ tal que $x\lt y$. A afirmação é verdadeira: por exemplo, para cada $x$ podemos tomar $y=x+1$. Um contraexemplo teria de ser um natural $x$ para o qual não existisse natural maior. b Existe um natural $y$ tal que todo natural $x$ satisfaz $x\lt y$. A afirmação é falsa, pois, escolhido qualquer $y$, o número $y+1$ não é menor que $y$. c Existe um natural $x$ menor que todos os naturais $y$. Falsa: qualquer que seja $x$, tomando $y=x$ tem-se $x\lt x$, que é falso. d Para todo natural $y$ existe um natural $x$ menor que $y$. Falsa: para $y=0$ não existe natural $x\lt 0$. (Para $y\geq 1$ basta $x=y-1$.) e Existem naturais $x$ e $y$ com $x\lt y$. Verdadeira: $x=1$, $y=2$. f Todo natural é menor que todo natural. Falsa: com $x=y=1$, $1\lt 1$ é falso.

Exercício 1.17

Reescreva as seguintes definições matemáticas simbolicamente:
Comutatividade: A soma de $x$ com $y$ é igual a soma de $y$ com $x$.
Não-comutatividade: Existem $x$ e $y$ tal que a soma de $x$ com $y$ é diferente da soma de $y$ com $x$.
Identidade: Existe um elemento $e$ tal que a soma de $x$ com $e$ é $x$.
Transitividade: Se $x$ é menor igual que $y$ e $y$ é menor igual que $z$ então $x$ é menor igual que $z$.
Reflexividade: Para todo $x$, $x$ é menor igual a $x$

Ver solução

a $\forall x, \forall y, x+y=y+x$. b $\exists x, \exists y \, \mid \, x+y\neq y+x$. c $\exists e \, \mid \, \forall x, x+e=x$. d $\forall x, \forall y, \forall z,\ (x\leq y \mathop{\mathit{e}}y\leq z \Rightarrow x\leq z)$. e $\forall x,\ x\leq x$.

Exercício 1.18

O que as seguintes afirmações significam? Elas são verdadeiras? Dê exemplos e contraexemplos quando possível. O universo de discurso em todos os casos é os números naturais.
$\forall x, \exists y \, \mid \, (2x-y=0)$
$\exists y \, \mid \, \forall x, (2x-y=0)$
$\exists y \, \mid \, \exists z \, \mid \, (y+z=100)$

Ver solução

a Para todo natural $x$ existe um natural $y$ com $2x=y$. Verdadeira: dado $x$, tome $y=2x$. b Existe $y$ tal que para todo $x$, $2x-y=0$. Falsa, pois se $x=0$ então $y=0$, e se $x=1$ então $y=2$. c A afirmação nos diz que existem dois números cuja soma é $100$. Verdadeira pois $15+85=100$.

Exercício 1.19

Para as seguintes proposições, escreva a negação, em português e simbólica, de cada uma delas.
Para todo número real $x$, para todo número real $y$, $x+y=0$.
Para todo número real $x$, existe um número real $y$ tal que $x+y=0$.
Para todo $\epsilon \gt 0$, existe $N_0 \in \mathbb {N}$ tal que para todo $n\gt N_0$, $\left\lvert a_n-L\right\rvert \leq \epsilon $

Ver solução

a Existem reais $x$ e $y$ tais que $x+y\neq 0$. Simbolicamente: $\exists x\in \mathbb {R},\ \exists y\in \mathbb {R}\, \mid \, x+y\neq 0$. b Existe um real $x$ tal que, para todo real $y$, $x+y\neq 0$. Simbolicamente: $\exists x\in \mathbb {R}\, \mid \, \forall y\in \mathbb {R},\ x+y\neq 0$. c Existe $\epsilon \gt 0$ tal que, para todo $N_0\in \mathbb {N}$, existe $n\gt N_0$ com $\left\lvert a_n-L\right\rvert \gt \epsilon $. Simbolicamente: $\exists \epsilon \gt 0 \, \mid \, \forall N_0\in \mathbb {N},\ \exists n\gt N_0 \, \mid \, \left\lvert a_n-L\right\rvert \gt \epsilon $.

Exercício 1.20

Exemplos e ou Contraexemplos
Para todos números naturais pares $m,n$, temos que $n+m$ é par.

Ver solução

A afirmação é verdadeira, logo não há contraexemplos. Se $m=2a$ e $n=2b$ com $a,b$ naturais, então $m+n=2(a+b)$ é par. Exemplo: $2+4=6$.

1.2 Demonstrações

1.2.1 Por que Demonstrar?

“A lógica é a higiene que o matemático pratica para manter as suas ideias saudáveis e fortes. “
Hermann Weyl

Nas seções anteriores aprendemos a reconhecer a estrutura de afirmações matemáticas. Agora surge uma diferença fundamental entre observar que uma afirmação parece verdadeira e demonstrar que ela é verdadeira.

Considere a afirmação

\[ n^2+n+41 \text{ é primo para todo } n\in \mathbb {N}. \]

Calculando os primeiros valores, encontramos números primos para $n=0,1,2,\dots ,39$. Quarenta verificações consecutivas fornecem uma evidência impressionante. Mesmo assim, a afirmação é falsa: para $n=40$,

\[ 40^2+40+41=41^2, \]

que não é primo.

Esse exemplo mostra uma das razões centrais para demonstrar. Uma afirmação universal fala de todos os elementos de um domínio, muitas vezes infinito. Verificar casos particulares, mesmo muitos deles, não percorre esse domínio inteiro. Os exemplos ajudam a descobrir padrões e a testar conjecturas; os contraexemplos podem destruí-las. Mas, para estabelecer uma afirmação universal, precisamos de um argumento que explique por que ela vale para um elemento arbitrário.

Uma demonstração é justamente esse tipo de argumento: uma sequência de passos em que cada conclusão decorre das hipóteses, das definições ou de fatos já estabelecidos. Ela não substitui a intuição nem a experimentação. Ao contrário, frequentemente nasce delas. Sua função é transformar uma boa razão para acreditar em uma afirmação em uma justificativa matemática que não dependa da quantidade de casos observados.

Essa passagem — de exemplos para argumentos gerais — é uma das mudanças centrais da matemática escolar para a matemática universitária. Nos exemplos seguintes, veremos algumas formas básicas de construir tais argumentos.

1.2.2 Métodos de Demonstração

Rigor é para o matemático o que a moral é para os homens.
André Weil

Começaremos com demonstrações envolvendo propriedades elementares dos números inteiros e racionais. Para acompanhar os exemplos, precisaremos apenas recordar algumas definições simples:

Dizemos que um inteiro não nulo $a$ divide um inteiro $b$ se existe $k\in \mathbb {Z}$ tal que $b=ak$.
Um inteiro é par se pode ser escrito na forma $2k$, com $k\in \mathbb {Z}$; é ímpar se pode ser escrito na forma $2k+1$.
Um número real $r$ é racional se existem $p,q\in \mathbb {Z}$, com $q\neq 0$, tais que $r=\frac{p}{q}$.
Um número real é irracional se não é racional.

Essas definições serão usadas imediatamente nos argumentos que seguem. A ideia não é memorizá-las isoladamente, mas observar como uma demonstração começa muitas vezes traduzindo uma hipótese para a linguagem precisa de sua definição.

Demonstração Direta

A demonstração direta é a forma mais simples de demonstração que nós tratamos nesta seção, e é a mais óbvia: para demonstrar que $p \Rightarrow q$ suponha que $p$ é verdadeiro, e através de uma série de etapas, cada uma seguinte das anteriores, conclui-se $q$.

Exemplo 1.15

Se $n,m$ são números pares então $n+m$ também é um número par.

Um bom modo de iniciar uma demonstração é identificando as hipóteses e a tese e esclarecendo os seus significados, e o significado dos termos envolvidos:

Hipótese 1: $n$ é par. Por definição de número par, temos que existe um inteiro $k_1$ tal que $n=2k_1$.

Hipótese 2: $m$ é par. De modo análogo, temos pela definição de número par que existe (possivelmente outro) inteiro $k_2$ tal que $m=2k_2$.

Tese: Queremos provar que $n+m$ é par, ou seja, que existe um inteiro $k_3$ tal que $n+m = 2k_3$.

Feito isso vamos a demonstração:

Demonstração ▼

Como $n,m$ são pares existem inteiros $k_1,k_2$ tais que $n=2k_1$ e $m=2k_2$. Desta forma temos que $n+m=2k_1+2k_2$, e colocando em evidência o $2$ teremos:

\[ n+m=2(k_1+k_2) =2k_3 \]

onde $k_3=k_1+k_2$ é um número inteiro. E assim $n+m$ é um número par.

Exemplo 1.16

Se $a$ divide $b$ e $b$ divide $c$, então $a$ divide $c$.

Novamente começaremos identificando as hipóteses e a tese e esclarecendo os seus significados:

Hipótese 1: $a$ divide $b$. Isso significa que existe um número inteiro $k_1$ tal que $b=ak_1$.

Hipótese 2: $b$ divide $c$. Isso significa que existe um número inteiro $k_2$ tal que $c=bk_2$.

Tese: Queremos provar que $a$ divide $c$, ou seja, queremos mostrar que existe um número inteiro $k_3$ tal que $c=ak_3$

Demonstração ▼

Pelas hipóteses temos que existem inteiros $k_1, k_2$ tais que $b=a.k_1$ e $c=b.k_2$.

Substituindo a primeira expressão na segunda teremos:

\[ c=bk_2 = (ak_1)k_2=a (k_1k_2)=ak_3 \]

onde $k_3=k_1k_2$ é um número inteiro. O que prova que $a$ divide $c$.

Exemplo 1.17

Se $n$ é um número ímpar então $n^2$ é um número ímpar.

Hipótese: $n$ é um número ímpar, i.e, $\exists k_1 \in \mathbb {Z}$ tal que $n=2k_1+1$

Tese: $n^2$ é um número ímpar, i.e, $\exists k_2 \in \mathbb {Z}$ tal que $n^2=2k_2+1$

Demonstração ▼

Como $n$ é um número ímpar, existe um inteiro $k_1$ tal que $n=2k_1+1$ e assim:

\[ n^2 = (2k_1+1)^2 = 4k_1^2 + 4k_1 + 1 \Rightarrow n^2 = 2(2k_1^2 + 2k_1) + 1 \]

Como $2k_1^2 + 2k_1$ é um número inteiro, temos pela definição que $n^2$ é ímpar.

Exercício 1.21

Demonstre as seguintes afirmações:
Se $a$ divide $b$ e $a$ divide $c$ então $a$ divide $b + c$.
Se $p,q$ são números racionais, então $p+q$ é um número racional.
Se $p,q$ são números racionais, então $p\cdot q$ é um número racional.
Se $r_1$ e $r_2$ são raízes distintas de $p(x) = x^2 + b x + c$, então $r_1 + r_2 = - b$ e $r_1 r_2 = c$.

Ver solução

a Se $b=ak$ e $c=al$ com $k,l$ inteiros, então $b+c=a(k+l)$. b Sejam $p=\frac{a}{b}$ e $q=\frac{c}{d}$, com $a,b,c,d$ inteiros e $b,d\neq 0$. Então $p+q=\frac{(ad+bc)}{bd}$, com $ad+bc$ e $bd\neq 0$ inteiros. c Com a mesma notação, $p\cdot q=\frac{ac}{bd}$, e $bd\neq 0$. d Como $r_1,r_2$ são raízes, $r_1^2+br_1+c=0$ e $r_2^2+br_2+c=0$. Subtraindo, $(r_1-r_2)(r_1+r_2)+b(r_1-r_2)=0$; como $r_1\neq r_2$, dividindo por $r_1-r_2$ obtemos $r_1+r_2=-b$. Da primeira equação, $c=-r_1^2-br_1=-r_1^2+(r_1+r_2)r_1=r_1r_2$.

Demonstração por Redução ao Absurdo

Uma demonstração por redução ao absurdo (também conhecida como demonstração por contradição ou ainda por reductio ad absurdum) é uma técnica de demonstração no qual se demonstra que se algum enunciado fosse verdadeiro, ocorreria uma contradição lógica, e portanto o enunciado deve ser falso.

Exemplo 1.18

Existem infinitos números primos.

Demonstração ▼

Suponha, por absurdo, que existam apenas finitos números primos, que denotaremos por $p_1,p_2,\dots ,p_n$. Considere

\[ q=p_1p_2\cdots p_n+1. \]

Como $q\gt 1$, ele possui algum divisor primo, digamos $r$. Esse primo $r$ não pode ser nenhum dos primos $p_1,\dots ,p_n$: se $p_i$ dividisse $q$, como também divide o produto $p_1p_2\cdots p_n$, então dividiria a diferença

\[ q-p_1p_2\cdots p_n=1, \]

o que é impossível. Portanto existe um primo $r$ que não está na lista $p_1,\dots ,p_n$, contradizendo a hipótese de que havíamos listado todos os primos. Logo existem infinitos números primos.

Exemplo 1.19

$\sqrt{2}$ é irracional.

Demonstração ▼

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=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:

\begin{equation} a^2=2b^2 \label{raiz21} \tag{1.1} \end{equation}

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 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$:

\begin{equation} a=2k \label{raiz22} \tag{1.2} \end{equation}

Substituindo 1.2 em 1.1 temos:

\begin{equation} (2k)^2=2b^2 \Rightarrow 4k^2=2b^2 \Rightarrow 2k^2=b^2 \tag{1.3} \end{equation}

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.

Exemplo 1.20

Não existem soluções inteiras positivas para a equação $x^2 - y^2 = 1$.

Demonstração ▼

Vamos realizar a demonstração por redução ao absurdo. Desta forma, vamos supor que existe uma solução $(a, b)$ com $a $ e $b$ inteiros positivos, satisfazendo $a^2-b^2=1$. Então fatorando temos:

\[ a^2-b^2=(a-b)(a+b) = 1. \]

Como $a+b$ e $a-b$ são inteiros cujo produto é $1$, temos que ou $a+b=a-b=1$ ou $a+b=a-b=-1$. No primeiro caso, podemos adicionar as duas equações para obter $a = 1$ e $b = 0$, contradizendo o nosso pressuposto inicial de que $a$ e $b$ são positivos. No segundo caso de modo semelhante, obtemos que $a = -1$ e $b = 0$, novamente contrariando a nossa hipótese. Logo por redução ao absurdo, temos que não existem soluções inteiras positivas para a equação $x^2 - y^2 = 1$.

Exercício 1.22

Use o método de redução ao absurdo para provar cada um das seguintes proposições.
$\sqrt[3]{2}$ é irracional.
Não existem soluções inteiras positivas para a equação $x^2 - y^2 = 10.$

Não existem soluções racionais para a equação $x^5 + x^4 + x^3 + x^2 + 1 = 0.$

Dados $a,b,c$ números inteiros. Mostre que se $a$ não divide $bc$, então $a$ não divide $b$.

Ver solução

Dica: use a mesma estratégia que foi usada para provar que $\sqrt{2}$ é irracional.

Ver solução

Dica: fatore $x^2-y^2=(x-y)(x+y)$ e note que $x-y$ e $x+y$ têm a mesma paridade (a diferença entre eles é $2y$). Se ambos são ímpares, o produto é ímpar; se ambos são pares, o produto é múltiplo de $4$. Em nenhum caso o produto pode ser $10$.

Ver solução

Dica: Por redução ao absurdo, suponha que existe um racional $\frac{p}{q}$ (podemos assumir que $p$ e $q$ são coprimos, ou seja, que a fração é irredutível, e $q\gt 0$) que satisfaz a equação. Multiplicando por $q^5$ obtemos $p^5+p^4q+p^3q^2+p^2q^3+q^5=0$. Todos os termos, exceto $q^5$, são divisíveis por $p$; logo $p$ divide $q^5$ e, sendo $p$ e $q$ coprimos, $p=\pm 1$. Analogamente, todos os termos exceto $p^5$ são divisíveis por $q$, logo $q$ divide $p^5$ e $q=1$. Assim $x=\pm 1$, mas nenhum dos dois é raiz da equação.

Ver solução

Suponha, por absurdo, que $a$ não divide $bc$ mas $a$ divide $b$. Então $b=ak$ para algum inteiro $k$, e $bc=a(kc)$, ou seja, $a$ divide $bc$: contradição.

Demonstração por Contraposição

O método de demonstração por contraposição baseia-se no fato que uma implicação $p\mathop{\mathit{implica}}q$ é equivalente a sua contrapositiva $\mathop{\mathit{não}}q \mathop{\mathit{implica}}\mathop{\mathit{não}}p$. Assim, no método de demonstração por contraposição ao invés de se demonstrar a implicação $p \mathop{\mathit{implica}}q$, demonstra-se que $\mathop{\mathit{não}}q \mathop{\mathit{implica}}\mathop{\mathit{não}}p$. Vejamos alguns exemplos.

Exemplo 1.21

Se $n$ e $m$ são números inteiros para os quais $n + m$ é par, então $n$ e $m$ tem a mesma paridade.

Vamos provar essa proposição usando o método de demonstração por contraposição. Observe que a versão contrapositiva deste teorema é: "Se $n$ e $m$ são dois números inteiros com paridades opostas, então sua soma $n+m$ deve ser ímpar".

Para a versão contrapositiva temos:

Hipótese: “$n$ e $m$ são dois números inteiros com paridades opostas”,
Tese “soma $n+m$ deve ser ímpar”

Demonstração ▼

Faremos a demonstração por contraposição. Desta forma supomos que $n$ e $m$ tem paridades opostas, ou seja, um deles é par e o outro ímpar, e assim não há perda de generalidade em supor que $n$ é par e $m$ é ímpar. Logo, existem inteiros $k_1$ e $k_1$ tais que $n = 2k_1$ e $m = 2k_2 +1$. Calculando a soma

\[ n + m = 2k_1 + 2k_2 + 1 = 2 (k_1 + k_2) + 1 \]

e observando que $k_1+k_2$ é um número inteiro, temos que $n+m$ é um inteiro ímpar, por definição.

Qual a diferença entre uma demonstração por contraposição de uma demonstração por redução ao absurdo?

Vamos analisar como os dois métodos de trabalho ao tentar provar "Se $p$, então $q$".

Método de redução ao absurdo: assuma $p$ e $\mathop{\mathit{não}}q$ e então devemos provar que estas duas hipóteses levam a algum tipo de contradição lógica.
Método de contraposição: assuma $\mathop{\mathit{não}}q$ e então devemos provar $\mathop{\mathit{não}}p$.

O método de contraposição tem a vantagem de que seu objetivo é claro, temos que demonstrar $\mathop{\mathit{não}}p$. Por outro lado, no método da contradição, o objetivo é demonstrar uma contradição lógica, porém nem sempre é claro qual é a contradição que vamos encontrar.

Exemplo 1.22

Se $n^2$ é ímpar, então $n$ é ímpar

Demonstração ▼

Nesse caso a contrapositiva é: “se $n$ é par então $n^2$ é par”

Assim por contraposição. Suponha então que $n$ é par, logo existe um número inteiro $k$ tal que $n = 2k$, e assim:

\[ n2 = (2k)^2 = 4k^2 = 2(2k^2) \]

Como $2k^2$ é um inteiro, $n^2$ é par.

Exercício 1.23

Prove cada uma das seguintes proposições pelo método de contraposição.
Se $x$ e $y$ são dois números inteiros cujo produto é par, então pelo menos um dos dois deve ser par.
Se $x$ e $y$ são dois números inteiros cujo produto é ímpar, então ambos têm de ser ímpares.
Se $a$ e $b$ são números reais tais que o produto $ab$ é um número irracional, então ou $a$ ou $b$ deve ser um número irracional.

Ver solução

a Contrapositiva: se $x$ e $y$ são ambos ímpares, então $xy$ é ímpar. De fato, $x=2m+1$ e $y=2n+1$ dão $xy=2(2mn+m+n)+1$. b Contrapositiva: se $x$ ou $y$ é par, então $xy$ é par. Se, por exemplo, $x=2m$, então $xy=2(my)$. c Contrapositiva: se $a$ e $b$ são ambos racionais, então $ab$ é racional. Isso segue de $\frac{p}{q}\cdot \frac{r}{s}=\frac{pr}{qs}$, com $q,s\neq 0$.

Exercício 1.24

Mostre que o produto de um número racional não nulo com um número irracional é um número irracional.

Ver solução

Sejam $r\neq 0$ racional e $x$ irracional, e suponha, por absurdo, que $rx$ seja racional. Como $r\neq 0$, $\frac{1}{r}$ é racional e $x=\frac{1}{r}\cdot rx$ seria produto de racionais, logo racional, contradição.

Exercício 1.25

Mostre que se $a$ e $b$ são números racionais, então $a + b$ é um número racional.

Ver solução

Se $a=\frac{p}{q}$ e $b=\frac{r}{s}$, com $p,q,r,s$ inteiros e $q,s\neq 0$, então $a+b=\frac{(ps+qr)}{qs}$, com $ps+qr$ e $qs\neq 0$ inteiros.

Exercício 1.26

Mostre que um número inteiro de 4 dígitos é divisível por 3 se a soma dos seus dígitos for divisível por 3.

Ver solução

Se $N=1000a+100b+10c+d$, então $N=3(333a+33b+3c)+(a+b+c+d)$. Se $3$ divide $a+b+c+d$, então $3$ divide os dois termos da soma e portanto divide $N$.

Demonstrações de “se e somente se”

Muitos teoremas na matemática são apresentados sob a forma "$p$ se, e somente se, $q$". Essa afirmação é equivalente a "se $p$, então $q$ ese $q$, então $p$". Logo, para demonstrar uma afirmação da forma "$p$ se, e somente se, $q$", devemos demonstrar duas implicações separadamente.

Exemplo 1.23

Dois inteiros $a$ e $b$, possuem paridades diferentes se, e somente se, $a + b$ é um número ímpar

Demonstração ▼

Temos que provar duas implicações:

Se $a$ e $b$ possuem paridades diferentes então $a + b$ é um ímpar;
Se $a + b$ é ímpar então $a$ e $b$ possuem paridades diferentes.

Vamos provar a implicação: se $a$ e $b$ possuem paridades diferentes então $a + b$ é ímpar.

Sem perda de generalidade como por hipótese $a$ e $b$ possuem paridades diferentes, podemos assumir que $a$ é par e que $b$ é ímpar. Desta forma existem inteiros $k_1,k_2$ tais que $a=2k_1$ e $b=2k_2+1$, e assim:

\[ a+b=2k_1+2k_2+1= 2(k_1+k_2)+1 \]

e assim $a+b$ é ímpar.

Agora, demonstraremos a implicação: se $a + b$ é ímpar então $a$ e $b$ possuem paridades diferentes. Na verdade provaremos a contrapositiva dessa afirmação: se $a$ e $b$ possuem paridades iguais então $a + b$ é par.

Temos dois casos a considerar ambos $a$ e $b$ pares e ambos $a$ e $b$ ímpares.

Se $a$ e $b$ são ambos pares então existem $k_1,k_2$ tal que $a=2k_1$ e $b=2k_2$ e desta forma

\[ a+b=2(k_1+k2) \]

e assim $a+b$ é par.

Se $a$ e $b$ são ambos ímpares então existem $k_1,k_2$ tal que $a=2k_1+1$ e $b=2k_2+1$ e desta forma

\[ a+b=2k_1+1+2k2+1= 2(k_1+k2+1) \]

e assim $a+b$ é par.

Exercício 1.27

Dado dois inteiros $a$ e $b$, o produto $ab$ é um número par, se e somente se, pelo menos um dos números inteiros, $a$ ou $b$, for par.

Ver solução

Se $a=2k$, então $ab=2(kb)$ é par (analogamente se $b$ é par). Reciprocamente, pela contrapositiva: se $a=2m+1$ e $b=2n+1$, então $ab=2(2mn+m+n)+1$ é ímpar.

Exercício 1.28

Dados $a,b,c$ inteiros com $c\neq 0$. Mostre que $a$ divide $b$ se e somente se $ac$ divide $bc$.

Ver solução

Se $b=ak$, então $bc=(ac)k$, logo $ac$ divide $bc$. Reciprocamente, se $bc=(ac)k$, então $c(b-ak)=0$ e, como $c\neq 0$, $b=ak$.