You are here
Home ›modal logic GL
Primary tabs
modal logic GL
The modal logic GL (after Gödel and Löb) is the smallest normal modal logic containing the following schema:
-
W: .
GL is also known as provability logic, because it is used to study the provability and consistency of first order Peano arithmetic.
Recall that 4 is the schema .
Proposition 1.
In any normal modal logic, implies .
The proof of this requires some theorems and meta-theorems of a normal modal logic.
Proof.
We start with the tautology , which an instance of the schema . Since is a theorem in any normal modal logic, is a theorem by the substitution theorem. By the syntactic property RM, is a theorem. Since is an instance of W, by law of syllogism, is a theorem.
Next, from the tautology , we have the theorem by RM. Combining this with the last theorem in the previous paragraph, we see that, by law of syllogism, , or 4, is a theorem. ∎
Corollary 1.
4 is a theorem of GL.
A binary relation is said to be converse well-founded iff its inverse is well-founded.
Proposition 2.
W is valid in a frame iff is transitive and converse well-founded.
Proof.
Suppose first that the schema W is valid in , then any theorem of GL is valid in , so in particular 4 is valid in , and hence is transitive (see here). We next show that is converse well-founded. Suppose not. Then there is a non-empty subset such that has no -maximal element. We want to find a model such that, for some propositional variable and some world in , , or equivalently, and . Let be the valuation such that . Pick any . Suppose . To show that , we want to show that . There are two cases:
-
If , then . Furthermore, since does not contain an -maximal element, there is a such that . Since , . Since , . As a result, .
-
If , then , so that .
Next, we want to show that . Since , and does not have an -maximal element, there is a such that . Since , . But since , .
Conversely, let be a transitive and converse well-founded frame, a model based on , and a world in . We want to show that . So suppose . Then the set is not empty. Since is converse well-founded, has a -maximal element, say . So and . Now, if , then , which means there is a such that and . But since is transitive and , we get , implying , contradicting the -maximality of . Therefore, , or . As a result, . ∎
Proposition 2 immediately implies
Corollary 2.
GL is sound in the class of transitive and converse well-founded frames.
Remark. However, unlike many other modal logics, GL is not complete in the class of transitive and converse well-founded frames. While its canonical model (hence the corresponding canonical frame) is transitive (because 4 is valid in it), it is not converse well-founded.
Instead, it can be shown that GL is complete in the restricted class of finite transitive and converse well-founded frames, or equivalently, finite transitive and irreflexive frames.
Mathematics Subject Classification
03B45 Modal logic (including the logic of norms)03F45 Provability logics and related algebras (e.g., diagonalizable algebras)
- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)
- Other useful stuff
Recent Activity
new question: Sorry to steal a few minutes of your time for this question, but i honestly don't know what else to do. by Whrazithar
new question: equality of the determinants of submatrices of an orthogonal matrix by ismayli
Jun 11
new correction: Typo by suitangi
Jun 2
new question: Creating another set with same cardinality. by hkkass
Jun 1
new image: ProblemOneRevised by unlord
new Education: Chapter II by rspuzio
May 31
new collection: The Calculus by Davis and Brenke by rspuzio
new question: Proofs by weixifan
new question: Summation Integration Question by trevor.nickle
May 27
new correction: typo+finite measure hypothesis by Filipe


