Outsmarting my Logic Lecturer

To be upfront, the title is clickbait. However, I did manage to solve a problem where my logic lecturer did not intend for anyone to solve. How do I know that? He told me. Anyway, here is the problem.

The Problem

Let \(T\) consist of \(\forall x \neg Rxx\), \(\forall x \forall y (Rxy \rightarrow Ryx)\), \(\exists x \exists y\ x \neq y\), and for each pair natural numbers \(m,n > 1\) the sentence

where \(A_{m,n}(u_1, \cdots, u_m, v_1, \cdots, v_n)\) is the conjunction of all inequalities

• \(u_i \neq u_j\) for all \(1\leq i < j \leq m\),
• \(v_i \neq v_j\) for all \(1\leq i < j \leq n\), and
• \(u_i \neq v_j\) for all \(1\leq i \leq m\) and \(1\leq j \leq n\),

and where \(B_{m,n}(x, u_1, \cdots, u_m, v_1, \cdots, v_n)\) is the conjunction of

• \(x \neq u_i\) for all \(1\leq i \leq m\),
• \(x \neq v_i\) for all \(1\leq i \leq n\),
• \(Rxu_i\) for \(i=1,\cdots,m\), and
• \(\neg Rxu_i\) for \(i=1,\cdots,n\).

Let \(A\) be the sentence

Does \(T\) entail \(A\)? If yes, produce a proof in the first-order calculus. If not, produce a counter-model.

The Solution

No, \(T\) does not entail \(A\). Let \(\mathfrak{M}\) be a model with the domain \(\{\alpha, \beta\}\) and the assignments \(a^{\mathfrak{M}} = \alpha, b^{\mathfrak{M}} = \beta\), and \(R^\mathfrak{M} = \{(\alpha, \beta), (\beta, \alpha)\}\). We show that \(\mathfrak{M}\) is a model such that \(\mathfrak{M}\models T\) but \(\mathfrak{M}\nvDash A\).

