• $\mathcal{F}, \mathcal{G}$ are non-empty families

• prove If $\mathcal{F} \subseteq \mathcal{G}$ then $\cap\mathcal{G} \subseteq \cap\mathcal{F}$

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$.

• 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$

• $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$

• 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)

• $\aleph_0 is the infinite number with the smallest cardinality. The next largest is $ℵ_1$, then $ℵ_2$, and so on.

• $|\mathcal{P}(\mathbb{Z}^+) = 2^{\aleph_0}$ and $\mathcal{P}(\mathbb{Z}^+)$ is uncountable, so we know that $2^{\aleph_0} > \aleph_0$.

• The continuum hypothesis is that $2^{\aleph_0} = \aleph_1$

• CH cannot be either disproved or proved using Zermelo-Frankel set theory.

1. $\lnot\lnot P$ (prem)

2. $\lnot\lnot P \to (\\not P \to \lnot\lnot P)$ (PL 1)

3. $\lnot P \to \lnot\lnot P$ (1, 2 MP)

4. $(\lnot P \to \lnot\lnot P) \to ((\lnot p \to \lnot p) \to p)$ (PL 3)

5. $(\lnot P \to \lnot P) \to P$ (4, 3 MP)

6. $\lnot P \to \lnot P$ (exercise a)

7. $P$ (5, 6 MP)

• base case is always $\phi$ is atomic (has zero connectives)

• induction $\phi$ is compound (has at least one connective, has $k + 1$ connectives)

  • often has subcases

  • number of subcases determined by connectives

  • Sider:

    • $\phi = \lnot \psi$ for some wff $\psi$

    • $\phi = (\psi \to \chi)$ for some wffs $\psi$ and $\chi$

      • for induction hypothesis, assume $\psi$, $\chi$ have a given property, then use IH to prove that $(\phi \to \chi)$ has the given property

• induction on number of connectives is also known as induction on formula complexity

• Sometimes, to prove a result, you must prove a stronger fact.

• (1) For L2, prove that every wff containts twice as many parentheses as connectives:

  • Let $p(\sigma)$ be the number of (occurences) of parenthesis in an L2 string (sequence of symbols from the language) $\sigma$, $c(\sigma)$ for connectives

  • Prove: For any L2-wff $\phi$, $p(\phi) = 2c(\phi)$.

  • Proof (by induction on the number ($n$) of connectives in in $\phi$):

    • Base case: $n = 0$, $\phi$ is a sencence letter. $p(\phi) = 0$ and $c(\phi) = 0$. So $p(\phi) = 2c(\phi)$ as required.

    • IH: For any L2-wff $\alpha$ with fewer than $k + 1$ connectives is such that $p(\alpha) = 2c(\alpha)$

    • Inductive Step: $n = k + 1$ for some $k \in \mathbb{N}$, $\phi$ is a compound wff. There are 2 cases.

      1. $\phi = (\lnot \psi)$, for some L2-wff $\psi$. $\psi$ has $k$ connectives. By the IH, we know that $p(\psi) = 2c(\psi)$. $p((\lnot \psi)) = p(\psi) + 2$, $c((\lnot \psi)) = c(\psi) + 1$, $p((\lnot \psi)) = 2c(\psi) + 2 = 2(c(\psi) + 1) = 2c((\lnot \psi))$

      2. $\phi = (\psi * \chi)$ for some L2-wffs $\psi$ and $\chi$ and some binary L2 connective $*$ ($\land, \lor, \to, \iff$). $\phi$ has $k + 1$ connectives, so between them $\psi$ and $\chi$ have $k$ connectives together. So each of $\psi$ and $\chi$ has fewer than $k + 1$ connectives. By the IH, we know that $p(\psi) = 2c(\psi)$ and $p(\chi) = 2c(\chi)$. $p(\phi) = p((\psi * \chi)) = p(\psi) + p(\chi) + 2 = 2c(\psi) + 2c(\chi) + 2 = 2(c(\psi) + c(\chi) + 1) = 2c((\psi * \chi)) = 2c(\phi)$ $\square$

