Consider:

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

(b) \(\Gamma\models\phi\supset \psi\)and:

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

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.

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.

How do you establish that a set of premises

*doesn't*logically entail some result? Show that:- \(Rab \not\models \exists x Rxx\)
- \(Rab \not\models \neg\exists x Rxx\)

Show that:

- \(\exists x\forall y Rxy \models \forall y\exists x Rxy\)

but:

- \(\forall y\exists x Rxy \not\models \exists x\forall y Rxy\)

- \(Rab \not\models \exists x Rxx\)
Show it to be false that:

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

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]\)?

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

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

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