Back to the class

__Quiz 4__

Consier the sentence $\phi$ given by $\forall x \exists y R(x,y),$ where $R$ is a binary relation.

1. Define a structure $M$ for which $M \vDash \phi$.

*Solution*: Let $M=([0,\infty)|R)$ and interpret $R(x,y)$ as $x=\sqrt{y}$ (note: the symbol "$\sqrt{y}$" typically refers to the "principal", i.e. positive, square root only). Then $M \vDash \phi$ (because my universe has only non-negative real numbers in it!).

2. Define a structure $M$ for which $M \not\vDash \phi$.

*Solution*: Define the structure $M=(\mathbb{R},R)$ and interpret $R(x,y)$ as $x=\sqrt{y}$. Then $M \not\vDash \phi$ because if $x=-1$ then there is no $y \in \mathbb{R}$ for which $-1=\sqrt{y}$.