make that three conjectures

I'm beginning to wonder if it is the case that for every winning E-strategy s there is an expansion s' of s such that s' is a winning D-strategy. The example I'm doing is:

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

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

The first one is wholly my own, and this one I have a lot less data to base it on than others, and I can't even really say why I think it might be true. However, it's something for me to spend some time (using the nifty new "search for a strategy (interactively)" functionality, which I am loving) investigating, and it doesn't seem 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.

Bold conjectures

Because what's the point of making a conjecture if it isn't provocative? After a short but extremely fruitful with Chris and Jesse this afternoon, and bolstered up on the basis of a whole two examples that I've worked through, I have the following two 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.

So: The hunt for counterexamples is on!

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.