First, we show that \(\mathfrak{M} \models \forall x \neg Rxx\). Recall that \(\mathfrak{M} \models \forall x \neg Rxx\) iff \(\mathfrak{M}' \models \neg Raa\) for all models \(\mathfrak{M}'\) that differ from \(\mathfrak{M}\) at most the assignment of \(a\). Let \(\mathfrak{M}'\) be an arbitrary model that differs from \(\mathfrak{M}\) at most the assignment of \(a\). Because there are only two ways to assign \(a\) an object, either \(\alpha\), or \(\beta\), there are only two ways \(\mathfrak{M}'\) could assign \(a\) an object. Let us consider each case in turn. First, \(a^{\mathfrak{M}'} = \alpha\). Because the ordered pair \((\alpha, \alpha)\) is not a member of \(R^\mathfrak{M} = R^{\mathfrak{M}'}\), \(\mathfrak{M}' \nvDash Raa\). Hence, \(\mathfrak{M}' \models \neg Raa\). Second, \(a^{\mathfrak{M}'} = \beta\). By the same line of reasoning mutatis mutandis, \(\mathfrak{M}' \models \neg Raa\). Hence, \(\mathfrak{M}' \models \neg Raa\); \(\mathfrak{M} \models \forall x \neg Rxx\).

Second, we show that \(\mathfrak{M} \models \forall x \forall y (Rxy \rightarrow Ryx)\). Recall that \(\mathfrak{M} \models \forall x \forall y (Rxy \rightarrow Ryx)\) iff for all models \(\mathfrak{M}'\) that differ from \(\mathfrak{M}\) at most the assignment of \(a,b\), \(\mathfrak{M}' \models (Rab \rightarrow Rba)\). Recall further that given any model \(\mathfrak{N}\), \(\mathfrak{N} \models (Rab \rightarrow Rba)\) iff \(\mathfrak{N} \nvDash Rab\) or \(\mathfrak{N} \models Rba\). Now, let \(\mathfrak{M}'\) be an arbitrary model that differs from \(\mathfrak{M}\) at most the assignment of \(a,b\). There are only four ways \(\mathfrak{M}'\) could assign \(a,b\) an object:

1. \(a^{\mathfrak{M}'} = b ^{\mathfrak{M}'} = \alpha\),
2. \(a^{\mathfrak{M}'} = b ^{\mathfrak{M}'} = \beta\),
3. \(a^{\mathfrak{M}'} = \alpha, b^{\mathfrak{M}'} = \beta\),
4. \(a^{\mathfrak{M}'} = \beta, b^{\mathfrak{M}'} = \alpha\).

We consider each case in turn. Consider the first case, \(a^{\mathfrak{M}'} = b ^{\mathfrak{M}'} = \alpha\). Because \((\alpha, \alpha)\) is not a member of \(R^\mathfrak{M} = R^{\mathfrak{M}'}\), \(\mathfrak{M}' \nvDash Rab\). Hence, \(\mathfrak{M}' \models (Rab \rightarrow Rba)\). The second case follows similarly. Consider the third case, \(a^{\mathfrak{M}'} = \alpha, b^{\mathfrak{M}'} = \beta\). Because \((\beta, \alpha)\) is a member of \(R^\mathfrak{M} = R^{\mathfrak{M}'}\), \(\mathfrak{M}' \models Rba\). Hence, \(\mathfrak{M}' \models (Rab \rightarrow Rba)\). The fourth case follows similarly. From cases 1, 2 ,3, and 4, we have exhausted all the possible assignments of \(a,b\) by \(\mathfrak{M}'\); \(\mathfrak{M}' \models (Rab \rightarrow Rba)\). Hence, \(\mathfrak{M}' \models (Rab \rightarrow Rba)\) for all such-and-such \(\mathfrak{M}'\); \(\mathfrak{M} \models \forall x \forall y (Rxy \rightarrow Ryx)\).

Third, we show that \(\mathfrak{M} \models \exists x \exists y\ x \neq y\). Recall that \(\mathfrak{M} \models \exists x \exists y\ x \neq y\) iff there is a model \(\mathfrak{M}'\) that differs from \(\mathfrak{M}\) at most the assignment of \(a,b\) such that \(a \neq b\). We note that \(\mathfrak{M}\) differs from \(\mathfrak{M}\) at most the assignment of \(a,b\); there is no difference in assignment. Further, we note that \(a^\mathfrak{M} \neq b^\mathfrak{M}\); \(\alpha \neq \beta\). Hence, there is a model \(\mathfrak{M}'\) that differs from \(\mathfrak{M}\) at most the assignment of \(a,b\) such that \(a\neq b\); that model is \(\mathfrak{M}\). Therefore, \(\mathfrak{M} \models \exists x \exists y\ x \neq y\).

Fourth, we show that for all natural numbers \(m,n>1\),

Let natural numbers \(m,n > 1\) be arbitrary. We note that \(m + n >2\). Recall that

iff

for all models \(\mathfrak{M}'\) that differ from \(\mathfrak{M}\) at most the assignment of \(a,b,\cdots, c_{m+n-2}\). Let \(\mathfrak{M}'\) be an arbitrary model that differs from \(\mathfrak{M}\) at most the assignment of \(a,b,\cdots, c_{m+n-2}\). We note that because there are only 2 objects in our domain and \(m+n > 2\) constant symbols that \(\mathfrak{M}'\) must assign, there must be a natural number \(i\), \(1 \leq i \leq m+n-2\), such that either \(a^{\mathfrak{M}'} = b^{\mathfrak{M}'}\), \(a^{\mathfrak{M}'} = c_i^{\mathfrak{M}'}\), \(b^{\mathfrak{M}'} = c_i^{\mathfrak{M}'}\), or \(c_i^{\mathfrak{M}'} = c_j^{\mathfrak{M}'}\) for some \(j \neq i\) and \(1 \leq j \leq m+n-2\). This is true by the pigeonhole principle. Now, recall that

iff

Because of the above fact that there must be at least two co-referential constants, \(\mathfrak{M}'\nvDash A_{m,n}(a, b \cdots c_{m+n-2})\); \(\mathfrak{M}'\models (A_{m,n}(a, b \cdots c_{m+n-2})\rightarrow \exists x B_{m,n}(x, a, b, \cdots, c_{m+n-2}))\). Hence, \(\mathfrak{M}\models\forall u_1 \cdots \forall u_m \forall v_1 \cdots \forall v_n (A_{m,n}(u_1, \cdots, u_m, v_1, \cdots, v_n)\rightarrow \exists x B_{m,n}(x, u_1, \cdots, u_m, v_1, \cdots, v_n)).\)

From the above four points, \(\mathfrak{M} \models T\). Let us show that \(\mathfrak{M} \nvDash A\). Recall that \(\mathfrak{M} \nvDash A\) iff for all models \(\mathfrak{M}'\) that differ from \(\mathfrak{M}\) at most the assignment of \(a,b,c,d,e\),

Let \(\mathfrak{M}'\) be an arbitrary model that differs from \(\mathfrak{M}\) at most the assignment of \(a,b,c,d,e\). By the same reasoning as in the fourth point, there must be a collision between at least 2 out of 5 constants listed. Hence, \(\mathfrak{M}' \nvDash a,b,c,d \text{ are mutually distinct}\); \(\mathfrak{M} \nvDash A\). Hence, \(\mathfrak{M}\models T\) but \(\mathfrak{M}\nvDash A\); \(T\nvDash A\). Q.E.D.