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.