Problem 1
Consider the language of partial order. Define predicates for \((a) x\) is the maximum; \((b) x\) is maximal; \((c)\) there is no element between \(x\) and \(y\); (d) \(x\) is an immediate successor (respectively predecessor) of \(y ;(e) z\) is the infimum of \(x\) and \(y\).
Problem 1
Write down the similarity type for the following structures: (i) \(\langle\mathbb{Q},<, 0\rangle\) (ii) \(\langle\mathbb{N},+, \cdot, S, 0,1,2,3,4, \ldots, n, \ldots\rangle\), where \(S(x)=x+1\), (iii) \(\left\langle\mathcal{P}(\mathbb{N}), \subseteq, \cup, \cap,{ }^{c}, \emptyset\right\rangle\), (iv) \(\langle\mathbb{Z} /(5),+,+,-1,0,1,2,3,4)\), (v) \(\langle\\{0,1\\}, \wedge, \vee, \rightarrow, \neg, 0,1\rangle\), where \(\wedge, \vee, \rightarrow, \neg\) operate according to the ordinary truth tables, (vi) \(\langle\mathbb{R}, 1\rangle\), (vii) \(\langle\mathbb{R}\rangle\), (viii) \(\left\langle\mathbb{R}, \mathbb{N},<, T,{ }^{2}, \mid 1,-\right\rangle\), where \(T(a, b, c)\) is the relation \(b\) is between \(a\) and \(c^{\prime}\), is the square function, and || the absolute value.
Problem 1
Show that all propositional tautologies are true in all structures (of the right similarity type).
Problem 2
Show \(\models \forall x(\varphi(x) \leftrightarrow \exists y(x=y \wedge \varphi(y)))\) and \(\vDash \forall x(\varphi(x) \leftrightarrow \forall y(x=y \rightarrow \varphi(y)))\), where \(y\) does not occur in \(\varphi(x)\)
Problem 3
Show that \(\models \varphi(t) \leftrightarrow \forall x(x=t \rightarrow \varphi(x))\) if \(x \notin F V(t)\).
Problem 3
Let \(\mathfrak{A}_{1}=(\mathbb{N}, \leq)\) and \(\mathfrak{A}_{2}=\langle\mathbb{Z}, \leq\rangle\) be the ordered sets of natural, respectively integer, numbers. Give a sentence \(\sigma\) such that \(\mathfrak{A l}_{1} \models \sigma\) and \(\mathfrak{A}_{2} \models \neg \sigma\). Do the same for \(\mathfrak{A}_{2}\) and \(\mathfrak{B}=\langle\mathbb{Q}, \leq\rangle\) (the ordered set of rationals). N.B. \(\sigma\) is in the language of posets; in particular, you may not add extra constants, function symbols, etc., defined abbreviations are of course harmless.
Problem 4
Check which terms are free in the following cases, and carry out the substitution: (a) \(x\) for \(x\) in \(x=x\), (f) \(x+w\) for \(z\) in \(\forall w(x+z=\overline{0})\), (b) \(y\) for \(x\) in \(x=x\) (g) \(x+y\) for \(z\) in \(\forall w(x+z=\overline{0}) \wedge\) (c) \(x+y\) for \(y\) in \(z=\overline{0}\) \(\exists y(z=x)\), (d) \(\overline{0}+y\) for \(y\) in \(\exists x(y=x)\), (h) \(x+y\) for \(z\) in \(\forall u(u=v) \rightarrow\) (e) \(x+y\) for \(z\) in \(\forall z(z=y)\). \(\exists w(w+x=\overline{0})\),
Problem 4
Let \(\sigma=\exists x \forall y(x \leq y \vee y \leq x)\). Find posets \(\mathfrak{A}\) and \(\mathfrak{B}\) such that \(\mathfrak{A} \models \sigma\) and \(\mathfrak{B} \models \neg \sigma\).
Problem 5
Consider \(\sigma_{1}=\forall x(x \sim x), \sigma_{2}=\forall x y(x \sim y \rightarrow y \sim x), \sigma_{3}=\forall x y z(x \sim\) \(y \wedge y \sim z \rightarrow x \sim z\) ). Show that if \(\mathfrak{Q} \models \sigma_{1} \wedge \sigma_{2} \wedge \sigma_{3}\), where \mathfrak{ } \(=\langle A, R)\), then \(R\) is an equivalence relation. N.B. \(x \sim y\) is a suggestive notation for the atom \(\bar{R}(x, y)\).
Problem 6
Show \(\not \models \exists x \varphi \rightarrow \forall x \varphi\).
