Tuesday, June 28, 2011

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

8 comments:

  1. How do we characterize CL using Felscher-style dialogues?

    I'm confused by this question, because we know at least one answer: D10+D13+E. (This is what our proof showed. The only difference between Felscher and Fermüller is notation; the ruleset hasn't changed.)

    Can you expand on why you think that D10 and D13 are not salient for CL, given that they are part of the only known characterization we have of CL?

    ReplyDelete
  2. I'm assuming that D10 and D13 are present.

    This question is asked apropos a question about the redundancy of E. Chris wonders under what circumstances E is redundant. N shows that it's not redundant for {D10,D13}. The questions here are: what about

    * {D10,D11,D13}

    * {D10,D12,D13}

    There are two questions to investigate:

    (A1) What is the logic of {D10,D11,D13,E}?

    (A2) What is the logic of {D10,D11,D13}?

    (B1) What is the logic of {D10,D12,D13}?

    (B2) What is the logic of {D10,D12,D13,E}?

    Are the logics of (A1) and (A2) the same? Are the logics of (B1) and (B2) the same? If so, then we've found another case (or cases) of the redundancy of E.

    ReplyDelete
  3. Well, A2 is IL, and thus I would be amazed if A1 is not also IL (in fact, I think that would be possible). And I'm pretty sure I still stand by my earlier conjecture, that B1 is also IL, which means that B2 likely is as well.

    ReplyDelete
  4. Jesse and I both proved (pretty quickly) that D10+D12+D13 is not CL: It doesn't validate excluded middle.

    ReplyDelete
  5. I've found that

    * Peirce's formula is valid under E rules − D11;

    * Peirce's formula is invalid under D rule − D11.

    ReplyDelete
  6. I've arrived at a new conjecture for characterizing CL: take the N ruleset (D10, D13) with the structural rule that says that O cannot repeat moves. (It is permitted for P to repeat moves; indeed, this seems essential.) Call this ruleset J. I've tried the formulas in our predefined list of formulas at http://www.dialogical-logic.info that I know are tautologies but which aren't intuitionistically valid, and I can find J-winning strategies for each of them. I can also find J+E-winning strategies, too. The formulas I tried:

    * Peirce's formula
    * Excluded middle
    * Double negation elimination
    * Scott's formula
    * Smetanich's formula
    * De Morgan not-and-implies-or-not

    I thus have two new guesses on hand:

    (1) J gives us CL

    (2) E is redudant for J (that is, J+E gives rise to the same set of valid formulas as J)

    ReplyDelete
  7. "take the N ruleset (D10, D13) with the structural rule that says that O cannot repeat moves"

    I'm also quite confident that this characterizes CL, since it's essentially the same conjecture that I had yesterday:

    D10+D13+D14=CL

    Where D14=A P-attack may be defended at most once.

    Your formulation implies mine. What I think is important about E, for CL, is not the direct-responsiveness, but the restriction on the number of times O can make a particular move.

    ReplyDelete
  8. Sorry, your version doesn't imply mine, my version implies yours.

    ReplyDelete