% Homework Exercises due 6 October

61. Consider:

    > \(a) $\Gamma,\phi\models\psi$  
    > \(b) $\Gamma\models\phi\cond\psi$
    
    and:

    > \(e) $\phi\bimodels\psi$ (that is, $\phi\models\psi$ and $\psi\models\phi$)  
    > \(f) $\models\phi\bicond\psi$

    Prove that (a) iff (b); and prove that (e) iff (f). You may find that an earlier homework already gives most of the solution to one of these; if so, you can of course cite your work for that earlier problem without repeating.

62. I passed out a fallacious "proof" which is distributed in many math books (not in earnest). The proof says:

    > Theorem: For any integer $n \ge 1$, all the numbers in a set of $n$ numbers are equal to each other.

    > Inductive proof: It is obviously true that all the numbers in a set consisting of just one number are equal to each other, so the basis step is true. For the inductive step, let $A=\set{a_1,a_2,\dots,a_k,a_{k+1}}$ be any set of $k+1$ numbers. Form two subsets each of size $k$:

    > > $B=\set{a_1,a_2,\dots,a_k}$  
    > > $C=\set{a_1,a_3,\dots,a_{k+1}}$

    > ($B$ consists of all the numbers in $A$ except $a_{k+1}$, and $C$ consists of all the numbers in $A$ except $a_2$.) By inductive hypothesis, all the numbers in $B$ equal $a_1$ and all the numbers in $C$ equal $a_1$ (since both sets have only $k$ members). But every number in $A$ is in $B$ or $C$, so all the numbers in $A$ equal $a_1$; hence all are equal to each other.

    Exercise 62 is to identify and explain the mistake in this proof.

63. I passed out another fallacious "proof" copied from the Epp book. To prove that a composition of onto functons is onto, a student wrote:

    > Suppose $f\colon X\to Y$ and $g\colon Y\to Z$ are both onto. Then

    > > $\forall y\in Y, \exists x\in X$ such that $f(x)=y$

    > and

    > > $\forall z\in Z, \exists y\in Y$ such that $g(y)=z$.

    *(Sorry, that was always supposed to be $g(y)$. JP mistyped it earlier. This "proof" is still flawed. It continues...)*

    > So

    > > $(g\circ f)(x) = g(f(x)) = g(y) = z$

    > and thus $g\circ f$ is onto.

    Exercise 63 is to explain the mistake(s) in this proof.

    There is a deep similarity between what's gone wrong in the previous "proof" and in this one; I will ask for your ideas about this when we meet.


64. How do you establish that a set of premises *doesn't* logically entail some result? Show that:

    > (a) $Rab \not\models \exists x Rxx$  
    > (b) $Rab \not\models \neg\exists x Rxx$  

    Show that:

    > (c) $\exists x\forall y Rxy \models \forall y\exists x Rxy$

    but:

    > (d) $\forall y\exists x Rxy \not\models \exists x\forall y Rxy$  


65. Show it to be false that:

    > If $\models \phi\vee\psi$ then $\models\phi$ or $\models\psi$.

66. If $\phi$ is the formula $Fx \cond \forall y(Gyx \vee P \vee \exists x Hx)$, then (a) What is $\phi[x\leftarrow w]$? (b) What is $\phi[x\leftarrow y]$? (c) What is $\phi[P\leftarrow \forall x Gxy]$?

67. Symbolize in predicate logic using $=$: (a) Andy loves Beverly, but she loves someone else. (b) Alice loves no one other than Beverly.

68. Is $(\phi\cond\psi)\cond(\neg\phi\cond\neg\psi)$ a tautology? Explain. (This question may be less straightforward than you first think.)

69. Explain the difference between $\interp{\phi[x\leftarrow a]}_{\script M\,q}$ and $\interp{\phi}_{\script M\,q[x:=a]}$.