## Saturday, December 31, 2011

### Farewell to dialogues

## Tuesday, July 5, 2011

### Summary of the trip

- 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

### Would you look at that!

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:

### probably surprising to no one other than me

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

### returning to the role of E

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

### Teasing rules apart

Formula | D10+D12+D13 | D10+D12+D13+E |
---|---|---|

Excluded middle | not valid | not valid |

Peirce | not valid | valid |

WEM | not valid | not valid |

Cond. EM | not valid | not valid |

Dummett | not valid | not valid |

DNI | valid | valid |

DNE | valid | valid |

K | valid | valid |

B | valid | valid |

C | valid | valid |

W | valid | valid |

Scott | tried to depth 36 | tried to depth 20 |

Smetanich | tried to depth 24 | valid |

DM1 | valid | valid |

DM2 | valid | valid |

DM3 | valid | valid |

DM4 | valid | valid |

*not*valid because of the existence of infinite branches. I don't have a proof of this yet.

### Fill in the Blanks

**Note: Rather than continuing to update this post, the results can be found in the results paper linked in this post.**

D10 | D11 | D12 | D13 | E | notes | |
---|---|---|---|---|---|---|

N | X | X | AU | |||

CL | X | X | X | AKU | ||

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 | |

IL | X | X | X | X | Felscher | |

IL | X | X | X | X | X | Felscher |

### make that three conjectures

(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.

### Characterizing classical logic dialogically

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 characterizeCLusing 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:

- D11
- 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*.) - D12
- Attacks may be answered at most once.
- E
**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.

### two more conjectures

*prima facie*false:

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

### Proof of BC #2

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.QED

- 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

### When P must repeat a move

### New functionality on the dialogues site: interactively searching for strategies

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 of BC 1

Proof: Assume roundnis the first time where O violates E, that is, he references some roundn−isuch thati≠ 1. Assume further that this is the first time that roundn−ihas been referenced. Now, look at round (n−i)+1. What move does O reference here? If it is notn−i, then, contra assumption, round n is not the first round where E has been violated. If it isn−i, then, contra assumption, roundnis not the first round wheren−iis referenced. QED.

### Some evidence for a bold conjecture

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:¬¬(((A → B) → C) → (((B → A) → C) → C))

- in the left branch at move 15;
- in the middle branch also at move 15;
- in the right branch at move 9.

### Bold conjectures

- [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

### A simpler case

(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

### How do D and E diverge?

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 role of D11 and D12 in IL

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

### this is what happens when you think too much about dialogues

- D11: Only the latest open attack may be defended.
- D12: An attack may be answered at most once.

## Wednesday, May 11, 2011

### What we've been up to

- 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

### Inside Arguments, Coimbra, Portugal

*against*an argumentation-theoretic understanding of dialogue games. While it may be the case that Lorenzen's original motivation for dialogical semantics came from a desire to connect intuitionistic theoremhood with real principles of dialogue, interaction, and debate, it is unclear to what extent this philosophical foundations can be carried through to the extensions of the approach to classical logic, modal logic, etc. We give three arguments against any strong connection between actual argumentative practice and dialogical semantics:

- 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

### Presentation on dialogue games for classical logic at ProDi

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

### Live Blogging: ProDi Day 1, part 3

**Tero Tulenheimo**is speaking on "Remarks on Game-Based Theories of Meaning". He points out how game-theoretic semantics are importantly connected with truth-conditional theories of meaning. Interesting, dialogue games like those for N indicate, or at least seem to, that truth-conditional semantics are

*not*necessary for a class of dialogue games to be able to capture a logic. But perhaps this just means (as many people have argued), that N is meaningless. The talk now veers to the realism/anti-realism debate, and the connections with Hintikka's game-theoretic semantics. Unfortunately, my battery will be dying soon, so I doubt I'll be able to finish blogging this talk.

### Live Blogging - ProDi Day 1, part 2

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.

### Live Blogging: ProDi Day 1

**Shahid Rahman**, "Towards Dialogical Harmony", is presenting material related to his paper "Negation in the Logic of First Degree Entailment and Tonk. A Dialogical Study", comin out this year in G. Primiero et al.,

*(Anti)Realism. The Realism-Realism Debate in the Age of Alternative Logics*(Springer). I read this paper last fall and it was at times interesting and at times frustrating. His concept of "dialogical harmony" actually overlaps quite a bit with our investigations into different types of neutrality last fall. In particular, he accepts player independence. Now, the argument I gave back in August against player independence was:

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

### Announcement: Two new papers

- "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.

## Saturday, January 22, 2011

### Recent news

**N**. Both papers have been coming along nicely, and I hope that in another two weeks we'll have some interesting and important results to announce here.