# Formal Logic

## General notes

• CSCE 235 notes – some of this material (at least regarding relations and functions) is also covered here

## Lecture 3 – 2018-01-16

### HW Prob 3

• $$\mathcal{F}, \mathcal{G}$$ are non-empty families
• prove If $$\mathcal{F} \subseteq \mathcal{G}$$ then $$\cap\mathcal{G} \subseteq \cap\mathcal{F}$$
Givens Goal
$$\mathcal{F} \subseteq \mathcal{G}$$ $$\cap\mathcal{G} \subseteq \cap\mathcal{F}$$
$$\forall x (x \in \cap\mathcal{G} \to x \in \cap\mathcal{F})$$
$$x \not\in \cap\mathcal{F}$$ $$x \not\in \cap\mathcal{G}$$
$$\exists X \in \mathcal{F}(x \not\in X)$$ (call it S)
$$S \in \mathcal{F}$$
$$x \not\in S$$
$$S \in G$$
$$\exists X \in \mathcal{G} (x \not\in X)$$
$$x \not\in \cap\mathcal{G}$$

### Chapter 3 – Continued

#### §3.4 Proofs involvig conjunctions and biconditionals

• Conjunctions require that each side be proved separately
• Biconditionsals should be treated as two separate conditionals
• arrows or ’right-to-left’ and ’left-to-right’ can show which side you are proving
• if using arrows, use double arrows for clarity
• TFAE/TFAAE The Following Are All Equivalent
• Example 3.4.4: Prove that $$A \cap (B \setminus C) = (A \cap B) \setminus C$$ (Any $$x$$ that’s a member of one set is also a member of the other) Let $$x$$ be arbitrary. It suffices to show that $$x \in A \cap (B \setminus C)$$ iff $$x \in (A \cap B)\setminus C$$. TFAE:
• $$x \in A \cap (B \setminus C)$$,
• $$x \in A \land x \in B \setminus C$$,
• $$x \in A \land (x \in B \land x \not\in C)$$,
• $$(x \in A \land x \in B) \land x \not\in C$$,
• $$x \in A \cap B \land x \not\in C$$,
• $$x \in (A \cap B)\setminus C$$ $$\square$$
• § 3.4, Question 7: Prove $$\mathcal{P}(A \cap B) = \mathcal{P}(A)\cap\mathcal{P}(B)$$.
• Let $$X$$ be an arbitrary set. It suffices to show hat $$X \in \mathcal{P}(A \cap B)$$ iff $$\mathcal{P}(A)\cap\mathcal{P}(B)$$. TFAE:
• $$X \in \mathcal{P}(A \cap B)$$
• $$X \subseteq A \cap B$$ (def’n of $$\mathcal{P}$$)
• $$\forall x (x \in X \to x \in A cap B)$$ (def’n of $$\subseteq$$)
• $$\forall x (x \in X \to (x \in A \land x \in B))$$ (def’n of $$\cap$$)
• $$\forall x (x \in X \to x \in A) \land \forall x (x \in X \to x \in B)$$ (refer to predicate logic)
• $$X \subseteq A \land X \subseteq B$$ (def’n of $$\subseteq$$)
• $$X \in \mathcal{P}(A) \land X \mathcal{P}(B)$$ (def’n of $$\mathcal{P})$$
• $$\mathcal{P}(A)\cap\mathcal{P}(B)$$ (def’n of $$\cap$$)

#### §3.5 Proofs involving disjunctions

• Given disjunction $$P \lor Q$$
• rule out a side, use disjunctive syllogism
• Otherwise, break proof into cases, for the first, assume $$P$$ and prove goal; for the second, assume $$Q$$ and prove the goal. This may require different subsidiary goals.
• Proving
• Prove one side, and then derive $$P \lor Q$$
• Assume $$\lnot P$$, then derive $$Q$$, amounts to $$\lnot P \to Q \equiv P \lor Q$$, or $$\lnot Q$$ then $$P$$, is $$\not Q \to P \equiv P \lor Q$$
• use reductio
• break into cases, in each case, prove either $$P$$ or $$Q$$
• Cases require that cases are exhaustive
• Example 3.5.1: Prove that if $$A \subseteq C$$ and $$B \subseteq C$$ then $$A \cup B \subseteq C$$

Givens Goal
$$A \subseteq C$$
$$B \subseteq C$$ $$A \cup B \subseteq C$$
$$\forall x (x \in A \cup B \to x \in C)$$
$$x$$ is arbitrary
$$x \in A \lor x \in B$$ $$x \in C$$

Proof: Suppose $$A \subseteq C$$ and $$B \subseteq C$$. Let $$x$$ be an arb. member of $$A \cup B$$. It suffices to show that $$x \in C$$. $$x \in A \cup B$$, so $$x \in A$$ or $$x \in B$$. We will proceed by cases.

1. $$x \in A$$, $$A \subseteq C$$, so $$x \in C$$
2. $$x \in B$$, $$B \subseteq C$$, so $$x \in C$$, $$\square$$
• Example 3.5.2: Prove $$A \setminus (B \setminus C) \subseteq (A \setminus B) \cup C$$

Givens Goal
$$x$$ is arbitrary
$$x \in A \setminus (B \setminus C)$$ $$x \in (A \setminus B) \cup C$$
$$x \in A$$
$$x \not\in B \setminus C$$
$$\lnot(x \in B \land x \not\in C)$$
$$x \not\in B \lor x \in C$$
$$x \in A \setminus B \lor x \in C$$
$$(x \in A \land x \not\in B) \lor x \in C$$

Proof: Let $$x$$ be an arbitrary member of $$A \setminus (B \setminus C)$$. Then $$x \in A$$ and $$x \not\in B \setminus C$$. By the latter, either $$x \not\in B$$ or $$x \in C$$.

1. $$x \not\in B$$, Since $$x \in A$$, $$x \in A \setminus B$$
2. $$x \in C$$

In each case, either $$x \in A \setminus B$$ or $$x \in C$$. Hence $$x \in (A \setminus B) \cup C$$. Since the choice of $$x$$ was arbitrary $$A \setminus (B \setminus C) \subseteq (A \setminus B) \cup C$$. $$\square$$

#### §3.6 Existence and Uniqueness Proofs

• $$\exists !x P(x)$$ means exactly one thing satisfies $$P$$
• $$\exists x (P(x) \land (\forall y(P(y \to y = x))))$$
• second half is uniqueness
• Example 3.6.2: Prove that there is a unique set $$A$$ such that for every set $$B$$, $$A \cup B = B$$. ($$\exists!A \forall B(A \cup B = B)$$) Proof:
Existence
The empty set $$\emptyset$$ is such that $$\forall B (\emptyset \cup B = B)$$.
Uniqueness
Suppose for a contradiction that $$A$$ is a non-empty set such that $$\forall B (A \cup B = B)$$. $$A$$ constains at least one element – call it $$a$$. Let $$B = \emptyset$$. Then $$a \in A \cup B$$, but $$a \not\in B = \emptyset$$. Contradiction! $$\rightarrow\leftarrow$$
(no term)
Thus $$\emptyset$$ ist the unique set with the desired property. $$\square$$
• Example 3.6.4: Suppose $$A \cap B \neq emptyset$$, $$A \cap C \neq \emptyset$$, and $$A$$ has exactly one element. Prove that $$B \cap C \neq \emptyset$$. Proof: $$A$$ has exactly one element – call it $$a$$. $$A \cap B \neq \emptyset$$, so there is some object in both $$A$$ and $$B$$. This must be $$a$$. $$\therefore a \in B$$. Similarly, since $$A \cap C \neq \emptyset$$, $$a \in C$$. $$a \in B$$ and $$a \in C$$, so $$a \in B \cap C$$. Hence $$B \cap C \neq \emptyset$$. $$\square$$

## Lecture 4 – 2018-01-18

### Ex 3.5 q 5

Suppose $$B \not\subseteq A$$, then there is an element of $$B$$ call it $$b$$ such that $$b \not\in A$$. $$b \in B \setminus A$$. A fortiori $$b \in (A \setminus B) \cup (B \setminus A)$$. $$\therefore b \in A\triangle B$$. But $$b \not\in A$$, $$\therefore A \triangle B \not\subseteq A$$.

### Binary Relations (§4.1-§4.3)

#### Definitions

• ordered pair is a set that contains elements in a specific order
• $$(a, b)$$ or $$\langle a, b \rangle$$
• set-theoretic definitions:
• must be assymetric
• Kuratowski is most common
• most crucial is that $$(a, b) = (c, d)$$ iff $$a = c$$ and $$b = d$$
• more generally there do exist ordered n-tuples, sets in which the order of the coordinates is fixed
• cartesian product
• $$A \times B = \forall (a, b) \{(a, b) | a \in A \land b \in B\}$$
• $$A \times \emptyset = \emptyset \times A = \emptyset$$
• generally $$A \times B \neq B \times A$$, unless $$A = B$$
• relations
• $$R \subseteq A \times B$$
• sets of ordered pairs, and any set of ordered pairs is a relation
• relations require sets to also be denoted
• $$\emptyset$$ is often called the empty relation
• $$(x, y) \in R$$ can also be written as $$xRy$$, $$Rxy$$ or $$x$$ is $R$-related to $$y$$
• $$n$$ place relations are possible
• as are self-relations
• Defs
domain
$$\{a \in A | \exists b\in B ((a, b) \in R)\}$$
range
$$\{b \in B | \exists a\in A ((a, b) \in R)\}$$
inverse
$$R^{-1} = \{(b, a) \in B \times A | (a, b) \in R\}$$
composition
$$S \circ R = \{(a, c) \in A \times C | \exists b \in B ((a, b) \in R \land (b, c) \in S)\}$$
identity
$$i_A = \{(x, y) \in A \times A | x = y \}$$

#### Special properties

reflexive
$$\forall x \in A (Rxx)$$ – every dot has a self-loop
irreflexive
$$\forall x \in A (\lnot Rxx)$$ – No dot has a self-loop
non-reflexive
neither reflexive nor irreflexive
partially reflexive
$$\forall x \in A \forall y \in A ((Rxy \lor Ryx) -to Rxx)$$, $$\forall x \in A \forall y \in A (Rxy \to (Rxx \land Ryy))$$ – everything with an arrow in or outt has a self-loop
symmetric
$$\forall x \in A \forall y \in A (Rxy \to Ryx)$$ – for every edge from a to b, there’s an edge from b to a
asymetric
$$\forall x \in A \forall y \in A (Rxy \to \lnot Ryx)$$ – no arrow is double
non-symmetric
Neither symmetric no assymetric
anti-symmetric
$$\forall x \in A \forall y \in A ((Rxy \land Ryx) \to x=y)$$, $$\forall x \in A \forall y \in A ((Rxy \land x \neq y) \to \lnot Ryx)$$ – No arrow which joins two distinct dots is double, every double arrow is a loop
transitive
$$\forall x \in A \forall y \in A \forall z \in A ((Rxy \land Ryz) \to Rxz)$$ – every two-part journey has a shortcut
intransitive
$$\forall x \in A \forall y \in A \forall z \in A ((Rxy \land Ryz) \to \lnot Rxz)$$ – no two-part journey has a shortcut
non-transitive
neither transitive nor intransitive
equivalence
reflexive, symmetric and transitive
empty
$$\forall x \in A \forall y \in A (\lnot Rxy)$$ – there are no edges
connected
$$\forall x \in A \forall y \in A(x \neq y \to (Rxy \lor Ryx))$$ – any two distinct nodes are connected by at least one edge
• has various meanings see handout
serial
$$\forall x \in A \exists y \in A (Rxy)$$ – every node has at least one edge coming from it
unary function
$$\forall x \in A \exists! y \in A(Rxy)$$ – every node has exactly one arrow going from it

## Lecture 5 – 2018-01-23

• $n$-ary functions are $n+1$-ary relations

### Unary Functions

• a unary function from $$A$$ to $$B$$ is a relation $$F \subseteq A \times B$$ such that $$\forall a \in A \exists!b \in B(aFb)$$
• To indicate $$F$$ is a function from $$A$$ to $$B$$, $$F : A \to B$$
• functions are often denoted by lowercase letters
• $$f(a) = b$$
• if $$(a, b) \in f$$, $$b$$ is an image of $$a$$ under $$f$$
• domain – $$\{a \in A | \exists b \in B (a, b) \in f\}$$, always will be $$A$$
• range – $$\{b \in B | \exists a \in A (a, b) \in f\}$$ (a subset of the codomain), may not always be $$B$$
• Composition – $$f: A \to B$$, $$g : B \to C$$. Then $$g \circ f : A \to C$$ for any $$a \in A$$, the value is given by $$(g \circ f)(a) = g(f(a))$$
• types
injective (one-to-one)
$$\forall a_1 \in A \forall a_2 \in A (f(a_1) = f(a_2) \to a_1 = a_2)$$ (each $$b$$ is the image of at most one $$a$$)
surjective (onto)
$$\forall b \in B \exists a \in A (f(a) = b)$$ (range = codomain = $$B$$) (each $$b$$ is the image of at least one $$a$$) (specification of codomain is crucial)
bijective (one-to-one correspondence)
$$f$$ is both injective and surjective (each $$b$$ is the image of exactly one $$a$$)
• an inverse will be a relationship from $$B$$ to $$A$$, but may not always be a function.
• it will only be a function iff the original function is bijective
• Bijection allow us to shsow that two infinite sets are the same size even if one is a proper subset of the other
• Problem 8.2 Q8: Suppose $$f: A \to B$$ and $$g: B \to C$$
• Prove that if $$g \circ f$$ is onto (surjective), then $$g$$ is onto.

Givens Goal
$$f: A \to B$$
$$g: B \to C$$
$$g \circ f$$ is surjective $$g$$ is surjective
$$\forall c \in C \exists b \in B g(b) = c$$
let $$c$$ be an arbitrary element of $$C$$ $$\exists b \in B : g(b) = c$$
$$g \circ f : A \to C$$
$$\forall c \in C \exists a \in A ((g \circ f)(a) = c)$$
$$g(f(a)) = c$$

Proof: Suppose $$g \circ f$$ is surjective. Let $$c$$ be an arbitrary member of $$C$$. To show that $$g$$ is surjective, it suffices to show that $$g(b) = c$$ for some little $$b \in B$$. $$g \circ f : A \to C$$ and $$g \circ f$$ is surjective. So for any element of $$C$$ and for $$c$$ in particular, it is an image of some element of $$A$$ under $$g \circ f$$. I.E. for some $$a \in A$$, $$(g \circ f)(a) = c$$. By Theorem 5.5.5, $$g(f(a)) = c$$. Now, $$f(a) \in B$$. Thus there is an element of $$B$$, namely $$f(a)$$ such that $$c$$ is the image of that element under $$g$$. $$\square$$

## Lecture 6 – 2018-01-25

### § 5.1 Q 9a

• $$f: A \to C$$
• $$g : B \to C$$
• Show: if $$A \cap B = \emptyset$$, then $$f \cup g : A \cup B \to C$$.
• NTS: $$\forall x \in A \cup B \exists! y \in C (x, y) \in f \cup g$$
• let $$x$$ be arbit member of $$A \cup B$$
• $$x \in A \lor x \in B$$
• Cases
• $$x \in A$$, $$\exists! y \in C (x, y) \in f$$ since $$A \cap B = \emptyset$$, $$x \not\in B$$, and $$(x, y) \not\in g$$
• $$x \in B$$, $$\exists! y \in C (x, y) \in g$$ since $$A \cap B = \emptyset$$, $$x \not\in C$$, and $$(x, y) \not\in f$$

### Infinite sets

• Sets are equinumerous if $$A \sim B$$ iff there is a bijection $$f: A \to B$$. For each natural number $$n$$, let $$I_n = \{i \in \mathbb{Z}^{+} | i \leq n \}$$ Then a set $$A$$ is finite iff there is a natural number suh that $$I_n \sim A$$, otherwise a set is infinite.
• The cardinality of a finite set ($$|A|$$) is the unique $$n$$ such that $$I_n \sim A$$
• If $$A \sim B$$ and $$C \sim D$$, then $$A \times C \sim B \times D$$ (Thm 7.1.2)
• If $$A \sim B$$, $$C \sim D$$, $$A \cap C = \emptyset$$ and $$B \cap D = \emptyset$$ then $$A \cup C \sim B \cup D$$ (Thm 7.1.2)
• Equinumerosity is reflexive, symmetric and transitive (Thm 7.1.3)
• A set $$A$$ is denumerable iff $$\mathbb{Z}^{+} \sim A$$. It is countable iff either finite or denumerable, otherwise it’s uncountable.
• If $$A$$ and $$B$$ are finite, disjoint sets, then $$|A \cup B| = |A| + |B|$$
• The cardinality of an infinite set $$A$$ can be designated as $$|A|$$. If $$A$$ is denumerable, then $$|A| = \aleph_{0}$$
• Some denumerable sets:
• $$\mathbb{Z}^{+}$$
• $$\mathbb{Z}$$ (alternate)
• $$\mathbb{Z}^{+} \times \mathbb{Z}^{+}$$ (matrix, start at origin, go left one, go diag up, go up, go diag down, repeat)
• $$\mathbb{Q}$$ (similar as before, with axes as numerator and denominators, denoms enumerated as $$\mathbb{Z}$$, and equivalents removed)
• Ways to generating countable sets
• if $$A$$ and $$B$$ are countable, then so are $$A \times B$$ and $$A \cup B$$ (Thm 7.2.1)
• The union of countably many countable sets is countable (7.2.2)
• if $$A$$ is a countable set, then the set of all finite sequences of elements of $$A$$ is countable (Thm 7.2.4)
• $$\mathcal{P}(\mathbb{Z}^{+})$$ is not countable! (Thm 7.2.5, Cantor’s Theorem) There is no bijection $$f: \mathbb{Z}^{+} -to \mathcal{P}(\mathbb{Z}^{+})$$
• Proof: Suppose, for a contradiction, that there is a bijection $$f$$ (as above). Consider the set $$D = \{x \in \mathbb{Z}^{+} | x \not\in f(x)\}$$. $$D \subseteq \mathbb{Z}^+$$, so $$D \in \mathcal{P}(\mathbb{Z}^+)$$. Since $$D \in \mathrm{Cod}(f)$$, and $$f$$ is a bijection (specifically because it’s a surjection), there is some member of $$\mathbb{Z}^+$$, call it $$n$$, s.t. $$f(n) = D$$. Either $$n \in f(n)$$ or $$n \not\in f(n)$$
• Suppose $$n \in f(n)$$. $$f(n) = D$$, so $$n \in D$$. But, by the membership criterion for $$D$$, $$n \not\in f(n)$$. $$\therefore n \not\in f(n)$$. $$\rightarrow\leftarrow$$
• So, $$n \not\in D$$. By the membership criterion for $$D$$, $$n \in f(n)$$. $$\rightarrow\leftarrow$$
• Therefore, there is no such bijection $$f$$. $$\therefore \mathcal{P}(\mathbb{Z}^+)$$ is uncountable. $$\square$$
• $$\mathbb{R}$$ is also uncountable (Thm 7.2.6)

