Timeline for How are Modal Logic and Graph Theory related?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2013 at 19:55 | vote | accept | Samuel Reid | ||
| Feb 4, 2013 at 20:04 | history | edited | Noah Schweber | CC BY-SA 3.0 |
Added citation
|
| Feb 4, 2013 at 20:00 | comment | added | Noah Schweber | @Emil: thanks for the citation! I spent a while looking for that paper with no luck. Re: your first point on terminology, I recall learning the opposite convention, that $R$ being well-founded meant that every $R$-increasing sequence terminates, but looking through my notes/books I can't see where I got that convention; so maybe I'm just conflating the picture with that of descriptive set theory (where, if your trees grow upwards, a tree is well-founded if every increasing chain terminates). | |
| Feb 4, 2013 at 13:56 | comment | added | Emil Jeřábek | It’s S. K. Thomason, Reduction of second-order logic to modal logic, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 21 (1975), no. 1, 107–114. One can in fact fix $\phi$, so the reduction is to Kripke validity in a particular finitely axiomatized modal logic. (Thomason only states it for monadic second-order logic, but as far as I can see, this makes no difference, as one can encode a pairing function in the binary relation.) | |
| Feb 4, 2013 at 13:02 | comment | added | Emil Jeřábek | ... is recursively reducible to the relation “$\psi$ is valid in every Kripke frame in which $\phi$ is valid”. | |
| Feb 4, 2013 at 13:01 | comment | added | Emil Jeřábek | Well, $R\subseteq X^2$ is well-founded if every nonempty subset of $X$ has an $R$-minimal element, and converse well-founded if every such set has an $R$-maximal element. These are distinct properties, and GL corresponds to transitive frames with the latter property. As for the connection to second-order logic: modally definable second-order properties are indeed rather special (e.g., they are monadic $\Pi^1_1$, and they are preserved by the four operations listed), but the “sort of converse” you mention might be the result (due to Thomason, IIRC) that validity in full second-order logic ... | |
| Feb 3, 2013 at 23:52 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 778 characters in body
|
| Feb 3, 2013 at 20:19 | history | answered | Noah Schweber | CC BY-SA 3.0 |