$\mathbf K1.1$ is sound and strongly complete w.r.t. frames for which $R$ is a partial function

111 Views Asked by At

(Blackburn et al.'s Modal Logic, Ex 4.3.1): Let $1.1$ be the axiom $\diamond p\to\square p$. Show that $\mathbf K1.1$ is sound and strongly complete with respect to the class of all frames $(W,R)$ such that $R$ is a partial function.

Firstly, I am confused about the meaning of a partial function. After a quick Google search, I found out that a partial function $f$ from $X$ to $Y$ is essentially a function $f: S\to Y$ where $S\subset X$ (possibly improper). In other words, we are basically allowing the function to forget about some values in the domain. That being said, we know $R\subset W\times W$. If $R$ is a partial function, then the idea is that we can have isolated worlds, right? In addition, one world can be mapped to only one other (because $f: S\to Y$ is a function, so it is well-defined).

Just want to quickly verify my solution.

  1. Suppose the class of all frames $(W,R)$ in which $R$ is a partial function is denoted by $P$. Then, for every frame $\mathfrak F \in P$, we show $\mathfrak F\Vdash \diamond p\to\square p$. $\mathfrak F\Vdash \diamond p\to\square p$ if and only if $\mathfrak F,w\Vdash \diamond p\to\square p$ for all $w\in W$. Consider arbitrary $w\in W$. Suppose $\mathfrak F,w\Vdash \diamond p$. Then, there exists $v\in W$ such that $wRv$ and $\mathfrak F,v\Vdash p$. Moreover, for all $v' \in W, v'\ne v$, we have $w\lnot Rv'$. This is because $R$ is a partial function. Hence, $\mathfrak F,w\Vdash \square p$. One direction is done!

  2. Next, I want to show that if $\mathfrak F\Vdash \diamond p\to\square p$ (for all frames in $P$), i.e. $\mathfrak F,w\Vdash \diamond p\to\square p$ for all $w\in W$, then $R$ is a partial function. This is easily done too, and I am skipping the proof.

Another question I have is, where are soundness and completeness coming into play, exactly? When we say soundness, we want $\vdash \implies \Vdash$. For completeness, it's the other way round. Since $1.1$ is put into the axioms of $\mathbf K1.1$, perhaps the first part (1) of my solution corresponds with proving soundness, i.e. seeing if the axiom is valid in all frames of a particular type? If yes, then the other part (2) is probably completeness, but I do not really see how.

Could someone help me really understand if what I'm doing is right, and why I am doing it? I have difficulty understanding the bigger picture of completeness and soundness in modal logic. Thanks!

1

There are 1 best solutions below

4
On BEST ANSWER

Your proof sketch aims to show that the 1.1-formula defines the class of frames whose accessibility relations are partial functions. But that is a frame correspondence result and not a frame completeness result, which you are asked to show in the exercise.

But there is a connection here between frame correspondence and frame completeness. To show the completeness result you may use what Blackburn et al. call a completeness-via-canonicity argument: Prove that the 1.1-formula is canonical for partial functionhood. That is prove (i) that the canonical frame of every normal modal logic containing the 1.1-formula is partially functional and (ii) that the 1.1-formula is valid in every partially functional frame.

Now your frame correspondence result has already covered (ii). What is still left is (i). To show (i), let $ \diamond p \rightarrow \square p \in \Lambda$, where $\Lambda$ is any normal logic, and Let $\mathcal{F}^{\Lambda} = (W^{\Lambda}, R^{\Lambda})$ be the canonical frame for $\Lambda$. Suppose that $R^{\Lambda}st, R^{\Lambda}sv$, for arbitrary $s,t,v \in W^{\Lambda}$ and that $\psi \in t$. So, $\diamond \psi \in s$. As $\diamond \psi \rightarrow \square \psi \in s$, we then have that $\square \psi \in s$. As $R^{\Lambda}sv$ it follows that $\psi \in v$. Hence $t \subseteq v$. Analogously, it can be shown that $v \subseteq t$.