PhD Notes

Contents:

Learning-based truth tracking (2)

\[\gdef{\phi}{\varphi} \gdef{\epsilon}{\varepsilon} \gdef{\prop}{\mathsf{Prop}} \gdef{\l}{\mathcal{L}} \gdef{\LL}{\mathbb{L}} \gdef{\lprop}{\l_0} \gdef{\S}{\mathcal{S}} \gdef{\D}{\mathcal{D}} \gdef{\Q}{\mathcal{Q}} \gdef{\K}{\mathsf{K}} \gdef{\Kdual}{{\widehat{\mathsf{K}}}} \gdef{\KW}{\mathsf{KW}} \gdef{\A}{\mathsf{A}} \gdef{\N}{\mathbb{N}} \gdef{\streams}{\mathsf{str}}\]

Preliminaries

  • \(\prop\) is a countable set of propositional atoms, and \(\lprop\) the corresponding propositional language. We write \(\alpha, \beta\) etc for formulas in \(\lprop\).

  • \(\S\) is a finite set of sources. We write \(i, j\) etc for sources in \(\S\).

  • \(\l\) is the modal language over \(\prop\) with modalities \(\K_i\phi\), for \(i \in \S\). We write \(\phi, \psi\) etc for formulas in \(\l\).

  • \(\Kdual_i\) is an abbreviation for \(\neg \K_i \neg\).

  • A model is a triple \(M = (X, \{R_i\}_{i \in \S}, v)\), where \(X\) is a set of states, each \(R_i\) is an equivalence relation on \(X\), and \(v: \prop \to 2^X\) is a valuation (i.e. an S5 model). The satisfaction relation between pointed models \((M, x)\) and formulas in \(\l\) is defined as usual.

  • A domain is a pair \(\D = (X, v)\).

  • \(\Omega_\D\) denotes the set of pointed models \((M, x)\), where \(M\) is a model in \(\D\) and \(x \in X\). We describe elements in \(\Omega_\D\) as worlds, and denote them by \(w, w'\) etc.

  • For \(\phi \in \l\), write \(\|\phi\|_\D = \{w \in \Omega_\D \mid w \models \phi\}\).

  • A learner (in domain \(\D\)) is a function \(L: (\S \times \lprop)^* \to 2^{\Omega_\D}\) which maps each finite sequence of reports of the form \((i, \alpha)\) to a set of worlds. \(L\) is consistent if \(L(\sigma) \ne \emptyset\) for all sequences \(\sigma\).

  • Let \(\epsilon \in (\S \times \lprop)^\N\) be a sequence of reports, and let \(\bigcirc \in \{\K, \Kdual\}\). Say \(\epsilon\) is \(\bigcirc\)-sound for \(w \in \Omega_\D\) iff for all \((i, \alpha) \in \epsilon\) we have \(w \models \bigcirc_i\alpha\). Say \(\epsilon\) is \(\bigcirc\)-complete if whenever \(w \models \bigcirc_i\alpha\) we have \((i, \alpha) \in \epsilon\). Say \(\epsilon\) is a \(\bigcirc\)-stream for \(w\) if it both \(\bigcirc\)-sound and \(\bigcirc\)-complete. The set of \(\bigcirc\)-streams for \(w\) is denoted by \(\streams_\bigcirc(w)\)

  • For a sequence \(\epsilon\) and \(n \in \N\), let \(\epsilon[n]\) denote the initial prefix of \(\epsilon\) of length \(n\).

Learning

  • Take a domain \(\D = (X, v)\). The following definitions will be made with respect to \(\D\). We write \(\Omega\) for \(\Omega_\D\).

  • A question \(\Q\) is a partition of \(\Omega\). For \(w \in \Omega\), the unique set in \(\Q\) containing \(w\) is denoted by \(\Q_w\).

  • The set of questions forms a (bounded, complete) lattice when ordered by refinement (denoted \(\preceq\))

  • \(\Q\) is \(\bigcirc\)-solvable if there is a consistent learner \(L\) such that for every \(w \in \Omega\) and every \(\bigcirc\)-stream \(\epsilon\) for \(w\), we have \(L(\epsilon[n]) \subseteq \Q_w\) for cofinitely many \(n \in \N\).

  • Any \(\phi \in \l\) induces the question \(\Q_\phi = \{\|\phi\|, \|\neg\phi\|\}\). Say \(\phi\) is solvable iff \(\Q_\phi\) is.

Topological characterisation of solvability

  • Again, fix a domain \(\D\).

  • Let \(\tau_\bigcirc\) be the topology on \(\Omega\) generated by \(\{\|\bigcirc_i\alpha\| \mid i \in \S, \alpha \in \lprop\}\). For a finite sequence \(\sigma\), write \(U_\sigma^\bigcirc = \bigcap_{(i, \alpha) \in \sigma}{\|\bigcirc_i\alpha\|}\). Then the set of \(U^\bigcirc_\sigma\) is a basis for \(\tau_\bigcirc\).

  • Say \(S \subseteq \Omega\) is constructible if \(S\) is a finite union of locally closed sets. 1 Say \(S\) is \(\omega\)-constructible if it is an (at most) countable union of locally closed sets. 2

Theorem 1

\(\Q\) is \(\bigcirc\)-solvable if and only if each \(A \in \Q\) is \(\omega\)-constructible in \(\tau_\bigcirc\).

Conjecture 1

Suppose \(\phi \in \l\) has no atomic subformulas. 3 Then \(\phi\) is both \(\K\)-solvable and \(\Kdual\)-solvable.

Potential proof.

Proof idea for \(\K\)-solvability:

  • For any such \(\phi\), \(\|\phi\|\) is contained in the Boolean algebra generated by sets of the form \(\|\K_i\alpha\|\).

  • These sets are all open in \(\tau_\K\).

  • It is known that the constructible sets form the smallest Boolean algebra (wrt the usual set-theoretic meet, join and complement) containing all open sets. Hence \(\|\phi\|\) is constructible.

  • Hence \(\|\phi\|\) is also \(\omega\)-constructible in \(\tau_\K\).

  • Since constrictible sets are closed under complementation, \(\|\neg\phi\|\) is also constructible and hence \(\omega\)-constructible.

Proof idea for \(\Kdual\)-solvability:

  • Any \(\phi\) can be re-written in terms of \(\Kdual\) only using the duality \(\K_i = \neg \Kdual_i \neg\).

  • Thus \(\|\phi\|\) is contained in the Boolean algebra generated by \(\|\Kdual_i\alpha\|\).

  • By the same argument, \(\|\phi\|\) is constructible in \(\tau_{\Kdual}\).

  • Conjecture 1 would imply that we can always determine the truth of any statement about knowledgeability which is expressible in \(\l\). This includes “know-whether” formulas \(\KW_i\alpha = \K_i\alpha \lor \K_i\neg\alpha\).

Conjecture 2

The following are equivalent:

  1. For all \(i \in \S\) and \(\alpha \in \lprop\), \(w \models \bigcirc_i\alpha\) iff \(w' \models \bigcirc_i\alpha\).

  2. \(w\) and \(w'\) are indistinguishable in \(\tau_\bigcirc\).

  3. Every \(\sigma\) \(\bigcirc\)-sound for \(w\) is \(\bigcirc\)-sound for \(w'\).

  4. \(\streams_\bigcirc(w) = \streams_\bigcirc(w')\).

  • This would seem to imply that any pair of worlds are \(\tau_\K\)-indistinguishable iff they are \(\tau_\Kdual\)-indistinguishable.

  • Let \(\simeq\) denote the equivalence relation of topological indistinguishibility (by above, this is the same relation for both \(\K\) and \(\Kdual\)). Let \(\Q_{\text{dist}}\) denote the corresponding partition of \(\Omega\).

Conjecture 3

  1. If \(\Q\) is \(\bigcirc\)-solvable then \(\Q_{\text{dist}} \preceq \Q\)

  2. Finite meets and joins of solvable questions are solvable. That is, the set of solvable questions is a sublattice of the set of questions.

  • This would imply that any \(\alpha \in \lprop\), if both \(\alpha\) and \(\neg\alpha\) are satisfiable then \(\alpha\) is not solvable. 4

Questions and further research

  • To what extent is the actual state identifiable in the limit? Identifying the state exactly is not possible, since the question \(\Q_{\text{state}}\) defined by \(w \sim w'\) iff \(x^w = x^{w'}\) is not solvable (by the indistinguishibility argument). We can address this question by trying to find the most-refined solvable question \(\Q\) such that \(\Q_{\text{state}} \preceq \Q\).

    My feeling is that we have an even coarser lower bound: we cannot identify the true state at \(w\) beyond what would be the combined knowledge of all the sources: \(I_w = \bigcap_{i \in \S}R_i(x)\). In earlier (handwritten, digital) notes I showed something like the following: if \(w, w'\) are such that each \(R_i(x) \subseteq X\) is closed in the topology on \(X\) generated by \(\{v(\alpha) \mid \alpha \in \lprop\}\) and \(\epsilon\) is a stream for \(w\) and \(w'\), then \(I_w = I_{w'}\).

  • When is a question solvable given background knowledge? Say \(\Q\) is solvable (by consistent \(L\)) wrt background knowledge \(S \subseteq \Omega\) if \(L\) identifies the correct answer on every stream for each world in \(S\). My conjecture is that this is possible if and only each \(A \cap S\), for \(A \in \Q\), is \(\omega\)-constructible in the subspace topology on \(S\).

  • How can we justify looking at learners from a semantic perspective (i.e. the output is a set of worlds) rather than a syntactic perspective (i.e. the output is a set of \(\l\)-formulas)? Say \(L\) is definable if for each \(\sigma\) there is \(\Gamma_\sigma \subseteq \l\) such that \(L(\sigma) = \|\Gamma_\sigma\|\). Our approach could be justified if there is a question \(\Q\) which is only solvable by non-definable learners.

1

This is a standard definition

2

As far as I can tell, this terminology is due to Baltag et. al. [BGS16].

3

i.e. \(\phi\) is built up from formulas of the form \(\K_i\alpha\) using conjunction and negation.

4

This was shown directly in the other notes. To show it here, take two worlds \(w, w'\) with different states and universal relations for all \(i\). Then \(w, w'\) will be indistinguishable, so will be contained in the same open and closed sets. Thus \(w, w'\) are contained in the same locally closed sets. If \(\Q\) is solvable then \(\Q_w\) is a union of LC sets. The term in the union containing \(w\) therefore must also contain \(w'\), so \(\Q_w = \Q_{w'}\).