Skip to main content
23 votes
Accepted

What is the modal logic of outer multiverse?

I've noticed that recently you have asked a few questions about my work, and so let me thank you; you are kind to take an interest. This particular question can be seen as part of the subject of set-...
Joel David Hamkins's user avatar
15 votes
Accepted

Are buttons really enough to bound validities by S4.2?

Unfortunately, the argument I had had in mind seems broken to me now, and I retract the claim. I wonder what of it can be salvaged? Let me explain what I had had in mind. The main idea was this: it ...
Joel David Hamkins's user avatar
12 votes
Accepted

Difference between provability and the existence of a proof?

First note this isn't a constructive logic, so it's wrong to think of "$X$" as "there is a proof of $X$". (Even in constructive logic I find that dubious.) Second note that if $X$ ...
Will Sawin's user avatar
  • 138k
11 votes
Accepted

Why is it not possible to define the necessity operator internally $\Box: \Omega \to \Omega$ in a topos?

As said in the comment, I'm not sure what to add to the paragraph, the point is that in a topos there is no functions $\Omega \to \Omega$ that has the property expected of a neccessity operator except ...
Simon Henry's user avatar
  • 40.5k
10 votes
Accepted

Interpretations of modal logic where $\Box$ means "valid"

$\def\R{\mathrel R}$No, this is not possible. Recall that the depth of a point $x$ in a transitive frame $(W,R)$ is the maximal length $d$ of a strictly increasing chain starting at $x$, i.e., $x_1,\...
Emil Jeřábek's user avatar
9 votes

Non-trivial consequences of Löb's theorem

Löb's theorem can be used to show that there exist equilibria in games like prisoner's dilemma when the participants are computer programs that can read each other's source code. If player 1 can show ...
Dan Piponi's user avatar
  • 8,126
9 votes
Accepted

Are there atoms in the lattice of intermediate logics?

There are no atoms. Assume for contradiction that $L$ is an atom. Since $L$ strictly contains IPC, there is a finite rooted Kripke frame $F$ that does not validate $L$, thus $L$ proves the Jankov–De ...
Emil Jeřábek's user avatar
8 votes
Accepted

Substitutional modality

$\def\ml{\mathrm{ML}}\let\LOR\bigvee\let\ET\bigwedge$The question you asked is a variant of Problem 42 in Friedman [1]. It also has an intuitionistic analogue, Problem 41, which asks if there exists ...
Emil Jeřábek's user avatar
8 votes
Accepted

Modal vs First-Order Logic on finite models

