Saturday, December 31, 2011
Tuesday, July 5, 2011
- Jesse and I finished up our extended paper on N, "A Curious Dialogical Logic and Its Composition Problem", and sent it off.
- Significant new features have been added to the dialogues website, including the long-awaited ability to compute strategies interactively and the possibility of selecting arbitrary rulesets (from a pre-defined set of rules).
- Our goal with Chris was to find out general conditions under which it can be proved that E is redundant; we have not gotten as far as we like, but the results of my various pokings and proddings on the subject are contained in "Some Remarks on the E rule in Dialogical Logic".
Friday, July 1, 2011
OK, now this result does surprise me. I think I just found a ruleset that is not closed under modus ponens! D10+D12+D13+E:
- validates ~~φ->φ.
- validates (~~φ->φ)->(φv~&phi).
- does not validate φv~φ.
And here are my proofs to double check my work, because this is very, very strange:
In fact, the same also holds of D10+D12+D13, without E:
And I wouldn't say it's exactly surprising to me, since that seems to imply I expected the opposite, whereas I didn't have any expectations at all.
I spent a lot of yesterday testing a number of other formulas under D10+D12+D13 and D10+D12+D13+E, and I think I have another conjecture about how E works, namely, while adding E may increase the number of validities (e.g., going from N to CL), it will never decrease the number; I have not found a single formula which is valid under the non-E ruleset but invalid when E is added. There is probably an easy, straightforward explanation of this/proof that this always happens, but I haven't spend any time thinking about it yet.
Even if there is, though, it's still something interesting to point out, because it is not a general phenomenon (i.e., that increasing the number of rules in your ruleset will never decrease the set of validities), since D10+D12+D13 validates all four version of DeMorgan's, but this is not the case if you add D11, since one of the versions is not intuitionistically acceptable.
Thursday, June 30, 2011
One of the original motivations our work with Chris here in Vienna started with is contexts under which we can show that E is redundant; IL is an obvious case, and hence D10+D11+D13 is as well. D10+D12+D13 was a surprising (to some) countercase. CL is an obvious countercase...or is it?
It appears that the unique redundancy of E in IL noted above is actually closely tied to Felscher's formulation of the rules. If we stray from there (keeping E: "The Opponent must immediately respond to the previous Proponent move") and start formulating rules on our own, can we perhaps come away with sets of rules where the presence or absence of E is irrelevant?
When we talked about this a few days ago, my conjecture was that it's not the immediate-response consequence of E that is so important for CL, but rather the restriction on the number of moves O can make. I propose the following:
- D10: P cannot assert an atom before O does.
- D13: A P-statement can be attacked at most once.
- D14: A P-attack can be defended at most once.
Certainly D10+D13+E implies D10+D13+D14. But D10+D13+D14 does not imply E, since it relaxes the immediate-response constraint.
So one hypothesis for how to go about constructing rules that would allow us to prove the redundancy of E in a particular ruleset is by looking at variants of the bounded rules that Krabbe proposed in his 1985 Synthese article which put constraints on the number of times O can repeat a move.
However, if you are in the context of E, what is it that separates IL from CL? It is the ability of P to go back and essentially "change his mind" about a defense, e.g., in the case of excluded middle. So here, it appears that the important distinction is not how many times O can repeat a move, but how many times P can. The case is not quite the same, though: In IL, there are contexts where P is allowed to repeat a move (same formula/symbolic attack, same stance, same reference), and in CL, it is not that we are allowing P to repeat a move that he's already made, but rather to re-refer to a move of O that he's already referred to. So the cases aren't quite parallel, but it still shows a tantalizing dimension to consider.
Tuesday, June 28, 2011
|Excluded middle||not valid||not valid|
|WEM||not valid||not valid|
|Cond. EM||not valid||not valid|
|Dummett||not valid||not valid|
|Scott||tried to depth 36||tried to depth 20|
|Smetanich||tried to depth 24||valid|
|not CL||X||X||X||excluded middle, Peirce not valid|
|not CL||X||X||X||X||validates Peirce, does not validate excluded middle|
|IL||X||X||X||U, blog post|
|IL||X||X||X||X||U, blog post|
(not (not (implies (implies (implies a b) c) (implies (implies (implies b a) c) c))))i.e.,
¬¬(((A → B) → C) → (((B → A) → C) → C))
And if I start off by following the E-strategy we found last week for this formula, I can extend the left-most branch and then close it, but once I get into the middle branch, I'm finding I'm getting into what appears to be a cycle; I'm running out of options which don't provide branching for O, so the width of the tree keeps getting bigger and bigger and bigger.
Of course, maybe I haven't figured out the right algorithm for closing the branches. But I spent a lot of yesterday afternoon, and a good portion of this morning, working on it, and I'm getting into the same rut every single time. This makes me worried.
ETA: I was wrong! (Thank goodness). After at one point exploring the tree down to depth 46 and width I-have-no-idea), I started from scratch for yet another time, and finally found a winning D-strat that extends the E-strat (but only at the leaves, so this may not in fact be a winning D-strat; that's to test next). Unfortunately, the strat is too wide to get a screen shot of and display here. However, I've saved the code and you can view it here.
Here's a simple question:
Do we know how to characterize classical logic (CL) dialogically?
The answer is, thankfully, “yes”. Various proofs are available. Together with a masters student at the ILLC, Aleks Knoks, Sara and I found a correspondence between LK deductions (more precisely, deductions in a proof search-friendly variant of LK) and (what we called) classical dialogues. (Our proof does not literally use Felscher's notation for dialogue games; instead, we extended Fermüller's notation, found in his “Parallel dialogue games and hypersequents for intermediate logics”. It's clear that there's no essential difference between Fermüller-style games and Felscher-style games.
Here's a related question:
How do we characterize CL using Felscher-style dialogues?
The question is motivated by a desire to find some general framework for dialogues in which we can understand how the E-rule above is redundant. The motivating example is the dialogical characterization of intuitionistic logic (IL): it turns out that the E-rule is redundant in the presence of other structural rules. One way to understand the redundance of E is to look at other logics and their dialogical characterizations. Is the E rule redundant for these, too?
Turing to classical logic, the salient structural rules are:
- Defenses must be against only the most recent open attack. (An attack is said to be open if there is no defensive move in the game that responds to the attack. Non-open attacks are closed.)
- Attacks may be answered at most once.
- O must react to the immediately preceding statment by P.
Based on the work mentioned before, I'm pretty sure that one way to get CL is to keep E but remove the other two rules. But this is, for the present discussion, a negative example because the E rule, far from being redundant, is crucial. We can't drop all three of these conditions. The result of doing so is the curiosity N; and we have known for some time that N ≠ CL. This leaves open some other questions: what if we keep D11 or D12? Do we find that E is redundant in those cases as well?
Sara's recent slick observation about the redundancy of D12 helps with this, but we still have some work to do.
Conjecture: Let s be a winning E-strategy for phi. Extend s to s' by augmenting the tree wherever required so that the result is a winning D-strategy. Claim: The E-violating moves will occur after P has asserted an atom.
Check back often for evidence for or against this conjecture.
The second one is one that Chris proposed, namely whether D10+D12+D13=CL (i.e., we drop E, but add D12). Now, you might recall from a week or two ago that I conjectured that D10+D12+D13=IL, not CL (and I already have an easy proof that D10+D11+D13=IL), so it will be interesting to see how this pans out.
Friday, June 24, 2011
Let s be a winning D-strategy for \phi, and b a branch in s where E is violated. Let b' be the result of truncating b immediately before the first violation of E (so that the new leaf of b' is a P node). Let s' be the result of doing this for every branch b where E is violated. Claim: s' is a winning E-strategy.
- s' is an E-strategy: All moves which violate E have been removed. All other rules are unaffected by truncation:
- D10: If P has asserted an atom p in round n of b', then he asserted it at round n of b, and since b followed D10, O's assertion of occurred at some earlier round m. Since m < n, O's assertion of p is in b', so D10 is respected.
- D11, D12, D13: Straightforward.
- s' is a winning E-strategy. Suppose b' in s' is such that P has not won. Either:
(1) is not possible, by construction of s'. (2)Suppose that at the leaf (let it be round n) O has a legal move. Any move that is legal under E is also legal under D, which means that this move already appeared in s, in some branch b* which diverged from b at round n:
- The leaf of b' is a move by O, or
- The leaf of b' is a move by P, but there is a legal continuation of the branch according to E.
Since b' is in s', we know that b* was not truncated before round n. Hence, the result of cutting b off at round n+1 looks like this:
b round n (P's move) b* / \ round n+1: E-violating move by O round n+1: E-non-violating move by O And hence, contra assumption, n is not a leaf in b'.
round n (P's move) | round n+1: E-non-violating move by O
Thanks to some prodding from Sara, I've implemented some new functionality to the dialogues site: interactively searching for strategies. As usual, one specifies an initial formula and a ruleset. The site then develops the full dialogue tree (that is, the tree that represents all possible moves consistent with the chosen ruleset) to the first Opponent node that has multiple children. One then chooses one of the children (i.e.., one chooses a move for Proponent). The site then continues to develop the dialogue tree, ignoring the unselected children of that Opponent node, until it encounters another Opponent node that has multiple children. One again makes a choice, and so forth. This process ends either when one finds that the choices that one has made for Proponent amount to a winning strategy, or when one finds that there is no winning strategy that is consistent with the choices made so far.
Some functionality is still not implemented. During the interactive search for a strategy, one makes choices about how Proponent should respond. There may not be a winning strategy consistent with those choices. If so, the website simply informs you of this, without letting you go back and choose some alternative course. Even if a winning strategy is found, the website does not permit one to choose alternative paths (thereby possibly discovering a different winning strategy). This functionality actually does exist in the interactive "command line" interface (for the brave, see PLAY-STRATEGY-SEARCH-GAME in the source), but it has not yet been translated to an HTML presentation yet.
With the site one can also now specify heuristics to tack on to a selected ruleset. Strictly speaking, there's no difference between heuristic rules and any other structural rule (in fact, heuristic rules are implemented as structural rules). Playing a game with a ruleset S and heuristic set H just means playing according to the ruleset S ∪ H.
At the moment, only one heuristic rule is presented to you: forbid Proponent from making identical moves (same move, same stance, same reference, same assertion). This can help significantly cut down the set of possibilities available to Proponent. Sara and I have conjectured that adding this heuristic rule to the D and E rulesets does not affect their logical strength: Proponent has a winning D (respectively E) strategy iff Proponent has a winning D (respectively E) winning strategy in which Proponent never repeats a move.
Thursday, June 23, 2011
Proof: Assume round n is the first time where O violates E, that is, he references some round n−i such that i≠ 1. Assume further that this is the first time that round n−i has been referenced. Now, look at round (n−i)+1. What move does O reference here? If it is not n−i, then, contra assumption, round n is not the first round where E has been violated. If it is n−i, then, contra assumption, round n is not the first round where n−i is referenced. QED.
¬¬(((A → B) → C) → (((B → A) → C) → C))This formula was put forward by Chris as a potential counterexample owing to the way that he thinks of Sara's conjecture: for Chris, Sara is claiming that one can get away without contraction in an intuitionistic sequent calculus. But we know the latter not to be the case, hence one should look at at intuitionistically valid formulas for which every sequent deduction involves contraction. Whence the formula above. It turns out that this is not yet a counterexample to Sara's claim. Here is one strategy discovered interactively for that formula (with the help of some brand new functionality of the dialogical logic software that I've been working on, which will be released soon): In this example, see various cases where the E rule is violated:
- in the left branch at move 15;
- in the middle branch also at move 15;
- in the right branch at move 9.
- [In a D strategy] The first time that the E rule is violated, the reference of that round has already appeared as the reference of an earlier round.
- (Corollary of the first) The first time that the E rule is violated, if you chop the branch off at the previous move (i.e., P's move), the result of doing so for all branches in a winning D-strategy will be a winning E-strategy.
Monday, June 20, 2011
(implies (implies (and p p) q) (implies (and p p) q))Or, in readable fashion:
(((P ∧ P) → Q) → ((P ∧ P) → Q))I'm hoping that this example is small enough that the dialogues website can compute both the D and E strategies for me.
---ETA: This is still too complicated a formula for the site, so I calculated the D and E strategies by hand; they do differ, but only by the final two moves in two of the three branches [ETA, 23Jun: This is wrong; I did not finish filling out one of the branches]. I came up with a more interesting example:
(implies (implies (and p p) (implies p q)) (implies (and p p) (implies p q)))Or, readable:
(((P ∧ P) → (P → Q) → ((P ∧ P) → (P → Q))Here, not only does the game not immediately end when Pro asserts an atom (he does so in the attack on an implication, which means that Opp still has the possibility to defend), but the D and E strategies differ by the final four moves in two of the branches. If I can think of a way to nicely represent the trees in HTML, I'll try to post all four strategies here.
Thursday, June 16, 2011
In order to understand how to get from D strategies to E strategies, I've been trying to think about cases where they diverge -- that is, dialogues which are D-strategies, but not already additionally E-strategies. Recall that we are in the presence of D11 and D13; by D11, an attack may be defended at most once, and by D13, a P-assertion can be attacked at most once. These put significant constraints on O. In fact, I've come to the conclusion that the only time when O will be faced with a choice is when P has attacked a conditional; then, and only then, O has a choice between defending the conditional and attacking its antecedent (assuming it is non-atomic). In either of these cases, it follows that the conditional was originally asserted by O.
Under what conditions will a conditional be asserted by O? In defense of \wedge_L, \wedge_R, or ?, or as an attack on a negation. The former imply that O has previously asserted a conjunction or a disjunction one of whose conjuncts/disjuncts is a conditional. Take the latter; this means that P has asserted a negated conditional. I have yet to come up with an example where P actually does so, but I'm wondering if it shouldn't be possible to construct one via substitution of such for an atom in a IL-valid formula. Hmmmm...
Well, I've found a formula which should be IL-valid and allows O to assert a conditional:
(implies (not (not (implies (and p p) q))) (not (not (not (not (implies (and p p) q))))))
Or, in more readable format:
(¬¬((P ∧ P) → Q) → ¬¬¬¬((P ∧ P) → Q))
However, at the point where O has a choice of moves, if he doesn't take the option of defending the attack on the conditional, then he loses it; the rest of the dialogue is so full of attacks on negations, which are undefensible and hence always remain open, that D11 will prevent him from going back and re-defending. So, in order for a D strategy to differ from an E strategy, (a) O must assert a conditional, (b) P must attack it, (c) O must defend it immediately.
Friday, June 10, 2011
The proof relies on the fact that once an attack has been defended, it is no longer open. Since D11 requires that every defense be made against an open attack, once an attack has been defended and is closed, no defense will be made against it again. Thus, any attack will be answered at most once.This shows that D10-D11-D13 is a sufficient ruleset to generate IL. I kind of thought one of the results would be trivial; and this was it. I still think that it may be the case that D10-D12-D13 also characterizes IL, but I haven't had time to work further on that conjecture.
Wednesday, June 8, 2011
- D11: Only the latest open attack may be defended.
- D12: An attack may be answered at most once.
Wednesday, May 11, 2011
- Jesse and I revised our paper from the Inside Arguments Colloquium and submitted it for the proceedings: "What is Dialogical About Dialogical Logic?"
- The two of us along with Aleks Knoks have had a short paper accepted to TABLEAUX 2011 in July: "Dialogue Games for Classical Logic". Either Jesse or Aleks, or both, will be attending the conference.
- Jesse presented the long version of this paper at ProDi in Tübingen, as mentioned in an earlier post; Ole Thomassen Hjortland had some nice things to say about our results.
- Next big thing on the dialogical horizon is our 6-week visit to Vienna to work with Chris Fermüller, Christoph Roschger, and Friedrich Slivovsky.
Tuesday, March 29, 2011
- The lack of disagreement on the proper set of structural rules for intuitionistic logic (cf. the wildly different approaches of, e.g., Felscher and Rahman).
- The problem, illustrated by N, of the interplays that arise in sets of independently plausible structural rules.
- Difficulties in identifying acceptable criteria which allow us to rule out particle rules for connectives like tonk, but which do not force us to rule out, e.g., the particle rules for negation.
Tuesday, March 1, 2011
I presented the result (joint with Sara and Aleks Knoks, whom we snagged to work on dialogues with us) on an extension of what I've been calling Fermüller-style dialogue games to classical logic. Fermüller gave a nice presentation of a dialogue game for intuitionistic logic, and presented a proof of the soundness and completeness of his games in his “Parallel Dialogue Games and Hypersequents for Intermediate Logics” (which was discussed earlier [Part 1], [Part 2], [Part 3], [Part 4]). Chris Fermüller was at the workshop and attended my talk. He didn't much like the name “Fermüller-style dialogues”, the idea being that his dialogues are at most a notational variant of ordinary dialogue games. I defended the choice of term by pointing out that the idea of extending his intuitionistic games to classical logic was more attractive and feasible than it is for other formalisms for dialogues. I think this is a case where a change of notation is significant.
As I expected, there was some pushback at the basic motivation of the paper, which is that our result is worthwhile owing to the extremely small number of explicit proofs in the dialogue literature of the correspondence between classical logic and classical dialogues (in whatever form one likes). We know of only two proofs, one by Fermüller himself, and another by Sørensen and Urzyczyn. Our proof has the advantage that it works with a standard sequent calculus, rather than with hypersequents (Fermüller) or one that is specially tuned for the purpose of establishing the correspondence (Sørensen and Urzyczyn).
It was an honor to present the work to an audience that contained several experts on dialogical logic. Here are the slides. The presentation was rather less than ideal: there were so many talks on dialogues preceding mine (not to mention that Fermüller himself presented his games immediately before me) that the first several slides could have been cut, and other interesting issues from the paper could have been dealt with. The paper on which the slides are based can be found on Sara's homepage or on my homepage.
Friday, February 25, 2011
Next up, Laurent Keiff, "Dialogues and Trivializing Connectives". This should be interesting, as one of the questions he's asking is "What are the limits of the framework?", which is closely related to questions Jesse and I explored last fall.
His definition of dialogue games follows the approach of Fermüller; there is an initial set of assertions by the Opponent, and he indicates positions of games via dialogue sequents. However, he only allows one assertion of Proponent in the initial state, so his dialogues are, at base, intuitionistic.
For Keiff, particle rules must be "anonymous"; this is just player neutrality at the local level. Unfortunately, he doesn't give sufficiently precise definitions of the particle and structural rules to evaluate whether the same worry that I have from Rahman's paper is present here.
Much of his talk is focusing on developing rules for tonk, and tonk-like operators. I have to confess, I'm not entirely sure I understand the fascination the Lille people have with tonk. It seems like it will always be possible to allow, or not allow, tonk rules. This, in and of itself, is not problematic, any more than the fact that classical proof theory allows the introduction of a tonk rules. What's important is that we can block the adoption of tonk, that we're not forced to use it. So, if we're interested in investigating interesting logics that arise from the dialogical tradition, we should avoid adding trivializing connectives like tonk.
First, structural rules which are wholly player neutral will result in the inconsistent logic: Proponent has a winning strategy for every atom p, so at least some asymmetry/nonneutrality in the rules is required.I am curious to see if he addresses this problem in the remainder of the talk; if he doesn't, I intend to ask him about it. Curiously, at least one version of particle rules for FDE-negation that he introduces is not player neutral. --- I asked my question; I don't think I was able to express myself clearly, because his answer was "of course you have to have some asymmetry" in order to build a logic. So I'm not sure what his motivation for arguing for player neutrality is, nor how he gets the required asymmetry from his symmetric particle rules.
Tuesday, February 8, 2011
- "Dialogue Games for Classical Logic". In this paper we introduce a class of dialogue games for classical logic, building on both Felscher 1985 and Fermüller 2003, and give a rigorous proof of the correspondence between the two.
- A Tableau System for the Dialogical Logic N". In this paper we define a tableau system for the logic N, and prove that it is sound and complete with respect to the logic. The proofs go via a reduction to canonical tableaux and algorithms for converting closed tableaux into winning strategies and vice versa.