1. Consider:

    (a) \(\Gamma,\phi\models\psi\)
    (b) \(\Gamma\models\phi\supset \psi\)


    (e) \(\phi\mathbin{{=}\!|{\models}}\psi\) (that is, \(\phi\models\psi\) and \(\psi\models\phi\))
    (f) \(\models\phi\subset\supset \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.

  2. 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=\{\, 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=\{\, a_1,a_2,\dots,a_k \,\}\)
    \(C=\{\, 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.

  3. 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\)


    \(\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...)


    \((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.

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

    1. \(Rab \not\models \exists x Rxx\)
    2. \(Rab \not\models \neg\exists x Rxx\)

    Show that:

    1. \(\exists x\forall y Rxy \models \forall y\exists x Rxy\)


    1. \(\forall y\exists x Rxy \not\models \exists x\forall y Rxy\)
  5. Show it to be false that:

    If \(\models \phi\vee\psi\) then \(\models\phi\) or \(\models\psi\).

  6. If \(\phi\) is the formula \(Fx \supset \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]\)?

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

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

  9. Explain the difference between \([\![\, \phi[x\leftarrow a] \,]\!]_{\mathscr{M}\,q}\) and \([\![\, \phi \,]\!]_{\mathscr{M}\,q[x:=a]}\).