• (5) Let $\phi$ be an L1-wff (or for L2-wffs) that contains no negation symbols. Prove that for every interpretation $\mathcal{I}$, if $\mathcal{I}(a) = 1$ for every sentence letter $A$ then $V_\mathcal{I}(\phi) = 1$.

  • Proof (by induction on the number ($n$) of connectives in $\phi$).

    • Base case: $n = 0$ $\phi$ is a sentence letter, so $\mathcal{I}(\phi) = 1$ by assumption. Then $V_\mathcal{I}(\phi) = 1$, by the definition of valuation (clause for atomic wffs).

    • IH: For any L1 wff $\beta$ with fewer than $k + 1$ connectives, if every s.l. $\alpha$ appearing in $\beta$ is s.t. $\mathcal{I}(\alpha) = 1$, then $V_\mathcal{I}(\beta) = 1$.

    • Inductive Step: $n = k + 1$ for some $k \in \mathbb{N}$. There are four cases:

      1. $\phi = (\psi \land \chi)$ for some L1-wffs $\psi$ and $\chi$. Let $\mathcal{I}$ be an interpretation that assigns 1 to every S.L. appearing in $\phi$. So, $\mathcal{I}$ assigns 1 to every S.L. in $\psi$ and $\chi$. By the IH, $V_\mathcal{I}(\psi) = 1$ and $V_\mathcal{I}(\chi) = 1$. By def. of valuation (clause for $\land$), $V_\mathcal{I}((\psi \land \chi)) = 1$.

      2. $\phi = (\psi \lor \chi)$

      3. $\phi = (\psi \to \chi)$

      4. $\phi = (\psi \iff \chi)$

    • 2 to 4 are proved just as in case 1, but using the clauses for $\lor$, $\to$, $\iff$ respectively in the def. of valuation. $\square$

• (6) Prove than no L1-wff that contains only binary connectives is a contradiction. (A contradiction is a wff that is assigned 0 by every valuation.)

  • We have proved in Question 5, that if an L1-wff $\phi$ contains no $\lnot$, then if $\mathcal{I}(\alpha) = 1$ for every S.L. $\alpha$ in $\phi$, then $V_\mathcal{I}(\phi) = 1$. Hence $\phi$ cannot be a contradiction.

• if $\vdash_{PL}\phi$, then $\models_{PL}\phi$ (if there is an axiomatic proof for $\phi$, then $\phi$ is a tautology)

• Proof (by induction on the number, $n$ of lines in an axiomatic proof of $\phi$):

  • Base Case: $n = 1$. $\phi$ is an axiom. There are three cases:

    • $\phi$ is an instance of PL1: $\phi = (\psi \to (\chi \to \psi))$ for some PL-wffs $\psi$ and $\chi$. Suppose for a contradiction that $\not\models\phi$ ($\not\models(\psi\to(\chi\to\psi)))$, then for some interpretation $\mathcal{I}$, $V_{\mathcal{I}}(\psi\to(\chi\to\psi)) = 0$. By the def. of $\to$, $V_{\mathcal{I}}(\psi) = 1$, but $V_{\mathcal{I}}(\chi \to \psi) = 0$. By the latter, $V_{\mathcal{I}}(\psi) = 0$. $\rightarrow\leftarrow \therefore\models\phi$

    • $\phi$ is an instance of PL2 : Left as an exercise

    • $\phi$ is an instance of PL3 : Left as an exercise

  • Inductive step: $n = k + 1$, ($k \in \mathbb{N}$) Four cases: 1-3, $\phi$ is an instance of PL1-PL3, proved as in the base case. 4 is $\phi$ was derived by an application of MP on two previous lines, $(\psi \to \phi)$ and $\psi$. $\vdash \psi\to\phi$ and $\vdash\psi$. Each of these ($\psi \to \phi$ and $\psi$) has an axiomatic proof with fewer than $n$ lines. Therefore, by IH, $\psi \to \phi$ and $\psi$ are tautologies. Then $V_{\mathcal{I}}(\psi \to \phi) = 1$ and $V_{\mathcal{I}}(\psi) = 1$. $\therefore $V_{\mathcal{I}}(ɸ) = 1$, by def. $→$. $\mathcal{I}$ was arbitrary, so $\modelsɸ$. $\square$

• 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$

• 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$

• 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.

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 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)$)

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$

• 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$.

