Tutorial 7

1

At least one student “attended every lecture”:

$$(\exists x)(\forall y)(S(x)\wedge L(y)\to A(x,y))$$

Every lecture, at least one student attended:

$$(\forall y)(\exists x)(S(x)\wedge L(y)\to A(x,y))$$

2

1. $(\forall x)(\forall y)(B(x)\wedge W(y)\to E(x,y))$
2. $(\forall x)(B(x)\wedge (\exists y)(W(y)\to E(x,y))\wedge (\exists y)(W(y)\to \neg E(x,y)))$
3. $(\forall x)(\forall y)(B(x)\wedge W(y)\to \neg E(y,x))$
4. $(\forall x)(\exists y)(W(y)\to \neg E(x,y))$

3

1. All occurrences of $y$ are unbound, all occurrences of $x$ are bound to $\forall x$.
2. The first $x$ is unbound / free, the second and third occurrences of $x$ are both bound to $\forall x$, the occurrence of $y$ is unbound.
3. All occurrences of $x$ are bound to $\forall x$, all occurrences of $y$ are bound to $\exists y$.

4

1. $(y\ge 0\wedge \forall x(N(x)\to x\ge y))(y/3)$

$$\begin{array}{r}(3\ge 0\wedge \forall x(N(x)\to x\ge 3))\\ \forall x(N(x)\to x\ge 3)\\ \perp \\ \text{consider when }x=0,1,2\end{array}$$

“If $x$ is a natural number, it is greater than or equal to $3$.”

2. $(x\ge 0\wedge \exists y(N(y)\wedge x\ge y))(x/3)$

$$\begin{array}{r}(x\ge 0\wedge \exists y(N(y)\wedge x\ge y))(x/3)\\ (3\ge 0\wedge \exists y(N(y)\wedge 3\ge y))\\ \exists y(N(y)\wedge 3\ge y)\\ \top \end{array}$$

“There exists $y$ that is a natural number and smaller than $3$.”

3. $(\forall x(N(x)\to \exists y(N(y)\wedge x>y)))(x/3)$

$$\begin{array}{r}(\forall x(N(x)\to \exists y(N(y)\wedge x>y)))(x/3)\\ \forall x(N(x)\to \exists y(N(y)\wedge x>y))\\ \perp \\ \text{consider when }x=0\end{array}$$

“For all $x$, if $x$ is a natural number then there exists $y$ where $y$ is a natural number and $x$ is greater than $y$.”

4. $(\forall x(N(x)\to \exists y(N(y)\wedge y>x)))(y/3)$

$$\begin{array}{r}(\forall x(N(x)\to \exists y(N(y)\wedge y>x)))(y/3)\\ \forall x(N(x)\to \exists y(N(y)\wedge y>x))\\ \top \end{array}$$

“For all $x$, if $x$ is a natural number then there exists $y$ where $y$ is a natural number and $y$ is greater than $x$.”