Week 2: Truth, Consequence, and Inference

(a) True. \([\![\mathit{skaters}]\!] = \{2,4\}\) and both 2 and 4 belong to \([\![\mathit{runners}]\!] = \{1,\dots,6\}\). So \(\{2,4\} \subseteq \{1,\dots,6\}\).

(b) False. The element 3 is in \([\![\mathit{runners}]\!]\) but not in \([\![\mathit{skiers}]\!] = \{1,4\}\). One such element is enough to make the sentence false. (Elements 2, 5, 6 also work.)

(c) False. The element 2 is a skater but not a skier.

(d) True. Every set is a subset of itself, so \([\![\mathit{runners}]\!] \subseteq [\![\mathit{runners}]\!]\). In fact All \(x\) are \(x\) is true in every model, for every noun \(x\), for the same reason.

By Definition 0.3 we must consider an arbitrary model \(\mathcal M\) in which both assumptions are true and show that the conclusion is true there too.

Suppose \(\mathcal M \models \textit{All } p \textit{ are } q\) and \(\mathcal M \models \textit{All } q \textit{ are } r\). By the definition of truth, \([\![p]\!] \subseteq [\![q]\!]\) and \([\![q]\!] \subseteq [\![r]\!]\).

Take any \(x \in [\![p]\!]\). Then \(x \in [\![q]\!]\) by the first inclusion, and then \(x \in [\![r]\!]\) by the second. So \([\![p]\!] \subseteq [\![r]\!]\), which means \(\mathcal M \models \textit{All } p \textit{ are } r\).

Since \(\mathcal M\) was arbitrary, the consequence holds in every model. This is the sparrows argument above, with the nouns replaced by letters.

We need one countermodel: a model where the assumption is true and the conclusion is false.

Let \(M = \{1, 2\}\), \([\![p]\!] = \{1\}\), \([\![q]\!] = \{1, 2\}\).

The assumption holds: \(\{1\} \subseteq \{1,2\}\). The conclusion fails: \(2 \in [\![q]\!]\) but \(2 \notin [\![p]\!]\), so \([\![q]\!] \not\subseteq [\![p]\!]\).

One countermodel is enough, because \(\Gamma \models \varphi\) requires the conclusion to hold in every model of \(\Gamma\). Note that the model of Figure 1 would also work, with \(p = \mathit{skiers}\) and \(q = \mathit{runners}\).

(a) We build the string using the clauses. \(p_0 \in \mathsf T\) and \(\mathrm F \in \mathsf T\) by clause 1. Then \((p_0 \wedge \mathrm F) \in \mathsf T\) by clause 3. Then \((\neg(p_0 \wedge \mathrm F)) \in \mathsf T\) by clause 2. Each step is a mechanical check of the form of the string; we never asked what \(\wedge\) or \(\neg\) means.

(b) \(\mathsf T\) is the smallest set closed under the three clauses. Every string produced by clause 2 or 3 begins with an opening parenthesis, and the strings from clause 1 are single symbols. The string \(p_0 \wedge\) is neither, so it is not produced by any clause and is not in \(\mathsf T\).

(a) Reflexive: \(n \le n\) for every natural number. Transitive: if \(n \le m\) and \(m \le k\) then \(n \le k\). The real numbers with the usual ordering form a preorder in the same way.

(b) Reflexive: every element of \(A\) is an element of \(A\), so \(A \subseteq A\). Transitive: if every element of \(A\) is in \(B\), and every element of \(B\) is in \(C\), then every element of \(A\) is in \(C\); so \(A \subseteq C\).

(a) Not reflexive: \((a,a) \notin R\). Not transitive either: \((a,b) \in R\) and \((b,c) \in R\), but \((a,c) \notin R\). One failure is enough, so \((A,R)\) is not a preorder.

(b) Reflexive: \(n - n = 0 \le 1\). Not transitive: \((2,1) \in E\) since \(2-1 = 1\), and \((1,0) \in E\) since \(1-0=1\), but \((2,0) \notin E\) since \(2 - 0 = 2 > 1\). So \((\mathbb N, E)\) is not a preorder.

(c) Transitive: if \(n < m\) and \(m < k\) then \(n < k\). Not reflexive: \(0 < 0\) is false. So \((\mathbb N, R)\) is not a preorder.

Note the convention: we write \(\le\) only when we are working with a preorder. For an arbitrary relation we use a letter such as \(R\).

(a) No. There is no upward path from \(d\) to the node of \(b,c\); the two middle nodes are not connected. In the list of pairs, \(d \le c\) does not appear.

(b) Yes. There is a line from the node \(b,c\) up to the node \(e,f,g\), and \(c\) and \(g\) are in those nodes. In the list, \(c \le g\) appears.

