Ex. 1.16 - O que as seguintes afirmações significam? Elas são universais ou particulares? Elas são verdadeiras? Dê exemplos e contraexemplos quando possível. O universo de discurso em todos os casos é os números naturais.
a) forall x, exists y mid(x<y)
b) exists y mid forall x,(x<y)
c) exists x mid forall y,(x<y)
d) forall y, exists x mid(x<y)
e) exists x|exists y|(x<y)
f) forall x, forall y,(x<y)

Passo 1

O enunciado pede para interpretar seis fórmulas com quantificadores sobre o conjunto dos números naturais, dizer se cada afirmação é de caráter universal (começa com forall) ou particular (começa com exists), avaliar sua veracidade e dar exemplos ou contraexemplos em cada caso. Vamos usar a definição de verdade de fórmulas quantificadas em N e o fato de que N não tem maior nem menor estrito absoluto.

Passo 2

Interpretação de a):
forall x,exists y,(x<y)
– é uma afirmação de caráter universal (começa com forall).
Verificamos se, para cada natural x, existe algum y em N tal que x<y.
Exemplo construtivo: dado x, basta escolher y = x+1, pois sempre x < x+1.
Logo, a afirmação é verdadeira.

Passo 3

Interpretação de b):
exists y,forall x,(x<y)
– é de caráter particular (começa com exists).
Isso diz que existe um natural y maior que todos os x em N, ou seja, um maior elemento em N.
Mas N não tem maior elemento: para qualquer candidato y, tome x = y e então x<y falha ou tome x=y+1 e x<y falha.
Portanto, é falsa.

Passo 4

Interpretação de c):
exists x,forall y,(x<y)
– é particular.
Significa que existe um natural x que seja estritamente menor que todo y em N.
Se existisse, teria que valer x< x, para y=x, o que é impossível.
Logo, não há elemento estritamente menor que todos; é falsa.

Passo 5

Interpretação de d):
forall y,exists x,(x<y)
– é universal.
Diz que todo natural y tem algum predecessor estrito x.
Mas para y=0 (ou para o primeiro elemento de N), não existe x<0.
Então, é falsa.

Passo 6

Interpretação de e):
exists x,exists y,(x<y)
– é particular.
Basta mostrar dois naturais em ordem: por exemplo, x=0 e y=1 satisfazem 0<1.
Logo, é verdadeira.

Passo 7

Interpretação de f):
forall x,forall y,(x<y)
– é universal.
Afirma que qualquer par (x,y) satisfaz x<y, mas basta escolher x=y ou x>y para ver que falha.
Logo, é falsa.

Resposta

a) universal, verdadeira (ex.: para x escolher y=x+1).
b) particular, falsa ( N não tem maior elemento).
c) particular, falsa (nenhum x está estritamente abaixo de si mesmo).
d) universal, falsa (o menor elemento não tem predecessor).
e) particular, verdadeira (ex.: 0<1).
f) universal, falsa (nem sempre x<y para todo par).

Exercícios de Livros Relacionados