Wednesday, December 17, 2008

Question about negations

Does anyone know of any proof systems in which some but not all contents have negations? I'm looking for examples for a developing project.


Greg said...

I'm not sure I completely understand exactly what you're looking for, but might proof systems for neutral and negative free logics fit the bill?

For any well-formed formula A, '~A' is a wff too, but if A is neither T nor F, neither is '~A'.

Or do you want a proof system where there are some wffs that, when you put a '~' in front of it, is NOT a wff? I.e., the 'weirdness' of the negation is written into the syntax, instead of the semantics?

Shawn said...

The latter, with the weirdness written into the syntax. Are there any natural proof systems in which for one class of wffs, if 'A' is in that class, then '¬A' is also a wff in that class, and for another class of wffs, 'A' can be in the class while '¬A' is not a wff. The idea being that there is a negation but not all propositions ("contents" is probably a better word here, notwithstanding my calling this syntax) have negations.

Noam said...

Something kind of like this happens in proof systems that distinguish different classes of formulas by polarity. Let's say you start with two classes Pos and Neg. Then you can cook up different kinds of negation connectives, which have different effects on polarities, e.g.:

~1 : Pos -> Pos
~2 : Pos -> Neg
~3 : Neg -> Pos
~4 : Neg -> Neg

This imposes a syntactic discipline on how you can negate formulas, e.g., you can't "1-negate" Neg-formulas, or "4-negate" Pos-formulas. Think of these as being semantically different flavors of negation. For example, ~1 could be intuitionistic negation, and ~4 could be anti-intuitionistic negation. Then this discipline says that a Pos-formula doesn't have an anti-intuitionistic negation. On the other hand, it does have some sort of negation, so maybe this is not what you were looking for?

Shawn said...

That is sort of what I'm looking for. Do you have any citations for a paper using that? It'd be nice if there were a case in which polarities were distinguished and, say, the logic had the 1 and 2 negations but not the 3 and 4 negations.

The other sort of example I had in mind was John Mumma's formal system for the Elements. His sequents have diagram elements that do not, if I remember right, admit negations while the proof elements do.

Noam said...

A sequent calculus with polarities was introduced in Girard's "On the unity of logic" paper, but in a somewhat looser form: you could apply any connective to formulas of any polarity, it just "behaves better" on formulas of the right polarity. This stricter polarity discipline shows up in Girard's more recent work, and in Olivier Laurent's thesis. Alternatively, you might have a better time with one of Paul Levy's papers on "call-by-push-value". These are phrased in terms of type theory/category theory rather than logic, but it's the same idea: two syntactically distinct classes of "value types" (like Pos) and "computation types" (like Neg), and different connectives associated with the different classes. Alternatively, you can try my paper.

That example you mention looks interesting. In a similar vein, you might have a look at "geometric logic", e.g. here.

Noam said...

oh, and also the paper just mentioned on Richard Zach's blog, From axioms to analytic rules in nonclassical logics, is a good reference for polarity. It's like Girard's original paper in that it doesn't enforce a syntactic separation between Pos and Neg. However, there is a natural sense in which negation "really" only applies to Pos, producing a Neg. To negate a Neg, you first have to coerce it to a Pos. In their paper, this coercion is implicit, but comes out explicitly in the "substructural hierarcy".