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

Table of Contents

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

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

Task 2

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

Task 3

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\))?

Author: Christian Straßer

Created: 2015-04-17 Fri 11:17

Emacs 24.4.1 (Org mode 8.2.10)