[FOM] primer on vagueness
Vladimir Sazonov
V.Sazonov at csc.liv.ac.uk
Sun May 22 17:03:03 EDT 2005
Quoting Charles Silver <silver_1 at mindspring.com>:
>
> Stewart Shapiro wrote:
> "Typical vague predicates give rise to the ancient *sorites paradox*,
> sometimes called the *paradox of the heap*. Here is an example:
>
> Premise: A man with no hair at all is bald.
>
> Premise: If a man has only n hairs on his head is bald, then so is a man
> with n+1 hairs.
>
> Conclusion: A man with 50,000 hairs on his head is bald.
>
> [Things skipped]...
>
> If a man with 0 hairs is bald, then so is a man with 1;
> if a man with 1 hair is bald, then so is a man with 2; ...
> This argument has 50,002 premises."
>
> ****
>
> In "Zooming Down The Slippery Slope," George
> Boolos shows how in a standard natural deduction
> system it is possible to infer essentially the same
> conclusion for 1,000,000 (one billion) hairs
> using fewer than 70 premises. He then extends
> this reasoning to various other numbers of hairs--
> for instance 2^30--while indicating how derivations
> can be compressed.
Recall that the proof of non-elementary complexity of cut
elimination by V. Orevkov is based on (I guess) analogous
compression. Roughly speaking, it is shown how to prove
"feasibility" or "existence" of the exponential tower
2^{2^...2^{1000}} of the hight 1000
from the totality of the successor operation.
Without the cat rule (or by using only normal natural deductions)
this is impossible to doo.
R. Parikh in his paper "Feasibility in arithmetic" (JSL, 1971)
added the predicate F (for "feasible" or, in our context, for "bold")
to Peano Arithmetic PA with postulating that F contains 0, 1 and is
under successor and +. He also postulated that the exponential
tower like above, but of the hight 2^1000, denotes a number not in F.
F is not allowed to participate in the induction axiom.
He demonstrated that the shortest proof of contradiction is longer
that (roughly) 2^1000. Therefotre this theory is practically consistent.
This is a quite rigorous way of approaching to the concepts of
feasibility and to the heap (or bold man) paradox. This
approach is really non-classical because no model for F above
exists in the ordinary set-theoretical framework. Intuitiuonistic,
and modal logics as well as the approaches to this paradox
described by Stewart Shapiro in the recent posting are reducible
these or other ways to the classical set theory (Kripke models,
realizability, or the like). Nothing such is evidently possible
for Parikh's formalization of F. Feasibility is completely
new concept for mathematics, like it was some time ago with
negative numbers, irrationals, infinitesimals, etc.
Parikh's upper bound for F (the exponential tower of the hight
2^1000) is intuitively too rough. Intuitively, just one stage
tower 2^1000 should be OK. Orevkov's result above demonstrates
that with the cut rule alloweed this bound is impossible to
improve essentially. In my paper "On feasible numbers", 1995,
it is shown that without cut rule the number 2^1000 can be
(feasibly) consistently postulated as the upper bound for F.
(There is some plausible intuitive justification leading to
something like this restriction on the cut rule.)
What is interesting, are some consequences we have from such a
theory of feasible numbers. Even for 1000 the effect of the
heap paradox can be modelled. For some definable predicate M
(for "medium") it is shown that
M(0),
forall x (M(x) => M(x+1)), and
\neg M(1000)
hold without any (feasible) contradiction. The point is that,
although with the cut (or modus ponens) rule we can deduce
M(1000), elimination of this rule will make the proof non-feasible
(in fact, containing more than 2^1000 of symbols). For small
numbers like 1,2,3, we can eliminate the cut rule and prove
in the system that M(1), M(2), M(3),...
But for bigger numbers it becomes more and more difficult to do
this and, in fact, impossible for 1000.
There are even more strange effects in this theory of feasibility.
I would like to conclude on the possible opposition
of vague vs. mathematical.
Although the first coming opinion that feasibility is a vague
concept, and therefore non-mathematical, I strongly believe
that this contrasting is incorrect. The ordinary intuitive
mathematical concepts are non-vague only at the first sight.
Under a properly understood philosophy of mathematics based
on the formalist approach there is no reason to consider
them in this way. Say, the above considerations give some
formalizations (axioms + proof rules) of feasibility.
We deduce some results on this vague concept in exactly
the same (non-vague) manner as in the ordinary mathematics.
As in classical mathematics some questions are undecidable.
What is the difference, except that some axioms and rules
are chosen in some special way? Moreover, the formalisms of
ZFC or PA are based, in fact, on the concept of a formal
proof of a *feasible length*. (Otherwise we go into infinite
regress.) Therefore the universe of sets or the "set" of
natural numbers are inherently vague as well. As in the case
of "vague" feasible numbers, certain questions are resolvable
positively or negatively. If we will concentrate on such resolvable
questions only then even feasible numbers will look as non-vague.
The very possibility of undecidable questions in mathematics
says about the vagueness of its most fundamental concepts. This
vagueness may seem as not exactly of the same character as that
of feasible numbers. But, philosophically, what is the difference
(except that ZFC and PA are well developed, unlike new feasibility
formalisms)?
The "length" (or the borderline between feasible and non-feasible)
of the row of feasible numbers is highly indefinite.
Is the "length" of the row of the natural numbers (satisfying
the axioms of PA or understood in terms of the abstraction of
potential infinity/feasibility based on some strong "iteration"
or extrapolation of the idea of feasibility) anything better?
Let us ask ourselves what are provably existent (in PA?, ZFC?...,
let even in PA only) natural numbers, and we will get the
strongest feeling of vagueness.
Vladimir Sazonov
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
More information about the FOM
mailing list