# Page 149

Location: Chapter 14, bonus exercises 1, 2 and 3

Note: part (d) of Exercise 1 cannot in fact be proven and has to be removed from the exercise.

## Exercise solutions

Note: in the following, the fact that bird $$x$$ sings is symbolised by $$x\in S$$, with $$S$$ the set of all singing birds.

### Exercise 1

Assuming the first three laws of Professor Byrd, one can proceed as follows:

(a) Either $$x\in S$$, in which case by Law 1 $$Pxx\in S$$, or $$x \notin S$$, so that by Law 2 $$Pxx \in S$$.

(b) Assume $$Py(Pyx) \in S$$: them either $$y\in S$$, in which case by Law 3 $$Pyx\in S$$, or $$y \notin S$$, so that by Law 2 $$Pyx\in S$$.

(c) Starting from the facts that $$Pxy\in S$$ and $$Pyz \in S$$, two cases are possible: (i) $$x\in S$$, so that by Law 3 $$y \in S$$, which together with the second assumption leads by Law 3 to $$z \in S$$ and then by Law 1 to $$Pxz\in S$$; or (ii) $$x\notin S$$, which immediately by Law 2 implies that, again, $$Pxz \in S$$.

(e) Given that $$Px(Pyz)\in S$$, either (a) $$x \in S$$ or (b) $$x \notin S$$. In the first case, by Law 3 one has $$Pyz\in S$$: now, either (a1) $$y\in S$$, in which case by Law 3 again it is $$z \in S$$, hence by Law 1 $$Pxz\in S$$ and subsequently $$Py(Pxz)\in S$$, or (a2) $$y \notin S$$, whereby immediately $$Py(Pxz)\in S$$. In case (b) above, instead, from $$x \notin S$$ one deduces $$Pxz \in S$$ by Law 2, hence directly through Law 1 the conclusion $$Py(Pxz)\in S$$ can be reached.

### Exercise 2

Adopting a notation in which a bird $$x$$ is lively if and only if $$x \in \mathcal{L}$$, the three Laws given are stated as follows:

\begin{align} \mbox{(a)}~& Px(Pxy)\in\mathcal{L} \Rightarrow & Pxy \in \mathcal{L}~,~\forall x,y\;, \\ \mbox{(b)}~& x\in\mathcal{L}, Pxy\in\mathcal{L} \Rightarrow & y \in \mathcal{L} ~,~\forall x,y\;, \\ \mbox{(c)}~& \forall x,\exists y ~/~ & Py(Pyx)\in\mathcal{L} ~\wedge~ P(Pyx)y\in\mathcal{L}\;. \end{align}

To prove that all birds are lively, one considers a generic bird $$x$$. By Law (c), $$\exists y$$ such that (c1) $$Py(Pyx)\in\mathcal{L}$$ and (c2) $$P(Pyx)y\in\mathcal{L}$$. By Law (a), from (c1) one finds that $$Pyx\in\mathcal{L}$$, which together with (c2) imply, by Law (b), that $$y\in\mathcal{L}$$. The latter two statements, in turn, again according to Law (b), lead to $$x \in \mathcal{L}$$.

### Exercise 3

The goal is to prove that Laws (a)-(c) given in the previous Exercise can be derived from Laws 1-4 of Problem 1, under the identification $$\mathcal{L} \equiv S$$, which concludes the reasoning.

To prove Law (a), first recall that if $$Px(Pxy)\in\mathcal{L}$$, then $$Px(Pxy)\in S$$. Then, either $$x\in S$$ or $$s \notin S$$. In the first case, by Law 3 one finds that $$Pxy\in S$$; in the second case, immediately by Law 2 the fact that $$Pxy\in S$$ follows. The statement can be expressed equivalently as $$Pxy\in\mathcal{L}$$.

Law (b) is a simple reformulation of Law 3 and requires no proof.

Law (c) can be proven as follows: first, by Law 4, $$\forall x, \exists y$$ such that $$y\in S \Leftrightarrow Pyx \in S$$. Now two lines of reasoning are needed, one for each of the two statements asserted by Law (c).

It can be that $$y\in S$$ or $$y\notin S$$. In the first case, one has that $$Pyx\in S$$ by Law 4 and then that $$Py(Pyx)\in S$$ by Law 1. In the second case, the first desired statement $$Py(Pyx)\in S$$ follows directly by Law 2; finally, it can be stated as $$Py(Pyx)\in \mathcal{L}$$.

Again, consider the cases $$y\in S$$ and $$y\notin S$$. In the former case, Law 1 yields directly $$P(Pyx)y \in S$$, while in the latter Law 4 gives $$Pyx\notin S$$, hence by Law 2 $$P(Pyx)y \in S$$. Again, the statement $$P(Pyx)y \in \mathcal{L}$$ is equivalent to what has just been proved.