edl-ex.tex

%!TEX root = edl.tex

\section*{Exercises for Chapter \ref{c:induct}: page \pageref{ex:induct}} \label{ans:induct}

{\small
\begin{enumerate}
	\item We want to show that the LNP holds. The LNP is a conditional claim: so we'll assume the antecedent (`left hand side') of the conditional, and show that the consequent (`right hand side') must then hold, by reasoning using the strong principle.

	We'll reason by \emph{reductio}. So we'll assume that there is a non-empty set of natural numbers $M$ with \emph{no} least member. So now consider this property of natural numbers: \emph{$n$ is not being a member of $M$}, symbolised $n \notin M$.

	Pick some number $k$ at random. Suppose that none of $k$'s  predecessors are in $M$. Could $k$ be in $M$? If it were, it would be the least member of $M$, because it is the earliest member of the natural number sequence to be found in $M$. But $M$ has no least member. So $k\notin M$. Discharge our supposition, we get this conditional: \emph{if for all $n<k$, $n\notin M$, then $k\notin M$}. Since $k$ was random, we didn't use any specific features of $k$ at all. So this reasoning would hold for any number at all. So we have this claim: \emph{For all $k$ (if for all $n<k$, $n\notin M$, then $k\notin M$)}. This is in the right form to apply strong induction. So we conclude: \emph{for all $k$, k \notin M}.

	But now we have a problem: for if no number is a member of $M$, and $M$ is a subset of the natural numbers, then there is only one option: $M$ is empty. Our supposition was that $M$ is non-empty. So collectively,  our suppositions have led to a contradiction. We blame the supposition that $M$ has no least member, so we conclude that if $M$ is a non-empty set of natural numbers, then it must have some least member.

	 \item  Suppose there is some sentence operator \emph{not} that when applied to some sentence $P$ yields a sentence \emph{not-$P$} which is true just in case $P$ is false, and false just in case $P$ is true. We can use this principle, along with plausible principles about truth and disjunction, to argue that Bivalence leads to the LEM.

If Bivalence is true, then for every meaningful sentence $P$, either $P$ is true or $P$ is false. By our assumption about \emph{not}, it follows that either $P$ is true or not-$P$ is true. But then `$P$ or not-$P$' is true (by the principle that if $\phi$ is true or $\psi$ is true, then `$\phi$ or $\psi$' is true). If $\phi$ is true, then $\phi$. So for any meaningful $P$, $P$ or not-$P$, which is the LEM.

The argument from LEM to Bivalence is trickier. We cannot simply run the above argument in reverse. Suppose we try: we assume the LEM, and then conclude that for each $P$, `$P$ or not-$P$' is true. Does this mean that either $P$ is true or `not-$P$' is true? 

Not necessarily. Consider the case of vagueness. Suppose Alice is borderline tall, neither definitely tall nor definitely not tall. It is natural to say that a sentence can be true only if it is definite. A sentence is definite if it doesn't contain any vague terms, or if it does contain them, they don't make a difference. One influential approach to vagueness known as \emph{supervaluationism} \citep{fine} says that the vague terms don't make a difference just in case the sentence would be true no matter how the vague terms are made precise. So the sentence `Alice is tall' is indefinite, because it contains a vague term and on some ways of making `tall' precise, it is true – those where we make it precise by setting the boundary between tall and not-tall below Alice's height - and on other ways of making it precise, it is false. So `Alice is tall' is indefinite, and thus \emph{neither true nor false}. Hence Bivalence fails, according to the supervaluationist.

But what about the sentence `Alice is tall or not-(Alice is tall)'? No matter where we draw the boundary for `tall' – so long as we do it the same way in each disjunct – Alice will fall on one side or the other. So that sentence is definite: no matter how we make the vague expression precise, it doesn't change the truth value. So the whole sentence is definite. In fact, every instance of LEM is definitely true according to the supervaluationist. So while `$P$ or not-$P$' is always true, that doesn't entail – says the supervaluationist – that either $P$ is true or `not-$P$' is true. So the supervaluationist, at least, wants to resist the argument from LEM to Bivalence.
\end{enumerate}

\section*{Exercises for Chapter \ref{c:sets}: page \pageref{ex:sets}} \label{ans:sets}

