7
$\begingroup$

In this paper by Jeff Ketland, he notes:

With Henkin semantics, the Completeness, Compactness and Löwenheim-Skolem Theorems all hold, because Henkin structures can be re-interpreted as many-sorted first-order structures.

What is it about the full semantics for second-order logic that defies re-interpretation into a many-sorted first-order logic?

$\endgroup$
9
$\begingroup$

Many-sorted first-order logic does not place any internal, logical, requirement on the relationship of the domains of the various sorts. In particular, then, a two-sorted logic, with one sort running over "objects" and another sort running over "properties", places no particular logical requirement on the relationship of the domains. It doesn't require, for example, that if there are $\kappa$ objects, then there are $2^{\kappa}$ properties. By contrast, full semantics for second-order logic does require this, by requiring that the second-order quantifiers running over properties (thought of extensionally) do run over the full powerset of the domain of the first-order quantifiers -- indeed, that's what makes it "full"!

$\endgroup$
5
$\begingroup$

Full semantics differ from Henkin semantics In only one germane way: rather than considering arbitrary Henkin structures, full semantics considers only full structures. That shows immediately why e.g. the completeness theorem fails for full semantics:

  • Completeness: A formula is provable in second order logic if and only if the formula holds in all Henkin structures

  • Not every Henkin structure is a full structure, and there are formulas true in every full structure but not every Henkin structure

From the right point of view, it really is that straightforward.

$\endgroup$
  • $\begingroup$ Yes, between yours and Peter's answer it is really straightforward. It's one of those things that, once pointed out, seems completely obvious. $\endgroup$ – Dennis Jun 14 '13 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.