Timeline for Techniques for Reversing the Order of Quantifiers
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 6, 2011 at 14:23 | vote | accept | Sadeq Dousti | ||
| Feb 2, 2011 at 20:13 | comment | added | Charles Stewart | @Andrej: I am the sloppy one - Skolem/Herbrandisation conserves satisfiability, which is the dual of conserving provability. I seem to recall there being a moral truth about all quibbles containing errors. | |
| Feb 2, 2011 at 20:03 | comment | added | Andrej Bauer | @Charles: I agree with you in principle, and that is how I would talk if I talked to logicians. | |
| Feb 2, 2011 at 13:08 | comment | added | Charles Stewart | A quibble: your last point talks of transformations of formulae into "equivalent" formulae: this is sloppy language, I think. Skolem/Herbrandisation conserves provability, but you can usually find intepretations that distinguish them, while the equivalence of the two formulae in the Dialectica interpretation need not be constructively valid. It's worth talking in the more careful terms of "conserves soundness/provability", I think. | |
| Jan 24, 2011 at 20:23 | comment | added | András Salamon | @Sadeq: there is now a regular conference called Topology, Algebra, and Categories in Logic which explores these intimate connections: lif.univ-mrs.fr/~lsantoca/tacl2011 | |
| Jan 23, 2011 at 17:35 | comment | added | Neel Krishnaswami | @Sadeq: Follow the links in his post. Both Taylor and Escardo have poured shocking amounts of effort into exposition. Also, you might enjoy Steve Vickers' Topology via Logic. (I was somewhat disappointed by the Baez and Stay paper because IMO they presented linear logic in an unnecessarily confusing way.) | |
| Jan 23, 2011 at 6:14 | comment | added | Sadeq Dousti | @Mark: Seems like a promising source of study. There are even slides available, which makes reading easier. I'm still eager to know what's behind @Andrej's magical answer :D | |
| Jan 23, 2011 at 1:07 | comment | added | Mark Reitblatt | @Sadeq I'm not sure if this is what Andrej is talking about, but there's "Physics, Topology, Logic and Computation: A Rosetta Stone" by Baez and Stay. It's a short manuscript that's easily found on Google. | |
| Jan 22, 2011 at 23:02 | comment | added | Suresh Venkat | @Andrej, maybe you should write something on your blog. | |
| Jan 22, 2011 at 22:46 | comment | added | Daniel Apon | @Andrej: Started reading with tea. Had to take a break and come back with coffee. ;) I love it, great answer! | |
| Jan 22, 2011 at 21:03 | comment | added | Akash Kumar | Great Answer Andrej...I feel that my neurons are jumping. A very big thanks! | |
| Jan 22, 2011 at 19:55 | comment | added | Sadeq Dousti | @Andrej: Is there a good reference (specially a book or a lecture note) on the "intimate connections between logic, computation and topology"? | |
| Jan 22, 2011 at 17:21 | comment | added | Andrej Bauer | I feel flattered. I wish more people knew about the intimate connections between logic, computation and topology. | |
| Jan 22, 2011 at 17:17 | history | edited | Andrej Bauer | CC BY-SA 2.5 |
typos!
|
| Jan 22, 2011 at 17:14 | comment | added | Suresh Venkat | What an amazing answer. | |
| Jan 22, 2011 at 16:28 | comment | added | Hsien-Chih Chang 張顯之 | @Andrej, your answer is really good and educational. I never knew there's a relation between compactness and reversing quantifiers, until this post appears. I feel enlightened. | |
| Jan 22, 2011 at 13:08 | comment | added | Andrej Bauer | It is a very general condition (one space must be overt, the other compact, and the relation open), but it is also a technique: if you can find topologies that satisfy the conditions then you can invert the quantifiers. | |
| Jan 22, 2011 at 10:51 | comment | added | Sadeq Dousti | And another quick question: Does you answer imply techniques, or just the conditions? | |
| Jan 22, 2011 at 10:50 | comment | added | Sadeq Dousti | Very nice. I must admit that my knowledge is challenged by your answer, and I have to read it several times to grasp. (I just finished pass 1!) I think you have answered another important question I had in mind, too: What are the necessary and/or sufficient conditions for quantifier switching? Am I right? | |
| Jan 22, 2011 at 9:30 | history | answered | Andrej Bauer | CC BY-SA 2.5 |