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

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$$

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.

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$$

but:

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]}$$.