# Exercise Sheet 3 for: Adaptive Logics applied to the Philosophy of Science

Back to the main course site $$\def\impl{\supset} \def\Dab{{\sf Dab}}$$ $$\newcommand{\vd}[1]{\vdash_{\bf #1}}$$

Demonstrate that in system P strengthened with (K) $$\vdash \mathsf{O}(A \rightarrow B) \rightarrow ({\sf O}A \rightarrow {\sf O} B)$$ the aggregation principle (C) $$\vdash ({\sf O}A \wedge {\sf O}B) \rightarrow {\sf O}(A \wedge B)$$ is derivable.

Demonstrate that in system P strengthened with (C), (D) $$\vdash {\sf O}A \rightarrow \neg{\sf O}\neg A$$ is derivable.

Check whether if we restrict ourselves to limited frames the following definition is equivalent to how $$M,a \models_{P} {\sf O}A$$ is defined in Def. (P-O) on page 386:

$$M,a \models_{P} {\sf O}A$$ iff there is a maximal$$_{a}$$ $$b \in \mathcal{F}S_{a}$$ such that $$M,b \models_P A$$.

## Task 4: Weak vs. Strong Completeness

The adequacy results in the paper concern what is sometimes called weak completeness.

It goes as follows: where a logic L is identified with its set of theorems $${\sf S}$$, L is complete with respect to a set of frames $$\mathcal{F}$$ iff for every $$A$$ that is valid for $$\mathcal{F}$$, $$A$$ is a theorem of the logic L, ie., $$A \in {\sf S}$$.

The set of theorems of a logic L that is correlated with a set of axiom schemes and some inference rules is obtained as follows:

• take all instances of the axiom schemes (obtained by uniform substitution)
• apply the inference rules to this obtained set

Any formula that can be obtained by this procedure is a theorem of L.

Strong completeness does not only concern theorems of a logic, but rather the consequence relation that is characterised by L. The consequence set $$C_{\bf L}(\Gamma)$$ for a set of formulas $$\Gamma$$ is obtained by applying the inference rules of L to both $$\Gamma$$ and the instances of the axiom schemes. A logic L is strongly complete w.r.t. a set of frames $$\mathcal{F}$$ iff for all (possibly infinite) sets of premises $$\Gamma$$, if $$A$$ is valid in all models $$\langle F, v\rangle$$ of $$\Gamma$$ (where $$F \in \mathcal{F}$$) then $$A \in C_{\bf L}(\Gamma)$$.

One question that is not answered in Goble's article is the following:

Claim ($$\dagger$$): SDL also strongly complete w.r.t. limited standard preference frames.

Consider the following example, where $$A > B$$ is defined by $$\neg(B \ge A)$$: $$\Gamma = \left\{ \left(p_{i+1} \wedge \bigwedge_{j \le i} \neg p_j \right) > p_{i} \mid i \ge 1 \right\} \cup \{p_1 > \bot)\}$$.

Does it establish a counterexample to the claim ($$\dagger$$)?

Created: 2015-04-17 Fri 11:17

Emacs 24.4.1 (Org mode 8.2.10)

Validate