January 25th, 2012

beartato phd

(no subject)

Dan Licata asked me whether the coproduct-cancellation trace operator in James and Sabry's "Information Effects" is intuitionistically valid.

If I interpret it as just the proposition (A + B → A + C) → (A + C → A + B) → (B → C) × (C → B), then no. Consider the process of trying to prove it in a sequent calculus. Of the two goals B → C and C → B, let's just consider B → C by symmetry. So we have in the context (A + B → A + C) and (A + C → A + B) and B, and we're trying to prove C. If we try to focus on (A + C → A + B), we'll fail, assuming the propositional atoms are positive. So our only chance is (A + B → A + C), satisfying the antecedent with our B in the context. Now we have two branches to deal with; in one we have C, (and we're done) and in the other we have an A. But left with an A and a B in the context, we can't get anything new in the context; we can only keep hitting (A + B → A + C), and keep maybe getting unlucky and getting A.