\begin{enumerate}
	\item \begin{enumerate}
		\item $X\subseteq Y$ iff each member of $X$ is a member of $Y$. $Y \subseteq X$ iff each member of $Y$ is a member of $X$. If both hold, then $X$ and $Y$ have the same members. By extensionality, $x=Y$.  
		\item If $X\subseteq Y$ then every member of $X$ is also a member of $Y$. If $Y \subset Z$, all the members of $Y$ (which include among them all the members of $X$) are members of $Z$. So all the members of $X$ are also members of $Z$, i.e., $X\subseteq Z$. \setcounter{enumii}{3}
		\item If $X \subset Y$, then all members of $X$ are members of $Y$, but not vice versa. So there is at least one member of $Y$ which is not a member of $X$. So $Y\not\subset X$. 
	\end{enumerate}
	\item \begin{enumerate}
		\item $X\cap X$ is the set which has all the members in both $X$ and itself; but that is just the set which shares all its members with $X$, namely $X$ (by extensionality). Similar reasoning shows $X\cup X = X$. \setcounter{enumii}{2}
	\item The set which contains all the members of $X$ and all the members of the empty set can be distinct from $X$ only if there are members of the empty set, which there are not. \setcounter{enumii}{4}
	\item $X\cap(Y \cup Z)$ is the set containing just those members of $X$ which are also members of $Y$ or members of $Z$. There are thus two ways to be a member of this set: be a member of $X$ and  $Y$, or be a member of $X$ and $Z$ (or both). That is equivalent to: be a member of $X \cap Y$ or a member of $X \cap Z$ (or both). That is equivalent to: be a member of $(X\cap Y)\cup(X\cap Z)$. Here we have exploited the connection between conjunction and intersection, and disjunction and union, mentioned in the text. \setcounter{enumii}{6}
	\item The set $X \setminus (Y \cap Z)$ is the set of those members of $X$ which are not members of both $Y$ and $Z$. Something can be a member of this set just in case it is in $X$ but not in $Y$, or is in $X$ but not in $Z$ (or both). Equivalently: be a member of $X \setminus Y$ or a member of $X\setminus Z$; equivalently, be a member of $(X \setminus Y) \cup (X\setminus Z)$.
	\end{enumerate} \setcounter{enumi}{3}
	\item \begin{enumerate}
		\item $«x,y»= «u,v»$ iff $\{\{x\},\{x,y\}\} = \{\{u\},\{u,v\}\}$ iff either (i) $\{x\}=\{u\}$ and $\{x,y\}=\{u,v\}$ or (ii) $\{x\} = \{u,v\}$ and $\{x,y\} = \{u\}$. Case (ii) only holds when $x=y=u=v$, because extensionality entails that identical sets must have the same number of members. In that degenerate case, the theorem holds. In the non-degenerate case where $x≠y$, case (i) must hold. But case (i) holds iff $x=u$ and $y=v$, by extensionality again.
		\item If $x=y$ then $«x,y»=\{\{x\},\{x,x\}\}=\{\{x\},\{x\}\}=\{\{x\}\}$.
	\end{enumerate}
	\item  \begin{enumerate}\setcounter{enumii}{2}
		\item The powerset of any set $Z$ contains sets which have members of $Z$ as their only members. So $\wp(X)$ only contain sets of things from $X$; $\wp(Y)$ only contains sets of things from $Y$. So all the members of $\wp(X)\cup\wp(Y)$ are `pure' sets – it has no members which are sets mixing members of $X$ and $Y$ (except if $X \cap Y$ is non-empty). By contrast, $\wp(X\cup Y)$ does contain such mixed sets. In fact, it is easy to see that as long as there is an $X\setminus Y$ and $Y \setminus X$ are both non-empty, then $\wp(X) \cup \wp(Y) \subset \wp(X \cup Y)$. 

		For example, let $X = \{1,2\}, Y=\{2,3\}$. $\{1,3\}\in \wp(X\cup Y)$, but $\{1,3\}\notin \wp(X)\cup \wp(Y)$; by extensionality, $\wp(X) \cup \wp(Y) \neq \wp(X \cup Y)$. 
	\end{enumerate}\setcounter{enumi}{16}
	\item \begin{enumerate}
		\setcounter{enumii}{2}
		\item \begin{enumerate} 
			\item The successor function which maps each number to its immediate successor (i.e., $\mathsf{succ}(x) = x+1$) is into $\mathbb{N}$ but not onto, since there is no $n$ such that $\mathsf{succ}(n) = 0$ but $0 \in \mathbb{N}$.
			\item The identity function from natural numbers into integers $\mathbb{Z} = \{…,-3,-2,-1,0,1,2,3…\}$ is one-one, since each number is mapped to itself and no other number. But it is not a bijection, because there is no natural number $n$ such that $n = -1$.
			\item Any function which is not one-one has no inverse. So consider the squaring function on integers, $\mathsf{sq}(x) = x^{2}$ for any $x\in\mathbb{Z}$. Since $\mathsf{sq}(2)=\mathsf{sq}(-2)=4$, the relation which is the inverse of $\mathsf{sq}$ contains the pairs $\langle 4,2\rangle$ and $\langle 4,-2\rangle$, and so is not a function.
			\item An argument which is its own inverse is such that $f(f(x)) = f^{-1}(f(x)) = x$. Identity is its own inverse. A more interesting case is negation $\mathsf{n}$, discussed in chapter \autoref{c:l1semantics}. $\mathsf{n}=\{\langle T,F\rangle,\langle F,T\rangle\}$; swap the order of each pair, and we get the same set back. Another example is the function \textsf{rotate 180˚} on the domain of compass directions: apply the function twice, and we get the original argument back again. 
		\end{enumerate}
		\item The union of two functions is itself a function iff the constituent functions are not defined on any argument(s) in common. Since both constituent functions are relations, their union is a relation too (though perhaps on a different – larger – domain); and that relation meets the condition for being a function iff any $a$ which is in the domain of one constituent function and in the domain of the other is such that both functions assign to $a$ that same value.   
	\end{enumerate}
\end{enumerate}

\section*{Exercises for Chapter \ref{c:l1syntax}: page \pageref{ex:l1syntax}} \label{ans:l1syntax}

\begin{enumerate}
	\item Answer: \begin{quote}
		For any numbers $n$ and $m$, \cquote{n+m} denotes a number, as long as `$+$' denotes the addition operator.
	\end{quote} \setcounter{enumi}{2}
	\item Suppose that $\phi$ is a non-atomic \lone\ sentence which is formed in accordance with two formation rules. There are two possible cases: (i) $\phi$ begins with $\neg$. If $\phi$ was also produced by one of the other formation rules, then $\phi = \cquote{(\chi\oplus\pi)}$. If so, `$\neg$' would have to be the same symbol as `$($', which contradicts our supposition that no connective is also a piece of punctuation. (ii) $\phi = \cquote{(\chi\oplus\pi)}$  and $\phi = \cquote{(\psi\otimes\omega)}$ for sentences $\chi,\pi,\psi,\omega$ and binary connectives $\oplus,\otimes$. There are three options for where the relevant occurence of $\otimes$ can occur in $\cquote{(\chi\oplus\pi)}$: it can occur somewhere in $\chi$, it can occur at $\oplus$, or it can occur somewhere in $\pi$. \begin{itemize}
		\item Suppose it occurs in $\chi$. Then $\chi = \cquote{\psi\otimes\sigma}$ for some string $\sigma$. By \autoref{prefix}, since $\chi$ is a sentence, $\psi$ is not, contradiction. 

\item So suppose it occurs in $\pi$. Then $\psi = \cquote{\chi\oplus\sigma'}$ for some string $\sigma'$. Again by \autoref{prefix}, since $\psi$ is a sentence, $\chi$ is not, contradiction.
\item So $\cquote{\oplus=\otimes}$. But that would contradict our intitial assumption that `no character in any category is identical to any other character in that category'. 
	\end{itemize}
So there couldn't be any such sentence $\phi$.
\item Suppose $\phi$ is any \lone\ sentence, and every constituent sentence of $\phi$ of lower complexity is uniquely readable. $\phi$ was either formed by applying negation to a uniquely readable sentence, or applying one of the binary connectives to uniquely readable sentences. By the result of the previous exercise, there is exactly one formation rule that could have been applied to produce $\phi$, and it is uniquely determined which formation rule was applied to construct $\phi$. So $\phi$ too is uniquely readable.  By strong induction, every sentence of \lone\ is uniquely readable.
		
	\end{enumerate}

\section*{Exercises for Chapter \ref{c:l1semantics}: page \pageref{ex:l1semantics}} \label{ans:l1semantics}

\begin{enumerate}
\item $\Gamma \vDash \phi$ iff every \lone-structure $\mathscr{A}$ in which each member of $\Gamma$ is true is also one in which $\phi$ is true; iff every \lone-structure $\mathscr{A}$ in which each member of $\Gamma$ is true is also one in which $\neg\phi$ is false; iff every \lone-structure $\mathscr{A}$ is one in which at least one member of $\Gamma \cup \{\neg\phi\}$ is false; iff $\Gamma\cup\{\neg\phi\}$ is unsatisfiable.
\item \begin{enumerate}
	\item When $\Gamma\vDash\phi$, every line of the truth table on which each member of $\Gamma$ gets a $T$ will be one on which $\phi$ also gets a $T$.
	\item When $\Gamma$ is consistent, at least one line of the truth table will assign a $T$ to each member of $\Gamma$.
	\item When $\phi$ is a contradiction, it will get $F$ on every line of the truth table.
	\item When $\phi$ and $\psi$ are logically equivalent, they get the same value on every line of the truth table. 
\end{enumerate}
\setcounter{enumi}{3}
\item \begin{enumerate}
	\item Suppose $\chi = (\phi\wedge \psi)$. Then $\val{\chi}{A} = F$ iff either $\val{\phi}{A} = F$ or $\val{\psi}{A}=F$ iff either $\val{\phi}{A}\neq T$ or $\val{\psi}{A}\neq T$ iff $\val{\phi \wedge \psi}{A}≠T$ iff $\val{\chi}{A}≠T$.
	\item Suppose $\chi = (\phi \to \psi)$. Then $\val{\chi}{A} = F$ iff $\val{\phi}{A}=T$ and $\val{\psi}{A}=F$ iff $\val{\phi}{A}≠F$ and $\val{\psi}{A} ≠T$ iff  $\val{\phi\to\psi}{A}≠T$ iff $\val{\chi}{A}≠T$.
	\item Suppose $\chi=(\phi\bicond\psi)$. Then $\val{\chi}{A} =F$ iff $\val{\phi}{A}≠\val{\psi}{A}$ iff $\val{(\phi\bicond\psi)}{A}≠T$ iff $\val{\chi}{A}≠T$.
\end{enumerate}
\setcounter{enumi}{8}

\item If $\phi$ and $\psi$ express the same truth-function $f_{n}$, and they contain the same sentence letters $s_{1},…,s_{n}$ then in every structure $\mathscr{A}$, $$f(\mathscr{A}(s_{1}),…,\mathscr{A}(s_{n}))= \val{\phi}{A} = \val{\psi}{A}.$$
But then these two sentence have the same truth value in every \lone-structure, and are logically equivalent. The restriction to sentences with the same sentence letters is crucial. $(P\wedge Q)$ and $(P \wedge R)$ both express the conjunction function $\mathbf{k}$, but are not logically equivalent.

If $\phi$ and $\psi$ contain the same $n$ sentence letters and are logically equivalent, then in every \lone-structure $\mathscr{A}$, $\val{\phi}{A}=\val{\psi}{A}$. If $\phi$ expresses $f$, then $f(\mathscr{A}(s_{1}),…,\mathscr{A}(s_{n})) = \val{\phi}{A}=\val{\psi}{A}$. But since $\psi$ contains just $s_{1},…,s_{n}$ too, $\psi$ also expresses $f$. 

\item The underlying result is this: for any structure $\mathscr{A}$, $$\val{\neg(\phi\bicond\psi)}{A} = \val{(\neg\phi\bicond\psi)}{A}.$$ For $\val{\neg(\phi\bicond\psi)}{A} = T$ iff $\val{\phi\bicond\psi}{A}=F$ iff $\val{\phi}{A}≠\val{\psi}{A}$ iff $\val{\neg\phi}{A}=\val{\psi}{A}$ iff $\val{\neg\phi\bicond\psi}{A}=T$.

Suppose we have some sentence of our language $\mathcal{L}_{\bicond,\neg}$, which has a constituent which is a negated biconditional. We can apply the above result, and \autoref{tequiv}, to derive that the sentence obtained by replacing this constituent by `pushing in' the negation to apply only to the antecedent of the biconditional is logically equivalent to our original sentence. If  we apply this procedure again to the new sentence, and repeatedly the sentence obtained as a result of the procedure, we will eventually drive all negations to rest against sentence letters, and none will have any occurrence of $\bicond$ in their scope. The procedure always reduces the complexity of any negated biconditional sentence, so it will terminate eventually because every sentence has finite complexity. (In effect we have an induction on the maximal complexity of constituents which are negated biconditionals: the procedure shows that if we have a sentence with no negated biconditional constituent of complexity greater than $i$, that is logically equivalent to a sentence with containing no negated biconditional constituent of complexity greater than $i-1$; if our induction hypothesis is that all sentences with a negated biconditional constituent of complexity no greater than $i-1$ are equivalent to sentences with no biconditional in the scope of negation, we have our result. The procedure described may be a little easier to intuitively grasp than induction on complexity of constituents.)

So consider $¬(¬(P\bicond Q)\bicond R)$. We see that the sentence is a negated biconditional, so we apply the procedure to obtain $(¬¬(P \bicond Q) \bicond R)$. We apply the procedure to $¬(P\bicond Q)$ obtaining $(¬(¬P \bicond Q)\bicond R)$. Finally, we apply the procedure to $¬(¬P \bicond Q)$, obtaining $((¬¬P \bicond Q) \bicond R)$.

\end{enumerate}

\section*{Exercises for Chapter \ref{c:l1meta}: page \pageref{ex:l1meta}} \label{ans:l1meta}

\begin{enumerate}
\item \begin{enumerate}\setcounter{enumii}{1}
	\item 	$\val{\phi \wedge \psi}{A} = \max\left(\val{\phi}{A},\val{\psi}{A}\right) = \max\left(\val{\psi}{A},\val{\phi}{A}\right) = \val{\psi\wedge \phi}{A}$, by commutatively of `$\max$'. 
	\item $\mathbf{k}$ is commutative and associative. For, e.g., $\mathbf{k}\left(\val{\phi}{A},\val{\psi}{A}\right) = \val{\phi \wedge \psi}{A} = \val{\psi \wedge \phi}{A} = \mathbf{k}\left(\val{\psi}{A},\val{\phi}{A}\right)$. Similarly, $\mathbf{k}(x,\mathbf{k}(y,z)) = \mathbf{k}(\mathbf{k}(x,y),z)$.
\end{enumerate}\setcounter{enumi}{3}
\item Our task is to construct a sentence in conjunctive normal form that expresses any arbitrary truth function. Suppose we are given an $n$-place truth function. Select $n$ sentence letters $\{s_{1},…,s_{n}\}$, and construct a sentence using them as follows. \begin{itemize}
	\item If in some structure $\mathscr{A}$, $f(\val{s_{1}}{A},…,\val{s_{n}}{A}) = F$, call $\mathscr{A}$ an $f$-disagreeing structure. If $\mathscr{A}$ is an $f$-disagreeing structure, let $$S^{\mathscr{A}}_{i} = \begin{cases}
		s_{i} &\text{if } \val{s_{i}}{A} = F\\	
		¬s_{i} &\text{if } \val{s_{i}}{A} = T.
	\end{cases}$$ For each $f$-disagreeing structure $\mathscr{A}$, we can see that $\val{S_{i}^{\mathscr{A}}}{A} = F$.
	\item Define $\mathfrak{d}_{\mathscr{A}} = \left[\bigvee_{i=1}^{n}S^{\mathscr{A}}_{i}\right]$ for each $f$-disgreeing structure $\mathscr{A}$. Since in each $f$-disagreeing structure, the disjuncts of this disjunction are all $F$, the disjunction $\mathfrak{d}_{\mathscr{A}}$ also is $F$ in an $f$-disagreeing structure $\mathscr{A}$. Indeed, by construction, $\mathfrak{d}_{\mathscr{A}}$ is false only in $\mathscr{A}$ and structures that agree with $\mathscr{A}$ on sentence letters in $\{s_{1},…,s_{n}\}$ – only those structures are guaranteed to be ones where every disjunct is false. 

	There are only finitely many equivalence classes of structures that agree on the setence letters in $\{s_{1},…,s_{n}\}$; for each such class which contains an $f$-disagreeing structure,  pick some $f$-disgreeing structure from it at random. There are finitely many of these chosen $f$-disagreeing structures which can be enumerated $\mathscr{A}_{1},…\mathscr{A}_{m}$. 
	\item Define $\mathfrak{c} = \left[\bigvee_{j=1}^{m} \mathfrak{d}_{\mathscr{A}_{j}}\right]$. This conjunction is false whenever it has any false conjunct, and true otherwise. It is thus false on every $f$-disagreeing structure, and true otherwise. So it expresses $f$.

	If there are no $f$-disagreeing structures, let $\mathfrak{c} = (P\vee \neg P)$, which is obviously true on every structure, just like $f$, and is degenerately in CNF. 
\end{itemize}
What we have done is create a sentence which says, `we are not in row $x$ \emph{and} we are not in row $y$ \emph{and} … \emph{and} we are not in row $z$', for each row of the truth table for $s_{1},…,s_{n}$ where $f$ gets the value $F$.  

\item  Recall that a truth-function is positive iff $f(T,…,T) = T$. Suppose $\phi$ expresses $f$. We want to show that if $\phi$ contains only $\to$ and $\wedge$ as its connectives, $f$ is positive.

\emph{Base case}. $\phi$ is a sentence letter, $s$. If $s$ expresses $f$, then $f(\val{s}{A})=\mathscr{A}(s)$. So if $\mathscr{A}(s) = T$, $f(T) = T$. So $f$ is positive.

\emph{Induction step}. $\phi$ is complex (a conjunction or conditional), and the induction hypothesis holds of its simpler constituents $\phi$ and $\psi$. Then $\psi$ and $\chi$ both express positive truth functions, $f_{\psi}$ and $f_{\chi}$ – so $f_{\psi}(T,…T) = T = f_{\chi}(T,…,T)$.
\begin{itemize}
 	\item $\phi = (\psi \wedge \chi)$. $\phi$ then expresses the truth function $\mathbf{k}(f_{\psi}(\cdots),f_{\chi}(\cdots))$. Since those constituent truth functions are positive, $$\mathbf{k}(f_{\psi}(T,…,T),f_{\chi}(T,…,T)) = \mathbf{k}(T,T)=T.$$ So $\phi$ expresses a positive truth function too.
 	\item $\phi = (\psi \to \chi)$. $\phi$ then expresses the truth function $\mathbf{c}(f_{\psi}(\cdots),f_{\chi}(\cdots))$. Since those constituent truth functions are positive, $$\mathbf{c}(f_{\psi}(T,…,T),f_{\chi}(T,…,T)) = \mathbf{c}(T,T)=T.$$ So $\phi$ expresses a positive truth function too.
 \end{itemize} 
\setcounter{enumi}{5}
\item  \begin{enumerate}\setcounter{enumii}{1}
	\item Yes; $(¬\phi \to \psi)$ is logically equivalent to the disjunction $(\phi \vee \psi)$, and we already know that disjunction and negation are together expressively adequate. 
	\setcounter{enumii}{3}
	\item No. The two-place connectives are all positive, and so cannot ever express a truth-function which is not positive. Negation is not positive, but no sentence involving only negation can be used to express any constant one-place truth function, since $\mathbf{n}(x) ≠ x$, but for a constrant truth function $f(T)=T$ or $f(F)=F$.
	\item $\downarrow$ is expressively complete: $(\phi\downarrow\phi)$ is logically equivalent to $\neg\phi$; and $((\phi\downarrow\psi)\downarrow(\phi\downarrow\psi))$ is logically equivalent to $(\phi\vee\psi)$. And we know that $\{\neg,\vee\}$ is expressively complete.
	\item A 2-place truth-function is expressively adequate if it is able to express all 16 2-place truth functions. \begin{itemize}
	\item It cannot be positive (else it would not be able to express those 8 truth-functions which get the value $F$ when given $T,T$ as input) - this rules out the 8 positive truth functions, leaving 8.
	\item It cannot be negative (i.e., $f(F,F)=F$), since it would not be able to express those 8 truth functions which are not negative. 
	\item This leaves 4 candidates: \begin{tabular}{cc|cccc}
\toprule
	~ & ~ & $f_{\uparrow}$ & $f_{\text{n-right}}$ & $f_{\text{n-left}}$ & $f_{\downarrow}$ \\
	\midrule
	$T$ & $T$ & $F$ & $F$ & $F$ & $F$\\
	$T$ & $F$ & $T$ & $T$ & $F$ & $F$\\
	$F$ & $T$ & $T$ & $F$ & $T$ & $F$\\
	$F$ & $F$ & $T$ & $T$ & $T$ & $T$\\	
	\bottomrule
\end{tabular}

But $f_{\text{n-left}}$ is the truth-function $f(x,y) =\mathbf{n}(x)$, and $f_{\text{n-right}}$ is the truth-function $f(x,y) =\mathbf{n}(y)$. Neither of these truth-functions is able to express any of the 8 truth functions where $f(F,T)=f(T,F)$.  \end{itemize}
So only the connectives which express $f_{\uparrow}$ and 
	$f_{\downarrow}$ are expressively complete by themselves. 
\item $\bot$ is not expressively adequate by itself, since it is not true in any structure and so cannot express any positive truth-function. However, $\{\to,\bot\}$ is expressively adequate: $(P \to \bot)$ expresses the same truth-function as $\neg P$ (because that conditional expresses the function that yields $F$ iff only if $P$ is true and $\bot$ is false, but since $\bot$ is always false, iff $P$ is true). And it can be easily verified that $((P\to\bot)\to Q)$ expresses disjunction $(P\vee Q)$. And conjunction isn't expressively adequate itself.
\end{enumerate}
\item  \begin{enumerate}
	\item We can express negation using $\to$ and $\to^{\star}$ as follows: $P \to^{\star} (P \to P)$ (or $P \to (P \to^{\star} P)$). Since $\{\neg,\to\}$ are expressively adequate, so too is $\{\to,\to^{\star}\}$.

	Self-duality is not sufficient for expressive adequacy, since $\{¬\}$ is a self-dual set without being expressively adequate. Nor is it necessary, since $\{\uparrow\}$ is expressively adequate without being a self-dual set. 
	\item The definition of duality is such that if $f(x,y) = z$ then $f^{\star}(x^{\star},y^{\star}) = z^{\star}$. If $f =f^{\star}$, so that $f$ is self-dual, then if $f(T,F) = z$, $f(F,T) = z^{\star}$, so $f(T,F)≠f(F,T)$. Likewise $f(T,T)≠f(F,F)$. 

	There are 16 2-place truth-functions. But 12 of them are such that either the top line or bottom line of the truth-table are the same, or the two middle lines of the truth table are the same. So only 4 could be self-dual: the four degenerate truth-functions that track their first input or second input or their negations, $f_{\text{left}}, f_{\text{n-left}}, f_{\text{right}}, f_{\text{n-right}}$. These are self-dual, basically because when we `flip' the truth table, these functions directly follow the flipped inputs to the truth-functions, undistorted by any contribution from the other input.
\end{enumerate}
\setcounter{enumi}{8}
\item \begin{enumerate}
	\item $(¬Q \vee R)$;
	\setcounter{enumii}{2}
	\item $(P\to Q)$.
\end{enumerate}
\item \begin{enumerate}
	\setcounter{enumii}{1} \item If $\Gamma \vDash^{\!\star} \Delta$, then every structure which satisfies all of $\Gamma$ satisfies at least one of $\Delta$. So there can be no structure which satisfies all of $\Gamma$ and none of $\Delta$. Let $\widetilde{\Delta}$ be the set which results from taking every member of $\Delta$ and negating it (i.e., $\widetilde{\Delta} = \{\neg\delta : \delta\in \Delta\}$). Then $\Gamma\cup\widetilde{\Delta}$ is unsatisfiable. By Compactness, some finite subset of $\Gamma\cup\widetilde{\Delta}$ is unsatisfiable – call that set $G\widetilde{D}$. There are three cases to consider: \begin{itemize}
		\item $G\widetilde{D}$ contains elements from both $\Gamma$ and $\widetilde{\Delta}$. Let $\Phi$ be the conjunction of all sentences in both $\Gamma$ and $G\widetilde{D}$. Since the latter is finite, the conjunction is finite: $(\phi_{1}\wedge…\wedge \phi_{m})$. Let $\Psi'$ be the conjunction of all sentences in $\widetilde{\Delta}$ and $G\widetilde{D}$. Since $\Psi'$ is a conjunction of negated sentences $(\neg\psi_{1}\wedge…\wedge ¬\psi_{n})$, it is logically equivalent to a negated disjunction $¬(\psi_{i}\vee…\vee \psi_{n}) = ¬\Psi$. (Note that $\Psi$ is the embedded disjunction.) Since $G\widetilde{D}$ is unsatisfiable, $\Phi,¬ \Psi \vDash$; by \autoref{entuns}, $\Phi\vDash \Psi$, and $\Phi$ and $\Psi$ are of the right form.
		\item $G\widetilde{D}$ contains elements only from $\Gamma$. Let $\Phi$ be the conjunction of every sentence in $G\widetilde{D}$, and let $\Psi$ be an arbitrary finite disjunction of members from $\Delta$. Since $G\widetilde{D}\subseteq \Gamma$, $\Phi$ is of the right form, and since $\Phi$ is a contradiction, $\Phi\vDash\Psi$.
		\item  $G\widetilde{D}$ contains elements only from $\widetilde{\Delta}$. Then every structure makes some member of $\Delta$ true whose negation is in $G\widetilde{D}$. Let $\Psi$ be the disjunction of negations of every sentence in $G\widetilde{D}$; this is a finite tautologous disjunction. Let $\Phi$ be an arbitrary finite conjunction of members from $\Gamma$. Since $\Psi$ is a tautology, $\Phi\vDash \Psi$.
	\end{itemize}
\end{enumerate}
\item \begin{enumerate}
	\item The set of effective procedures is roughly the set of finite recipes in English. Each such recipe is a finite sequence of characters drawn from a finite alphabet, and by the same argument as in the Key Lemma \ref{keylemma}, there are only countably many effective procedures. We suppose they can be recursively enumerated because the set of finite sets of English sentences can be effectively generated – this follows from the fact that we can effectively generate finite subsets of $\mathbb{N}$.
	\item \begin{enumerate}
		\item If there were an effective procedure for computing $d$, it would be a member of $E$ – say it would be the $k$-th recipe under the relevant enumeration of recipes. But if $d$ is computed by the $k$-th recipe, then $d=f_{k}$. But $d(k) ≠ f_{k}(k)$, by construction of $d$. So $d$ cannot be computed by the $k$-th recipe. Since $k$ was arbitrary, $d$ cannot be computed by any effective recipe specifiable in English.
		\item Suppose there were an effective procedure for sorting recipes into those which are \emph{good} (compute a function in a finite time) and those which are \emph{garbage} (not computing a function, not halting in a finite time.) This procedure would determine a function: $$g(i) = \begin{cases}
			1 &\text{ iff the $i$-th recipe in $E$ is good;}\\
			0 &\text{ otherwise}.
		\end{cases}$$

If this function $g$ is effectively computable, then $d$ is effectively computable. The recipe for computing each $d(n)$ is this: \begin{verbatim}
    On given input n, compute g(n) 
        If g(n) = 0, then set d(n) = 1. 
        If g(n) = 1, then compute f_n(n)
            If f_n(n) = 1, then set d(n) = 2;
            If f_n(n) ≠ 1, then set d(n) = 1.
\end{verbatim} 
If $g$ is a good test for effective procedures, every function in this little flowchat is calculate by an effective procedure, so for each $n$, we determine the value of $d(n)$ in a finite time. So $d$ is effectively computable. But the previous exercise just showed that $d$ is not effectively computable, hence $g$ is not effectively computable.

This shows that the set of effective procedures is recursively enumerable but not recursive.

	\end{enumerate}
\end{enumerate}
\end{enumerate}

}

\section*{Exercises for Chapter \ref{c:l1tabl}: page \pageref{ex:l1tabl}} \label{ans:l1tabl}

{\small
\begin{enumerate}
\item ~{\leaf{$P$\\ $\mathbf{\otimes}$}\leaf{$Q$\\ $\mathbf{\otimes}$}\branch{2}{$P\vee Q$}\branch{1}{$¬¬(P\vee Q)$\\ $¬P$\\ $¬Q$}\qobitree
}


\item \begin{enumerate}
	\item ~
	 {\leaf{$P$\\ $¬(P \vee P)$\\ $¬P$\\ $¬P$\\ $\mathbf{\otimes}$} \leaf{$P$\\ $\mathbf{\otimes}$}\leaf{$P$\\ $\mathbf{\otimes}$}\branch{2}{$¬P$\\$P \vee P$}\branch{2}{$¬(P \bicond (P \vee P))$ }\leaf{$¬P$\\ $\mathbf{\otimes}$}\leaf{$¬P$\\ $\mathbf{\otimes}$}\branch{2}{$P$\\$¬(P \wedge P)$} \leaf{$¬P$\\ $(P \wedge P)$\\ $P$\\ $P$\\ $\mathbf{\otimes}$}\branch{2}{$¬(P \bicond(P \wedge P))$}\branch{2}{$¬((P\bicond (P\vee P))\wedge(P\bicond (P\wedge P)))$}	\qobitree}
 \setcounter{enumii}{4}
	\item ~ {\leaf{$¬P$\\$\mathbf{\otimes}$}\leaf{$Q$\\$\mathbf{\otimes}$}\branch{2}{$P$}\leaf{$R$\\$\mathbf{\otimes}$}\branch{2}{$P \to Q$\\ $¬((P \vee R) \to (Q \vee R))$\\ $P\vee R$\\ $¬(Q \vee R)$\\ $¬Q$\\ $¬R$}\branch{1}{$¬((P\to Q) \to ((P \vee R) \to (Q \vee R)))$}
	\qobitree}
\end{enumerate}
\item \begin{enumerate}\setcounter{enumii}{3}
	\item ~ 
	{\leaf{$¬(P\to Q)$\\ $P$\\ $¬Q$\\ $\mathbf{\otimes}$} 
	\leaf{$Q$\\ $\mathbf{\otimes}$} \branch{2}{$¬P$\\ $¬Q$} \branch{1}{$(P\to Q) \to Q$\\ $¬(P\vee Q)$}\qobitree
	}
	\item ~ {
	\leaf{$¬P$\\ $\mathbf{\otimes}$} \leaf {$¬Q$\\ $\mathbf{\otimes}$} \branch{2}{$P$\\ $Q$}
	\leaf{$¬¬P$\\ $\mathbf{\otimes}$} \leaf{$¬¬Q$\\ $\mathbf{\otimes}$} \branch{2}{$¬P$} 
	\leaf{$¬¬P$\\ $\mathbf{\otimes}$} \leaf{$¬¬Q$\\ $\mathbf{\otimes}$} \branch{2}{$¬Q$} \branch{2}{$¬P$\\$¬Q$} \branch{2}{$¬(P\wedge Q)$ \\ $¬(¬P \wedge ¬Q)$} \branch{1}{$P \bicond Q$ \\ $¬(¬(P\wedge Q)\to(¬P \wedge ¬Q))$} \qobitree 
	}
\end{enumerate}
\item \begin{enumerate}
	\item ~ {
	\leaf{$¬P$} \leaf{$¬R$} \branch{2}{$¬(P\wedge R)$} \leaf{$Q$} \branch{2}{$¬R$} 
	\leaf{$¬P$\\ $\mathbf{\otimes}$} \leaf{$¬R$} \branch{2}{$¬(P \wedge R)$} \leaf{$Q$\\ $\mathbf{\otimes}$} \branch{2}{$¬(P \to Q)$\\ $P$\\ $¬Q$} \branch{2}{$(P\wedge R) \to Q$ \\ $¬(R \wedge(P \to Q))$}\qobitree
	}
	\item ~ {
	\leaf{$P$} \leaf{$Q$} \branch{2}{$Q$} \branch{1}{$P \vee Q$\\ $P$ \\ $¬¬Q$} \qobitree
	}

\end{enumerate}
 \setcounter{enumi}{5}
\item Any finished tableau generated by $\{\neg\phi\}$ is closed, because that is what $\vdash\phi$ means. Consider a tableau $\mathsf{T}$ generated by $\neg(\psi\to\phi)$. We apply the negated conditional rule, adding $\psi$ and $\neg\phi$ below the root node. Then we extend the resulting tableau by adding the subsequent contents of every branch on some finished tableau generated by $\{\neg\phi\}$ to every branch stemming from $¬\phi$ on $\mathbf{T}$. So $\mathbf{T}$ is closed (it may not be finished, if there are tableau rules to apply to $\psi$; but it doesn't matter, since adding more sentences cannot unclose a closed branch). So $\vdash\psi\to\phi$.
\end{enumerate}

\section*{Exercises for Chapter \ref{c:tablmeta}: page \pageref{ex:tablmeta}} \label{ans:tablmeta}

{\small
\begin{enumerate}
\item 
\item \begin{enumerate}
	\item The truth function $\mathbf{nor}$. Here is the informal argument. In any tableaux system, for each connective, there is a rule for that connective, and a rule for the negated connective. The left displayed rule clearly concerns the connective $\odot$; so perhaps the right displayed rule concern its `negation'? If so, given that right-hand rule is of the form $\chi\odot\chi$, \emph{that} must be how to express negation in this system. So the left-hand rule now says: from $\phi\odot\psi$, conclude both that $\phi$ is false and $\psi $ is false; so $\phi\odot\psi$ is sufficient for neither of $\phi$ or $\psi$ to be true. The right-hand rule says: from the falsity of $\phi\odot\psi$, conclude that either $\phi$ or $\psi$ is true. From both rules together, therefore, we know that both $\phi$ and $\psi$ being false is necessary and sufficient for $\phi\odot\psi$ to be true, i.e., that $\odot$ expresses the truth function $\mathbf{nor}(x,y) = 1$ iff $x=0$ and $y=0$. 

\item If both $\phi$ and $\phi\odot\phi$ occur on a branch.
\end{enumerate}
\end{enumerate}

}

% \section*{Exercises for Chapter \ref{c:l1nd}: page \pageref{ex:l1nd}} \label{ans:l1nd}

% {\small
% \begin{enumerate}
% \item f
% \end{enumerate}

% }

% \section*{Exercises for Chapter \ref{c:ndmeta}: page \pageref{ex:ndmeta}} \label{ans:ndmeta}

% {\small
% \begin{enumerate}
% \item 
% \end{enumerate}

% }

\section*{Exercises for Chapter \ref{c:l2}: page \pageref{ex:l2}} \label{ans:l2}

{\small
\begin{enumerate}
\setcounter{enumi}{1}
\item By Definition \ref{ltwosats}, $\valsa{\exists\upsilon\phi} = T$ iff $\vals{\phi}{A}{\beta}=T$ for at least one variable assignment $\beta$ over $\mathscr{A}$ differing from $\alpha$ \emph{at most} in its assignment to $\upsilon$, iff  $\vals{¬\phi}{A}{\beta}=F$ iff $\vals{¬\phi}{A}{\beta}≠T$ iff $\valsa{\forall\upsilon\neg\phi}≠T$ (since $\beta$ is a variable assignment differing from $\alpha$ at most in what it assigns to $\upsilon$), iff $\valsa{\neg\forall \upsilon¬ \phi}=T$.
\setcounter{enumi}{6}
\item If $\Gamma,\phi[\tau/\upsilon]\vDash \psi$, then every \ltwo-structure in which all of $\Gamma$ and $\phi[\tau/\upsilon]$ are satisfied is also a structure in which $\psi$ is satisfied. 

Suppose there is an \ltwo-structure $\mathscr{A}$ in which all members of $\Gamma$ are satisfied, and $\exists \upsilon \phi$ is satisfied, but $\psi$ is not. Then there is a variable assignment $\alpha$ such that $\valsa{\phi}=T$. There exists an altered structure $\mathscr{A}'$ such that $\vals{\tau}{A'}{\alpha}=\alpha(\tau)$ – i.e., it assigns to $\tau$ what $\alpha$ assigns to $\upsilon$ in $\mathscr{A}$. Since $\valsa{\phi}=T$, $\val{\phi[\tau/\upsilon]}{A'}{\alpha}=T$.  Suppose $\Gamma$ is also satisfied in $\mathscr{A}'$ (if it is not, choose another altered structure in which it is: if there is none, then $\Gamma \cup \{\exists \upsilon \phi\}$ must be unsatisfiable, and the desired conclusion follows trivially). But then $\mathscr{A}'$ must make $\psi$ true by hypothesis. On the other hand, since $\mathscr{A}'$ differs from $\mathscr{A}$ only in what it assigns to $\tau$, and $\tau$ doesn't occur in $\psi$, $\psi$ must also be false in $\mathscr{A}'$ since we've assumed it is false in $\mathscr{A}$. Contradiction: so $\Gamma, \exists \upsilon\phi \vDash \psi$.


\setcounter{enumi}{9}
\item Consider any \ltwo-structure $\mathscr{A}$ which makes $\forall \xi (\phi\bicond \psi)$ true under some arbitrary variable assignment $\alpha$. $\mathscr{A}$ is such that $\vals{\phi\bicond \psi}{A}{\beta} = T$ for any variable assignments $\beta$ differing from $\alpha$ at most in what they assign to $\xi$. 

Suppose $\valsa{\forall \xi\phi} ≠ \valsa{\forall \xi\psi}$. Then for one such variable assignment $\beta$ differing from $\alpha$ at most in what it assigns to $\xi$, $\vals{\phi}{A}{\beta}≠\vals{\psi}{A}{\beta}$. But since $\vals{\phi\bicond \psi}{A}{\beta} = T$, $\vals{\phi}{A}{\beta}=\vals{\psi}{A}{\beta}$. Contradiction; so $\valsa{\forall \xi\phi} = \valsa{\forall \xi\psi}$, and hence $\valsa{\forall \xi \phi \bicond \forall \xi \psi}=T$.

\setcounter{enumi}{14}
\item An uncountable domain has too many members to be named; that was the problem for substitutional quantification. But since all of our formula are finite, no open formula of \ltwo\ ever has more than finitely many variables needed to be assigned values by any one variable assignment. So whenever we need to consider whether a sentence is true, we only need to consider variable assignments which temporarily assign names to finitely many members of the uncountable domain.

But we have enough variable assignments so that any object which can be discussed even indirectly can be temporarily named. So consider the problem case $\forall x (\text{Integer}(x))$ evaluated in a structure $\mathscr{A}$ with domain of the reals $\mathbb{R}$ and an interpretation which assigns to every constant an integer. This quantified sentence  is nevertheless false, since there is a variable assignment $\alpha$ on that structure which assigns to $x$ some non-integer value, and $\valsa{\text{Integer}(x)}=F$.



\end{enumerate}

}

% \section*{Exercises for Chapter \ref{c:l2nd}: page \pageref{ex:l2nd}} \label{ans:l2nd}

% {\small
% \begin{enumerate}
% \setcounter{enumi}{1}
% \item 2
% \setcounter{enumi}{6}
% \item 7
% \setcounter{enumi}{9}
% \item 10
% \setcounter{enumi}{14}
% \item 15


% \end{enumerate}

% }

 \section*{Exercises for Chapter \ref{c:lequals}: page \pageref{ex:lequals}} \label{ans:lequals}

% {\small
% \begin{enumerate}
% \setcounter{enumi}{1}
% \item 2
% \setcounter{enumi}{6}
% \item 7
% \setcounter{enumi}{9}
% \item 10
% \setcounter{enumi}{14}
% \item 15


% \end{enumerate}

% }

\section*{Exercises for Chapter \ref{c:cond}: page \pageref{ex:cond}} \label{ans:cond}

{\small
 \begin{enumerate}
\item Each instance of the form $((\phi \to \psi)\wedge\phi)\vDash\psi$ is a valid entailment. By Upper, $((\phi \to \psi)\wedge\phi)\Rightarrow\psi$. By Import-Export, $(\phi\to\psi)\Rightarrow(\phi\Rightarrow\psi)$. By Lower, $(\phi\to\psi)\to(\phi\Rightarrow\psi)$. Assume $\phi\to\psi$; by \emph{modus ponens} for $\to$, we may conclude $\phi\Rightarrow\psi$. The converse direction is immediate from Lower. So $\phi\to\psi$ is equivalent to $\phi\Rightarrow\psi$.
\item \begin{enumerate}
	\item John is using an informal analogue of the deduction theorem: that $\phi,\psi\vDash\psi$ suffices for $\psi\vDash\text{If }\phi, \psi$. This perhaps doesn't seem plausible when $\phi$ is arbitrary, though the general form seems defensible enough: when both $\phi$ and $\psi$ are actually used in the derivation of some conclusion $\chi$, then $\psi$ alone suffices for `If $\phi$, $\chi$'.
	\item This is contraposition, which looks very plausible for the English indicative (though see below). For if $\phi$'s truth leads to $\psi$'s truth, as the conditional appears to represent, then if $\psi$ were false, it can't still be that $\phi$ is true – otherwise $\psi$ would be false and also true.
	\item Suppose $\phi\to\psi$. This is equivalent to $\neg\phi\vee\psi$. If $\psi$, then by John's argument, `if $\phi$, $\psi$'. If $\neg\phi$, then by John's argument, `If $\neg\psi$, $¬\phi$', so by Mary's argument, `If $\phi$, $\psi$'. So on each disjunct, `If $\phi$, $\psi$' follows. So $\phi\to\psi$ entails `If $\phi$, $\psi$'.
	\item As long as `If $\phi$, $\psi$' entails $\phi\to\psi$, we have logical equivalence and hence `if' is the material conditional. But both contraposition and the deduction theorem may not be in the end correct for the English indicative.
\end{enumerate}
\item \begin{enumerate}
	\item Consider any \lone\ structure $\mathscr{A}$ in which $\phi\to\psi$ is true. Either $\phi$ is false in $\mathscr{A}$ or $\psi$ is true; iff either $\neg\psi$ is false in $\mathscr{A}$ or $\neg\phi$ is true; iff $\neg\neg\psi$ is true in $\mathscr{A}$ or $\neg\phi$ is true; iff $\neg\neg\psi\vee\neg\phi$ is true in $\mathscr{A}$; iff $\neg\psi\to\neg\phi$ is true in $\mathscr{A}$.
	\item Examples that seem to show contraposition failing for the counterfactual exist. Here are a couple: \begin{exe}
\ex		\begin{xlist}
			\ex If Michael Jordan had been short, he wouldn't have been really short. \label{cfacta1} ($S\, \Box\!\!\rightarrow ¬RS$)
			\ex So, If Michael Jordan had been really short, he wouldn't have been short. \label{cfacta2} ($RS\, \Box\!\!\rightarrow ¬S$)
		\end{xlist}
	\end{exe}
	 Intuitively, \eqref{cfacta1} is true but \eqref{cfacta2} false. Here's another example. Suppose I have chronic back pain, leaving me housebound.
	\begin{exe}
		\ex \begin{xlist}
			\ex If I'd been able to leave the house, I would (still) have had a bad back. \label{cfactb1}
			\ex So, If I hadn't had a bad back, I wouldn't have been able to leave the house. \label{cfactb2}
		\end{xlist}
	\end{exe}
Intuitively, \eqref{cfactb1} might be true – if I'd been able to leave the house, it would have been because I'd improved just enough to do so, not been totally cured. But then \eqref{cfactb2} is false: I would easily have been able to leave the house then!

It is easy to draw similarity spheres which represent these situations in Lewis' semantics. They have to have the closest $A$-world be a $C$-world, but the closest $¬C$-world \emph{still} be an $A$-world.
\item Suppose $\Box(\phi\to\psi)$ holds at $w$, but $v(w,\Box(¬\psi\to ¬\phi))=F$. Then there is an accessible world $w'$ such that $v(w',¬\psi\to ¬\phi)=F$, so $v(w',¬\psi)=T$ and $v(w',¬\phi)=F$, so that $v(w',\psi)=F$ and $v(w',\phi)=T$. But then $v(w',\phi\to\psi)=F$, hence $v(w,\Box(\phi\to\psi))=F$, contradiction. So there is no such $w$; contraposition for the strict conditional is valid in any logic extending $\mathscr{L}_{\mathsf{K}}$.
\end{enumerate}
\item \begin{enumerate}
	\item In any $\mathscr{L}_{1}$-structure $\mathscr{A}$, for any sentences $\phi,\psi$ either $|\phi|_{\mathscr{A}} = |\psi|_{\mathscr{A}}$ or $|\phi|_{\mathscr{A}} = |¬\psi|_{\mathscr{A}}$. If the former, $|\phi\to\psi|_{\mathscr{A}} = T$. If the latter, $|\phi\to ¬\psi|_{\mathscr{A}} = T$. So in any $\mathscr{A}$, $|(\phi\to\psi)\vee(\phi\to ¬\psi)|_{\mathscr{A}} = T$.
	\item Consider an $\mathscr{L}_{\mathsf{K}}$ model with domain $\{w,w'\}$, such that $v(w,\phi)=v(w',\phi)=T$, $v(w,\psi)=F$, $v(w',\psi)=T$. Then $v(w,\phi\to\psi)=F$, $v(w',\phi\to ¬\psi)=F$. Assume $w\mathscr{R}w$ and $w\mathscr{R}w'$; then $v(w,\Box(\phi\to\psi))=F$ and $v(w,\Box(\phi\to ¬\psi))=F$.
	\item Lewis' example is: `if Bizet and Verdi had been compatriots, they would have both been French'. He thinks: this is false. It is true that both would have been French, or both Italian – the closest world where they share a nationality is one where only one of them has to change their actual nationality. In the similarity semantics, the set of closest worlds where Bizet and Verdi are compatriots has at least two members. Indeed, the violation of this condition is the formal analogue of CEM: if there is a unique closest $A$-world, then since either $C$ or $¬C$ is true at it, either $A\, \Box\!\!\rightarrow C$ or $A\, \Box\!\!\rightarrow ¬C$ is true actually.
	\item This is tough to answer. But it may only appear plausible because we consider too few cases. Consider this: I have a fair coin in my pocket, which I never toss. I say: `Had I tossed this coin, it would have landed heads'. This seems false: part of what it is to be a fair coin is that there is no determinate fact of the matter about what would happen if I toss it. You wish to deny what I say. But you do not deny it by asserting this equally false counterfactual: `Had you tossed the coin, it would not have landed heads'. You rather should say: `It isn't the case that had you tossed the coin, it would have landed heads'.
	
	While asserting $A \Rightarrow ¬C$ suffices to deny $A\Rightarrow C$, it is not equivalent to the negation of that conditional, in general. It is more plausible to equate $¬(A \Rightarrow C)$ with $(A \Rightarrow ¬C)$ in the case of the indicative. There we are considering just one world – actuality – and what must be true of it under the supposition that $A$. Since just one of $C, ¬C$ is true of actuality, one is true under that supposition, which would give us CEM. But the counterfactual invites us to consider alternatives to actuality, and there may be more than one such alternative to be considered which can allow for violations of CEM.
\end{enumerate}
\item It certainly seems good for both at first glance. Note immediately that since the counterfactual satisfies both Upper and Lower, if the counterfactual satisfied Import-Export, then by Gibbard's theorem the counterfactual would be the material conditional. So there must be violations of Import-Export in Lewis' semantics. Consider: $(\phi\wedge \psi)\,\Box\!\!\to ¬\phi$ is always false (at least when there is some $\phi\wedge \psi$ world). But we can construct a model where $\phi\, \Box\!\!\to (\psi\,\Box\!\!\to¬\phi)$ is true. ('If I had picked your pocket, then if you had been watching me the whole time, I wouldn't have picked your pocket' - sounds a bit awkward but can see a reading on which it might be true.)

The indicative is more interesting, since people have used Import-Export to provide counterexamples to \emph{modus ponens}. Recall McGee's election example  from \autoref{c:cond}. The counterexample to \emph{modus ponens} is supposed to arise because we think the antecedent of the conditional ('a Republican wins!') is likely true, and yet the embedded conditional consequent likely false. Yet the larger conditional itself seems true – because it follows from the  true conditional \ref{imp} by Import-Export. We seem to have a choice: accept `if that creature has lungs, it's a lungfish'; reject Import-Export; or reject \emph{modus ponens}. Many have found rejecting Import-Export, and thus rejecting the nested conditional, the most palatable way out. The material conditional approach accepts the conclusion; Stalnaker's semantics for indicatives invalidates Import-Export.

\end{enumerate}
}