Understanding Hintikka's scandal of deduction (as depicted by D'Agostino)

Question

I am having trouble understanding Hintikka's Scandal of Deduction, as depicted in D'Agostino's article. According to this account, the problem stems from the fact that, while first order logic is undecidable, the completeness theorem shows that there is a semi-decision procedure. The problem is, even if given a set of premises a conclusion is indeed the logical consequence, there is no guarantee that we can obtain that proof within bounded resources (I take it as there being a practical resource limitation). And there is certainly no such procedure if the conclusion is not a logical consequence.

There have already been threads about this as listed below, and I have indeed read them all; but still I am not understanding it.

Is there a deduction analog to the problem of induction?

What is the difference between depth and surface information?

Is the problem of logical omniscience intractable?

Q1: First confusion I have concerns depth information; according to D'Agostino it is defined to be equivalent to semantic information (ie. in terms of possible worlds excluded), whereas the answer defines it as '...an ideal limit, all that we can, in principle, obtain from the armchair, without making any new observations.' It also seems to distinguish depth info from surface info by depth in terms of counts of quantifiers. I don't see how the latter's definition is in anyway related to being equivalent to semantic information.

Regarding the ideal limit bit, here is what I think it is saying but I am not at all sure: it concerns the cognitive limitation of human to see logical consequences that are of certain degree of complexity, i.e. The depth info of a sentence according to this formulation, are ALL logical consequences that are theoretically derivable, regardless of the limitation of human cognitive power.

For example, the Last Fermat theorem is a part of depth information derivable by sentences of number theory, but because of its complexity it is beyond human's cognitive power to immediately deduce it just by looking at sentences of number theory.

Q2: The quantifiers are the most confusing part: I don't at all understand the relevance of quantifier in this context; is this supposed to be an objective measure of how complicated the information a sentence conveys? e.g. ∀n∈N(n=n) is more complicated than ∃x∈N∀y∈N (x≤y) because the latter has two quantifiers? And surface information are those that have no quantifier (since 'Surface information is depth 0')?

I don't really see why quantifier is involved; for me the two sentences above, while having different counts of quantifiers, are pretty much equal in terms of being trivially true. Also if surface info are supposed to increase after we have known a new theorem through deduction, then I don't see how the quantifier is involved - I just cannot make the connection.

Answer 1

1) Depth information

D'Agostino's Philosophy of Mathematical Information explicitly disclaims defining information. He takes "the operational view that, whatever its nature may be, information manifests itself in an agent’s disposition to answer questions". This can be quantified (following Carnap-Bar Hillel, and more generally, Hintikka) by introducing possible worlds, and thinking of them as different conglomerates of answers to all meaningful questions. Then the depth information in a sentence can be identified with the region of the possible worlds' space ruled out by it for an ideal reasoner, one without any computational limitations. The bigger this region, the more questions the ideal reasoner can answer definitively (the rest can have different answers in different remaining worlds). The "ideal limit, all that we can, in principle, obtain from the armchair, without making any new observations" is just a colorful way of describing the capabilities of such an ideal reasoner.

2) Quantifier depth

The quantifier depth (in a normalized form and under a deduction system of special type) was indeed thought by Hintikka as representing the complexity of a sentence. Hintikka's reason for taking quantifier depth as a measure of complexity relates to how the reasoning is modeled in certain types of deduction systems, natural deduction systems. There, to reason about quantified formulas one "instantiates" the quantified variables by introducing individuals they stand for, and reasoning about those. So ∀n∈N(n=n) only requires reasoning about one such individual (an integer), whereas ∃x∈N∀y∈N(x≤y) involves a relation between two different ones. The more individuals (and relations) are involved, the more complex the reasoning becomes, according to Hintikka. A non-ideal reasoner with bounded resources can only handle so much complexity.

This is made more vivid by the classical example of demonstrations in Euclidian geometry. There, the reasoning can be traced on a diagram with different geometric items, and the more individuals are introduced (by auxiliary constructions, which Hintikka assimilates to instantiations of bound variables) the more complex the diagram, and the tracing of it, becomes.

One can see already from this sketch that the quantifier depth is a rather crude measure of complexity. Intuitively, not just the number of items, but also the complexity of relationships between them should play a role (a diagram with n isolated dots is not that complex). And the number of quantifier alterations also seems relevant, in addition to the overall quantity of quantifiers. For example, ∀y∈N∃x∈N(x≤y) seems more complex than ∃x∈N∀y∈N(x≤y) because it introduces a functional dependence of x on y, whereas in the latter x is the same for all y. Indeed, this intuition in reflected in the level of a formula in the so-called arithmetical hierarchy. As many authors pointed out, there is an even more basic problem: quantifier depth can not at all account for the kind of complexity embodied in complicated Boolean tautologies, for example. To account for that, D'Agostino and Floridi introduced a second dimension of complexity of arguments (also specific to the modes of reasoning in natural deduction systems), namely the depth of nested conditional arguments that introduce and discharge assumptions. Whether combining their measure with Hintikka's can account for all other types of complexity in reasoning is an interesting research question.