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.

Teasing rules apart

Based on the chart in my previous post, the most interesting pair of candidates to look at is D10+D12+D13 and D10+D12+D13+E. I went through the first 17 predefined formulas on the dialogues site, for the following results (formulas of particular note have been highlighted in red):

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

The ones where I tried to a certain depth I'm pretty sure are 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

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.

Proof of BC #2

Proving the second bold conjecture from yesterday turned out to be straightforward:

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. The leaf of b' is a move by O, or
  2. The leaf of b' is a move by P, but there is a legal continuation of the branch according to E.
  (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:

  b		round n (P's move)		b*
  	/		\
  round n+1: E-violating move by O				round n+1: E-non-violating move by O

  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:

  round n (P's move)

  |

  round n+1: E-non-violating move by O

  And hence, contra assumption, n is not a leaf in b'.

QED

When P must repeat a move

In his previous post, Jesse said that we'd speculated that the heuristic where P never repeats a move could be added to either D or E without any consequence (other than cutting down the search space). We'd thought this for quite some time but yesterday afternoon found various counterexamples, of which the simplest is the double negation of excluded middle: Here, P is required to repeat his attack on the negation in order for force P to attack the disjunction, so that he can go back and redefend it. (In a sense, this mimics the behavior you get when you drop D12, and allow repeat defenses to be. It's just that in this case, by allowing P to repeat his attack, he doesn't repeat his defense, because the defenses are to separate attacks.) But the pattern is more general: I'm pretty sure any double-negation of a classically-valid disjunction will require P to attack the same formula twice.

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.

Proof of BC 1

I was pretty sure that I had an easy way to prove Bold Conjecture #1, and I ran it by Jesse; all I had to say was "induction + pigeonhole principle" and he essentially rattled off the rest, which was good confirmation for me that my intuition was right. I should probably still write it up in full detail, but essentially, it is this:

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.

Some evidence for a bold conjecture

Sara has formulated a conjecture or two about the difference between the D and E rulesets. Sara proposed the example to Chris, who proposed looking for a counterexample with the formula

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

Each branch contains a violation of E, and there is in fact only one violation in each branch. Sara's conjecture still holds because if we were to chop off each branch the first time a violation of the E rule occurs, we obtain an E-strategy. This doesn't prove Sara's conjecture, of course, but in light of the purported significance of this formula (Chris thought it would turn out to be a counterexample) and its complexity (there are eight connectives appearing in it), this is certainly a satisfying piece of evidence in favor of the conjecture.

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!

A simpler case

Some amount of thought on the previous post made it clear to me that my example was way more complicated than it needs to be. The following formula should be IL valid and allows Opp to assert a conditional so that Pro can attack it:

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

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.

The role of D11 and D12 in IL

Thinking more on what I wrote about a few days ago, I'm convinced of the redundancy of D12 ("An attack may be answered at most once") in the presence of D11 ("At any round, a player may defend against only the latest open attack made by the other player"). An easy proof:

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.

this is what happens when you think too much about dialogues

You start developing gut feelings; and the problem with gut feelings is that they are hard to transfer. It was a gut feeling about how N worked that led me to the characterization of implications in that system; and Jesse didn't believe me until he'd fully worked out a proof. Working with N meant focus on D10 and D13. Today, for reasons I'm not still entirely sure, I found myself back in Felscher's article, looking at D11 and D12, and suddenly I'm not seeing how they aren't redundant w.r.t. each other:

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

I got Jesse to set up two new rulesets on the dialogues site, D10-D11-D13, and D10-D12-D13, and after some simple playing around with the latter, I'm beginning to develop another feeling in my gut, namely that one or the other of these is sufficient to characterize IL, even though at this point I haven't a clue which. I would LOVE to find a counterexample to this gut feeling, but I've got a feeling there's no systematic way to go about finding one, and thus I must test it via hit-and-miss potential counterexamples. Hmmm. Or maybe I can find a nice axiomatization of IL and test each axiom in both sets. Would that really be enough?