On p. 30–31 of Van Benthem’s Notes on modal definability (Notre Dame Journal of Formal Logic 30 (1988), #1, pp. 20–35), you can find a (brief!) sketch of a proof that the modal formula $$(\Diamond\...
Emil Jeřábek's user avatar
6 votes

Is the axiom $\Diamond\Box\varphi\to\Box\Diamond\varphi$ in c.c.c. forcing potentialism equivalent to the productivity of c.c.c. forcing?

Failure of $\sf CH$ It seems I was a bit off on my initial go at showing $(.2)_{ccc}$ entails the failure of $\mathsf{CH}$. Here is the correct argument. Proposition 1: Assuming $(.2)_{ccc}$. If $...
Not Mike's user avatar
  • 1,615
6 votes
Accepted

Preserve validity between the two Kripke frames

The result is actually false, for $m=6$. (One can bring it down to $m=2$ with a bit of effort.) Let $n$ be arbitrarily large, and $\phi_n(\vec q)$ be a Jankov–De Jongh frame formula of $\def\p#1{\...
Emil Jeřábek's user avatar
5 votes

Are buttons really enough to bound validities by S4.2?

We now know that the existence of arbitrarily many independent buttons suffices to bound the validities by Grz.2. It is one of the results from my forthcoming work—Modal theory of the category of sets—...
Wojciech Aleksander Wołoszyn's user avatar
5 votes

In modal logic, is there a formula that could express the inverse of accessibility relation?

No there is not. To be a little more precise on the formalism involved, we consider the following language of propositional modal logic over a set $Var=\{p_0,p_1,\dots\}$ of propositional variables: ...
blub's user avatar
  • 163
4 votes
Accepted

How to get $\omega$-regular expression from buchi automaton

A Büchi automaton is a finite automaton that one runs on infinitely long strings (length $\omega$), with the proviso that the string is accepted if infinitely often the machine had visited an ...
Joel David Hamkins's user avatar
4 votes

How can you formalize the metamathematics conventionally used to state Godel’s theorem?

I may not be understanding your question, but here goes: In most cases (aside from some metamathematics of set theory itself) the metalanguage is implicitly understood to be ZFC. So Gödel's first ...
James's user avatar
  • 1,498
4 votes
Accepted

Translations between S4 and S5 modal logics

As written, there is a trivial such translation: just put $F'=\top$ for all formulas $F$. Assuming you actually wanted to formulate the condition as “if and only if” rather than just “if”, a simple ...
Emil Jeřábek's user avatar
4 votes
Accepted

Initial reference on Gödel-Löb axiom in Kripke semantic of $GL$

The paper Provability: the emergence of a mathematical modality by Boolos and Sambin says (bottom of page $9$) that the first fact was independently gotten by Kripke and Segerberg, and gives the ...
Noah Schweber's user avatar
4 votes

How complicated are 3-player clopen determinacy facts?

The "finitary part" $M_{\mathsf{fin}}$ of $M_{\mathsf{all}}$ is decidable (which may be evidence that the answer to the full question is yes). Namely, there is an effective translation ...
Fedor Pakhomov's user avatar
4 votes
Accepted

Existence of certain formulas in modal logic K

$\def\eq{\leftrightarrow}\def\sset{\subseteq}$An example of such a formula is $$\phi(p,q)=(\Box p\to p)\land(p\to(q\eq\neg\Box q)).$$ Lemma. The formula $\phi$ satisfies condition 1. Proof: Let $(F,R)$...
Emil Jeřábek's user avatar
4 votes
Accepted

Kripke frame, lattice and some intermediate logics

The set $T=\{\log(\def\F{\mathcal F}\F):\text{$\F$ is finite}\}$ of tabular logics is a filter in the (complete, Heyting) lattice $\DeclareMathOperator\Ext{Ext}\def\I{\mathbf{Int}}\Ext\I$ of ...
Emil Jeřábek's user avatar
3 votes
Accepted

Superintuitionistic logics which are not hereditary/monotonic: impossible or possible?

Every propositional logic $L$ weaker than classical logic (i.e., any logic whose provable propositions are a subset of classically provable propositions) has a Kripke model. Just take $W = \{\star\}$, ...
Andrej Bauer's user avatar
  • 47.8k
3 votes
Accepted

Counterexample equivalent in relevant logic DL

From D3 and D4, 1- $A\wedge\neg B\rightarrow A$. 2- $A\wedge\neg B\rightarrow \neg B$. From 2, D8 and R1, 3- $B\rightarrow \neg(A\wedge\neg B)$. From 1, 3 and R3 (taking $B=A$, $C=B$, $A=A\wedge\neg B$...
Rodrigo Freire's user avatar
3 votes
Accepted

Can we avoid the modal collapse in a certain Intuitionistic modal logic by abandoning ¬◯⊥ but retaining the law of the excluded middle?

Notice that by the inference rule $$\frac{M\supset N}{\bigcirc M\supset\bigcirc N}\tag{@}$$ we have $$\frac{\bot\supset N}{\bigcirc \bot\supset\bigcirc N}$$ But $\bot\supset N$ always holds. So either ...
Bjørn Kjos-Hanssen's user avatar
3 votes

Literature on Kripke models

Brian F. Chellas: Modal Logic: An Introduction, 1980. Starts very basic but covers in detail the beautiful completeness theorem proofs for the basic systems like $S5$, $S4$, $K$.
Bjørn Kjos-Hanssen's user avatar
3 votes
Accepted

Modal logic of "mostly-satisfiability"

First point is that this logic is simply the provability logic of formalized $\widehat{\mathsf{ZFC}}$-provability, i.e. the provability logic of the provability predicate: $$\mathsf{Prv}_{\widehat{\...
Fedor Pakhomov's user avatar
2 votes

Literature on Kripke models

I can't say that this is the 'best' introduction to Kripke models (as 'best' is always a relative term), but John P. Burgess's survey article "Kripke Models" presumes only knowledge of propositional ...
Thomas Benjamin's user avatar
2 votes
Accepted

What kind of set theory is obtained from the canonical models of K?

There is a 'research report(?)' from the Institute for Logic, Language, and Computation (a rersearch institute of the University of Amsterdam) by Goivanna D'Agostino, Angelo Montanari, and Alberto ...
Thomas Benjamin's user avatar
2 votes
Accepted

A question on two modal formulas

I do have some of my own code that I was able to modify to investigate this. Short answer (1) is not a theorem of $\mathbf{KD4.2}$ since it is invalid on the frame $F=(W,R)$ where $W=\{A,B,C\}$ and $...
JuneA's user avatar
  • 333
2 votes
Accepted

Modal collapse upon addition of the law of the excluded middle to an Intuitionistic modal logic

I'll write $\to$ instead of $\supset$, and $\bot$ instead of false, below. Since Law of Excluded Middle is given, I'll argue using classical propositional logic. Since $M\to\bigcirc M$ is already ...
Bjørn Kjos-Hanssen's user avatar

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