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\)
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]}\).