1. Considere a sentença \varphi=\forall \mathbf{x} \exists \mathbf{y} \exists \mathbf{z}(\mathbf{P}(\mathbf{x}, \mathbf{y}) \wedge \mathbf{P}(\mathbf{z}, \mathbf{y}) \wedge(\mathbf{P}(\mathbf{x}, \mathbf{z}) \rightarrow \mathbf{P}(\mathbf{z}, \mathbf{x}))).
Qual dos seguintes modelos satisfaz \varphi ?
a) O modelo M consiste no conjunto dos números naturais com P definido como \{(\mathrm{m}, \mathrm{n}), \mathrm{m}<\mathrm{n}\}.
b) O modelo M’ consiste no conjunto dos números naturais com P definido como \{(\mathrm{m}, 2 \mathrm{~m}), \mathrm{m} é um número natural}.
a) O modelo \mathrm{M}^{\prime \prime} consiste no conjunto dos inteiros com P definido como \{(\mathrm{m}, \mathrm{n}), m divide n\}.

Passo 1

O enunciado nos dá a sentença
\varphi = \forall x\,\exists y\,\exists z\bigl(P(x,y)\wedge P(z,y)\wedge (P(x,z)\rightarrow P(z,x))\bigr).
Isso significa: para cada elemento x do domínio, devemos encontrar elementos y e z tais que
  1. P(x,y) seja verdadeiro,
  2. P(z,y) seja verdadeiro,
  3. e satisfaça a implicação P(x,z)\rightarrow P(z,x), ou seja, ou P(x,z) é falso ou P(z,x) é verdadeiro.

Passo 2

Modelo (a): domínio \mathbb{N}, P(m,n) se e somente se m<n.
Dado qualquer x\in\mathbb{N}, escolhemos
y = x+1,\quad z = x.
Então \;P(x,y) é x< x+1, logo verdadeiro, \;P(z,y) é x< x+1, também verdadeiro,
e \;P(x,z) é x<x, que é falso,
logo a implicação P(x,z)\to P(z,x) vale (falso \to qualquer coisa é verdadeiro).
Conclusão: \varphi é satisfeita em (a).

Passo 3

Modelo (b): domínio \mathbb{N}, P(m,n) se e somente se n=2m.
Para cada x, a única forma de P(x,y) é escolher y=2x. Em seguida, P(z,y) obriga y=2z, ou seja, 2x=2z\Rightarrow z=x.
Ficamos com
y=2x,\quad z=x.
Verificamos a implicação: \;P(x,z) é P(x,x), que só ocorre se x=2x, isto é, x=0. Nesse caso P(z,x) também é P(0,0), verdadeiro. Para x\neq0, P(x,z) é falso e a implicação vale trivialmente.
Conclusão: \varphi é satisfeita em (b).

Passo 4

Modelo (c): domínio \mathbb{Z}, P(m,n) se e somente se m divide n.
Para cada x\in\mathbb{Z}, basta escolher
y = x,\quad z = x.
Então P(x,y) é “ x divide x”, verdadeiro, e P(z,y) é “ x divide x”, também verdadeiro.
Quanto à implicação P(x,z)\rightarrow P(z,x), temos P(x,x) e P(x,x) ambos verdadeiros, logo a implicação vale.
Conclusão: \varphi é satisfeita em (c).

Resposta

Todos os três modelos satisfazem \varphi: (a), (b) e (c).

Exercícios relacionados