Sunday, September 09, 2007

Isomorphism note

The theorem that isomorphic structures agree on the truth values of all sentences is one of those theorems that cuts across normal logical boundaries. It is true for first-order logics, second-order logics, and higher-order logics. It is also true in infinitary logics. Certain monotony properties for quantifiers are like this as well, as pointed out by van Benthem. The medieval logicians knew about the latter; they probably were not aware of the former. Is there an "order-free" framework in which to state and prove these theorems? Is category theory capable of that? I'm curious since this makes two theorems that modern logical theorizing blinds us to the generality of.


Brad said...

I'm sure your local category theorist will say something like

"well this fact really just ends up being a special case of the more ELEGANT and GENERAL observation that Lambek made while shaving during world war 2 that a natural transformation on an endofunctor between monadic bivalent boolean toposes is cartesian closed---which of course gives one nice way of seeing why zfc, simply typed lambda calculi, linear logic, martin lof type theory, topology, and the internet are really just different ways of talking about the same thing!"

Kenny said...

That's a good example of a theorem that obviously has some generality, but needs to be reproved almost every time. At the same time though, you might think that the reason it's true across the board isn't due to the presence of some over-arching theorem, but rather than being able to prove such a theorem is a condition of adequacy on any good definition of a logical system. What good is a notion of isomorphism if it doesn't entail that the same sentences are true in both structures? Or perhaps contrariwise, what good is a notion of truth in a structure if it's not preserved under isomorphism?

Shawn said...

That is a good question. I was thinking that it is a general theorem that needed more general expression. It didn't occur to me that it might be a criterion of adequacy on the notion of truth in a structure. Are there any general criteria for telling when something like this is an adequacy condition on a concept rather than an instance of a general theorem?