• 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

• 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}}(ɸ) = 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$

• 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 \in \mathbb{N} $ɸ = ψ → χ$ $V_{\mathcal{I}}(ɸ) = V_{\mathcal{I}}(ψ → χ) = 0$ iff $V_{\mathcal{I}}(ψ) = 1$ and $V_{\mathcal{I}}(χ) = 0$. By IH, $V_{\mathcal{I}}(χ)$ for at most two of the four interps. Therefore, $V_{\mathcal{I}}(ψ → χ) = 0$ for at most two of the four interps. $\square$

• For 16, relevant property is when P = 1, Q = 0, and Q = 1, P = 0

• 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 $\alpha = \gamma.$ Then obviously, $* = +$, and $\beta = \delta$. $\square$

• 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$

• 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

• 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$.

• 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

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 α) ≥q 0$, $1 - P(α) ≥q 0$, $1 ≥q P(α)$

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)$

• 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$

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

• $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)

• 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}$

• 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$

• 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

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}$

A binary relation over $\mathcal{W}, the accessibility relation -- $R ⊂seteq W × W$

$\mathcal{I}$

A two-place function ( the interpretation function) such that for any sentence letter $\alpha$ and for any $w \in W$, $\mathcal{I}(\alpha, w)$ is either 1 or 0 ($\mathcal{I} : S \times \mathcal{W} \mapsto \{0, 1\}$).

frame

of a model $\langle\mathcal{W}, \mathcal{R}, \mathcal{I}\rangle$ – the ordered pair $\langle\mathcal{W}, \mathcal{R}\rangle$

MPL Valuation

Where $\mathcal{M}$ is an MPL-model, $\alpha$ is a sentence letter, and $\phi, \psi$ are any wffs, and $w$ is a member of $\mathcal{W}$, then:

• $V_{\mathcal{M}}(\alpha, w) = \mathcal{I}(\alpha, w)$

• $V_{\mathcal{M}}(\lnot\phi, w) = 1$ iff $V_{\mathcal{M}}(\phi, w) = 0$

• $V_{\mathcal{M}}(\phi \to \psi, w) = 1$ iff either $V_{\mathcal{M}}(\phi, w) = 0$ or $V_{\mathcal{M}}(\psi, w) = 1$

• $V_{\mathcal{M}}(\square\phi, w) = 1$ iff for every $v \in \mathcal{W}$, if $\mathcal{R}wv$, then $V_{\mathcal{M}}(\phi, v) = 1$

Model for a system

An S-model for any system S is defined as an MPL model whose accessibilty relation $\mathcal{R}$ has the named feature:

System	Accessibility Feature
K	No requirement
D	Serial (in $\mathcal{W}$)
T	Reflexive (in $\mathcal{W}$)
B	Reflexive and symmetric
S4	Reflexive and transitive
S5	Reflexive, symmetric, transitive (equivalence relation)

• An S4 model is a model whose accessibility relation is refexive and transitive, the model itself can be reflexive and transitive

• All models are K models

validity in a model

A wff $\phi$ is valid in a model $\mathcal{M}$ iff for every $w \in \mathcal{W}$, $V_{\mathcal{M}}(\phi, w) = 1$

validity in a model

A wff $\phi$ is valid in a model $S \in \{\text{K}, \text{D}, \text{T}, \text{B}, \text{S4}, \text{S5}\}$ iff it is valid in every S-model. Written $\models_{S} \phi$

• Stronger systems tend to have more valid wffs

• $K \prec D \prec D \prec T \prec (B, S4) \prec S5$

semantic consequence in a system

$\phi$ is semantic consequence in $S$ of a set $\Gamma$ iff for every $S$-model, $\mathcal{M}$, and each $w \in \mathcal{W}$ if $V_{\mathcal{M}}(\gamma, w) = 1$, then $V_{\mathcal{M}}(\phi, 1) = 1$. $\Gamma \models_{S}\phi$

