Math 557 Sep 26
Midterm 1 Review
Solution 1. First prove readibility, i.e. the statement that for any \(\mathcal{L}\)-formula \(\varphi\), exactly one of the following cases holds:
- There exist terms \(s,t\) such that \(\varphi \equiv s=t\).
- There exists a relation symbol \(R\) and, if \(n\) is the arity of \(R\), terms \(t_1, \dots, t_n\) sucht that \(\varphi \equiv Rt_1\dots t_n\).
- There exists a formula \(\psi\) such that \(\varphi \equiv \neg \psi\).
- There exist formulas \(\psi, \theta\) such that \(\varphi \equiv (\psi \land \theta)\).
- There exists a variable \(x\) and a formula \(\psi\) such that \(\varphi \equiv \exists x \psi\).
To see this, let \(F\) be the subset of \(\mathcal{L}^*\) such that every \(\theta \in F\) satisfies exactly one of (1)-(5). Then \(F\) contains all atomic formulas and is closed under \(\neg, \land, \exists x\). Since the set of \(\mathcal{L}\)-formulas is the smallest such set, it follows that every \(\mathcal{L}\)-formula is contained in \(F\), and therefore has the desired property.
Second we argue that a proper initial segment of a formula cannot be a formula. We proceed by induction on the length \(l\) of \(\varphi\). For \(l=1\) there is no formula of that length. Now suppose \(\varphi\) is a formula of length \(l+1\), and \(\beta\) is a proper initial segment. We may assume \(\beta\) is not empty. We consider theses (1)-(5) from readability.
- Case \(\varphi \equiv s=t\)
- Either \(\beta \equiv s = t'\) with \(t \subset t'\), but this would contradict that no proper initial segment of a term is a term. Or \(\beta \equiv s=\): An easy induction over the length of a formula shows that no formula ends with \(=\). Or \(\beta \subseteq s\). Another easy induction shows that no formula can be a term or an initial segment of a term.
- Case \(\varphi \equiv Rt_1\dots t_n\)
- If \(\beta\) were a formula, it has to be of the form \(Rs_1\dots s_n\). Comparing terms, we would see that one of the \(s_i\) is a proper initial segment of some \(t_j\), which is impossible.
- Case \(\varphi \equiv \neg \theta\)
- Then \(\beta \equiv \neg \beta'\) with \(\beta'\) a proper initial segment of \(\theta\). By inductive hypothesis, \(\beta'\) is not a formula, hence \(\neg \beta'\) is not a formula either.
- Case \(\varphi \equiv (\psi \land \theta)\)
- Then \(\beta\) starts with \((\) but does not end with \()\). Another induction shows that for any formula, the number of \((\)’s always equals the number of \()\)’s.
- Case \(\varphi \equiv \exists x \varphi\)
- Neither ‘\(\exists\)’ nor ‘\(\exists x\)’ are formulas. If \(\beta\) is longer than that, it is of the form \(\exists x \beta'\). By inductive hypothesis, \(\beta'\) is not a formula, and hence \(\beta\) is not a formula (by readability). varphi
Finally, we prove unique readability: The choices in (1)-(5) are unique.
- Case (1)
- Suppose \(\varphi \equiv s=t \equiv s'=t'\). Since no proper initial segment of a term is a term, it must hold that \(s\equiv s'\) and \(t \equiv t'\).
- Case (2)
- Suppose \(\varphi \equiv Rt_1\dots t_n \equiv S s_1\dots s_k\). Then \(R \equiv S\) and \(n=k\). Comparing terms inductively, using again the fact that no proper initial segment of a term is a term, we get \(s_i \equiv t_i\) for all \(i\).
- Case (3)
- Suppose \(\varphi \equiv \neg \psi \equiv \neg \theta\). Immediately, we infer \(\psi \equiv \theta\).
- Case (4)
- Suppose \(\varphi \equiv (\psi_1 \land \theta_1) \equiv (\psi_2\land \theta_2)\). Assume \(\psi_1 \not\equiv \psi_2\). Then \(\psi_1\) is a proper initial segment of \(\psi_2\) or vice versa (since both of them are part of \(\varphi\)). Either case is impossible due to the fact that no proper initial segment of a formula is a formula. Hence \(\psi_1 \equiv \psi_2\) and thus also \(\theta_1 \equiv \theta_2\).
- Case (5)
- Suppose \(\varphi \equiv \exists x \psi \equiv \exists y \theta\). By comparing entries, we get \(x \equiv y\) and thus $, as desired.
Solution 2. Suppose \(\mathcal{L} = \{c_1, \cdots, c_k, f_1^{(a_1)}, \dots f_l^{(a_l)}, R_1^{(b_1)}, \dots, R_j^{(b_j)} \}\) where the \((a_i), (b_m)\) denote the arities of the respective symbols.
Since \(\mathcal{M}\) is finite, we may assume \(M = \{1, \dots, n\}\) for some \(n \in \mathbb{N}\).
The basic idea is to collect all “elementary facts” about \(\mathcal{M}\) in a single formula (think of a group multiplication table, just for all functions and relations).
Define
\[\begin{aligned} \varphi \equiv \; \exists x_1, \dots, x_n \biggl ( & \bigwedge_{i \neq m} x_i \neq x_l \; \land \; \forall y \bigvee_{i \leq n} y = x_i \\ & \land \bigwedge_{i \leq k} c_i = x_{c^{\mathcal{M}}_i} \\ & \land \bigwedge_{i\leq l} \bigwedge_{\pi \in \{1,\dots, n\}^{a_i}} f_i x_{\pi(1)} \dots x_{\pi(a_i)} = x_{f^{\mathcal{M}}_i(\pi(1), \dots, \pi(a_i))} \\ & \land \bigwedge_{i\leq j} \bigwedge_{\pi \in \{1,\dots, n\}^{b_i}} \delta_\pi R_i x_{\pi(1)} \dots x_{\pi(b_i)} \biggr ) \end{aligned}\]
where \(\delta_\pi\) is empty if \(R(\pi(1), \dots, \pi(b_i))\) holds in \(\mathcal{M}\), and \(\neg\) if not.
Assme \(\mathcal{N} \models \varphi\). Due to the first line of the equation, \(N\) has exactly \(n\) elements, and let \(r_i \in N\) be the witness to \(\exists x_i\). Define a mapping \(\tau: M \to N\) by letting \(\tau(i) = r_i\). We claim that \(\tau\) is an isomorphism.
By definition we have \(\tau(c_i^{\mathcal{M}}) = r_{c_i^{\mathcal{M}}}\). Moreover, by the second line of the formula, \(r_{c^{\mathcal{M}}_i}\) is the unique element of \(N\) that makes the formula \(c_i = x_{c_i^{\mathcal{M}}}\) true. It follows that \(\tau(c_i^{\mathcal{M}}) = c_i^{\mathcal{N}}\) for all \(1 \leq i \leq k\).
Using a similar argument with the third line of the formula, we obtain \[ \tau(f_i^{\mathcal{M}}(s_1, \dots, s_{a_i})) = r_{f_i^{\mathcal{M}}(s_1, \dots, s_{a_i})} = f^{\mathcal{N}}(r_{s_1}, \dots, r_{s_{a_i}}) = f^{\mathcal{N}}(\tau(s_1), \dots, \tau(s_{a_i}) \] The argument for \(R^{\mathcal{M}}(s_1, \dots, s_{b_i}) \iff R^{`\mathcal{N}}(\tau(s_1), \dots, \tau(s_{b_i}))\) is similar.
On the other hand, if \(\mathcal{M} \cong \mathcal{N}\) via \(\tau\), then \(\mathcal{N} \models \psi[\tau(1), \dots, \tau(n)]\), where \(\psi\) is such that \(\varphi \equiv \exists x_1, \dots, x_n \: \psi\), due to the fact that \(\tau\) is an isomorphism, and thus \(\mathcal{N} \models \varphi\).
Solution 3. Let \(\mathcal{L} = \{<\}\), where \(<\) is a binary relation symbol. Define
\[\begin{aligned} \psi \equiv \; & \forall x \; x \nless x \\ & \land \forall x,y \; x < y \lor x=y \lor y < x \\ & \land \forall x,y,z \; (x < y \land y < z) \to x < z \\ & \land \forall x \exists y \; x < y \end{aligned}\]
The formula says that \(<\) is a linear order with no maximal element.
Clearly, \((\mathbb{Z}, <) \models \psi\).
Now suppose \(\mathcal{M} \models \psi\). Due to the last line of \(\psi\), there exists a function \(f: M \to M\) such that \(x < f(x)\) for all \(x \in M\). We claim that for any \(x\) and for any \(n \neq m\), \[ f^{(n)}(x) \neq f^{(m)}(x) \] This follows from antireflexivity (line one) and transitivity (line three).
Therefore, the set \[ \{x, f^{(1)}(x), f^{(2)}(x), \dots \} \] is an infinite subset of \(N\).
Solution 4. We give derivations below (with brief justifications). We collect simple substeps into a single one.
For \(\{\varphi \to \psi \} \vdash \exists x \varphi \: \to \: \exists x \psi\;\):
| Formula | Justification |
|---|---|
| \(\varphi \to \psi\) | given |
| \(\psi \to \exists x \psi\) | (Q2) |
| \(\varphi \to \exists x \psi\) | tautology |
| \(\neg \exists x \psi \to \neg \varphi\) | tautotolgy |
| \(\forall x ( \neg \exists x \psi \to \neg \varphi)\) | \(\forall\)-intro |
| \(\neg \exists x \psi \to \forall x \varphi\) | (Q1), \(x\) not free in \(\neg \exists x \psi\) |
| \(\neg \forall x \neg \varphi \to \exists x \psi\) | tautology |
| \(\exists x \varphi \to \exists x \psi\) | (Q3) |
For \(\{\varphi \to \psi \} \vdash \forall x \varphi \: \to \: \forall x \psi \;\):
| Formula | Justification |
|---|---|
| \(\varphi \to \psi\) | given |
| \(\forall x \varphi \to \varphi\) | Example 2.6.1 (d) |
| \(\forall x \varphi \to \psi\) | Tautology |
| \(\forall x (\forall x \varphi \to \psi)\) | \(\forall\)-intro |
| \(\forall x \varphi \to \forall x \psi\) | (Q1), \(x\) not free in \(\forall x \varphi\) |
Solution 5. We first argue that any finite partial order \((F,<)\) can be extended to a linear order.
We proceed by induction on the cardinality of \(F\).
For \(|F|=0\) there is nothing to prove.
Now assume \(|F|=n+1\). Pick an arbitrary \(a \in F\) and consider \(F \setminus \{a\}\). By inductive hypothesis, \(F \setminus \{a\}\) can be extended to a linear order \(a_1 < a_2 < \dots < a_n\).
If there does not exist \(i\) such that \(a_i <_F a\), we can extend to a linear order on \(F\) by putting \(a < a_i\) for all \(i\). Otherwise let \(k\) be maximal such that \(a_k < a\). Then \[ a_1 < \dots < a_k < a < a_{k+1} < \dots < a_n \] defines a linear order that extends \((F,<)\).
Now let \((P,<)\) be an arbitrary partial order. We extend the language \(\mathcal{L}_<\) of orders to \(\mathcal{L}_P\), where we add a new constant symcol \(c_p\) for every \(p \in P\).
Let \(T\) be the theory of linear orders (see first three lines of sentence \(\varphi\) in Problem 3) together with \[ \{ c_p < c_q : p <_P q \} \] In other words, if \(p\) is less than \(q\) according to \(P\), we add a corresponding axiom to our theory.
Any model of \(T\) is a liner order that extends \(P\).
Moreover, any finite subset \(T_0 \subseteq T\) induces a partial order on a finite subset of \(P\) (induced by those \(p\) for which \(c_p\) is part of a formula in \(T_0\)). By our argument in the first part, this finite partial order extends to a linear order, thereby giving a model of \(T_0\).
By compactness, \(T\) has a model \(\mathcal{M} = (M,<)\). By choice of \(T\), \((M,<)\) is a linear order. Furthermore, the mapping \[ c_p \mapsto c_p^{\mathcal{M}} \] is one-to-one since \(\mathcal{M} \models \forall x \ x \nless x\).
We can “pull back” the order on \(\mathcal{M}\) to \(P\) by letting \[ p <' q \iff c_p^{\mathcal{M}} <^{\mathcal{M}} c_q^{\mathcal{M}} \] By definition of \(T\), \(<'\) is a linear order that extends \(<_P\).