# 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.