Saturday, February 02, 2008

Making a virtue of a weakness

It is fairly common knowledge that classical logic is stronger, in a sense, than intuitionistic logic. There are things that you can prove in classical logic that you can't prove in intuitionistic logic, in a sense. I say "in a sense" because there are those translations from the former to the latter so that for everything you can prove in classical logic, something is provable in intuitionistic logic that the classical logician would consider equivalent but the intuitionistic one wouldn't. It is also fairly well known that intuitionistic logic distinguishes φ, ∼ φ, and ∼∼φ, when φ isn't itself a negated sentence, and certainly for all atomic sentences. Classical logic only distinguishes φ and ∼φ. Read more

Switching gears slightly, K and S4 are both weaker logics than S5. In S5, all strings of modal operators collapse down to the one on the far right, e..g [][]◊ p becomes ◊p. This means that in S5 there are only two modalities: [] and ◊ (ignoring details about definition for a second). In S4, there is no difference between strings of a single operator and the single operator, e.g. [][][][] and []. They are equivalent. If we look at, say, K, there are more modalities. In K there is a difference between [] and &\loz;[], for example. There is even a difference between [] and [][] for non-theorems. While there are only two modalities (possibly one if you define them right) that are primitive in any of the standard modal logics, this doesn't mean that there are only two modalities full stop. As indicated above, in S4 there are more than in S5 and even more in K.

There are a couple of upshots of this. One is that in a weaker logic we have more propositions, or contents, considered nonequivalent, or distinct by the logic's lights. This lets us see the fine structure of various operators and logical constants. Whereas classical logic wants to run roughshod over those details, intuitionistic (or relevance or minimal or...) logic forces us to pay attention to them because their derivational utility is lessened.

Another upshot, pointed out recently to me by a few people, among them my roommate and my model theory teacher, is that if fewer propositions are considered equivalent, then a space opens up between the propositions. Let's take the intuitionistic case since the details are the most studied and I'm more familiar with it. A space opens up between p and ∼∼ p, for atomic p. This can be exploited by adding principles to fill in the gap so to speak. The really interesting thing is that these principles need not be consistent with the classical equivalence of the propositions. To put it a different way, the principles can extend the system, or logic, in a way that is classically inconsistent, but perfectly consistent in the weaker logic. This has, apparently, been carried out a fair amount in constructive analysis, which is, roughly, real analysis done in intuitionistic logic with extra principles for dealing with infinite sequences. (This last may not be right. I can't find a good description of choice sequences online.) An example of something provable in constructive analysis that is inconsistent with classical analysis is Brouwer's theorem, that every function on a closed interval [a,b] is uniformly continuous. (The example is supplied by Feferman, who has a paper on the relation between classical and constructive analysis on his web page.)

The point here is that weakening the logic doesn't just mean that some things aren't provable. Rather, the interesting thing is that new things become provable. These new things that are inconsistent with a stronger logic. This need not be restricted to just math and logic though, although it might be easiest to see in those areas. If weakening the logic creates this sort of conceptual space, it seems like it opens the door for divergences in other areas of philosophy, e.g. semantics and the philosophy of language. It seems like this should open up some venues for investigation.

3 comments:

Ole Thomassen Hjortland said...

Very interesting paper on discriminatory power in logics: Lloyd Humberstone 'Logical Discrimination', http://tinyurl.com/35fpz9.

Shawn said...

Thanks Ole. This looks like it could be very helpful. I wasn't aware something like this was even out there.

Ole Thomassen Hjortland said...

It's a very nice article. I've tried to find similar stuff, but I suspect this is pretty original. There is definitely a lot of research to be done in that field; particularly with respect to embeddings, I think.