(c) Yes. \(g\) and \(e\) are in the same node, so \(g \le e\) and \(e \le g\); thus \(g \equiv e\).

(d) No. The path from \(a\) to \(e\) goes upward, not downward. \(e \le a\) is not in the list.

In \(\mathbf 2^{\mathrm{op}}\) the order is reversed: \(\mathrm T \le \mathrm F\). So \(\mathrm T\) is now at the bottom.

In \(\mathbf 2^{\flat}\) no element is below another different element. The two nodes stand side by side without a line. Both \(\mathbf 2^{\mathrm{op}}\) and \(\mathbf 2^{\flat}\) are preorders: reversing an order or keeping only the reflexive pairs preserves reflexivity and transitivity.

(a) Monotone: if \(n \le m\) then \(n + 1 \le m + 1\). Not antitone: \(0 \le 1\) but \(f(1) = 2 \le 1 = f(0)\) is false.

(b) Compute \(g(0) = 2\), \(g(1) = 0\), \(g(2) = 0\), \(g(3) = 2\). Not monotone: \(0 \le 1\) but \(g(0) = 2 \le 0 = g(1)\) is false. Not antitone: \(1 \le 3\) but \(g(3) = 2 \le 0 = g(1)\) is false. So \(g\) is neither.

(c) A constant function is both monotone and antitone: for any \(n \le m\), \(h(n) = 577 \le 577 = h(m)\) and also \(h(m) \le h(n)\). Every constant function has this property.

(d) The identity is monotone: \(n \le m\) gives \(i(n) = n \le m = i(m)\). It is not antitone: \(0 \le 1\) but \(1 \le 0\) fails.

(e) Antitone: take \(n \le m\). If \(n = 0\), then \(j(m) \le 1 = j(0)\) holds because \(j(m)\) is 0 or 1. If \(n > 0\), then \(m > 0\) too, and \(j(m) = 0 \le 0 = j(n)\). Not monotone: \(0 \le 1\) but \(j(0) = 1 \le 0 = j(1)\) fails.

In \(\mathbf 2\) the only pair \(p \le q\) with \(p \ne q\) is \(\mathrm F \le \mathrm T\). Monotone means \(f(\mathrm F) \le f(\mathrm T)\); antitone means \(f(\mathrm T) \le f(\mathrm F)\). The reflexive pairs never cause a problem.

\(f_1\) (constant T) and \(f_4\) (constant F): both conditions hold, so both monotone and antitone.

\(f_2\) is the identity: \(f_2(\mathrm F) = \mathrm F \le \mathrm T = f_2(\mathrm T)\), so monotone. Antitone would need \(\mathrm T \le \mathrm F\), which is false.

\(f_3\) is negation, it flips the truth values: \(f_3(\mathrm T) = \mathrm F \le \mathrm T = f_3(\mathrm F)\), so antitone; not monotone.

Summary: \(f_1, f_2, f_4\) are monotone; \(f_1, f_3, f_4\) are antitone.