### Cut Theorem

• Suppose from $$\Gamma_1$$ you can get $$\delta_1$$, $$\Gamma_2$$, $$\delta_2$$, to $$\Gamma_n$$, $$\delta_n$$
• If $$\Sigma$$ and $$\delta_1\ldots\delta_n$$ will give $$\phi$$, then $$\Gamma_1 \cup \ldots \cup \Gamma_n \cup \Sigma \vdash \phi$$

### Deduction Theorem

• If $$\Gamma \cup \{\phi\} \vdash \psi$$, then $$\Gamma \vdash (\phi \to \psi)$$
• Suppose that there is an axiomatic proof of $$\psi$$ from $$\Gamma \cup \{\phi\}$$, then we can convert this into an axiomatic proof of $$\phi \to \psi$$ from $$\Gamma$$
• Proof (by induction on $$n$$, the number of lines in an axiomatic proof of $$\psi$$ from $$\Gamma \cup \{\phi\}$$):
• Base case: $$n = 1$$. Cases are as follows: (NTS: there is an axiomatic proof of $$\phi \to \psi$$ from $$\Gamma$$)
1. $$\psi$$ is an axiom. – $$\vdash\psi$$ $$\psi$$ is an axiom by assumption, then $$\vdash \psi \to (\phi \to \psi)$$ (PL1), $$\vdash \phi \to \psi$$ (MP). A fortiori, $$\Gamma \vdash \phi \to \psi$$.
2. $$\psi \in \Gamma$$ – $$\Gamma \vdash \psi$$ ($$\psi \in \gamma$$), $$\vdash \psi \to (\phi \to \psi)$$ (PL1), $$\Gamma \vdash \phi \to \psi$$ (MP and Cut).
3. $$\psi = \phi$$ – So $$\phi \to \psi = \psi \to \psi$$. $$\vdash\psi\to\psi$$ (previous exercise). A fortiori $$\Gamma \vdash \psi \to \psi$$.
• Inductive Step: $$n = k + 1$$ ($$n \in \mathbb{N}^{+}$$). Cases follow:
1. $$\psi$$ is an axiom – See base case
2. $$\psi \in \Gamma$$ – see base case
3. $$\phi = \psi$$ – see base case
4. $$\psi$$ is derived from two previous lines, $$(\chi \to \psi)$$ and $$\chi$$ via MP. Each of $$(\chi \to \psi)$$ and $$\psi$$ has an axiomatic proof from $$\Gamma \cup \{\phi\}$$ with fewer than $$n$$ lines. By IH, $$\Gamma \vdash (\phi \to (\chi \to \psi))$$ and $$\Gamma \vdash (\phi \to \chi)$$. $$\vdash[\phi \to (\chi \to \psi)] \to [(\phi \to \chi) \to (\phi \to \psi)]$$ (PL2), $$\Gamma \vdash (\phi \to \psi)$$ (MP x2 and Cut). $$\square$$

### Completeness Theorem (weak)

• If $$\models\phi$$, then $$\vdash\phi$$ (if $$\phi$$ is valid, then $$\phi$$ is a theorem). If $$\not\vdash\phi$$, then $$\not\models\phi$$ is what will be proven.
• Definitions:
• $$\bot$$ (read “eet”) is an abbreviation of $$\lnot(P \to P)$$
• A set of wffs $$\Gamma$$ is inconsistent iff $$\Gamma \vdash \bot$$, can be written $$\Gamma\vdash$$. A set of wffs is consistent iff not inconsistent.
• A set of wffs $$\Gamma$$ is maximal iff for every wff $$\phi$$ either $$\phi \in \Gamma$$ or $$\lnot\phi \in \Gamma$$.
• A set of wffs $$\Gamma$$ is semantically consistent/satisfiable iff there is an interpretation $$\mathcal{I}$$ s.t. $$V_{\mathcal{I}}(\gamma) = 1$$ for all $$\gamma \in \Gamma$$. $$\Gamma \not\models$$ means satisfiable, $$\Gamma\models$$ means unsatisfiable.
• Lemma 2.1 Lemma on the Finiteness of Proofs: For any set of wffs $$\Gamma$$ and any wff $$\phi$$, if $$\Gamma \vdash \phi$$, then there is a finite subset $$\Gamma_0 \subseteq \Gamma$$ s.t. $$\Gamma_0 \vdash \phi$$.
• Lemma 2.2 Lemma on Consistency: For any set of wffs $$\Gamma$$, if there is a wff $$\phi$$ s.t. $$\Gamma\vdash\phi$$ and $$\Gamma \vdash \lnot\phi$$, then $$\Gamma$$ is inconsistent.

## Lecture 10 – 2018-02-08: Completeness Theorem – Continued

• A consequence of lemmas 2.1 and 2.2 – a set is inconsistent iff it has a finite subset that is inconsistent

### Lindenbaum’s Lemma (2.3)

Lemma 2.3 Lindenbaum’s Lemma: If $$\Delta$$ is a consistent set of wffs, then there is a maximal consistent set of wffs $$\Gamma$$ s.t. $$\Delta \subseteq \Gamma$$.

Proof. Enumerate all PL-wffs: $$\phi_1, \phi_2, \phi_3, \ldots$$

