Exercício 16. Nesse exercício assuma que todas as variáveis têm mesmo domínio e vamos omiti-lo.
Teorema 3. Se existe x tal que \mathrm{P}(x) e existe x tal que \mathrm{Q}(x) então existe x tal que \mathrm{P}(x) e \mathrm{Q}(x).
Em símbolos: (\exists x, \mathrm{P}(x)) \wedge(\exists x, \mathrm{Q}(x)) \rightarrow \exists x(\mathrm{P}(x) \wedge \mathrm{Q}(x)).
Demonstração. Considere o seguinte argumento
  1. (\exists x, \mathrm{P}(x)) \mathrm{e}(\exists x, \mathrm{Q}(x)) (premissa)
  2. \exists x, \mathrm{P}(x) (simplificação de 1)
  3. \mathrm{P}\text{(c)} (instanciação existencial de 2)
  4. \exists x, \mathrm{Q}(x) (simplificação de 1)
  5. \mathrm{Q}\text{(c)} (instanciação existencial de 4)
  6. \mathrm{P}\text{(c)} e \mathrm{Q}\text{(c)} (conjunção de 3 e 5)
  7. \exists x,(\mathrm{P}(x) e \mathrm{Q}(x)) \quad (generalização existencial de 7)
    (a) Dê um contraexemplo para a afirmação feita no teorema, isto é, encontre um domínio D e predicados P e Q sobre elementos de D para o qual a sentença não vale.
    (b) Indique o(s) erro(s) na demonstração.

Passo 1

O enunciado afirma o “Teorema”
(\exists x\,P(x))\land(\exists x\,Q(x))\;\longrightarrow\;\exists x\,(P(x)\land Q(x))
e dá uma “demonstração” usando instâncias existenciais sobre a mesma constante c. Precisamos (a) dar um contraexemplo que torne a implicação falsa e (b) apontar o erro no argumento.

Passo 2

Para o contraexemplo, escolha o domínio
D = \{1,2\}
e defina os predicados
P(x)\colon x\text{ é par},\quad Q(x)\colon x\text{ é ímpar}.ééí

Passo 3

Verifique que
\exists x\,P(x)
é verdadeiro (pois P(2) vale) e
\exists x\,Q(x)
é verdadeiro (pois Q(1) vale), mas
\neg\exists x\,(P(x)\land Q(x))
é verdadeiro, porque nenhum elemento de D é ao mesmo tempo par e ímpar. Logo a fórmula inteira é falsa em D.

Passo 4

No “argumento” dado, o erro está em reusar a mesma constante c para instanciar ambas as existências. A regra de instanciação existencial exige um símbolo novo para cada quantificador \exists; não se pode inferir Q\text{(c)} a partir de \exists x\,Q(x) usando o mesmo c já escolhido para P\text{(c)}.

Resposta

(a) Um contraexemplo é D=\{1,2\}, P(x)\colon x é par, Q(x)\colon x é ímpar.
(b) O erro é instanciar as duas existências com a mesma constante c; cada \exists exige um termo novo e independente.

Exercícios relacionados