First we work out the order on \(\mathbf 2^{\mathrm{op}} \times \mathbf 2\). By Definition 0.10, \((p,q) \le (p',q')\) iff \(p \le p'\) in \(\mathbf 2^{\mathrm{op}}\) (that is, \(p' \le p\) in \(\mathbf 2\)) and \(q \le q'\) in \(\mathbf 2\). The first coordinate may go from T to F, and the second from F to T.

So \((\mathrm T,\mathrm F)\) is the bottom element, \((\mathrm F, \mathrm T)\) is the top, and \((\mathrm F,\mathrm F)\), \((\mathrm T,\mathrm T)\) are in the middle and not comparable with each other. This is the diamond in Figure 4.

Now apply \(\to\): the bottom \((\mathrm T,\mathrm F)\) goes to F, and the other three pairs go to T. Going up in the diamond, the value never goes from T down to F. Concretely, take any \(x \le y\) in the product. If \(x = (\mathrm T,\mathrm F)\), the value at \(x\) is F, and F is below every element of \(\mathbf 2\). Otherwise the value at \(x\) is T; then \(y \ne (\mathrm T, \mathrm F)\) because \((\mathrm T,\mathrm F)\) is the bottom, so the value at \(y\) is also T. In both cases the value at \(x\) is \(\le\) the value at \(y\). So \(\to\) is monotone.

Note that \(\to\) is not monotone from \(\mathbf 2 \times \mathbf 2\) to \(\mathbf 2\): there \((\mathrm F,\mathrm F) \le (\mathrm T, \mathrm F)\), but \(\mathrm T \le \mathrm F\) fails. Taking the opposite order in the first coordinate is exactly what makes the function monotone. This is the reason for the "op".

\(g\) is monotone (Example 9(a)). \(f\) is monotone: if \(n \le m\) then \(\{0,\dots,n\} \subseteq \{0,\dots,m\}\), because every number up to \(n\) is also a number up to \(m\).

By Proposition 0.15, \(f \circ g\) is monotone. Directly: \((f \circ g)(x) = \{0, 1, \dots, x+1\}\), and if \(x \le y\) then \(\{0,\dots,x+1\} \subseteq \{0,\dots,y+1\}\).

\(\mathcal M \models a = b\), because \([\![a]\!] = 1 = [\![b]\!]\).

\(\mathcal M \not\models a = c\), because \([\![a]\!] = 1 \ne 2 = [\![c]\!]\).

\(\mathcal M \models c = c\), because \([\![c]\!] = [\![c]\!]\). This holds for every name in every model.

Two observations from Figure 5: two different names can refer to the same element, as in real life (\([\![\mathit{Superman}]\!] = [\![\mathit{Clark\ Kent}]\!]\)), and an element of the model need not have any name (here 3 and 4).

Reading from the top: the leaves \(d = a\), \(a = c\), \(b = c\) are all in \(\Gamma\). Rule t combines \(d = a\) and \(a = c\) into \(d = c\). Rule s turns \(b = c\) into \(c = b\). Rule t combines \(d = c\) and \(c = b\) into \(d = b\).

Checking this proof requires no knowledge of what the names refer to. Each step only matches the shape of a rule.

Rule t needs the middle name to match: \(a = c\) and \(c = b\). The assumption is \(b = c\), so we first apply rule s to it. Then t gives \(a = b\).

For \(\vdash b = b\), the proof is a single application of rule r, with no premises. Its tree has only the conclusion \(b = b\).

\(R_1\) is not reflexive: \((2,2) \notin R_1\). So it is not an equivalence relation. (It is not symmetric either: \((3,4) \in R_1\) but \((4,3) \notin R_1\).)

\(R_2\) is reflexive (all four pairs \((x,x)\) are present), symmetric (the only non-reflexive pairs are \((1,2)\) and \((2,1)\), each other's reverse), and transitive (the only chains are like \(1\,R_2\,2\), \(2\,R_2\,1\), giving \(1\,R_2\,1\), which is present). So \(R_2\) is an equivalence relation. Classes: \([1] = \{1,2\} = [2]\), \([3] = \{3\}\), \([4] = \{4\}\). Quotient: \(X/R_2 = \{\{1,2\}, \{3\}, \{4\}\}\), often written \(\{[1],[3],[4]\}\).

\(R_3\) relates every pair among \(1,2,3\) in both directions, and \(4\) only to itself. Reflexivity, symmetry, and transitivity all hold. Classes: \([1] = [2] = [3] = \{1,2,3\}\) and \([4] = \{4\}\). Quotient: \(X/R_3 = \{\{1,2,3\}, \{4\}\}\).

\(R\) is an equivalence relation: it compares the values \(x \bmod 12\), and equality of values is reflexive, symmetric, and transitive. The classes are \([0] = \{0, 12\}\), \([1] = \{1, 13\}\), and so on; the quotient is \(\{[0], [1], \dots, [11]\}\), the 12-hour clock.

The concern: \([3] + [11]\) is defined through the numbers 3 and 11, but \([3] = [15]\) and \([11] = [23]\). If we had chosen 15 and 23 as representatives, we would compute \(15 + 23 = 38\).

Check: \(3 + 11 = 14\) and \(14 \bmod 12 = 2\); \(38 \bmod 12 = 2\). Both choices give \([2]\). In general, if \(x \bmod 12 = x' \bmod 12\) and \(y \bmod 12 = y' \bmod 12\), then \((x+y) \bmod 12 = (x'+y') \bmod 12\). So the result does not depend on which representatives we pick, and the definition is proper.

Whenever a function or relation is defined on a quotient set through representatives, this independence check must be done.

By soundness, if \(\Gamma \vdash a = c\) then every model of \(\Gamma\) satisfies \(a = c\). So it is enough to find one model of \(\Gamma\) where \(a = c\) is false.

Take \(M = \{1, 2\}\), \([\![a]\!] = [\![b]\!] = 1\), \([\![c]\!] = [\![d]\!] = 2\). Then \(\mathcal M \models a = b\) and \(\mathcal M \models c = d\), so \(\mathcal M \models \Gamma\). But \([\![a]\!] = 1 \ne 2 = [\![c]\!]\), so \(\mathcal M \not\models a = c\).

Hence \(\Gamma \not\models a = c\), and by soundness \(\Gamma \nvdash a = c\). Trying to search through all possible proof trees is not needed.