We define a series of sets $$\Gamma_i$$ as follows: $$\Gamma_0 = \Delta, \Gamma_{n + 1} = \left\{ \begin{matrix} \Gamma_n \cup \{\phi_{n+1}\} & \text{if}\ \Gamma_n \cup \{\phi_{n+1}\} \text{is consistent} \\ \Gamma_n \cup \{\phi_{n+1}\} & \text{Otherwise} \end{matrix} \right.$$

Each $$\Gamma_i$$ is consistent.

Proof by induction on $$i$$:

• Base case: $$i = 0$$, $$\Gamma_0 = \Delta$$, and $$\Delta$$ is consistent by assumption.
• Inductive step: $$i = n + 1$$ ($$n \in \mathbb{N}$$). Suppose, for a contradiction, that $$\Gamma_{n + 1}$$ is inconsistent, i.e., $$\Gamma_{n + 1} \vdash \bot$$. By the construction of the $$\Gamma$$ series, this means that $$\Gamma_n \cup \{\phi_{n+1}\} \vdash \bot$$ and $$\Gamma_n \cup \{\lnot\phi_{n+1}\} \vdash \bot$$. By the Deduction Theorem, $$\Gamma_n \vdash (\phi_{n+1} \to \bot)$$ and $$\Gamma_n \vdash (\lnot \phi_{n+1} \to \bot)$$, $$\{(\phi_{n+1} \to \bot), (\lnot \phi_{n+1} \to \bot)\} \vdash \bot$$, by Excluded Middle MP. Then $$\Gamma_n \vdash\bot$$, by the Cut Theorem. But, by the IH, $$\Gamma_n$$ is consistent. $$\rightarrow\leftarrow$$

Thus, each $$\Gamma_i$$ is consistent. Now define $$\Gamma = \{\phi | \phi \in \Gamma_i \text{for some}\ i \in \mathbb{N}\}$$. We need to show that $$\Gamma$$ is consistent, maximal and a superset of $$\Delta$$.

• $$\Gamma$$ is consistent: Suppose, for a contradictio that $$\Gamma\vdash\bot$$. By the Lemma on Fininteness of Proofs, the axiomatic proof of $$\bot$$ from $$\Gamma$$ uses only finitely many members of $$\Gamma$$, say $$\Psi_1, \ldots, \Psi_m$$. By the construction of $$\Gamma$$, each $$\Psi_i$$ must be a member of some member of $$\Gamma_{j_{i}}$$. Let $$k$$ be the largest of $$j_1, \ldots, j_n$$. Then, since each member of the $$\Gamma$$ series is a superset of each earlier member, $$\Psi_1, \ldots, \Psi_m \in \Gamma_k$$. So $$\Gamma_k\vdash\bot$$, but we know that each $$\Gamma_k$$ is consistent because each member of the $$\Gamma$$ series is consistent.
• $$\Gamma$$ is maximal: By the construction of the $$\Gamma$$ series, each wff $$\phi_i$$ is such that either $$\phi_i \in \Gamma_{i - 1}$$ or $$\lnot\phi_i \in \Gamma_{i - 1}$$. So $$\Gamma$$ is maximal.
• $$\Gamma$$ is a superset of $$\Delta$$: $$\Gamma_0 = \Delta$$, and $$\Gamma_0 \subseteq \Gamma$$. So $$\Delta \subseteq \Gamma$$. $$\square$$

### Lemma on features of MCSs

Lemma 2.4 Lemma on features of Maximal Consistent Sets (MCSs): where $$\Gamma$$ is any MCS of wffs:

• 2.4a: For any wff $$\phi$$, exactly one of $$\phi$$ and $$\lnot\phi$$ is a member of $$\Gamma$$.

Proof: By the definition of maximality, at least one of $$\phi$$ and $$\lnot\phi$$ must be in $$\Gamma$$. By the Lemma on Consistency (2.2), $$\Gamma$$ cannot contain both $$\phi$$ and $$\lnot\phi$$ (or it would be inconsistent). $$\square$$

• 2.4c: For any wff $$\phi$$, $$\phi \in \Gamma$$ iff $$\Gamma \vdash\phi$$

Proof:

$$\Rightarrow$$ Trivial.

$$\Leftarrow$$ We’ll prove the contrapositive. Suppose $$\phi \not\in \Gamma$$, then $$\not\phi \in \Gamma$$ (by Lemma 2.4a (or maximality)). Then $$\Gamma\vdash\lnot\phi$$. If $$\Gamma\vdash\phi$$, the $$\Gamma$$ would be inconsistent, by the Lemma on Consistency. So $$\Gamma\not\vdash\phi$$. $$\square$$

• 2.4b: For any wffs $$\phi$$ and $$\psi$$, $$(\phi \to \psi) \in \Gamma$$ iff either $$\phi \not\in \Gamma$$ or $$\psi \in \Gamma$$.

Proof:

$$\Rightarrow$$ Suppose that $$(\phi\to\psi) \in \Gamma$$, and that $$\phi \in \Gamma$$. Then $$\Gamma\vdash\phi\to\psi$$ and $$\Gamma\vdash\psi$$, so $$\Gamma\vdash\psi$$ by MP.

$$\Leftarrow$$ We’ll prove the contrapositive. Suppose $$(\phi\to\psi) \not\in \Gamma$$ Then $$\lnot(\phi\to\psi) \in \Gamma$$, by lemma 2.4a (or maximality). $$\{\lnot(\phi \to \psi)\} \vdash \phi$$ and $$\{\lnot(\phi \to \psi)\} \vdash \lnot\psi$$, by Negated Conditional (PL toolkit). $$\Gamma\vdash\lnot(\phi\to\psi)$$, so $$\Gamma\vdash\phi$$ and $$\Gamma\vdash\lnot\psi$$ by Cut. Thus $$\phi \in \Gamma$$ and $$\lnot\psi\in\Gamma$$ by lemma 2.4c. $$\lnot\psi\in\Gamma$$, so $$\psi\not\in\Gamma$$, by lemma 2.4a. $$\square$$

• 2.4d: There is an interpretation $$\mathcal{I}$$ such that for every wff $$\phi$$, $$V_{\mathcal{I}}(\phi) = 1$$ iff $$\phi\in\Gamma$$.

Proof: Define an interpretation $$\mathcal{I}$$ as follows: Where $$\alpha$$ is a sentence letter, let $$\mathcal{I}(\alpha) = 1$$ iff $$\alpha\in\Gamma$$.

We will show that for any wff $$\phi$$, $$V_{\mathcal{I}}(\phi) = 1$$ iff $$\phi \in \Gamma$$. (The big result)

Proof by induction on $$n$$, the number of connectives in $$\phi$$.

• Base Case: $$n = 0$$. $$\phi$$ is a sentence letter. TFAE:
• $$V_{\mathcal{I}}(\phi) = 1$$
• $$\mathcal{I}(\phi) = 1$$ (def of valuation for sentence letters)
• $$\phi \in \Gamma$$ (by specification of $$\mathcal{I}$$)
• Inductive step: There are two cases
• $$\phi = \lnot\psi$$ for some PL-wff $$\psi$$. TFAE:
• $$V_{\mathcal{I}}(\phi) = 1$$
• $$V_{\mathcal{I}}(\lnot\psi) = 1$$ ($$\phi = \lnot\psi$$)
• $$V_{\mathcal{I}}(\psi) = 0$$ (def of valuation for $$\lnot$$)
• $$\psi\not\in\Gamma$$ (IH)
• $$\lnot\psi\in\Gamma$$ (lemma 2.4a)
• $$\phi\in\Gamma$$ ($$\phi = \lnot\psi$$)
• $$\phi = \psi \to \chi$$. TFAE:
• $$V_{\mathcal{I}}(\phi) = 1$$
• $$V_{\mathcal{I}}(\psi \to \chi) = 1$$ ($$\phi=(\psi\to\chi)$$)
• Either $$V_{\mathcal{I}}(\psi) = 0$$ or $$V_{\mathcal{I}}(\chi) = 1$$ (def Val $$\to$$)
• Either $$\psi \not\in\Gamma$$ or $$\chi\in\Gamma$$ (IH)
• $$(\psi \to\chi) \in \Gamma$$ (lemma 2.4b)
• $$\phi\in\Gamma$$ ($$\phi = (\psi \to \chi)$$)

### The Weak Completeness Theorem

Proof: Suppose $$\not\vdash\phi$$, the $$\{\lnot\phi}\not\vdash$$. For suppose otherwise: $$\{\lnot\phi\} \vdash\bot$$. So $$\vdash\lnot\phi\to\bot$$, by Deduction Theorem. I.E. $$\vdash \lnot\phi\to\lnot(P\to P)$$ Then $$\vdash(P\to P) \to \phi$$, by Contraposition 1 (PL Toolkit). $$\vdash P\to P$$, by previous exercise. ∴ $$\vdash\phi$$ by MP. $$\Rightarrow\Leftarrow$$. So $$\{\lnot\phi\}$$ is consistent. By Lindenbaum’s Lemma, there is a maximal consistent set $$\Gamma$$ such that $$\lnot\phi\in\Gamma$$. By Lemma 2.4d, there is an interpretation $$\mathcal{I}$$ such that $$V_{\mathcal{I}}(\gamma) = 1$$ for all $$\gamma \in \Gamma$$. In particular, $$V_{\mathcal{I}}(\lnot\phi) = 1$$. So $$V_{\mathcal{I}}(\phi) = 0$$. $$\therefore\not\models\phi$$. $$\square$$

## Lecture 11 – 2018-02-13

### Expressive Adequacy in Sentential Logic

• Require $$\lnot$$, $$\land$$ and $$\lor$$
• Truth function is $n$-ary, from $$\{0, 1\}^n$$ to $\{0, 1\}$$• for an$n$-ary truth function $$\mathcal{T}$$, there are $$2^n$$ rows in the truth table, and a total possible $$2^{2^n}$$ truth functions. • $$f_{\mathcal{T}} : \{0, 1\}^{n} \to \{0, 1\}$$ • symbolizing – a wff $$\phi$$ symbolizes an$n$-place truth function $$f$$ iff $$\phi$$ contains all and only sentence letters $$P_1, \ldots P_n$$, and for any interpretation $$\mathcal{I}$$, $$V_{\mathcal{I}}(\phi) = f(\mathcal{I}(P_1), \ldots, \mathcal{I}(P_n))$$ • expressing – A set of connectives can express a truth function $$f$$ iff there is a wff $$\phi$$ containing no connectives not in that set that symbolizes $$f$$ • expressive adequacy – A set of connectives is expressively adequate iff all truth functions can be symbolized by wffs containing no connectives not in that set. A set of connectives is expressively adequate iff it can express every truth function. (A/K/A adequacy, expressive completeness, completeness) • disjunctive normal form – a wff is in DNF iff it is a disjunction of the form $$(\Sigma_1 \lor \cdots \lor \Sigma_n)$$, where ieach dijunct $$\Sigma_i$$ ($$1 \leq i \leq n$$) is a conjunction of the prom $$(\phi_1 \land \cdots \phi_m)$$, and each $$\phi_j$$ ($$1 \leq j \leq m$$) is a literal, either a sentence letter or a negation of a sentence letter, with no sentence letter appearing more than once within each disjunct $$\Sigma_i$$ • there are variants, full disjunctive normal form requires each sentence letter in use to be in each $$\Sigma_i$$ • within each disjunct, the literals must be in alphabetical/numerical order. • disjuncts having to be in specific order • DNF Theorem – any truth function that assigns 1 to at least one input can be symbolized by a wff in DNF. • Corollary to the DNF theorem – the set of connectives $$\{\lnot, \land, \lor\}$$ Proof: If a truth functions assigns 1 to at least one input, it can be symbolized by a wff in DNF. Such a wff uses no connectives not in $$\{\lnot, \land, \lor\}$$. If a truth function assigns 1 to no inputs, it can be symbolized by the wff $$P \land \lnot 1$$ Either way, the set $$\{\lnot, \land, \lor\}$$ can express any truth function. Hence $$\{\lnot,\land,\lor\}$$ is expressively adequate. $$\square$$ • Assuming the expressive adequacy of $$\{\lnot, \land, \lor\}$$, show the expressive adequacy of $$\{\lnot, \land\}$$. $$P_1 \lor P_2 \equiv \lnot(\lnot P_1 \land \lnot P_2)$$ must be shown. • Show $$\{\lnot, \to\}$$ • Express $$\land$$ and $$\lor$$ • $$P_1 \land P_2 \equiv \lnot(P_1 \to \lnot P_2)$$ • $$P_1 \lor P_2 \equiv \lnot P_1 \to P_2 \equiv \lnot(\lnot P_1 \land \lnot P_2)$$ • Show $$\{\mid\}$$ (not both) • $$\lnot P \equiv P \mid P$$ • $$P \lor Q \equiv \lnot P \mid \lnot Q$$ • $$P \land Q \equiv \lnot (P \mid Q)$$ • Show $$\lor$$ in terms of $$\to$$ alone – $$(P \to Q) \to Q$$ • Showig expressive inadequacy. You have to show that the set has a certain feature, show that a particular truth function (negation, conjunction, etc) lacks this feature, and conclude that the set cannot express that truth function. Identifying the feature is the hardest. Lemma: Suppose $$\phi$$ is a wff containing no connectives other than $$\{\land, \lor, \to, \iff\}$$. Then on any interp $$\mathcal{I}$$ s.t. $$\mathcal{I}(\alpha) = 1$$, for every letter $$\alpha$$ that appears in $$\phi$$, $$V_{\mathcal{I}}(\phi) = 1$$. Proof by induction on $$n$$, the number of connectives in $$\phi$$. Base Case: $$n = 0$$. $$\phi$$ is a sentence letter, by assumption $$\mathcal{I}(\phi) = 1$$, so $$V_{\mathcal{I}}(\phi) = 1$$ Inductive Step: $$n = k + 1$$ ($$k \in \mathbb{N}$$). There are four cases: • $$\phi = (\psi \land \chi)$$ • $$\phi = (\psi \lor \chi)$$ • $$\phi = (\psi \to \chi)$$ • $$\phi = (\psi \iff \chi)$$ In each case, by IH, $$V_{\mathcal{I}}(\psi) = 1$$ and $$V_{\mathcal{I}}(\chi) = 1$$ when $$\mathcal{I}(\alpha) = 1$$ for every SL $$\alpha$$ in $$\phi$$. So $$V_{\mathcal{I}}(\psi \land \chi) = V_{\mathcal{I}}(\psi \lor \chi) = V_{\mathcal{I}}(\psi \to \chi) = V_{\mathcal{I}}(\psi \iff \chi)$$, by definitions of these connectives. $$\square$$ It follows that the set $$\{\land, \lor, \to, \iff\}$$ cannot express negation. Suppose, for a contradiction that there is a wff $$\phi$$ containing only these connectives and the letter $$p$$ that symbolizes negation. So, $$\phi \equiv \lnot P$$. So then, when $$\mathcal{I}(P) = 1$$, $$V_{\mathcal{I}}(P) = 0$$. But by the lemma we just proved, $$V_{\mathcal{I}}(P) = 1$$. ## Lecture 12 – 2018-02-15 ### Review of PS2 Prob 2 • Induction on number of connectives • base is $$n = 0$$, $$\phi = \alpha$$ • inductive step cases • $$\phi = \lnot \psi$$ • $$\alpha = \phi$$ – basecase • $$\alpha$$ is a component of $$\psi$$ – shown with TFAE • $$\phi = (\psi \to \chi)$$ • $$\alpha = \phi$$ – basecase • $$\alpha$$ is a component of $$\psi$$ or of $$\chi$$ or of both – TFAE is easiest ### Review of Homework Problem 12 • always 0, 1/2, all will be true • remember to try to find a specific property first • $$\phi = (\psi \to \chi)$$ • Lemma: A wff $$\phi$$ that uses no sentence letters other than $$P$$ and $$Q$$ and no connectives other than $$\lnot$$ and $$\leftrightarrow$$ will be such that $$V_{\mathcal{I}}(\phi) = 1$$ for an even number (0, 2 or 4) of the following interpretations: • $$\mathcal{I}_1(P) = 1$$, $$\mathcal{I}_1(Q) = 1$$ • $$\mathcal{I}_2(P) = 1$$, $$\mathcal{I}_2(Q) = 0$$ • $$\mathcal{I}_3(P) = 0$$, $$\mathcal{I}_3(Q) = 1$$ • $$\mathcal{I}_4(P) = 0$$, $$\mathcal{I}_4(Q) = 0$$ • Proof by induction on $$n$$ the number of connectives in $$\phi$$. • Base Case: $$n = 0$$ $$\phi$$ is a sentence letter, either $$\phi = P$$ or $$\phi = Q$$. If $$\phi$$ is P, then $$\phi$$ is assigned one by $$V_{\mathcal{I}_1}$$ and $$V_{\mathcal{I}_2}$$. If $$\phi = Q$$, then it is assigned 1 by $$V_{\mathcal{I}_1}$$ and $$V_{\mathcal{I}_3}$$ only. $$\phi$$ is assigned 1 by two valuations, 2 is even. • Inductive Step: $$n = k + 1$$, $$k \in \mathbb{N}$$ 1. $$\phi = \lnot \psi$$ By the IH, $$V_{\mathcal{I}}(\psi) = 1$$ far 0, 2, or 4 of the interpretations. By definition of$\lnot, $$V_{\mathcal{I}}(\phi) = 1$$ for either 4, 2 or 0 of the interpretations.
2. $$\phi = (\psi \leftrightarrow \chi)$$ We will divide this case into subcases that are jointly exhaustive.
1. $$\psi = 1$$ by all four valuations. Then $$V_{\mathcal{I}}(\chi)$$ for all $$\mathcal{I}$$. By the IH, $$V_{\mathcal{I}}(\chi) = 1$$ for an even number of $$\mathcal{I}$$. So is, therefore, $$\phi$$.
2. $$\chi = 1$$ by all four valuations. Refer to immediately previous case.
3. $$\psi = 1$$ by none of the valuations. Then, $$V_{\mathcal{I}}(\psi \leftrightarrow \chi) = V_{\mathcal{I}}(\lnot\chi) = 1 - V_{\mathcal{I}}(\chi)$$. By IH, $$V_{\mathcal{I}}(\chi)$$ is one for 0, 2 or 4 of the $\mathcal{I}$s. Therefore, $$\mathcal{\lnot\chi} = 1$$ for 4, 2 or 0 of the $\mathcal{I}$s.
4. $$\chi = 1$$ by none of the valuations. Refer to immediately previous case.
5. $$\psi$$ and $$\chi$$ are each assigned one by two valuations (not necessarily the same ones). There are three subsubcases according to how many of the two interpretations for which $$V_{\mathcal{I}}(\psi) = 1$$ are also such that $$V_{\mathcal{I}}(\chi) = 1$$
1. For the two interps such that $$V_{\mathcal{I}}(\psi) = 1$$, both are such that $$V_{\mathcal{I}}(\chi) = 1$$. $$V_{\mathcal{I}}(\psi) = V_{\mathcal{I}}(\chi)$$ for all 4. $$Thus V_{\mathcal{I}}(\phi) = V_{\mathcal{I}}(\psi \leftrightarrow \chi) = 1$$ for all 4 rows.
2. For the two interps such that $$V_{\mathcal{I}}(\psi) = 1$$, exactly one is such that $$V_{\mathcal{I}}(\chi) = 1$$. $$V_{\mathcal{I}}(\psi) = V_{\mathcal{I}}(\chi)$$ for exactly 2. $$Thus V_{\mathcal{I}}(\phi) = V_{\mathcal{I}}(\psi \leftrightarrow \chi) = 1$$ for exactly 2 rows.
3. For the two interps such that $$V_{\mathcal{I}}(\psi) = 1$$, neither is such that $$V_{\mathcal{I}}(\chi) = 1$$. $$V_{\mathcal{I}}(\psi) = V_{\mathcal{I}}(\chi)$$ for none. $$Thus V_{\mathcal{I}}(\phi) = V_{\mathcal{I}}(\psi \leftrightarrow \chi) = 1$$ for no rows. $$\square$$

### Practice

• Show that $$\land$$ cannot be expressed in terms of $$\to$$ alone.
• Let $$\mathcal{I}_1, \ldots, \mathcal{I}_4$$ be the same as above. Suppose $$\phi$$ is a wff that contains no SLs other than $$P$$ and $$Q$$ and no connectives other than $$\to$$. At most two of the interpretations are such that $$V_{\mathcal{I}}(\phi) = 0$$.
• Inductive Step shows $$V_{\mathcal{I}}(\psi \to \chi)$$

Proof: by inductions on $$n$$, the number of connectives in $$\phi$$

Base Case: $$n = 0$$, either $$P$$ or $$Q$$. By definition of the Interp. Functions, either way, at most 2 places it may be 0.

Inductive Step: $$n = k + 1$$, $n ∈ \mathbb{N} $$\phi = \psi \to \chi$$ $$V_{\mathcal{I}}(\phi) = V_{\mathcal{I}}(\psi \to \chi) = 0$$ iff $$V_{\mathcal{I}}(\psi) = 1$$ and $$V_{\mathcal{I}}(\chi) = 0$$. By IH, $$V_{\mathcal{I}}(\chi)$$ for at most two of the four interps. Therefore, $$V_{\mathcal{I}}(\psi \to \chi) = 0$$ for at most two of the four interps. $$\square$$ ### Notes on exercises • For 16, relevant property is when P = 1, Q = 0, and Q = 1, P = 0 ## Lecture 13 – 2018-02-20 ### Polish Notation and Unique Readability • operator comes before operands, also known as prefix notation • L1 defs • $$\ell(\sigma)$$ is the number of symbols in $$\sigma$$ • $$\sigma$$ and $$\tau$$ are strings of symbols $$\sigma$$ is an initial segment of $$\tau$$ iff $$\ell(\sigma) \leq \ell(\tau)$$ and the$i$th symbol of sigma is the same as the$i$th symbol of $$\tau$$ ($$1 \leq i \leq \ell(\sigma)$$) • $$\sigma_0$$ is a proper initial segment of $$\sigma$$ iff $$\sigma_0$$ is an initial segment of $$\sigma$$, but is not $$\sigma$$ ($$\ell(\sigma_0) < \ell(\sigma)$$) • Lemmas for L1: Balanced Parentheses Lemma Every L1-wff has an eual number of left and right parens (proof by induction on formula complexity) Left-Heaviness Lemma Every proper initial segment of an L1-wff has more left-parens than right-parens (induction on forumla complexity, requires balanced parens) Corollary on Proper Initial Segments No proper initial segment of an L1-wff is itself an L1-wff. (follows from previous) • Proof of Left-Heaviness Lemma Proof by induction on formula complexity. Let $$\phi$$ be an arbitrary L1 wff with $$n$$ connectives. Base Case: $$n = 0$$. $$\phi$$ is a sentence letter, so it has no PIS’s. So it’s vacuously true that all of it’s PIS’s are left-heavy. Inductive Step: $$n = k + 1$$, $$k \in \mathbb{N}$$. Cases: • $$\phi = (\lnot \psi)$$, for some L1-wff $$\psi$$. There are four subcases: • $$\phi_0 = ($$. Clearly $$\phi_0$$ is left-heavy. • $$\phi_0 = (\lnot$$. Clearly $$\phi_0$$ is left-heavy. • $$\phi_0 = (\lnot\psi_0$$, where $$\psi_0$$ is a PIS of $$\psi$$. $$\psi$$ has $$k$$ connectives, so by IH, $$\psi_0$$ is left-heavy. So $$\phi_0$$ is (even more) left-heavy. • $$\psi_0 = (\lnot\psi$$. By the Balanced Parentheses Lemma, $$\psi$$ has an equal number of left and right parens. So $$\phi_0$$ is left-heavy. • $$\phi = (\psi * \chi)$$, for some L1-wffs $$\psi$$ and $$\chi$$ and for some binary L1 connective $$*$$. There are six subcases: • $$\phi_0 = ($$. Clearly $$\phi_0$$ is left-heavy. • $$\phi_0 = (\psi_0$$, where $$\psi_0$$ is a PIS of $$\psi$$. $$\psi$$ has at most $$k$$ connectives, so by IH, $$\psi_0$$ is left-heavy. Thus $$\phi_0$$ is left-heavy. • $$\phi_0 = (\psi$$. $$\psi$$ has balanced parethesis by the Balanced Parenthesis Lemma. So, $$\phi_0$$ is left-heavy. • $$\phi_0 = (\psi *$$. See previous case. • $$\phi_0 = (\psi * \chi_0$$, where $$\chi_0$$ is a PIS of $$\chi$$. $$\psi$$ has balanced parens. But, $$\chi_0$$, having at most $$k$$ connectives, is left-heavy by IH. Thus, $$\phi_0$$ is left-heavy, (it has at least 2 excess left-parens). • $$\phi_0 = (\psi * \chi$$, $$\psi$$ and $$\chi$$ both have balanced parens, so $$\phi_0$$ has one excess left-paren, and is left-heavy. $$\square$$ • Proof of Corollary on Proper Initial Segments. Every PIS of an L1-wff is left-heavy, but no L1-wff is. $$\square$$ • The Unique Readability Theorem for L1. Every L1 wff is exactly one of the following: 1. A Sentence Letter 2. $$(\lnot\alpha)$$ for some unique L1-wff $$\alpha$$ 3. $$(\alpha * \beta)$$ for some unique L1-wffs $$\alpha$$ and $$\beta$$ and a unique binary connective $$*$$ Proof. First, we’ll show that the three types are mutually exclusive. (1) and (2) are obviously mutually exclusive (2) starts with left paren. As are (1) and (3), by the same logic. (2) and (3) are mutually exclusive. For a contradiction, suppose that a wff $$(\lnot \alpha) = (\beta * \gamma)$$ for some L1 wffs $$\alpha$$, $$\beta$$ and $$\gamma$$. Then the first symbol of $$\beta$$ bust be $$\lnot$$. But in L1, all compound wffs must start with a left-paren. ($$\rightarrow\leftarrow$$) Now we’ll show that within each type, every wff is uniquely readable. 1. Obviously, each SL is unique. 2. Suppose $$(\lnot \alpha) = (\lnot \beta)$$. Then clearly, $$\alpha$$ is $$\beta$$. 3. Suppose some L1 wff $$(\alpha * \beta)$$ for L1 wffs $$\alpha$$ and $$\beta$$ is such that $$(\alpha * \beta) = (\gamma + \delta)$$ for lome L1-wffs $$\gamma$$ and $$\delta$$ and for some L1 binary connective $$+$$. Suppose for a contradiction that $$\alpha \neq \gamma$$. Then it must be the case, since $$(\alpha * \beta)$$ and $$(\gamma + \delta)$$ are the same string, it must be the case that either $$\alpha$$ is a PIS of $$\gamma$$ or $$\gamma$$ is a PIS of $$\alpha$$. But by the Corollary on PIS, no WFF is a PIS of a WFF. $$\rightarrow\leftarrow$$. Therefore$α = γ.$Then obviously, $$* = +$$, and $$\beta = \delta$$. $$\square$$ ## Lecture 14: 2018-02-22 – Trivalent Logic • Definitions trivalent interpretation a function from the set of sentence letters to the set $$\{1, 0, \#\}$$ Designated truth value Where $$\mathcal{V}$$ is a set of truth-values for a particular semantics, designated truth-values are those elements of $$\mathcal{V}$$ that are relevant for validity and semantic consequence. For L • a WFF is L-valid iff it is assigned a designated truth value on all L-valuations • A wff $$\phi$$ is an L-semantic consequences of a set of wffs $$\Gamma$$ iff $$\phi$$ is assigned a designated truth value on any L-valuation on which every member of $$\Gamma$$ is assigned a designated value. Classical Interpretations have $$\{1, 0\}$$ and 1 is the only designated value. Trivalent is such that $$\{1, 0, \#\}$$, and 1 is the designated value. determinate truth value 1 and 0 are determinite, $$\#$$ is not. 0 and 1 are classical values truth-functionality A logic is truth-functional iff the value of a compound wff is a function of the values faithfulness a trivalent logic is faithfull if the truth-value of a compound matches its classical truth-value when the truth-values are determinite stability a tvl logicc is stable iff for any compound wff $$\phi$$, if $$\phi$$ receives a determinite value even though one of its components recieves the value $$\#$$, then changing the truth value of that component from $$\#$$ to 1 or 0 doesn’t change the determinate truth-value of $$\phi$$. • Review handouts ## Lecture 15: 2018-02-27 – Trivalent Logic, Fuzzy Logic and Trees ### Fuzzy Logic • Uses the same valuation clauses, but is a function from the set of sentence letters to $$[0, 1]$$ • $$FV_{\mathcal{I}}(\lnot \phi) = 1 - FV_{\mathcal{I}}(\phi)$$ • $$FV_{\mathcal{I}}(\phi \land \psi) = min(FV_{\mathcal{I}}(\phi), FV_{\mathcal{I}}(\psi))$$ • $$FV_{\mathcal{I}}(\phi \lor \psi) = max(FV_{\mathcal{I}}(\phi), FV_{\mathcal{I}}(\psi))$$ • $$FV_{\mathcal{I}}(\phi \to \psi) = 1 - (FV_{\mathcal{I}}(\phi) \dot{-} FV_{\mathcal{I}}(\psi))$$ • $$\{P \to Q, P} \models_{F} Q$$ is valid • suppose for a reductio that there is a fuzzy interpretation such that $$FV_{\mathcal{I}}(P \to Q) = FV_{\mathcal{I}}(P) = 1$$, but $$FV_{\mathcal{I}}(Q) \neq 1$$ Let $$FV_{\mathcal{I}}(Q) = q$$, $$q < 1$$. $$FV_{\mathcal{I}}(P \to Q) = 1 - (FV_{\mathcal{I}}(P) \dot{-} q) = 1$$ So $$FV_{\mathcal{I}}(P) \dot{-} FV_{\mathcal{I}}(Q) = 0$$, $$1 \dot{-} q = 0$$, but $$q < 1$$, so $$1 \dot{-} q > 0$$ $$\rightarrow\leftarrow$$ • $$A \to B \models \lnot A \lor B$$, $$\mathcal{I}(A) = 0.6$$, $$\mathcal{I}(B) = 0.7$$ ### Trees • breaks down sentences by branching • allows testing for tautologisness, semantic consequence (test an argument) • Kleene logic, 1 means known, Bochvar means that anywhere $$\#$$ occurs, the whole sentence is $$\#$$ • In general, review handout • Tree Rules for Kleene • Has an annotation for indeterminancy • Positive and Negative rules are the same, but indeterminante now exists, and there are three closure rules • A set is kleene-satisfiable iff there is a trivalent interp such that for every member of the set, the valuation is 1. To test , construct a tree, if the tree stays open, there’s a model. • to test semantic entailment, include all set members, do two trees, one with $$\lnot \phi$$ and $$\phi$$ marked as indeterminate. If both close, set entails $$\phi$$ • Validity again requires 2 trees, both closing. • \L{}ukasiewicz Rules • Only the rules for implication change, procedures are otherwise the same ## Lecture 16: 2018-03-01 – Relevance and paraconsistent logic • logics that are paraconsistent, relevance logics are a subset (a/k/a relevant logics) • background • liar paradox – S: “S is false” – trivalence helps • strengthened liar paradox – “S$$*$$ is either false or neither true nor false” – trivalence isn’t useful • dialetheism – view that some sentence care both true and false simultaneously, and some true contradictions • Richard Silvan’s Box • don’t require that all is accepted • Paraconsistent logics • a explosive logic is a logic in which the principle of explosion holds (see ex falso quodlibet) • a paraconsistent logic is a logic that is not explosive • relevance logics • variable-sharing priniciple – where $$\Gamma$$ is a set of wffs and $$\phi$$ is a wff, if $$\Gamma\vdash\phi$$, then $$\phi$$ has at least one sentence letter in common with at least one member of $$\Gamma$$. • a relevance logic is a logic in which the premises must be relevant to the conclusion. satisfaction of the variable sharing principle is necessary but not sufficient. Any logic that satisfies it is also paraconsistent, however not all paraconsistent logics satisfy this principle. Rejection of strict implication (contradiction strictly implies anything, tautology strictly implied by anything) is frequent. • FDE – first-degree entailment, relevance and paraconsistent – obeys variable sharing, quadrivalent • wff rules • all capital sentence letters are an FDE-wff • if $$\phi$$ and $$\psi$$ are FDE-wffs, so are $$\lnot \phi$$, $$(\phi \land \psi)$$ and $$(\phi \lor \psi)$$ • nothing is an FDE wff except by the previous two • $$\to$$ and $$\iff$$ are shortcuts • truth values • $$\mathcal{V} = \{1, b, n, 0\}$$, $$b$$ being both, $$n$$ being neither • $$\mathcal{D} = \{1, b\}$$ are designated • Truth tables – see handout • Interp is a function from the set of sentence letters to $$\mathcal{V}$$ • $$1 > b > 0$$, $$1 > n > 0$$, $$b$$ and $$n$$ are not comparable • valuation defined in handout • valid iff for every interp, the valuation is designated • semantic consequence iff for every interp, valuation is designated for all members of $$\Gamma$$, then valuation of $$\phi$$ is also designated • no tautologies, and all is satisfiable • LP – Logic of Paradox • $$\mathcal{V} = \{1, 0, b\}$$, $$\mathcal{D} = \{1, b\}$$ • interp is from sentence letters to $$\mathcal{V}$$ • almost same as FDE, just no $$n$$ • Truth tables same as Kleene, but with $$b$$ ($$\#$$) as designated • except there is a possibility of tautology – and they’re the same as classical logic tautologies • tree rules and methods are the same as for FDE, but with an added closure rule • however, some things are missing, including Modus Ponens • trees • entailment – when all is designated and final is undesignated, if closes – $$\oplus$$ is for designated, $$\ominus$$ is for undesignated, start with a tree where each is designated, iff treee closes, provides semantic entailment • validity – if closes with all being initially undesignated, valid. ## Lecture 17: 2018-03-06 – Supervaluations ### Review of HW • If $$\Gamma \not\models_{LP} \phi$$, then $$\Gamma \not\models_{FDE} \phi$$ • Suppose $$\Gamma \not\models_{LP} \phi$$. Then there is a trivalent interp $$\mathcal{I}$$ s.t. $$LPV_{\mathcal{I}}(\gamma)$$ is designated for all $$\gamma \in \Gamma$$, but $$LPV_{\mathcal{I}}(\phi) = 0$$. Let $$\mathcal{J}$$ be a quadrivalent interp. s.t. $$\mathcal{I}(\alpha) = \mathcal{J}(\alpha)$$ for each sentence letter $$\alpha$$. Then clearly $$LPV_{\mathcal{I}}(\psi) = FDEV_{\mathcal{J}}$$ for any wff $$\psi$$, since when the LSs take just the values $$1, b, 0$$ FDE truth tables are identical to LP truth tables. So therefore $$FDEV_{\mathcal{J}}(\gamma)$$ is designated for all $$\gamma \in \Gamma$$, and $$FDEV_{\mathcal{J}}(\phi) = 0$$. ### Supervaluationism • used to deal with vagueness • goal is to define sharp boundaries • Definitions: precisification $$\mathcal{I}$$ is a trivalent interp, $$\mathcal{C}$$ is a precisification of $$\mathcal{I}$$ iff $$\mathcal{C}$$ is a classical PL-interp such that for any sl, $$\alpha$$, if $$\mathcal{I}(\alpha) = 1$$ then $$\mathcal{C} = 1$$, and if $$\mathcal{I}(\alpha) = 0$$, then $$\mathcal{C}(\alpha) = 0$$ supervaluation Where $$\phi$$ is a wff and $$\mathcal{I}$$ is an inter, the supervaluation is the function $$SV_{\mathcal{I}}(\phi)$$ that assigns $$0, 1, \#$$ to each wff as follows: $SV_{\mathcal{I}}(\phi) = \left\{ \begin{matrix} 1 & \forall \mathcal{C} V_{\mathcal{C}}(\phi) = 1 \\ 0 & \forall \mathcal{C} V_{\mathcal{C}}(\phi) = 0 \\ \# & \text{Otherwise} \end{matrix}\right.$ supertruth, superfalsity Where $$\mathcal{I}$$ is a trivalent interp, valuations for $$\phi$$ for all $$\mathcal{C}$$ are 0 (superfalse) or 1 (supertrue) • vagueness can be an issue – puts sharp boundaries on grey areas, or can have issues with having good enough vagueness • supervaluations are non-truth-functional • Supervaluations do agree on tautologies, all classical tautologies are supertrue • Ex: $$\alpha \land \beta$$, $$\gamma \land \delta$$, $$SV_{\mathcal{I}}(\alpha) = SV_{\mathcal{I}}(\gamma) = \#$$, $$SV_{\mathcal{I}}(\beta) = SV_{\mathcal{I}}(\delta) = \#$$ • let $$\alpha = P$$, $$\beta = \lnot P$$, $$\gamma = P$$, $$\delta = Q$$ • $$\mathcal{I}(P) = \#$$ • $$\mathcal{I}(Q) = \#$$ • $$SV_{\mathcal{I}}(\alpha) = SV_{\mathcal{I}}(P) = \#$$ • $$SV_{\mathcal{I}}(\beta) = SV_{\mathcal{I}}(\lnot P) = \#$$ • $$SV_{\mathcal{I}}(\delta) = SV_{\mathcal{I}}(Q) = \#$$ • $$SV_{\mathcal{I}}(\alpha \land \beta) = SV_{\mathcal{I}}(P \land \lnot P) = 0$$ • $$SV_{\mathcal{I}}(\gamma \land \delta) = SV_{\mathcal{I}}(P \land Q) = \#$$ • For $$\lor$$ • $$SV_{\mathcal{I}}(\alpha) = SV_{\mathcal{I}}(\gamma)$$ • $$SV_{\mathcal{I}}(\beta) = SV_{\mathcal{I}}(\delta)$$ • $$SV_{\mathcal{I}}(\alpha \lor \beta) \neq SV_{\mathcal{I}}(\gamma \lor \delta)$$ • $$\alpha = P$$, $$\beta = \lnot P$$, $$\gamma = P$$, $$\delta = Q$$, $$\mathcal{I}(P) = \#$$, $$\mathcal{I}(Q) = \#$$ • $$SV_{\mathcal{I}}(\alpha) = SV_{\mathcal{I}}(\gamma) = SV_{\mathcal{I}}(P) = \#$$ • $$SV_{\mathcal{I}}(\beta) = SV_{\mathcal{I}}(\lnot P) = \#$$ • $$SV_{\mathcal{I}}(\delta) = SV_{\mathcal{I}}(Q) = \#$$. • $$SV_{\mathcal{I}}(\alpha \lor \beta) = SV_{\mathcal{I}}(P \lor \lnot P) = 1$$ • $$SV_{\mathcal{I}}(\gamma \lor \delta) = SV_{\mathcal{I}}(P \lor Q) = \#$$ • $$\models_{PL} \phi$$ iff $$\models_{S} \phi$$, and $$\Gamma \models_{PL} \phi$$ iff $$\Gamma \models_{S} \phi$$ • Addition of $$\Delta$$ operator changes classical principles • Conditional proof is no longer valid, semantic analog of deduction theorem • And Contraposition and reductio are also no longer useable ## Lecture 18: 2018-03-13 – Probabilities • Definitions sample space set of all possible discrete outcomes, assuming sample space is finite for simplicity event a subset of a finite sample space probability function a function from the subsets of the sample space $$S$$ (from events) to the closed interval [0, 1], $$P: \mathcal{P}(S) \to [0, 1]$$ • Axioms: let $$S$$ be a finite sample space, and $$P$$ be a probability function on subsets of $$S$$ 1. for any event $$A \subseteq S$$, $$P(A) \geq G$$. 2. $$P(S) = 1$$ 3. If $$A$$ and $$B$$ are mutually exclusive events in $$S$$, then $$P(A \cup B) = P(A) + P(B)$$ • On propositions $$P^{\prime}$$ is a variant of $$P$$, for any $$o \in S$$, and forr any events $$A, B \subseteq S$$ • $$P^{\prime}(o) = P(\{o\}^{})$$ • $$P^{\prime}(o \in A) = P(A)$$ • $$P^{\prime}(o \not\in A) = P(-A)$$ • $$P^{\prime}(o \in A \land o \in B) = P(A \cap B)$$ • $$P^{\prime}(o \in A \lor o \in B) = P(A \cup B)$$ • Then • $$P(A) \geq 0$$ • If $$A$$ is a tautology, $$P(A) = 1$$ • If $$A$$ and $$B$$ are mutually exclusive, $$P(A \lor B) = P(A) + P(B)$$ • Contradictions get 0 • Conditional probability: $$P(H|E)$$ (probability of $$H$$ given $$E$$, prob. of $$H$$ conditional on $$E$$) • $$H$$ for hypothesis • $$E$$ for evidence • $$P(H|E) = \frac{P(H \cap E)}{P(E)}$$, when $$P(E) > 0$$ • $$A$$ and $$B$$ are probabilistically independent iff $$P(A \cap B) = P(A) \cdot P(B)$$, true iff $$P(A|B) = P(A)$$ • $$|$$ in this case is not the Sheffer Stroke • Bayes’ Theorem • $$P(H|E) = P(E|H)\frac{P(H)}{P(E)}$$ – Original • $$P(H_i|E) = \frac{P(H_i)\cdot(P(E|H_i))}{P(H_1)P(E|H_1)+\cdots+P(H_n)P(E|H_n)}$$ – Total probabilities • $$\frac{P(H_1|E)}{P(H_2|E)} = \frac{P(H_1)}{P(H_2)} \times \frac{P(E|H_1)}{P(E|H_2)}$$ – Odds version (posterior odds is prior odds times likelihood ratio) ### Mini-proofs 1. $$P(\lnot \alpha) = 1 - P(a)$$ • By 2, $$P(\alpha \lor \lnot \alpha) = 1$$ • By 3, $$P(\alpha) + P(\lnot \alpha) = 1$$, $$P(\lnot \alpha) = 1 - P(\alpha)$$ 2. If $$\alpha$$ is a contradiction, then $$P(\alpha) = 0$$ • If $$\alpha$$ is a contradiction, then $$\lnot \alpha$$ is a tautology. Then, by Q1, $$P(\lnot \alpha) = 1 - P(\alpha)$$, by 2, $$P(\lnot \alpha) = 1$$. Therefore, $$P(\alpha) = 0$$ 3. $$0 \leq P(\alpha) \leq 1$$ • By 1, $$0 \leq P(\alpha)$$. • By Q1, $$P(\lnot \alpha) = 1 - P(\alpha) \geq 0$$. By 1, P(\lnot α) ≥ 0$, $$1 - P(\alpha) \geq 0$$, $$1 \geq P(\alpha)$$
4. If $$\alpha$$ and $$\beta$$ are semantically equivalent, then $$P(\alpha) = P(\beta)$$
• $$P(\alpha \lor \lnot \beta) = P(\alpha) + P(\beta)$$ by 3
• $$P(\lnot \beta) = 1 - P(\alpha)$$
• $$1 - P(\beta) = 1 - P(\alpha)$$
• $$P(\alpha) = P(\beta)$$

### Exercises

• Standard 52 card, what are probabilities
• either face or 10 – 4/13
• not diamond – 3/4
• either spade or face card – 1/4 + 3/13 - 3/52 = 11/26
• Two cards drawn, standard 52 deck
• h1 – draw heart first time
• h2 – draw heart second time
• two hearts w/ replacement – $$P(h1 \cap h2) = P(h1)P(h2) = 1/16$$
• two hearts w/o replacement – $$P(h1 \cap h2) = P(h1)P(h2|h1) = 1/17$$
• two cards not heart w/ replacement – $$P(-h1 \cap -h2) = P(-h1)P(-h2) = 3/4 \cdot 3/4 = 9/16$$
• two cards not heart w/o replacement – $$P(-h1 \cap -h2) = P(-h1)P(-h2|-h1)$$
• Heat lamps. 3% of production batches of Tropicana heat lamps fall below quality standards. 6% of the batches of Florida are below quality standards. A hardware store buys 40% from Tropicana, 60% from Florida
• D – defective
• T – Tropicana
• F – Florida
• P(D|T) = .03
• P(D|F) = .06
• P(T) = .4
• P(F) = .6
• Taken at random is both tropicana and defective $$P(T \cap D) = .4 * .03 = .012$$
• Taken at random and below quality standards, $$P(D) = P(T \cap D) + P(F \cap D) = 0.012 + 0.036 = 0.048$$
• $$P(T\cap D) / P(D) = .012/.048 = 0.25$$

### Tree Method

• Start at 1, split on mutual exclusivity, w/ nodes as values, and terminals being all preceding, multiply

## Lecture 19: 2018-03-15 – Probabilities continued

### HW

• $$P(\alpha \lor \beta) = P(\alpha) + P(\beta) - P(\alpha \land B)$$
• $$P(\alpha \lor \beta) = P((\alpha \land \beta) \lor (\alpha \land \lnot \beta) \lor (\lnot\alpha \land \beta))$$ (Q4)
• $$= P(\alpha \land \beta) + P(\alpha \land \lnot \beta) + P(\lnot\alpha \land \beta)$$ (Q9)
• $$= P(\alpha) + P(\lnot \alpha \land \beta)$$ (Q5)
• $$P(\alpha) + (P(\beta \land \alpha) - P(\beta \land \alpha) + P(\lnot \alpha \land \beta))$$
• $$P(\alpha) + (P(\beta \land \alpha) + P(\lnot \alpha \land \beta) - P(\beta \land \alpha))$$
• $$P(\alpha) + (P(\beta \land \alpha) + P(\beta \land \lnot \alpha) - P(\alpha \land \beta))$$ (Q4)
• $$P(\alpha) + P(\beta) - P(\alpha \land \beta)$$ (Q5)

### Probabilities

• Red and Black Cards
• three cards, one red on both sides, black on both sides, and one with a red side and one with a black side
• $$R$$ – red-red selected
• $$B$$ – black-black
• $$M$$ – red-black
• $$P(R) = P(B) = P(M) = \frac{1}{3}$$
• $$E$$ – Red side is up
• $$P(B|E) = 0$$
• $$P(E|R) = 1$$
• $$P(E|B) = 0$$
• $$P(E|M) = \frac{1}{2}$$
• $$P(R|E) = \frac{P(R)P(E|R)}{P(R)P(E|R) + P(B)P(E|B) + P(M)|P(E|M)} = \frac{2}{3}$$
• $$P(M|E) = \frac{P(M)P(E|M)}{P(R)P(E|R) + P(B)P(E|B) + P(M)|P(E|M)} = \frac{1}{3}$$
• The triangle
• $$T$$ – Lives in triangle
• $$E$$ – Child tests positive for toxic metals
• $$T$$ – 0.02
• $$E$$ – 0.14, 0.0028
• $$\lnot E$$ – 0.86
• $$\lnot T$$ – 0.98
• $$E$$ – 0.01, 0.0098
• $$\lnot E$$ – 0.99
• $$P(T|E) = \frac{P(T \cap E)}{P(T \cap E) + P(\lnot T \cap E)} = \frac{2/9}$$
• Drunk Driving
• $$D$$ – Suspect Drunk when stopped
• $$E_1$$ – Suspect fails breathalyzer
• $$E_2$$ – Suspect passes blood test
• Want $$P(D|E_1 \cap E_2$$
• 1
• $$D$$ – 0.9
• $$E_1$$ (0.8) – 0.72
• $$E_2$$ (0.1 – Sobered up) – 0.072
• $$\lnot E_2$$ (0.9) – 0.648
• $$\lnot E_1$$ (0.2) – 0.18
• $$E_2$$
• $$\lnot E_2$$
• $$\lnot D$$ – 0.1
• $$E_1$$ (0.2) – 0.2
• $$E_2$$ (1) – 0.2
• $$\lnot E_2$$ (0) – 0
• $$\lnot E_1$$ (0.8) – 0.8
• $$E_2$$
• $$\lnot E_2$$
• $$P(D|E_1 \cap E_2) = \frac{P(D\cap E_1 \cap E_2)}{P(D\cap E_1 \cap E_2) + P(\lnot D \cap E_1 \cap E_2)} = \frac{18}{23}$$

### Exercises III

• Problem 1
• $$E_1$$ – Dr. A doesn’t diagnose cancer
• $$E_2$$ – Dr. B diagnoses cancer
• $$C$$ – Carl has cancer
• 1
• $$C$$ – $$p$$
• $$E_1$$ (0.3) – $$0.3p$$
• $$E_2$$ (1) – $$0.3p$$
• $$\lnot E_2$$ (0) – 0
• $$\lnot E_1$$ (0.7) – $$0.7p$$
• $$E_2$$ (1) – $$0.7p$$
• $$\lnot E_2$$ (0) – 0
• $$\lnot C$$ – $$1 - p$$
• $$E_1$$ (1) – $$1 - p$$
• $$E_2$$ (0.3) – $$0.3(1 - p)$$
• $$\lnot E_2$$ (0.7) – $$0.7(1 - p)$$
• $$\lnot E_1$$ (0) – 0
• $$E_2$$
• $$\lnot E_2$$
• $$P(C|E_1 \cap E_2) = p$$

## Lecture 20: 2018-03-27 – Modal Logics – Semantics

• an extension of PL, introduces $$\box$$ and semantics for it

### Grammar

• Sentence Letters $$P, Q, R, \ldots$$ with or without subscripts
• Connectives $$\{\implies, \lnot, \square\}$$
• Parens
• WFF Rules
1. Sentence letters are wffs
2. If $$\phi$$ and $$\psi$$ are wffs, then $$\lnot \phi$$, $$(\phi \to \psi)$$ and $$\square \phi$$ are wffs.
3. Only strings that can be shown to be wffs using 1 and 2 are wffs.
• Defined connectives
• $$\Diamond\phi = \lnot\square\lnot\phi$$
• $$\phi \prec \psi = \square(\phi \to \psi)$$
• $$\land$$, $$\lor$$, $$\iff$$ as in classical propositional logic

### Semantics

MPL Model
an ordered triple $$\langle\mathcal{W}, \mathcal{R}, \mathcal{I}\rangle$$
$$\mathcal{W}$$
A non-empty set of objects (possible worlds)
$$\mathcal{R}$$

### Testing validity

• Box-diagramming for identifying which systems (if any) a wff is valid in
• Given a wff, put in in a large box, labeld $$r$$. Try to make the wff fales at $$r$$. If unable, it’s valid in whatever system in use
• Write 0 over main connective, and make relevant operands true/false
• put asterisks under connectives for existential commitments ($$\Diamond$$)
• For each existential commiment, have $$r$$ see a world where $$P$$ is true, and another where $$P$$ is false. This is a $$K$$ counter-model (a $$K$$ model in which the wff is not valid)
• K counter model – $$\mathcal{W} = \{r, a, b\}$$, $$\mathcal{R} = \{\langle r, a \rangle, \langle r, b \rangle\}$$, $$\mathcal{I}(P, a) = 1$$ all else 0
• Then try reflexivity
• $$\mathcal{R}$$ gets extended w/ reflexive pairs
• May be an S4 counter model – but make sure there aren’t three-step journeys without shortcuts
• And add symmetric pairs for B
• Then check for transitivity for S5

## Lecture 21: 2018-03-29 – Modal Logics, continued

### Box diagrams

• Steps
1. Place in a box and make false
2. Enter forced truth values
3. Enter daggers and after all forced moves are over
4. Enter asterisks
5. Discharge asterisks (do bottom first)
7. This is the model
• 6.3a 58
• $$K$$ counter, $$\mathcal{W} = \{r\}$$, $$\mathcal{R} = \emptyset$$, $$\mathcal{I}(\alpha, r) = 0$$ for every SL $$\alpha$$
• $$D$$ counter (also $$K$$), $$\mathcal{W} = \{r, a, b\}$$, $$\mathcal{R} = \{\langle r,a \rangle, \langle a,b \rangle, \langle b,b \rangle\}$$, $$\mathcal{I}(Q,a) = \mathcal{I}(P,b) = 1$$; all else $$0$$
• $$\models_T \square[P \to \Diamond (Q \to R)] \to \Diamond[Q \to (\square P \to \Diamond R)]$$
• $$\phi$$ is the original.
• Suppose for a contradiction that $$\not\models_T$$. Then, there is a $$T$$ model $$\mathcal{M}$$, where $$\mathcal{M} = \langle\mathcal{W}, \mathcal{R},\mathcal{I}\rangle$$, s.t., $$\exists w \in \mathcal{W} V_{\mathcal{M}}(\phi, w) = 0$$. (Subscript $$\mathcal{M}$$ omitted hereafter.) Then $$V(\square[P\to\Diamond(Q \to R)],w) = 1$$ and $$V(\Diamond[Q \to (\square P \to \Diamond R)], w) = 0$$. As $$\mathcal{R}$$ is reflexive, $$\mathcal{R}ww$$. So $$V(P\to\Diamond(Q\to R), w) = 1$$ and $$V(Q \to (\square \to \Diamond R), W) = 0$$. $$\therefore V(Q, w) = 1$$ and $$V(\square P \to \Diamond R, w) = 0$$, $$V(\square P, w) = 1$$ and $$V(\diamond P, w) = 0$$, since $$\mathcal{R}ww$$, $$V(P,w)=1$$. Then, $$V(\Diamond(Q \to R), w) = 1$$. Then $$\exists v \in \mathcal{W}$$ s.t. $$\mathcal{R}wv$$ and $$V(Q \to R, v) = 1$$. So $$\mathcal{R}wv$$ and $$V(\Diamond R, w) = 0$$, so $$V(R,v) = 0$$. Togetther, $$V(Q, v) = 0$$, then $$V(Q \to (\square P \to \Diamond R), v) = 1$$. But, since $$\mathcal{R}wv$$ and $$V(\Diamond[Q \to (\square P \to \Diamond R)] ,w) = 0$$ and $$V(Q \to (\square P \to \Diamond R), v) = 0$$. Contradiction!
   1*0  1 1  1    0   0  0* 1  0   1*1 0 0*0
b[P -> d (Q -> R)] -> d [Q -> (b P -> d R)]-+
*                     |            +-+
|
|                1               1 0   1*  0  0*
+--------->  a P -> d (Q -> R)   Q -> (b P -> R)  (A T model)
1
Q -> R

1*                  0  0*
b [P -> d (Q -> R)] -> d [Q -> (b P -> d R)]
|

0 1                  1 0   1*  0  0*
a: P -> d (Q -> R)      Q -> (b P -> d r)
\d                      |

1   0
b: P   R  -+
+-+


• 6.3 c
• B, T, D, K countermodel: $\mathcal{W} = \{r, a, b\}, $$\mathcal{R} = \{(r,r), (a,a), (b,b), (r,a), (a,b), (b,a), (a,r)\}$$, $$\mathcal{I}(Q, b) = \mathcal{I}(P, r) = 1$$, all else $$0$$ • Validity proof for $$S4$$ $$\models_{S4} \phi$$ $$\phi = \square(P \lor \Diamond Q) \to (\Square P \lor \Diamond Q)$$. Suppose for a contradiction that $$\not\models_{S4} \phi$$ Then there is an $$S4$$ model $$\mathcal{M} (= \langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle)$$ s.t. $$\exists w \in \mathcal{W} V_{\mathcal{M}}(\phi, w) = 0$$ (subscripte ommited hereafter) 1. $$V(\square (P \lor \Diamond Q), w) = 1$$ 2. $$V(\square P \lor \Diamond Q, w) = 0$$ 3. $$V(\square P, w) = 0$$ (2) 4. $$V(\Diamond Q, w) = 0$$ (2) 5. $$\exists x \in \mathcal{W}$$ s.t. $$\mathcal{R}wx$$ and $$V(P, x) = 0$$ (3) 6. (1, $$\mathcal{R}wx$$), $$V(P \lor \Diamond Q, x) = 1$$. 7. (5, 6) $$V(\Diamond Q, x) = 1$$ 8. (7) $$\exists y \in \mathcal{W}$$ s.t. $$\mathcal{R}xy$$ and $$V(Q, y) = 1$$. 9. $$\mathcal{R}wx$$ and $$\mathcal{R}xy$$, so by transitivity, $$\mathcal{R}wy$$ 10. So, by (4), $$V(Q, y) = 0$$. 11. Then by 8 and 10, we have a contradiction. B, T, D, K countermodel: 1* 0 1 1 0 0 0 0* r: b (P v d Q) -> (b P v d Q) + * +-+ ^ | v 0 1 0 a: P P v d Q + * +-+ ^ | v 1 b: Q + +-+ 1* 0 1 1 0 0 0 0* r: b (P v d Q) -> (b P v d Q) + * +-+ | | | | v | 0 1 0 | a: P P v d Q + | * +-+ | | | | | v | 1 | b: Q + <----------------+ Cannot be added -- d Q is false at R. Therefore valid in S4. +-+  ## Lecture 22: 2018-04-03 – Modal Logic, Axiomatic Systems ### Axiomatic Systems • All have PL1-PL3 • S5 is strongest • Also has MP • And NEC (necessitation), from $$\phi$$, you can know $$\square\phi$$ • $$K$$ (short for Kripke) (K) $$\square (\phi \to \psi) \to (\square\phi \to \square \to \psi)$$ • $$D$$ (Deontic) also includes (K) and (D) $$\square\phi \to \Diamond\phi$$ ($$\Diamond\top$$) • $$T$$ System K and (T) $$\square\phi\to\phi$$ ($$\phi \to \Diamond\phi$$) • $$S4$$, System T and (4) $$\square\phi\to\square\square\phi$$ ($$\Diamond\Diamond\phi \to \Diamond\phi$$) • $$B$$, System B and (B) $$\Diamond\square\phi \to \phi$$ ($$\phi \to \square\Diamond\phi$$) • $$S5$$, System T, plus (5) $$\Diamond\square\phi \to \square\phi$$ ($$\Diamond\phi \to \square\Diamond\phi$$) • System T plus (5) = System T plus (4) and (B) • $$\mathcal{R}$$ is euclidean if $$\forall w,x,y \in \mathcal{W} ((\mathcal{R}wx \land \mathcal{R}wy) \to \mathcal{R}xy)$$ • $$\mathcal{R}$$ is reflexive and Euclidean iff it is reflexive, symmetric, and transitive ### Metatheory #### Soundness • $$K + \Gamma$$ – the axiomatic system that has the same rules as $$K$$ (MP and NEC) and has all axioms of $$K$$ plus the members of $$\Gamma$$ • normal modal logic – A system of modal logic that has at least all the theorems of $$K$$ • Lemma on Soundness of Axioms – Lemma 6.2, All instances of the PL- and K-axiom schemas are valid in all MPL models • Proof of MPL validity of PL, p174 • Proof of MPL validity of K, left as exercise 6.2 • Proof: Suppose not. Then for some $$MPL$$ wffs $$\phi$$ and $$\psi$$, there is an MPL model $$\mathcal{M}$$ ($$= \langle\mathcal{W}, \mathcal{R}, \mathcal{I}\rangle$$) s.t. $$\square(\phi \to \psi) \to (\square\phi\to\square\psi)$$ is not valid in $$\mathcal{M}$$. Therefore, $$\exists w\in\mathcal{W}$$ s.t. $$V_{\mathcal{M}}(\square(\phi \to \psi) \to (\square\phi\to\square\psi), w) = 0$$ (subscript $$\mathcal{M}$$ ommitted). 1. $$V(\square(\phi\to\psi),w) = 1$$, $$\to$$ 2. $$V(\square\phi \to \square\psi, w) = 0$$ 3. $$V(\square\phi, w) = 0$$ 2 and $$\to$$ 4. $$V(\square\psi, w) = 1$$ 5. $$V(\psi, v) = 0$$ by 4 and $$\square$$, $$\exists v \in \mathcal{W}$$ 6. $$V(\phi, v) = 1$$ 7. $$V(\phi \to \psi, v) = 1$$. 7, 6, 5 gives contradiction • Lemma on Soundness of Rules – Lemma 6.3, For every MPL model $$\mathcal{M}$$, MP and NEC preserve validity in $$\mathcal{M}$$ • Soundness for $$K$$ – for any wff $$\phi$$, if $$\vdash_k\phi$$, then $$\models_k\phi$$. • Proof: by induction on $$n$$ (number of lines) on an axiomatic proof of $$\phi$$ in $$K$$. • Base Case: $$n = 1$$ $$\phi$$ is an axiom. $$\phi$$ is an instance of PL1-3 or $$K$$. All such instances are valid in all MPL models, by Lemma 6.2. $$\therefore\models_{K}\phi$$ • Inductive step: $$n = k + 1$$, $$k \in \mathcal{N}^+$$ 1. $$\phi$$ is an axiom. Proved as in base case. 2. $$\phi$$ is derived from either one or two previous lines by either NEC or MP. By the IH, the previous lines are valid in all MPL-models. By Lemma 6.3, NEC and MP are validity preserving. Hence, $$\models_{K}\phi$$. • To make for other systems, add an extra case for the relevant additional axiom schema. • $$T$$ $$\square\phi\to\phi$$ Suppose for a contradiction, that for some MPL wff $$\phi$$, $$\square\phi\to\phi$$ is not valid in some reflexive MPL model $$\mathcal{M}$$ ($$=\langle\mathcal{W},\mathcal{R},\mathcal{I}\rangle$$). So there exists $$w \in \mathcal{W}$$, s.t. $$V_{\mathcal{M}}(\box\phi \to \phi, w) = 0$$ (subscript ommited hereafter). 1. $$V(\square\phi, w) = 1$$ 2. $$V(\phi, w) = 0$$ 3. $$\mathcal{R}ww$$ 4. $$V(\phi, w) = 1$$ By 3 and 1, contradicts 2. • General Soundness Theorem (6.1, p173) – If $$\Gamma$$ is any set of modal wffs and $$\mathcal{M}$$ is an MPL-model in which each wff in $$\Gamma$$ is valid, then every theorem of $$K+\Gamma$$ is valid in $$\mathcal{M}$$. • Proof is by induction on number of steps in proof of a theorem in $$K+\Gamma$$. Use the two above lemmas. #### Completeness • PL toolkit is available and the same, along with the cut theorem for PL and deduction theorem for MPL • Provability from a set – a wff $$\phi$$ is provable in a system $$S$$ for a set $$\Gamma$$ ($$\Gamma\vdash_S\phi$$) iff either $$\Gamma = \emptyset$$ and $$\vdash_S\phi$$ or for some $$\gamma_1, \ldots \gamma_n \in \Gamma$$, $$\vdash_S ((\gamma_1\land\cdots\land\gamma_n) \to \phi)$$ • S-consistency – A set of wffs $$\Gamma$$ is$S$-inconsistent iff $$\Gamma\vdash_{S}\bot$$. A set is $$S$$ consistent iff not$S$-inconsistent. • Deduction theorem – if $$\Gamma\cup\{\phi\}\vdash_S\psi$$, then $$\Gamma\vdash_S(\phi \to \psi)$$ • Proof: Suppose the$Γ∪\{φ\}\vdash.$$$\Gamma\cup\{\phi\}$$ is clearly non-empty, so by the new def’n of provability from a set, for some wffs $$\alpha_1, \ldots, \alpha_n \in \Gamma\cup\{\phi\}$$, $$\vdash_S (\alpha_1 \land \cdots \land \alpha_n) \to \psi$$. Either then, $$\phi$$ is one of these, $$\alpha_k$$ or it’s not. 1. Suppose $$\phi = \alpha_k$$. Then $$\vdash_S (\alpha_1 \land \cdots \land \alpha_{k - 1} \land \alpha_{k + 1} \land \cdots \land \alpha_n) \to (\phi \to\psi)$$. By PL. Therefore $$\Gamma\vdash_S(\phi\to\psi)$$ 2. Suppose $$\phi$$ is not any of the$α$s. Then $$\alpha_1,\ldots,\alpha_n \in \Gamma$$. $$\vdash(\alpha_1 \land \cdots \land \alpha_n) \to (\phi \to \psi)$$, by PL. ## Lecture 23: 2018-04-05 – Modal Logic, Axiomatic Systems – Metatheory ### Completeness • Lemma on Feautres of Maximal S-consistent Sets (Lemma 6.5): Where $$\Gamma$$ is a maximal S-consistent set of MPL-wffs 6.5a For any MPL-wff $$\phi$$, exactly one of $$\phi$$ and $$\lnot\phi$$ is a member of $$\Gamma$$ 6.5b $$(\phi \to \psi) \in \Gamma$$ iff either $$\phi \not\in \Gamma$$ or $$\psi \in \Gamma$$ 6.5c If $$\vdash_S \phi$$, then $$\phi \in \Gamma$$. Proof: If $$\vdash_S\phi$$, then $$\vdash_S(\lnot\phi\to\bot)$$, since $$S$$ includes PL. $$\Gamma$$ is S-consistent, so $$\lnot\phi\not\in \Gamma$$. $$\Gamma$$ is maximal, so $$\phi\in\Gamma$$. 6.5d If $$\vdash_S(\phi\to\psi)$$ and $$\phi \in \Gamma$$, then $$\psi \in \Gamma$$. Proof: Suppose $$\vdash_S(\phi\to\psi)$$ and $$\phi \in \Gamma$$. By the former and lemma 6.5c, $$(\phi \to \psi) \in \Gamma$$. By lemma 6.5b, either $$\phi \not\in \Gamma$$ or $$\psi \in \Gamma$$. Since $$\phi \in \Gamma$$, $$\psi \in \Gamma$$. • $$\square^{-}(\Gamma)$$ – The set off wffs $$\phi$$ such that $$\square\phi\in\Gamma$$. Read “the box-strip of $$\Gamma$$”. • Lemma on Box-Strip (Lemma 6.6) – If $$\Delta$$ is a maximal S-consistent set of MPL-wffs containing $$\lnot\square\phi$$, then there exists a maximal S-consistent set of wffs, $$\Gamma$$, such that $$\square^{-}(\Delta) \cup \{\lnot\phi\} \subseteq \Gamma$$. Proof: • Show that $$\square^{-}(\Delta) \cup \{\lnot\phi\}$$ is S-consistent. Suppose for a contradiction, that $$\square^{-}(\Delta) \cup \{\lnot\phi\} \vdash_S \bot$$. Then $$\square^{-}(\Delta)\vdash_S(\lnot\phi\to\bot)$$ (subscript $$S$$ ommitted hereafter) by the (new) deduction theorem. So $$\square^{-}(\Delta) \vdash \phi$$ by PL. Either $$\square^{-}(\delta) = \emptyset$$ or not. Suppose$\square- = ∅. Then $$\vdash\phi$$ by def’n of S-provability from a set (first disjunct). Then $$\vdash\square\phi$$ by rule NEC. Then $$\square\phi \in \Delta$$ by lemma 6.5c. But $$\lnot\square\phi\in\Delta$$. Contradiction with lemma 6.5a. Thus, $$\square^{-}(\Delta) \neq \emptyset$$. By def’n of S-provability from a set (second disjunct). $$\exists\delta_1, \ldots, \delta_n \in \square^{-}^{}(\Delta)$$ s.t. $$\vdash(\delta_1\land\cdots\land\delta_n)\to\phi$$. So $$\vdash\square((\delta_1\land\cdots\delta_n)\to\phi)$$ by NEC. This means that $$\vdash\square(\delta_1 \to (\delta_2\to\cdots(\delta_n\to\phi)\ldots))$$. Then $$\vdash(\square\delta_1\to(\square\delta_2\to\cdots(\square\delta_n\to\square\phi)\ldots))$$ by $$n$$ applications of axiom schema $$K$$ and PL. Thus, $$\vdash(\square\delta_1\land\cdots\land\square\delta_n\land\lnot\square\phi)\to\bot$$ by PL. But $$\delta_1,\ldots,\delta_n \in \square^{-}(\Delta)$$ so $$\square\delta_1,\ldots,\square\delta_n\in\Delta$$ by def’n $$\square^{-}(\Delta)$$. Also $$\lnot\square\phi\in\Delta$$. $Δ\vdash\bot. Contradiction! Thus $$\square^{-}(\Delta)\cup \{\lnot\phi\}$$ is S-consistent. Step 2: By Lindenbaum’s Lemma, $$\exists$$ a mmaximal S-consistent set $$\Gamma$$ s.t. $$\square^{-}(\Delta)\cup\{\lnot\square\}\subseteq\Gamma$$. • Canonical Model – The canonical model for system $$S$$ is the MPL-model $$\langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$$ where: • $$\mathcal{W}$$ is the set of al maximal S-consistent sets of wff • $$\mathcal{R}wx$$ iff $$\square^{-}(w) \subseteq x$$ • $$\mathcal{I}(\alpha, w) = 1$$ iff $$\alpha \in w$$ for each sentence letter $$\alpha$$ and each $$w \in \mathcal{W}$$ • Beware! • The second clause says that $$\mathcal{R}wx$$ iff for each wff $$\square\phi$$ in $$w$$, $$\phi$$ is in $$x$$. • The definition of $$\mathcal{R}$$ says nothing about the properties of $$\mathcal{R}$$. So the definition of the canonical model for S4 doesn’t state that the accessibility relation is reflexive annd tranisitve, but this must be prove. • From $$\mathcal{R}$$: If $$\square\phi$$ is a member of world $$w$$ in the canonical model for S, then $$\phi$$ is a member of every world accessible from $$w$$ • Lemma on Box-Strip: If $$\Diamond\phi$$ is a member of world w$ in the canonical model for S, then $$\phi$$ is a member of some world accessible from $$w$$.
• Theorem on Canonical Models (Theorem 6.7, TCM) – Where $$\mathcal{M}$$ ($$= \langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$$) is the canonical model for any normal modal system S, for any wff $$\phi$$ and any $$w \in \W$$, $$V_{\mathcal{M}}(\phi, w) = 1$$ iff $$\phi \in w$$. Proof by induction on $$n$$ the number of connectives in $$\phi$$: Base case: $$n = 0$$ $$\phi$$ is a sentence letter. TFAE:

• $$V_{\mathcal{M}}(\phi, w) = 1$$ (Subscript $$\mathcal{M}$$ ommitted hereafter)
• $$\mathcal{I}(\phi,w) = 1$$ (def’n of MPL-val for sentence letters)
• $$\phi\in\w$$ (def’n of canonical model)

Inductive Step: $$n = k + 1$$ ($$k \in \mathbb{N}$$). 3 cases

1. $$\phi = \lnot\psi$$ TFAE:
• $$V(\phi, w) = 1$$
• $$V(\lnot\psi,w) = 1$$ $$\phi = \lnot \psi$$
• $$V(\psi,w) = 0$$ def’n of $$\lnot$$
• $$\psi \not\in w$$ IH
• $$\lnot\psi \in w$$ ($$\phi = \lnot\psi$$)
2. $$\phi = \psi \to \chi$$ TFAE:
• $$V(\phi, w) = 1$$
• $$V(\psi \to \chi, w) = 1$$ $$\phi = \psi \to \chi$$
• $$V(\psi, w) = 0$$ or $$V(\chi, w) = 1$$ definition of $$\to$$
• $$\psi \not\in w$$ or $$\chi \in w$$
• $$\psi \to \chi \in w$$ lemma 6.5b
• $$\phi \in w$$ ($$\phi = \psi \to \chi$$)
3. $$\phi = \square\psi$$ N.T.S: $$V(\square\psi,w) = 1$$ iff $$\square\psi \in w$$
• ($$\Rightarrow$$) Suppose $$V(\square\psi,w) = 1$$ Then $$\forall v \in \mathcal{W}$$ s.t. $$\mathcal{R}wv$$, $$V(\psi,v) = 1$$ By definition of $\square. Then $$\forall v \in \mathcal{W}$$ s.t. $$\mathcal{R}wv$$, $$\psi \in v$$ by IH ($$\*$$). Suppose for a contradicition that $$\square\psi \not\in w$$. Then $$\lnot\square\psi \in w$$ by lemma 6.5a. $$w$$ is a maximal S-consistent set, so by Lemma on Box-Strip, $$\square^{-}(w)\cup\{\lnot\square\psi} \subseteq \Gamma$$ for some maximal S-consistent set $$\Gamma$$. $$\Gamma \in \mathcal{W}$$ and $$\square^{-}(w) \subseteq \Gamma$$, so $$\mathcal{R}w\Gamma$$ by def’n of canonical model. So by ($$\*$$), $$\psi \in \Gamma$$, but $$\lnot\psi \in \Gamma$$. Contradiction with lemma 6.5a! Thus $$\square\psi \in \w$$ as required. • ($$\Leftarrow$$) Suppose $$\square\psi \in w$$ Then by definition of canonical model, $$\forall v \in \mathcal{W}$$ s.t. $$\mathcal{R}wv$$, $$\psi \in \w$$. (thus $$\square^{-}(w) \subseteq v$$) Then by IH, $$\forall v \in \mathcal{W}$$ s.t. $$\mathcal{R}wv$$, $$V(\psi, v) = 1$$. By definition of $$\square$$, $$V(\square\psi, w) = 1$$. • General Completeness Theorem (GCT, Corollary 6.8) – $$\phi$$ is valid in the canonical model for $$S$$ iff $$\vdash_S \phi$$. Proof in to directions, in each case using the theorem on canonical models. Refer to p181. Proof: Let $$\mathcal{M}$$ be the canonical model for S, where $$\mathcal{M} = \langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$$. • ($$\Rightarrow$$) Suppose $$\not\vdash_s \phi$$. Then $$\not\vdash \lnot\phi \to \bot$$ by PL. Thus $$\{\lnot\phi\}$$ is S-consistent. By Lindenbaum’s Lemma, $$\exists$$ maximal S-consistent set, call it $$w$$ s.t. $$\{\lnot\phi\}\subseteq w$$, i.e, $$\lnot\phi \in w$$. $$w \in \mathcal{W}$$, so by the TCM, $$V_{\mathcal{M}}(\lnot\phi, w) = 1$$ (subscript $$\mathcal{M}$$ ommitted herafter). Thus $$V(\phi, w) = 0$$ by def’n of $$\lnot$$. So $$\phi$$ is not valid in $$\mathcal{M}$$. • ($$\Leftarrow$$) Suppose $$\vdash_S \phi$$. Then by lemma 6.5c, $$\phi \in w$$ for any maximal S-consistent set w, i.e., any member of $$\mathcal{W}$$. By the TCM, $$V(\phi, w) = 1$$ forr all $$w \in \mathcal{W}$$. Therefore $$\phi$$ is valid in $$\mathcal{M}$$. • Using GCT to prove completeness of various systems: • Completeness theorem for K: $$\models_K \phi \implies \vdash_K\phi$$. Suppose $$\models_K\phi$$, i.e., $$\phi$$ is valid in all $$K$$ models. The canonical model for K is a K-model. So $$\phi$$ is valid in the canonical model for K. By GCT, $$\vdash_k\phi$$. • Completeness theorem for T: $$\models_T\phi \implies \vdash_T\phi$$ • Show that canonical model for T is a T-model,., I.e. reflexive Let $$\mathcal{M} = \langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$$ be the canonical model for T, and let $$w$$ be an arbitrary member of $$\mathcal{W}$$. We need to show that $$Rww$$, i.e., $$\square^{-}(w) \subseteq w$$. So let $$\phi$$ be an arbitrary element of $$\square^{-}(w)$$. $$\phi \in \square^{-}(w)$$. So $$\square\phi \in w$$, by def’n of box-strip. $$\vdash_T\square\phi \to \phi$$. (instance of T schema). By lemma 6.5d, $$\phi \in w$$. Thus $$\square^{-}(w)\subseteq w$$ Since $$w$$ was arbitrary, $$\mathcal{M}$$ is reflexive. • Suppose $$\models_T \phi$$, ie, $$\phi$$ is valid in all reflexive models. Then, by step 1, $$\phi$$ is valid in the canonical model for T. By GCT, $$\vdash_T\phi$$. ## Lecture 24: 2018-04-10 – Modal Logic, Applications ### Sider 6.1 • $$\models_O \phi$$ iff $$\models_{S5} \phi$$ • $$R$$ is total, then $$R$$ is reflexive, symmetric and transitive • Reverse does not hold • But equivalence relations are a superset of total relations • Then If $$\models_{S5} \phi$$, then $$\models_O \phi$$ • Prove $$\models_O\phi$$ then $$\models_{S5}\phi$$ by contrapositive Suppose $$\not\models_{}_{S5} \phi$$. Convert this S5-countermodel into an O-countermodel. $$\mathcal{M} = \langle\mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$$, $$V_\mathcal{M}(\phi, w) = 0$$ $$\mathcal{M}^{*}$$. Let $$\mathcal{W}^{*} = \{x \in \mathcal{W} : Rwx\}$$, $$\mathcal{R}^{*} = \mathcal{R} \cap (\mathcal{W}^{***} \times \mathcal{W}^{*}^{*})$$. Then, show by induction $$\forall x \in \mathcal{W}^{*}, \forall \psi V_{\mathcal{M}}(\psi, x) = V_{\mathcal{M}^{*}}(\psi, x)$$. Then apply the result, and $$V_{\mathcal{M}^*}(\phi, w) = 0$$ ### Deontic Logic • Grammar – PL plus $$O$$ for ought, $$M$$ for may, $$\lnot O \lnot \phi$$ • For some fixed agent $$S$$, “$$O\phi$$” means “S ought to see to it that $$\phi$$” • $$O\phi$$ means “It ought to be the case that $$\phi$$” • $$M\phi$$ means “It is acceptable for it to be the case that $$\phi$$” • Using MPL models, $$O$$ behaves like $$\square$$ • Accessibilty relation $$\mathcal{R}wv$$ iff everything at $$v$$ is in accordance with the norms in $$w$$ (or the norms binding agent $$S$$ in $$w$$) • Formal constraints given the interpretation • Seriality is requierd, then D • But sometimes $$O(O\phi \to \phi)$$, requires $$\mathcal{R}$$ to be shift-reflexive ($$\forall x \forall y (\mathcal{R}xy \to \mathcal{R} yy)$$) (Axiom U (for utopia)) • Worries • Does $$O$$ actually express what ’ought’ means? • Should the semantics/syntax for $$O$$ really be just like semantics/syntax $$\Square$$ • Never allows for genuine moral dilemmas (where you ought to A and also ought not to A) • Can’t express goodness but beyond the call of duty ### Epistemic Logic • Add to PL $$K$$, $$K\phi$$ – “It is known (perhaps by a fixed agent S) that $$\phi$$”, $$\lnot K \lnot\phi$$ – “As far as what is known is concerned, it might be true that $$\phi$$” (epistemic possibility) • $$K$$ is like $$\square$$ • $$\mathcal{R}wv$$ iff everything known in $$w$$ is true in $$v$$ • Knowledge implies truth, so $$\mathcal{R}$$ is reflexive, must be at least T. • $$KK$$ principle (positive introspection): $$K\phi \to KK\phi$$. Then S4, $$\mathcal{R}$$ must at least be transitive. (controversial) • Negative introspection $$\lnot K\phi \to K \lnot K\phi$$. (controversial) • Kripke semantics commits to a system at least as strong as $$K$$, so if $$\phi \models \psi$$, then $$K\phi \models K \psi$$, closure under logical entailment. We know all logical truths, and we know all consequences of anything we know. Proof: Let $$\mathcal{M}$$ be an arbitrary MPL-model. Suppose that $$\phi \models \psi$$. Where $$\mathcal{M} = \langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$$, then for any $$w \in \mathcal{W}$$, if $$V_{\mathcal{M}}(\phi, w) = 1$$, then $$V_{\mathcal{M}}(\psi, w) = 1$$. Now suppose that $$K\phi$$ is valid in $$\mathcal{M}$$. Then at any world $$v$$ s.t. $$\mathcal{R}wv$$, $$V(\phi, v) = 1$$. But then $$V(\psi, v) = 1$$ for any $$v$$ s.t. $$\mathcal{R}wv$$. Hence $$V(K\psi, w) = 1$$. $$\square$$ • Doxastic logic $$B\phi$$ “It is believed (perhaps by a fixed S) that φ”. Beliefe isn’t factive, so $$B\phhi \to \phi$$ doesn’t hold. $$T$$ isn’t valid. If the belief versions of positive and negative introspection are valid, then resulting system is K45. Beliefe may not actually be closed by conjunction ### Tense Logic • Primitives • $$G\phi$$ it is and will always be the case that $$\phi$$ (May have ’is’ removed) • $$H\phi$$ it is and halways has been the case that $$\phi$$ (ditto) • Defined • $$F\phi$$ it is or will at some point in the futurre be the case that $$\phi$$ (May have ’is’ removed) • $$P\phi$$ it is or was at some point in the past the case that $$\phi$$ (ditto) • Depending on interp (wether or not ’is’ is included) requires the semantics and logic to be adjusted. First interp • Models for PTL are similar to MPL • PTL-model – an ordered triple $$\langle \mathcal{T}, \leq, \mathcal{I} \rangle$$ • $$\mathcal{T}$$ is a non-empty set of objects (times) • $$\leq$$ at least as early as, binary relation over $$\mathcal{T}$$ • $$\mathcal{I}$$ two-place function, interpretation, similar to earlier. • If without ’is’, strictly less than, $$<$$ • $$V(G\phi, t) = 1$$ iff for every $$t^{\prime} \in \mathcal{T}$$ s.t. $$t \leq t^{\prime}$$, $$V(\phi, t^{\prime}) = 1$$ • $$V(H\phi, t) = 1$$ iff for every $$t^{\prime} \in \mathcal{T}$$ s.t. $$t^{\prime} \leq T$$, $$V(\phi, t^{\prime}) = 1$$ • Some PTL-valid wffs are PTL analogues of K-valid MPL-wffs, if replace $$\square$$ with either $$G$$ or $$H$$ uniformly, it will be PTL-valid • $$\models_{PTL} \phi \to GP \phi$$ Proof. Let $$M = \langle T, \leq, I \rangle$$ be an arbit PTL-model. Suppose that $$V(\phi, t) = 1$$ for an aribtrary $$t \in T$$. Then, for all $$t^{\prime}$$ s.t. $$t \leq t^{\prime}$$, then $$V(P\phi, t^{\prime}) = 1$$ (by truth conditions for $$P$$). So $$V(GP \phi, t) = 1$$ by truth conditions for $$G$$. $$\square$$ • $$\models_{PTL} \phi \to HF \phi$$ • However, there need to be constraints on $$\leq$$ – Should be from cosmology, philosophy of time, etc. • Reflexivity – every $$t \in \mathcal{T}$$ is s.t. $$t \leq \mathcal{T}$$ – $$G\phi \to \phi$$, $$H\phi \to \phi$$ • Transitivity – if $$t_1 \leq t_2$$ and $$t_2 \leq t_3$$, then $$t_1 \leq t_3$$, $$G\phi \to GG\phi$$, $$H\phi \to HH\phi$$ • Connectivity – should times be comparable? – Ask a Physicist! • Density – for any two times, there’s a time in between them • Antisymmetry – For any times $$t_1$$ and $$t_2$$, if $$t_1 \leq t_2$$ and $$t_2 \leq t_1$$, $$t_1 = t_2$$ • Eternality – there is neither a first nor a last time ## Lecture 25: 2018-04-12 – Predicate Logic • Grammar • $$\to, \lnot, \forall$$ – main connectives • Variables $$x, y, \ldots$$ with/without numerical subscripts • for each $$n > 0$$ n-place predicate $$F, G, \ldots$$ with/without numerical subscripts • individual constants (names) $$a, b, \ldots$$ with/without numerical subscripts • parens • a term is a variable or a constant • wff rules 1. if $$\Pi$$ is an $$n$$ place predicate and $$\alpha_1, \ldots \alpha_2$$ are terms, then $$\Pi\alpha_1\ldots\alpha_2$$ is a wff. 2. if $$\phi$$ and $$\psi$$ are wffs and $$\alpha$$ is a variable, then $$\lnot\phi$$, $$\phi\to\psi$$ and $$\forall\alpha\phi$$ are wffs. 3. Only strings from 1 and 2 are wffs • PC-wffs may contain free variables and redundant quantifiers • bound variables – An occurance of a variable $$\alpha$$ is bound in a wff $$\phi$$ iff that occurence of $$\alpha$$ is within an occurence of some wff of the form $$\forall\alpha\psi$$ within $$\phi$$ • free variables – an occurance of a variable that is not bound • closed formula – a wff with no free occurences of variables • open formula – a wff that is not closed • $$\exists\alpha\phi$$ – $$\lnot\forall\alpha\lnot\phi$$ • Models – $$\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$$ • $$\mathcal{D}$$ is a non-empty set (the domain) • $$\mathcal{I}$$ a function as follows • $$\alpha$$ being a constant, $$\mathcal{I}(\alpha) \in \mathcal{D}$$ • $$\Pi$$ being an $$n$$ place predicate, then $$\mathcal{I}(\Pi) \subseteq \mathcal{D}^n$$ – $$\mathcal{I}(\Pi)$$ is a set of$n$-tuples of elements drawn from $$\mathcal{D}$$, and $$\mathcal{I}(\Pi)$$ is an $$n$$ place relation on $$\mathcal{D}$$ • Variable assignments $$g$$ is a variable assignment for a model $$\langle \mathcal{D}, \mathcal{I} \rangle$$ iff $$g$$ is a function from the set of variables to $$\mathcal{D}$$. $$g_{u}^{\alpha}$$ is s.t. where $$g$$ is a variable assignment, $$\alpha$$ is a variable, and $$u \in \mathcal{D}$$ is a var assignment that is just like $$g$$ except that it assigns $$u$$ to $$\alpha$$, $$g_{u}^{\alpha}(\alpha) = u$$ • Denotation of a term, relative to a model and variable assignment – $$\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$$ is a model, $$g$$ is a variable assignment for $$\mathcal{M}$$ and $$\alpha$$ is aterm, $$[\alpha]_{\mathcal{M}_{g}}$$ is the denotation of $$\alpha$$ relative to $$\mathcal{M}$$ and $$g$$, defined as follows: $[\alpha]_{\mathcal{M}_{g}} = \left\{ \begin{matrix} \mathcal{I}(\alpha) & \text{if \alpha is a constant}\\ g(\alpha) & \text{if \alpha is a variable} \end{matrix} \right.$ • Valuation – $$V_{\mathcal{M}, g$$ for a model $$\mathcal{M}$$ and variable assignment $$g$$ for $$\mathcal{M}$$ is defined as a function from the set of wffs to $$\{0, 1\}$$ such that: • For any$n$-place predicate $$\pi$$ and any terms $$\alpha_1, \ldots, \alpha_n$$, $$V_{\mathcal{M},g} = 1$$ iff $$\langle[\alpha_1]_{\mathcal{M},g}, \ldots, [\alpha_n]_{\mathcal{M},g}\rangle \in \mathcal{I}(\Pi)$$ • $$V_{\mathcal{M},g}(\lnot\phi) = 1$$ iff $$V_{\mathcal{M},g}(\phi) = 0$$ • $$V_{\mathcal{M},g}(\phi\to\psi) = 1$$ iff either $$V_{\mathcal{M},g}(\phi) = 0$$ or $$V_{\mathcal{M},g}(\psi) = 1$$ • $$V_{\mathcal{M},g}(\forall\alpha\phi) = 1$$ iff for every $$d \in \mathcal{D}$$, $$V_{\mathcal{M},g_{d}^{\alpha}}(\phi) = 1$$ – ensures that $$V_{\mathcal{M}, g}(\forall x Fx) = 1$$ iff for every $$d \in D$$, $$d \in \mathcal{I}(F)$$ • Truth in a model – $$\phi$$ is true in a PC-model $$\mathcal{M}$$ iff for every variable assignment $$g$$ for $$\mathcal{M}$$, $$V_{\mathcal{M}, g}(\phi) = 1$$ • validity – a wff $$\phi$$ is PC-valid iff $$\phi$$ is true in all PC-models. • PC-semantic consequence – roughly as for PL ### Exercises • 4.2a – $$\models \forall x (Fx \to (Fx \lor Gx))$$ Proof. Suppose, for a reductio, that $$\not\models \forall x(Fx \to (Fx \lor Gx))$$. Then there is a PC-model $$\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$$ such that for some variable assignment $$g$$ for $$\mathcal{M}$$, $$V_{\mathcal{M}, g}(\forall x(Fx \to (Fx \lor Gx))) = 0$$. (Subscript $$\mathcal{M}$$ ommitted hereafter.) By the def’n of PC-valuation (clause for $$\forall$$), for some element of $$\mathcal{D}$$ call it $$d$$, s.t. $$V_{g_d^x}(Fx \to (Fx \lor Gx)) = 0$$. Then $$V_{g^x_d}(Fx) = 1$$ and$Vgxd(Fx ∨ Gx) = 0. Then by the latter $$V_{g^x_d}(Fx) = 0$$. Contradiction!
• $$\forall x Fx \models Fa$$ Proof. Suppose, for a reductio, that $$\forall x Fx \not\models Fa$$. Then $$\exists$$ a PC model $$\mathcal{M} = \langle\mathcal{M},\mathcal{I}\rangle$$, such that for some variable assignment $$g$$ for $$\mathcal{M}$$, $$V_{\mathcal{M},g}(\forall x Fx) = 1$$ but $$V_{\mathcal{M}, g}(Fx) = 0$$. (Subscript $$\mathcal{M}$$ ommitted hereafter.) By the latter, and the def’n of PC-valuation (clause for atomic wffs), $$[a]_{g} \not\in \mathcal{I}(F)$$. $$[a]_g = \mathcal{I}(a)$$. So $$\mathcal{I}(a) \not\in \mathcal{I}(F)$$. $$V_g(\forall x Fx) = 1$$, so for any $$d \in \mathcal{D}$$, $$V_{g^x_d}(Fx) = 1$$, but $$\mathcal{I}(a) \in \mathcal{D}$$, so $$V_{g^x_{\mathcal{I}(a)}}(Fx) = 1$$. So $$[x]_{g^x_{\mathcal{I}(a)}} \in \mathcal{I}(F)$$. $$[x]_{g^x_{\mathcal{I}(a)}} = \mathcal{I}(a)$$. $∴ $$\mathcal{I}(a) \in \mathcal{I}(F)$$. Contradiction! • 4.2d – $$\models\exists x\forall y Rxy \to \forall y \exists x Rxy$$ Proof. Suppose for a contradiction, that $$\not\models \exists x \forall y Rxy \to \forall y \exists x Rxy$$. Then there exists a PC-model $$\mathcal{M} = \langle\mathcal{D},\mathcal{I}\rangle$$ s.t. for some variable assignment $$g$$ for $$\mathcal{M}$$, $$V_{\mathcal{M},g}(\exists x\forall y Rxy \to \forall y \exists x Rxy) = 0$$. (Subscript $$\mathcal{M}$$ ommitted hereafter.) $$V_g(\exists x \forall y Rxy) = 1$$, and $$V_g(\forall y \exists x Rxy) = 0$$. For some element of $$\mathcal{D}$$, $$d_1$$ $$V_{g^x_{d_1}}(\forall y Rxy) = 1$$. For some element of $$\mathcal{D}$$, $$d_2$$, $$V_{g^y_{d_2}}(\exists x Rxy) = 0$$. Then for any $$d \in \mathcal{D}$$, $$V_{g^x_{d_1}^y_d}(Rxy) = 1$$ In particualr, since $$d_2 \in \mathcal{D}$$, $$V_{g^x_{d_1}^y_{d_2}}(Rxy) = 1$$. And for any $$d \in \mathcal{D}$$, $$V_{g^y_{d_2}^x_d}(Rxy) = 0$$. Since $$d_1 \in \mathcal{D}$$, $$V_{g^y_{d_2}^x_{d_1}}(Rxy) = 0$$. $$V_{g^x_{d_1}^y_{d_2}}(Rxy) = 1$$, so $$\langle[x]_{g^x_{d_1}^y_{d_2}}, [y]_{g^x_{d_1}^y_{d_2}} \rangle \in \mathcal{I}(R)$$. $$[x]_{g^x_{d_1}^y_{d_2}} = d_1$$, $$[y]_{g^x_{d_1}^y_{d_2}} = d_2$$, $$\langle d_1, d_2 \rangle \in \mathcal{I}(R)$$. $$V_{g^y_{d_2}^x_{d_1}}(Rxy) = 0$$, $$\langle [x]_{g^y_{d_2}^x_{d_1}}, [y]_{g^y_{d_2}^x_{d_1}} \rangle \not\in \mathcal{I}{R}$$, $$[x]_{g^y_{d_2}^x_{d_1}} = d_1$$, $$[y]_{g^y_{d_2}^x_{d_1}} = d_2$$. $$\langle d_1, d_2 \rangle \not\in \mathcal{I}(R)$$. Contradiction! ## Lecture 26: 2018-04-17 – Predicate Logic, continued ### Identity • Add the primitive $$=$$ • And the clause: if $$\alpha$$ and $$\beta$$ are terms, then $$\alpha = \beta$$ is a PC-wff • Definition of a model remains the same • $$V_{\mathcal{M},g}(\alpha = \beta) = 1$$ iff $$[\alpha]_{\mathcal{M}, g} = [\beta]_{\mathcal{M}, g}$$ • Identity Symbolization • Mark Twain is identical to Samuel Clemens – $$t = c$$ • Only Ted is happy – $$\forall x(x = t \iff Hx)$$ (Strong), $$\forall x(x\neq t \to \lnot Ht)$$ (weak) • Everyone except Ted is happy – $$\forall x (x \neq t \iff Hx)$$ (strong), $$\forall x (x \neq t \to Hx)$$ (weak) • number • there are at least $$n$$ Fs – $$\exists x_1 \exists x_2\ldots\exists x_n (Fx_1 \land Fx_2 \land \cdots \land Fx_n \land \delta)$$ – $$\delta$$ is the conjunction of all $$x_i \neq x_j$$ where $$i$$ and $$j$$ are integers between 1 and $$n$$, and $$i < j$$ • there exists at most $$n$$ Fs – $$\lnot$$ there exists at least $$n+1$$ Fs • there exists exactly $$n$$ Fs – the two above together • definite descriptions – the $$F$$ is $$G$$ #### Symbolization Exercises • Part A 1. $$\forall x \exists y \exists z (Byx \land Bzx \land y \neq x \land \forall w(Bwx \to (w = y \lor w = z)))$$ 2. $$\forall x (\exists y (Fx \land Byx \land \forall z ((Fz \land Bzx) \to z = y)) \land \exists y (My \land Byx \land \forall z ((Mz \land Bzx) \to z = y)))$$ 3. $$\exists x \lnot \exists y \exists z (Bxy \land Bxz \land y \neq z)$$ 4. $$\exists x \exists y ((\exists w (Bwz \land Bwy)) \land \forall z (\exists w (Bxw \land Bwz) \to y = z))$$ • Part B 1. $$\exists x (\forall y ((My \land Bxy) \iff y = x) \land Rx)$$ 2. $$\forall x ((Mx \land Bxb) \iff x = h)$$ 3. $$\forall x ((Bjx \land Bhx) \iff x = e)$$ 4. $$\forall x ((Lx \land Mx Bhx) \iff x = e)$$ #### Semantics • 5.1a $$Fab \models \forall x (x = a \to Fxb)$$ Proof. Suppose for a contradiction that $$Fab \not\models \forall x (x = a \to Fxb)$$. Then there $$\exists$$ a PC-model $$\mathcal{M}$$ ($$= \langle \mathcal{D}, \mathcal{I}\rangle$$) and a variable assignment $$g$$ for $$\mathcal{M}$$, such that: 1. $$V_{\mathcal{M},g}(Fab) = 1$$ (Subscript $$\mathcal{M}$$ ommitted hereafter) 2. $$V_g(\forall x (x = A \to Fxb)) = 0$$. 3. By 2, there is an element of $$\mathcal{D}$$, call it $$u$$ s.t. $$V_{g^x_u}(x = a \to Fxb)$$. 4. By 3, $$V_{g^x_u}(x = a) = 1$$. 5. And $$V_{g^x_u}(Fxb) = 0$$. 6. By 1, $$\langle [a]_g, [b]_g \rangle \in \mathcal{I}(F)$$. 7. By 6, $$\langle \mathcal{I}(a), \mathcal{I}(b) \rangle \in \mathcal{I}(F)$$ 8. By 5, $$\langle [x]_{g^x_u}, [b]_{g^x_u} \rangle \not\in \mathcal{I}(F)$$ 9. By 8, $$\langle u, \mathcal{I}(b) \rangle \not\in \mathca{I}(F)$$ 10. By 7 & 9, $$\mathcal{I}(a) \neq u$$. 11. By 4, $$[x]_{g^x_u} = [a]_{g^x_u}$$ 12. By 11, $$u = \mathcal{I}(a)$$. Contradiction! with 10. ### Functions • Add to the primitive vocab of PC • for each $$n > 0$$,$n$-place function symbols $$f, g, \ldots$$ with or without numerical subscripts • If $$f$$ is an$n$-place functions symbol and $$\alpha_1, \ldots \alpha_n$$ are terms then $$f(\alpha_1\ldots\alpha_n)$$ • To the specification of an interpretation, add • If $$f$$ is an$n$-place function symbol, then $$\mathcal{I}(f)$$ is an$n$-place (total) function over $$\mathcal{D}$$ • Denotation is now the following: $[\alpha]_{\mathcal{M},g} = \left\{ \begin{matrix} \mathcal{I}(\alpha) & \text{if} \alpha \text{is a constant} \\ g(\alpha) & \alpha \text{is a variable} \\ \mathcal{I}(f)([\alpha_1]_{\mathcal{M}, g},\ldots,[\alpha_n]_{\mathcal{M},g}) & \alpha \text{is a complex term} f(\alpha_1\ldots\alpha_n) \end{matrix}\right.$ ## Lecture 27: 2018-04-19 – Predicate Logic ### Functions – Symbolization • $$a = m(c)$$ • $$a = m(c)$$ • $$a = m(c) \land Bc$$ • $$\forall x (a = m(x) \iff c = x)$$ • $$\forall x ((a = m(x) \land Bx) \iff c = x)$$ • $$(p = m(c)) \lor (p = f(c))$$ • $$d = f(f(c))$$ • $$d = f(m(c))$$ • $$e = m(m(c))$$ • $$e = m(f(c))$$ • Two previous or’d together • $$(f(p) = f(c)) \land (m(p) = m(c))$$ • $$m(m(c)) = m(h) \land f(m(c)) = f(h)$$ (30) ### Functions – Semantics • $$\models \forall x \exists y f(x) = y$$ Proof. Suppose not for a contradiction. Then there exists a PC+FS-model $$\mathcal{M}$$ ($$= (\mathcal{D}, \mathcal{I})$$) s.t. for some var assignment $$g$$ for $$\mathcal{M}$$, 1. $$V_{\mathcal{M}, g} (\forall x \exists y f(x) = y) = 0$$ (subscript $$\mathcal{m}$$ ommitted hereafter) 2. By 1, for some element of $$\mathcal{D}$$ call it $$d$$, $$V_{g^x_d}(\exists y f(x) = y) = 0$$ 3. By 2, for any element $$u \in \mathcal{D}$$, $$V_{g^{x,y}_{d,u}}(f(x) = y) = 0$$ 4. By 3, for any element $$u \in \mathcal{D}$$, $$[f(x)]_{g^{x,y}_{d,u}} \neq [y]_{g^{x,y}_{d,u}}$$ 5. By 4, for any element $$u \in \mathcal{D}$$, $$\mathcal{I}(f)([x]_{g^{x,y}_{d,u}}) \neq u$$ 6. By 5, for any element $$u \in \mathcal{D}$$, $$\mathcal{I}(f)(d) \neq u$$. So $$\mathcal{I}(f)(d) \not\in \mathcal{D}$$ 7. But $$d \in \mathcal{D}$$ and $$\mathcal{I}(f) : \mathcal{D} \to \mathcal{D}$$, so $$\mathcal{I}(f)(d) \in \mathcal{D}$$. Contradiction! • $$\forall x f(x) = x \models f(f(a)) = a$$ Proof. Suppose not for a contradiction. Then there exists a PC+FS model $$\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$$ and a variable assignment $$g$$ for $$\mathcal{M}$$ s.t.: 1. $$V_{\mathcal{M},g} (\forall x f(x) = x) = 1$$ (Subscript$\mathcal{M} ommitted hereafter)
2. but $$V_g(f(f(a)) = a) = 0$$
3. By 2, $$[f(f(a))]_g \neq [a]_g$$
4. By 3, $$\mathcal{I}(f)([f(a)]_g) \neq \mathcal{I}(a)$$
5. By 4, $$\mathcal{I}(f)(\mathcal{I}(f)([a]_g)) \neq \mathcal{I}(a)$$
6. By 5, $$\mathcal{I}(f)(\mathcal{I}(f)(\mathcal{I}(a))) \neq \mathcal{I}(a)$$
7. $$\mathcal{I}(a) \in \mathcal{D}$$, so by 1, Vgx\mathcal{I}(a)(f(x) = x) = 1$8. By 7, $$[f(x)]_{g^x_{\mathcal{I}(a)}} = [x]_{g^x_{\mathcal{I}(a)}}$$ 9. By 8, $$\mathcal{I}(f)([x]]_{g^x_{\mathcal{I}(a)}}) = \mathcal{I}(a)$$ 10. By 9, $$\mathcal{I}(f)(\mathcal{I}(f)(a)) = \mathcal{I}(a)$$ 11. $$\mathcal{I}(f)(\mathcal{I}(a)) \in \mathcal{D}$$, so by 1, Vgx\mathcal{I}(f)(\mathcal{I}(a))(f(x) = x) = 1$
12. By 11, $$[f(x)]_{g^x_{\mathcal{I}(f)(\mathcal{I}(a))}} = [x]_{g^x_{\mathcal{I}(f)(\mathcal{I}(a))}}$$
13. By 12, $$\mathcal{I}(f)(\mathcal{I}(f)(a)) = \mathcal{I}(f)(\mathcal{I}(a))$$
14. By 13 and 10, $$\mathcal{I}(f)(\mathcal{I}(f)(\mathcal{I}(a))) = \mathcal{I}(a)$$. Contradiction! (6)

### Definite descriptions, the $$\iota$$ operator

• Add to the primitive vocab the $$\iota$$ operator
• $$G\iota x Fx$$, the frog is green
• $$\iota x (Gx \land Fx)$$
• New combined definition of term and wff
1. Every Variable or constant is a term
2. If $$\phi$$ is a wff and $$\alpha$$ is a variable, then $$\iota\alpha\phi$$ is a term (the $$\alpha$$ s.t. $$\phi$$)
3. If $$f$$ is an $n$-place function symbol and $$\alpha_1, \ldots, \alpha_n$$ are terms, then $$f(\alpha_1\ldots\alpha_2)$$ is a term
4. If $$\Pi$$ is an $n$-place predicate and $$\alpha_1, \ldots, \alpha_n$$ are terms, then $$\Pi\alpha_1\ldots\alpha_n$$ is a wff$5. If $$\alpha$$ and $$\beta$$ are terms, then $$\alpha = \beta$$ is a wff 6. If $$\phi$$ and $$\psi$$ are wffs, and $$\alpha$$ is a variable, then $$\lnot\phi$$, $$\phi \to \psi$$ and $$\forall\alpha\phi$$ are also wffs$
7. Only strings that can be shown to be terms or wffs using the previous are terms or wffs
• Denotation $[\alpha]_{\mathcal{M},g} = \left\{ \begin{matrix} \mathcal{I}(\alpha) & \text{constant}\\ g(\alpha) & \text{var} \\ \mathcal{I}(f)([\alpha_1]_{\mathcal{M},g}\ldots[\alpha_n]_{\mathcal{M},g}) & \text{function} \\ \text{undefined} & \text{some term is undef} \\ u \in \mathcal{D} V_{\mathcal{M},g}(\phi) = 1 & \iota \text{term, defined, undefined otherwise} \end{matrix} \right.$
• Generally, see the handout
• Symbolization Exercises
• $$s = \iota x Wxw$$
• $$J\iota x (Qx \land Bx \land Fx) \iota (Lx \land Dx)$$
• $$W \iota x Dx \land T \iota x Dx$$
• $$T \iota x(Dx \land Wx)$$
• $$m = \iota x (Wx \land \lnot Ax \iota y Fyx)$$ or $$m = \iota x (Wx \land \lnot A x \iota y Fym)$$

## Lecture 28: 2018-04-24 – More Predicate Logic

### $$\iota$$ symbolization, continued

• Number 8 $$D\iota x (Bxj \land Oxj) \land \exists x (Bxj \land Ojx \land \forall y ((Byj \land Ojy) \to y = x) \land \lnot Dx)$$
• $$\lnot\exists x (x = \iota y Ky)$$
• $$KpG\iota x(Gx \land Fxp)$$
• $$K\iota x(Bx \land Lxe)e$$
• $$\exists x \exists y (Bx \land Gy \land Lxy \land Fyx \land Kxy \land \forall z ((Bz \land Lzy) \to z = x) \land \forall z ((Gz \land Fzx) \to z = y))$$

### The $$\lambda$$ operator – complex predicate

• $$\lambda x (Bx \land Ex)$$ The property of being an $$x$$ s.t. $$Bx \land Ex$$
• if $$\alpha$$ is a variable and $$\phi$$ is a wff, then $$\lambda\alpha\phi$$ is a one-place predicate – the property of being an $$\alpha$$ s.t. $$\phi$$
• Add to term/wff definition, as a new atomic wff: if $$\alpha$$ is a variable, $$\phi$$ is a wff, and $$\beta$$ is a term, $$\lambda\alpha\phi\beta$$ is a wff
• Extension is $$\{ u \in \mathcal{D} | V_{\mathcal{M},g^{\alpha}_{u}}(\phi) = 1 \}$$ or $$\phi^{\mathcal{M},g,\alpha}$$
• extension of $$\lambda x(Fx \land Gx)$$ $$= \{u \in D : V_{g^x_u}(Fx \land Gx) = 1\} = \{u \in D | V_{g^x_u}(Fx) = 1 \land V_{g^x_u}(Gx) = 1\} = \{u \in D | u \in \mathcal{I}(F) \land u \in \mathcal{I}(G)\} = \mathcal{I}(F) \cap \mathcal{I}(G)$$
• Insert into recursive definition of a denotation and valuation: For any variable $$\alpha$$, wff $$\phi$$ and term $$\beta$$, $$V_{g}(\lambda\alpha\phi\beta) = 1$$ iff $$[\beta]_g \in \phi^{g\alpha}$$

### Exercises

• 13 – false – $$\exists x (Kx \land \forall y (Ky \to y = x) \land Bx)$$
• 14 – true – By 13
• 15 – false
• 16 – $$\lnot\lambda x Bx(\iota x Kx)$$ – true, notted 15
• 17 – False! Because there is no king of France
• Joanna
• $$D\iota x (Bxj \land Oxj) \land \lambda x \lnot Dx \iota x(Bxj \land Ojx)$$

### Second Order Logic

• quantifies over properties, not objects
• for each $$n$$ add $n$-place predicates $$X, Y, \ldots$$
• For WFFs, if $$\pi$$ is an $n$-place predicate variable and $$\alpha_1, \ldots, \alpha_n$$ are terms, then $$\pi\alpha_1\ldots\alpha_n$$ is a wff
• A variable assignment $$g$$ assigns to each $n$-place predicate variable an $n$-place relation over the domain
• For valuation:
• If $$\pi$$ is an $n$-place predicate variable and $$\alpha_1, \ldots, \alpha_n$$ are terms, then $$V(\pi\alpha_1\ldots\alpha_n) = 1$$ iff $$\langle[\alpha_1]_g, \ldots, [\alpha]_n\rangle\in g(\pi)$$
• If $$\pi$$ is an $n$-place predicate variable and $$\phi$$ is awff, then $$V_g(\forall\pi\phi) = 1$$ iff for every $$U$$ set of $n$-tuples from $$\mathcal{D}$$, $$V_{g^\pi_U}(\phi) = 1$$

## Lecture 29: 2018-04-26 – Second Order Logic

### Increased expressive power

• can make identicals indescernable, and indescernables identical
• $$\forall x \forall y (\forall X (Xx \iff Xy) \to x = y)$$
• invulnerable to objections such as that of Max Black
• cheapens properties?

### Semantics and Metatheory

• Exercise 5.11 – Show that the indiscernibility of identicals and the identity of indiscernibles are both true unde every variable assignment in every model.

Proof (indiscernibility of identicals): Suppose, for a contradiction that $$\not\models \forall x \forall y (x = y \to \forall X (Xx \iff Xy))$$. Then there exists a second-order model $$\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$$ and a variable assignment $$g$$ for $$\mathcal{M}$$ s.t.:

1. $$V_g(\forall x \forall y (x = y \to \forall X (Xx \iff Xy))) = 0$$
2. then there is an element of $$\mathcal{D}$$, call it $$u$$, s.t. $$V_{g^x_u}(\forall y (x = y \to \forall X (Xx \iff Xy))) = 0$$
3. Then $$v \in \mathcal{D}$$ s.t. $$V_{g^{x,y}_{u,v}}(x = y \to \forall X (Xx \iff Xy)) = 0$$
4. Then $$V_{g^{x,y}_{u,v}}(x = y) = 1$$ (3)
5. and $$V_{g^{x,y}_{u,v}}(\forall X (Xx \iff Xy)) = 0$$ (3)
6. By 5, there is some subset of $$\mathcal{D}$$, call it $$S$$ s.t. $$V_{g^{x,y,X}_{u,v,S}}(Xx \iff Xy) = 0$$
7. By 6, $$V_{g^{x,y,X}_{u,v,S}}(Xx) \neq V_{g^{x,y,X}_{u,v,S}}(Xy)$$
8. By 4, $$[x]_{g^{x,y}_{u,v}} = [y]_{g^{x,y}_{u,v}}$$, $$g^{x,y}_{u,v} (x) = g^{x,y}_{u,v}(y)$$. Therefore $$u = v$$
9. By 7, $$V_{g^{x,y,X}_{u,v,S}}(Xx) = 1$$ iff $$V_{g^{x,y,X}_{u,v,S}}(Xy) = 0$$
10. By 9, $$[x]_{g^{x,y,X}_{u,v,S}} \in g^{x,y,X}_{u,v,S}(X)$$ iff $$[y]_{g^{x,y,X}_{u,v,S}} \not\in g^{x,y,X}_{u,v,S}(X)$$
11. By 10, $$u \in S$$ iff $$v \not\in S$$. Contradiction! (with 8, $$u = v$$)

Proof (identity of indiscernibles): Suppose, for a contradiction that $$\lnot\models \forall x \forall y (\forall X (Xx \iff Xy) \to x = y)$$. Thene there exists a second-order model $$\mathcal{M} = \langle \mathcal{D}, \mathcal{I} \rangle$$ and a variable assignment $$g$$ for $$\mathcal{M}$$ s.t.

1. $$V_g(\forall x \forall y (\forall X (Xx \iff Xy) \to x = y)) = 0$$
2. By 1, there is an element of $$\mathcal{D}$$, call it $$u$$, s.t. $$V_{g^{x}_{u}}(\forall y (\forall X (Xx \iff Xy) \to x = y)) = 0$$
3. By 2, there is an element of $$\mathcal{D}$$, call it $$v$$, s.t. $$V_{g^{x,y}_{u,v}}(\forall X (Xx \iff Xy) \to x = y) = 0$$
4. By 3, $$V_{g^{x,y}_{u,v}}(\forall X (Xx \iff Xy)) = 1$$
5. and $$V_{g^{x,y}_{u,v}}(x = y) = 0$$
6. By 5, $$[x]_{g^{x,y}_{u,v}} \neq [y]_{g^{x,y}_{u,v}}$$
7. By 6, $$u \neq v$$
8. By 4, for any subset of $$\mathcal{D}$$, in particular for $$\{u\}$$, $$V_{g^{x,y,X}_{u,v,\{u\}}}(Xx \iff Xy) = 1$$
9. By 8, $$V_{g^{x,y,X}_{u,v,\{u\}}}(Xx) = V_{g^{x,y,X}_{u,v,\{u\}}}(Xy)$$
10. V_{gx,y,Xu,v,\{u\}}(Xx) = 1$iff $$[x]_{g^{x,y,X}_{u,v,\{u\}}} \in g^{x,y,X}_{u,v,\{u\}}(X)$$, iff $$u \in \{u\}$$. Clearly $$u \in \{u\}$$ so $$V_{g^{x,y,X}_{u,v,\{u\}}}(Xx) = 1$$ 11. By 9, 10, $$V_{g^{x,y,X}_{u,v,\{u\}}}(Xy) = 1$$, therefore $$v \in \{u\}$$, $$v = u$$ Contradiction with 7! ### Free Logic • a non-classical predicate logic in which a constant need not denote an existing object • Motivations • empty names – natural language names that denote existing entities • There could have been nothing! • Models $$\langle\mathcal{D}, \mathcal{D}^{\prime}, \mathcal{I} \rangle$$ • $$\mathcal{D}$$ – inner domain, possibly empty • $$\mathcal{D}^{\prime}$$ – outer domain, possibly empty • $$\mathcal{D} \cap \mathcal{D}^{\prime} = \emptyset$$ but $$\mathcal{D} \cup \mathcal{D}^{\prime} \neq \emptyset$$ • $$\mathcal{I}$$ is the interp function s.t. • if $$\alpha$$ is a constant, then $$\mathcal{I}(\alpha) \in \mathcal{D} \cup \mathcal{D}^{\prime}$$ • If $$\Pi$$ is an $$n$$ place predicate, then $$\mathcal{I}(\Pi)$$ is an$n\$-place relation over $$\mathcal{D}$$
• Variable assignment for model iff $$g$$ is a function from the set of variables to $$\mathcal{D} \cup \mathcal{D}^{\prime}$$
• denotations, etc are the same
• Valuation is the same as before but with only ever $$\mathcal{D}$$ for $$\forall$$
• truth in model, validity and semantic consequence are the same
• outer domain doesn’t have to be genuine non-existent entites
• denotation may be in either the outer or inner domain.
• $$\forall x \phi$$ is true iff $$\phi$$ is true of all objects in the inner domain
• An atomic wff is automatically assigend 0 by a var assignment if any of the terms fail to have denotations in the inner domain on that assignment. Such a term is empty. Negative free logic.
• However, atomic self-identity is automatically true, no matter if the denotation is in the outer domain.

### Free Logic exercises

• 5.14. $$\not\models \forall x Fx \to Fa$$, $$\mathcal{D} = \emptyset$$, $$\mathcal{D}^{\prime} = \{1\}$$, $$\mathcal{I}(a) = 1$$, $$\mathcal{I}(F) = \emptyset$$
• $$\mathcal{D} = \{2, 3\}$$, $$\mathcal{D}^{\prime} = \{1\}$$, $$\mathcal{I}(a) = 1$$, $$\mathcal{I}(F) = \{2, 3\}$$
• 5.15. Suppose for a contradiction that $$\not\models_{FPC} \forall x Fx \to (\exist y y = a \to Fa)$$ Then there is a model $$\mathcal{M} = \langle \mathcal{D}, \mathcal{D}^{\prime}, \mathcal{I} \rangle$$, and var assignment $$g$$ for $$\mathcal{M}$$ s.t.
1. $$V_g(\forall x Fx \to (\exists y y=a \to Fa)) = 0$$
2. By 1, $$V_g(\forall x Fx) = 1$$
3. and $$V_g(\exists y y=a \to Fa) = 0$$
4. By 3, $$V_g(\exists y = a) = 1$$
5. and $$V_g(Fa) = 0$$
6. by 4 there is an element of $$\mathcal{D}$$, call it $$u$$, s.t. $$V_{g^y_u} (y = a) = 1$$
7. by 6 $$[y]_{g^y_u} = [a]_{g^y_u}$$, so $$u = \mathcal{I}(a)$$
8. By 2, every element of $$\mathcal{D}$$, in particular $$u (= \mathcal{I}(a))$$ is s.t. $$V_{g^x_u}(Fx) = 1$$
9. By 8, $$[x]_{g^x_u} \in \mathcal{I}(F)$$. $$u \in \mathcal{I}(F)$$
10. By 5, $$\mathcal{I}(a) \not\in \mathcal{I}(F)$$. But $$u = \mathcal{I}(a)$$. Contradiction!