16 votes
Accepted

How does Modal Logic differ from Ordinary Predicate Logic?

Your impression is right, but missing the point in some sense: modal logic is strictly less powerful than first-order logic, and this is one of the reasons it is so important in various contexts (...
Noah Schweber's user avatar
9 votes
Accepted

Why, intuitively, is Lob's theorem true?

It's just a reformulation of Gödel's theorem : if you have some intuition for Gödel's theorem then you can transfer it to Löb's theorem. Indeed if PA proves $Prov(A)\to A$ then it means that the ...
Maxime Ramzi's user avatar
  • 43.4k
9 votes
Accepted

What kind of structure is an ISP?

$\mathbb{I}$, $\mathbb{S}$, and $\mathbb{P}$ are each operators on classes of structures: $\mathbb{I}(\mathcal{K})$ is the class of structures isomorphic to a structure in $\mathcal{K}$. $\mathbb{S}...
Noah Schweber's user avatar
9 votes
Accepted

What is meant by 'weak' logic?

A logic is stronger the more theorems it proves, and as a corollary, the fewer models it has. The more axioms there are, and the more specific an axiom is (in the sense that A is more specific than B ...
Natalie Clarius's user avatar
8 votes
Accepted

Are there any invalid $S5$-formulas $\psi$ such that $\diamond\psi$ is valid?

Consider $\psi = (P \lor \square \lnot P)$. $\psi$ is not valid in $S5$, since it's possible to have a world satisfying both $\lnot P$ and $\lozenge P$. But $\lozenge \psi$ is valid in $S5$. ...
Alex Kruckman's user avatar
7 votes
Accepted

How to interpret $\Box\Box A$ in the possible worlds

The first line says "$A$ necessarily holds in wolrd $w$ iff $A$ holds in all worlds reachable from $w$". You can think of it as, $A$ necessarily holds in wolrd $w$ iff $A$ holds all around as far as ...
frabala's user avatar
  • 3,712
7 votes
Accepted

Is modal logic S4 translatable into intuitionistic logic? If not, what modal system is?

this is Rajeev Gore from Canberra. I have received an email pointing me to this thread and asking where I would elucidate, so here goes. This is the first time that I have tried to post to a forum ...
rajeev gore's user avatar
6 votes
Accepted

Why is the Fixed-Point Axiom true?

The fixed-point treatment of common knowledge is not very intuitive. However, I will try to provide some explanation why it captures the properties of operators $C_G \varphi$. First, recall that ...
Charles Bronson's user avatar
5 votes
Accepted

The Logic of Satisfiability?

This is a great, and surprisingly subtle, question! Unfortunately the answer is necessarily a bit technical, so let me state the very short version here: While validity and provability perfectly ...
Noah Schweber's user avatar
5 votes
Accepted

Prove $\vdash \neg(\square F\land p)$ in $KD$

How about the following. (I will write $\bot$ instead of $F$). $\top$ is a theorem, and hence $\square \top$ is a theorem by the necessitation. Next, from $\square \top \rightarrow \lozenge \top$ (...
Charles Bronson's user avatar
5 votes
Accepted

What's the difference between modal and epistemic logic?

Epistemic logic is a type of modal logic. The term "modal logic" is used to refer to a gigantic class of logical systems - for example, contrast epistemic logic with temporal logic. The point is that ...
Noah Schweber's user avatar
5 votes
Accepted

Why is Normality an axiom in Modal Logic?

You are conflating the proof theory of modal logic with the semantics of modal logic. We can approach verifying statements in two ways: 1) formal proofs from the axioms. 2) informal arguments for ...
spaceisdarkgreen's user avatar
5 votes

What does $\Vdash$ mean?

It depends on which book you're reading. The symbol is used for different (but related) things in different contexts. I'm sure there are still more uses, but here are probably the three most common ...
HallaSurvivor's user avatar
4 votes

Gödel's ontological proof

I think the most important matter in understanding Gödel's proof is the interpretation of $P$. In this respect, I would like to mention that the popular interpretation of $P(φ)$ as "$φ$ is positive" ...
Ward Blondé's user avatar
4 votes

What is predicate lifting?

I understand the constructions involved in this sort of thing best by way of induction rather than coinduction; the differences aren't huge, but examples of induction come to mind more easily. Perhaps ...
Malice Vidrine's user avatar
4 votes
Accepted

A sequent calculus proof

The general recipe for answering such questions is based on a cut-elimination theorem. The authors state in footnote 28 that the $Cut$ rule is "admissible" for this calculus, which is another way to ...
Noam Zeilberger's user avatar
4 votes
Accepted

Modal operators are not extensional

How to understand the intensional nature of modal operators ? Consider the statement "It is possible that Aristotle did not tutor Alexander the Great." And make the following substitutions: ...
Mauro ALLEGRANZA's user avatar
4 votes

Equivalence between classical modal logic and propositional logic

Barring additional context, I cannot see a sense in which this is true. The key point here is that in contrast with propositional logic, modal logic has non-truth-functional operations. Any "...
Noah Schweber's user avatar
4 votes
Accepted

Proof of Gödel's Incompleteness Theorem by modal logic

Edit I rewrote the answer, to tailor more to the actual arguments given in the video rather than the usual textbook proofs. The argument is basically correct, but requires some elaborate technical ...
spaceisdarkgreen's user avatar
4 votes

Why is $\lozenge (p\to p)$ not valid in system $K$ of modal logic?

Consider the frame with a single world $w$ and no arrows (or if you prefer, empty accessibility relation). Then regardless of what $\varphi$ is, the sentence "$\Diamond\varphi$" will be false at $w$ ...
Noah Schweber's user avatar
4 votes
Accepted

Compactness theorem in modal logic

Specifically - the definition of satisfiability is very similar in modal logic. This similarity is superficial: there's a crucial way in which modal logic is closer to first-order logic in this ...
Noah Schweber's user avatar
4 votes
Accepted

What kind of Kripke frame validates $(\Diamond p \wedge \Diamond q) \rightarrow \Diamond(p\wedge q)$?

Intuitively, $$\mbox{"$(\Diamond p\wedge\Diamond q)\rightarrow\Diamond(p\wedge q)$ is valid"}$$ says that I can never partition the worlds I see into two different (nonempty) pieces: if I could, ...
Noah Schweber's user avatar
4 votes
Accepted

Confusion with Brouwer's Counterexample for Points on a Continuum Being Ordered

In intuitionistic logic saying that $r > 0$ or $r < 0$ or $r = 0$ means that you have to give me a proof for one of them and you have to tell me which one. By how we constructed $r$ this would ...
Mark Kamsma's user avatar
  • 12.9k
4 votes

Why is the Fixed-Point Axiom true?

The definition seems to be trying to capture exactly the recursive definition of "common knowledge" that you describe in your post. Using the axiom repeatedly, we would be able to reason ...
Gregory J. Puleo's user avatar
4 votes

If $S5 \vdash \alpha$ then $S4 \vdash \diamond \alpha$

Here is a proof which relies in the fact that S4 has the finite model property. If $S4 \nvdash \Diamond \alpha$, then you have a finite Kripke model $M$ where the accessibility relation is a preorder ...
Pilcrow's user avatar
  • 1,699
4 votes
Accepted

Modal Logic equipped with "$\overline{\Diamond}$"

The usual way to handle these "derived relations" is by adding additional relations to our frame, and working in a multimodal logic. We can encode your desired behavior by adding an ...
HallaSurvivor's user avatar
4 votes
Accepted

Two questions about the partial order of propositional modal logics

Both your questions have negative answers (although the first has an almost-positive answer). Below I'll write $[X]$ for the deductive closure of $X$. The defining sentence of $S_5$, namely $$\Diamond ...
Noah Schweber's user avatar
3 votes
Accepted

Categorical semantics for dynamic epistemic logic

This comes a year and a half late, but categorical semantics for DEL seem to be cutting edge research. Kohei Kishida lays out a categorical semantics for a flavour of DEL in this paper: Categories for ...
Javier Torres's user avatar
3 votes

Does the fact that a modal operator distributive over disjunction imply that a modal operator is distributive over conjunction?

No, not necessarily. When changing the connective, the modality has to interact with the negation ($p \wedge q \equiv \neg (\neg p \vee \neg q)$), so it may behave differently. The negation may ...
Graffitics's user avatar
  • 1,508

Only top scored, non community-wiki answers of a minimum length are eligible