3 Quantificadores

3.1 Predicatos

Um predicato é um sentença com variáveis. Por exemplo \[ P(x):\mbox{$x$ é par} \]
é um predicato com variável $x$. Neste caso, podemos substituir objetos no lugar de $x$. Por exemplo, substituindo $x=2$, obtemos a proposição verdadeira \[ P(2): \mbox{$2$ é par}. \] Se substituimos $x=3$, então obtemos a proposição \[ P(3): \mbox{3 é par} \] que é uma proposição falsa. Se substituimos $x=\pi$, então \[ P(\pi): \mbox{$\pi$ é par} \] não obtemos uma proposição válida, pois o conceito de ser par não faz sentido para o número $\pi$.

Definição 3.1 Sejam $P(x)$ um predicato e $A$ um conjunto. Dizemos que o predicato $P(x)$ é válido para $A$ se $P(a)$ é uma proposição (falsa ou verdadeira) para todo $a\in A$.

Exemplo 3.1 Por exemplo, a predicato ‘$P(x)$: $x$ é par’ é valido para o conjunto $\N$ de números naturais, pois cada natural ou é par ou é impar. Similarmente, o mesmo predicato é válido para o conjunto $\Z$ dos inteiros, mas ele não é válido para o conjunto $\Q$ de racionais, pois a propriedade de ser par não faz sentido para um número racional que não é inteiro.

3.2 Quantificador universal e existencial

Definição 3.2 Sejam $A$ um conjunto e $P(x)$ um predicato válido para $A$. A proposição \[ \forall x\in A: P(x) \] (leia se: ‘para todo $x\in A$, $P(x)$’) é verdadeira se $P(x)$ é uma proposição verdadeira para todo $x\in A$. Caso contrário a proposição $\forall x\in A: P(x)$ é falsa.

A proposição \[ \exists x\in A: P(x) \] (leia se:‘existe $x\in A$ tal que $P(x)$’) é verdadeira se $P(x)$ é verdadeira para algum $x\in A$. Caso contrário a proposição $\exists x\in A: P(x)$ é falsa.

Exemplo 3.2 Seja $A=\{2,3,5,7,11\}$ e seja ‘$P(x)$: $x$ é primo’. Então temos que a proposição $\forall x\in A:P(x)$ é verdadeira. Consequentemente, a proposição $\exists x\in A:P(x)$ é também verdadeira. Por outro lado, se ‘$Q(x)$: $x$ é par’, então $\forall x\in A:Q(x)$ é falsa, mas $\exists x\in A:Q(x)$ é verdadeira. Se ‘$R(x)$: $x$ é negativo’, então $\forall x\in A:R(x)$ e $\exists x\in A:R(x)$ são falsas.

3.3 Negação de proposições com quantificador

Considere a proposição $\forall x\in A: P(x)$. Esta proposição afirma que a proposição $P(x)$ está verdadeira para todo $x\in A$. A negação dessa proposição afirma que isso não é verdade; ou seja, $P(x)$ não é verdadeira para algum $x\in A$. Portanto, \[ \neg(\forall x\in A: P(x))\equiv \exists x\in A:\neg P(x). \]

Exemplo 3.3 Considere $A=\{-1,0,1\}$ e seja ‘$P(x)$: $x>0$’. Temos que a proposição $\forall x\in A: P(x)$ é falsa, pois tomando $x=-1$, $P(x)=P(-1)$ é falsa. Por outro lado \[ \neg (\forall x\in A:P(x))\equiv \exists x\in A:\neg P(x)\equiv \exists x\in A:x\leq 0 \] é verdadeira.

Similarmente, a negação da proposição $\exists x\in A: P(x)$ é $\forall x\in A: \neg P(x)$.

Exemplo 3.4 Considere $A=\{-1,0,1\}$ e seja ‘$P(x)$: $x>0$’. Temos que a proposição $\exists x\in A: P(x)$ é verdadeira, pois tomando $x=1$, $P(x)=P(1)$ é verdadeira. Por outro lado \[ \neg (\exists x\in A:P(x))\equiv \forall x\in A:\neg P(x)\equiv \forall x\in A:x\leq 0 \] é falsa.

3.4 Proposições com várias quantificadores

Na matemática, precisamos estudar frequentemente proposições que têm várias quantificadores. Considere o seguinte exemplo.

Exemplo 3.5 Sejam \[ A=\{2,3,5,7\}\quad \mbox{e}\quad B=\{6,8,9,10,12,14\} \] e considere a proposição \[ \forall x\in A:(\exists y\in B:x\mid y). \] (Lembre que ‘$x\mid y$’ signfica que ‘$y$ é múltiplo de $x$’; ou sejaj, ‘$x$ é divisor de $y$’.) Esta proposição quer dizer que para todo $x\in A$ existe $y\in B$ tal que $x\mid y$. Esta proposição é verdadeira pois cada elemento de $A$ possui um múltiplo em $B$. A negação desta proposição, pode ser escrita na maneira seguite: \[\begin{align*} \neg(\forall x\in A:(\exists y\in B:x\mid y))&\equiv\\ \exists x\in A:\neg (\exists y\in B:x\mid y)&\equiv\\ \exists x\in A:(\forall y\in B:x\nmid y). \end{align*}\]

Considere agora a proposição \[ \exists y\in B:(\forall x\in A:x\mid y). \] Esta proposição quer dizer que existe um elemento $y\in B$ tal que $y$ é múltiplo de todo elemento de $A$. Inspeção dos dois conjuntos mostra que isso não é verdade. A negação desta proposição pode ser determinada com a seguinte conta: \[\begin{align*} \neg(\exists y\in B:(\forall x\in A:x\mid y))&\equiv\\ \forall y\in B:\neg (\forall x\in A:x\mid y)&\equiv\\ \forall y\in B:(\exists x\in A:x\nmid y). \end{align*}\]

Exemplo 3.6 Proposições com vários quantificadores são comuns na área de cálculo. Por exemplo, para uma sequência infinita $a_1,a_2,a_2,\ldots$ de números reais, a definição que $\lim_{n\to \infty}a_n=a$ é escrita na seguinte maneira: \[ \forall \varepsilon\in \R_+:(\exists N\in \N:(\forall n\in\{N,N+1,N+2,\ldots\}:|a-a_n|\leq \varepsilon)). \] Aqui $\R_+$ é o conjunto dos números reais positivos. Esta mesma proposição está frequentamente escrita mais informalmente como \[ \forall \varepsilon>0:(\exists N>1:(\forall n\geq N:|a-a_n|\leq \varepsilon)). \] Geralmente, fica claro do contexto que $\varepsilon$ é um número real, e $N$ e $n$ são números naturais.

A negação (ou seja, a afirmação que $\lim_{n\to \infty}a_n\neq a$) está escrita como \[ \exists\varepsilon\in\R_+:(\forall N\in\N:(\exists n\in\{N,N+1,N+2,\ldots\}:|a-a_n|>\varepsilon)). \] Mais informalmente, a negação está escrita como \[ \exists\varepsilon>0:(\forall N>1:(\exists n\geq N:|a-a_n|>\varepsilon)). \]