• Exercise 6.2 A $\models_{D} (\square P \land \square (\lnot P \lor Q)) \implies \Diamond Q$ (ɸ) Suppose, for a contradiction that this wff is not D-valid. Then there is some $D$ model $\mathcal{M} = \langle \mathcal{W}, \mathcal{R}, \mathcal{I} \rangle$ s.t. the wff is not valid in $\mathcal{M}$. Then $\exists w \in \mathcal{W}$ s.t. $V_{\mathcal{M}}(\phi, w) = 0$. $V_{\mathcal{M}}(\square P \land \square(\lnot P \lor Q), w) = 1$ and $V_{\mathcal{M}}(\Diamond Q, w) = 0$ ($\implies$ clause in def'n of MPL-valuation) (ommiting the subscript $\mathcal{M}$ from here). Then $V(\square P, w) = 1$ and $V(\square(\lnot P \lor Q), 1) = 1$. $M$ is serial, so $\exists v \in \mathcal{W}$ s.t. $Rwv$. $Rwv$ and $V(\square P, w) = 1, so $V(P, v) = 1$. $Rwv$ and $V(\square(lnot P ∨ Q), w) = 1$, so $V(lnot P ∨ Q, v) = 1$. Then either $V(P, v) = 0$ (contradiction), so $V(Q, v) = 1$. Then, $Rwv$ and $V(◆ Q, w) = 0$, so $V(Q, v) = 0$ (contradiction). Therefore $ɸ$ is $D$ valid

• 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

• 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)

  6. Return to step 2 if not finished

  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.
               +-+

• 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

• 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^{-} = \empty. Then $\vdashɸ$ by def'n of S-provability from a set (first disjunct). Then $\vdash\squareɸ$ by rule NEC. Then $\squareɸ ∈ Δ$ by lemma 6.5c. But $lnot\squareɸ∈Δ$. Contradiction with lemma 6.5a. Thus, $\square^-(Δ) ≠q ∅set$. By def'n of S-provability from a set (second disjunct). $∃sδ_1, \ldots, δ_n ∈ \square^-^{}(Δ)$ s.t. $\vdash(δ_1∧⋯∧δ_n)→ɸ$. So $\vdash\square((δ_1∧⋯δ_n)→ɸ)$ by NEC. This means that $\vdash\square(δ_1 → (δ_2→⋯(δ_n→ɸ)\ldots))$. Then $\vdash(\squareδ_1→(\squareδ_2→⋯(\squareδ_n→\squareɸ)\ldots))$ by $n$ applications of axiom schema $K$ and PL. Thus, $\vdash(\squareδ_1∧⋯∧\squareδ_n∧lnot\squareɸ)→\bot$ by PL. But $δ_1,\ldots,δ_n ∈ \square^-(Δ)$ so $\squareδ_1,\ldots,\squareδ_n∈Δ$ by def'n $\square^-(Δ)$. Also $lnot\squareɸ∈Δ$. $Δ\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 $ɸ$ 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 $∀ v ∈ \mathcal{W}$ s.t. $\mathcal{R}wv$, $ψ ∈ v$ by IH ($\*$). Suppose for a contradicition that $\squareψ ¬∈ w$. Then $lnot\squareψ ∈ w$ by lemma 6.5a. $w$ is a maximal S-consistent set, so by Lemma on Box-Strip, $\square^-(w)∪\{lnot\squareψ} ⊂seteq Γ$ for some maximal S-consistent set $Γ$. $Γ ∈ \mathcal{W}$ and $\square^-(w) ⊂seteq Γ$, so $\mathcal{R}wΓ$ by def'n of canonical model. So by ($\*$), $ψ ∈ Γ$, but $lnotψ ∈ Γ$. Contradiction with lemma 6.5a! Thus $\squareψ ∈ \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$.

• $\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$

• 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

• 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

• 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

• 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 $V_{g^x_d}(Fx \lor 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)$. $\therefore $\mathcal{I}(a) ∈ \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!

• 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$

• 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.$$

• $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)

• $\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, V_{g^x_{\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, V_{g^x_{\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)

• 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)$

• 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))$

• $\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}$

• 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)$

• 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$

• 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?

• 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_{g^x,y,X_{u,v,\{u\}}}(Xx) = 1$ iff $[x]_{g^x,y,X_{u,v,\{u\}}} ∈ g^x,y,X_{u,v,\{u\}}(X)$, iff $u ∈ \{u\}$. Clearly $u ∈ \{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!

• 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.

• 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!