Problem 7
Show \(\not \models \exists x \varphi \wedge \exists x \psi \rightarrow \exists x(\varphi \wedge \psi)\).
Problem 7
Show that \(\mathfrak{A} \models \varphi \Rightarrow \mathfrak{A} \models \psi\) for all \(\mathfrak{A}\), implies \(\models \varphi \Rightarrow \models \psi\), but not vice versa.
Problem 8
Let \(\mathfrak{A}\) be a ring, give a sentence \(\sigma\) such that \(\mathfrak{A} \models \sigma \Leftrightarrow \mathfrak{A}\) is an integral domain (has no divisors of zero).
Problem 9
Show \(\models \forall x(\varphi \rightarrow \psi) \rightarrow(\forall x \varphi \rightarrow \forall x \psi) ; \models(\exists x \varphi \rightarrow \exists x \psi) \rightarrow \exists x(\varphi \rightarrow \psi)\) \(\models \forall x(\varphi \mapsto \psi) \rightarrow(\forall x \varphi \leftrightarrow \forall x \psi) ; \models(\forall x \varphi \rightarrow \exists x \psi) \leftrightarrow \exists x(\varphi \rightarrow \psi) ;\) \(\models(\exists x \varphi \rightarrow \forall x \psi) \rightarrow \forall x(\varphi \rightarrow \psi)\)
Problem 10
Define in the language of arithmetic: (a) \(x\) and \(y\) are relatively prime;
(b) \(x\) is the smallest prime greater than \(y\); (c) \(x\) is the greatest number
with \(2 x
Problem 12
Let \(S\) be a binary predicate symbol. Show \(\models \neg \exists y \forall x(S(y, x) \leftrightarrow \neg S(x, x))\). (Think of " \(y\) shaves \(x\) " and recall Russell's barber's paradox).
Problem 12
Monadic predicate calculus has only unary predicate symbols (no identity). Consider \(\mathfrak{A}=\left\langle A, R_{1}, \ldots, R_{n}\right\rangle\) where all \(R_{i}\) are sets. Define \(a \sim\) \(b:=a \in R_{i} \Leftrightarrow b \in R_{i}\) for all \(i \leq n\). Show that \(\sim\) is an equivalence relation and that \(\sim\) has at most \(2^{n}\) equivalence classes. The equivalence class of \(a\) is denoted by \([a]\). Define \(B=A / \sim\) and \([a] \in S_{i} \Leftrightarrow a \in R_{i}, \mathfrak{B}=\) \(\left\langle B, S_{1}, \ldots, S_{n}\right\rangle .\) Show \(\mathfrak{A l} \models \sigma \Leftrightarrow \mathfrak{B} \models \sigma\) for all \(\sigma\) in the corresponding language. For such \(\sigma\) show \(\models \sigma \Leftrightarrow \mathfrak{A} \models \sigma\) for all \(\mathfrak{A}\) with at most \(2^{n}\) elements. Using this fact, outline a decision procedure for truth in monadic predicate calculus.
Problem 14
Find prenex normal forms for (a) \(\neg((\neg \forall x \varphi(x) \vee \forall x \psi(x)) \wedge(\exists x \sigma(x) \rightarrow \forall x \tau(x)),\), (b) \(\forall x \varphi(x) \leftrightarrow \exists x \psi(x)\), (c) \(\neg(\exists x \varphi(x, y) \wedge \forall y(\psi(y)) \rightarrow \varphi(x, x)) \rightarrow \exists x \forall y \sigma(x, y)))\), (d) \(((\forall x \varphi(x) \rightarrow \exists y \psi(x, y)) \rightarrow \psi(x, x)) \rightarrow \exists x \forall y \sigma(x, y)\).
Problem 14
Let \(\mathfrak{A}=\langle\mathbb{N},<\rangle\) and
\(\mathfrak{B}=\langle\mathbb{N}, \Delta\rangle\), where \(n \Delta m\) iff (i)
\(n
Problem 15
Show \(\models \exists x(\varphi(x) \rightarrow \forall y \varphi(y))\). (It is instructive to think of \(\varphi(x)\) as ' \(x\) drinks').
